From a41ac791921329c33947a0748d76683868a9bbf6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Jan-Arve=20S=C3=A6ther?= Date: Thu, 11 Jun 2009 13:49:29 +0200 Subject: Improved sequential simplification. Added restoreSimplifiedGraph(). See comment in simplifyGraph on how the overall approach is. There are still outstanding issues: 1. Simplify parallel anchors 2. Use linear layout to distribute sequential anchors. --- src/gui/graphicsview/qgraphicsanchorlayout_p.cpp | 251 ++++++++++++++++++----- src/gui/graphicsview/qgraphicsanchorlayout_p.h | 2 + 2 files changed, 197 insertions(+), 56 deletions(-) diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp index 62d2d9a..0339f41 100644 --- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp @@ -126,21 +126,84 @@ inline static qreal checkAdd(qreal a, qreal b) return FLT_MAX; return a + b; } + +/*! + * \internal + * + * Takes the sequence of vertices described by (\a before, \a vertices, \a after) and replaces + * all anchors connected to the vertices in \a vertices with one simplified anchor between + * \a before and \a after. The simplified anchor will be a placeholder for all the previous + * anchors between \a before and \a after, and can be restored back to the anchors it is a + * placeholder for. + */ +static void simplifySequentialChunk(Graph *graph, + AnchorVertex *before, + const QVector &vertices, + AnchorVertex *after) +{ + int i; +#if 0 + QString strVertices; + for (i = 0; i < vertices.count(); ++i) + strVertices += QString::fromAscii("%1 - ").arg(vertices.at(i)->toString()); + QString strPath = QString::fromAscii("%1 - %2%3").arg(before->toString(), strVertices, after->toString()); + qDebug("simplifying [%s] to [%s - %s]", qPrintable(strPath), qPrintable(before->toString()), qPrintable(after->toString())); +#endif + + if (graph->edgeData(before, after)) { + qDebug("### FIXME: Need to merge parallel anchors, ignoring this simplification for now"); + return; + } + + qreal min = 0; + qreal pref = 0; + qreal max = 0; + + SequentialAnchorData *sequence = new SequentialAnchorData; + AnchorVertex *prev = before; + AnchorData *data; + for (i = 0; i <= vertices.count(); ++i) { + AnchorVertex *next = (i < vertices.count()) ? vertices.at(i) : after; + data = graph->takeEdge(prev, next); + min += data->minSize; + pref += data->prefSize; + max = checkAdd(max, data->maxSize); + sequence->m_edges.append(data); + prev = next; + } + + // insert new + sequence->minSize = min; + sequence->prefSize = pref; + sequence->maxSize = max; + sequence->m_children = vertices; + sequence->origin = data->origin == vertices.last() ? before : after; + graph->createEdge(before, after, sequence); +} /*! * \internal * * The purpose of this function is to simplify the graph. The process of simplification can be - * broken down to two methods: - * Algorithm can be described as: + * described as: * - * 1. Simplify all sequence of anchors into one anchor. + * 1. Simplify all sequences of anchors into one anchor. * If not first iteration and no further simplification was done, go to (3) * 2. Simplify two parallel anchors into one anchor. * If any simplification was done, go to (1) * 3. Done * + * + * The algorithm walks the graph in depth-first order, and only collects vertices that has two + * edges connected to it. If the vertex does not have two edges or if it is a layout edge, + * it will take all the previously collected vertices and try to create a simplified sequential + * anchor representing all the previously collected vertices. + * Once the simplified anchor is inserted, the collected list is cleared in order to find the next + * sequence to simplify. + * Note that there are some catches to this that are not covered by the above explanation. + * + * * Notes: - * * The algorithm should not make a sequence of the layout edge anchors. + * * The algorithm should not make a sequence of the layout edge anchors. * => Make sure those edges are not traversed * * A generic algorithm will make a sequential simplification node of a Left-HCenter-Right * sequence. This is ok, but that sequence should not be affected by stretch factors. @@ -165,67 +228,98 @@ void QGraphicsAnchorLayoutPrivate::simplifyGraph(QGraphicsAnchorLayoutPrivate::O v = stack.pop(); QList vertices = g.adjacentVertices(v); const int count = vertices.count(); + bool endOfSequence = (v->m_item == q && v->m_edge == layoutEdge) || count != 2; if (count == 2 && v->m_item != q) { candidates.append(v); + if (visited.contains(vertices.first()) && visited.contains(vertices.last())) { + // in case of a cycle + endOfSequence = true; + } } - if ((v->m_item == q && v->m_edge == layoutEdge) || (count != 2 && candidates.count() >= 1)) { - SequentialAnchorData *sequence = new SequentialAnchorData; - AnchorVertex * &sequenceLast = v; //alias - AnchorVertex *sequenceFirst = 0; + if (endOfSequence && candidates.count() >= 2) { + int i; + AnchorVertex *afterSequence= 0; + { + QList adjacentOfSecondLastVertex = g.adjacentVertices(candidates.last()); + Q_ASSERT(adjacentOfSecondLastVertex.count() == 2); + if (adjacentOfSecondLastVertex.first() == candidates.at(candidates.count() - 2)) + afterSequence = adjacentOfSecondLastVertex.last(); + else + afterSequence = adjacentOfSecondLastVertex.first(); + } + + AnchorVertex *beforeSequence = 0; + { QList adjacentOfSecondVertex = g.adjacentVertices(candidates.first()); Q_ASSERT(adjacentOfSecondVertex.count() == 2); if (adjacentOfSecondVertex.first() == candidates.at(1)) - sequenceFirst = adjacentOfSecondVertex.last(); + beforeSequence = adjacentOfSecondVertex.last(); else - sequenceFirst = adjacentOfSecondVertex.first(); - - // The complete path of the sequence to simplify is: sequenceFirst, , sequenceLast - qreal min = 0; - qreal pref = 0; - qreal max = 0; - -/* // ### DEBUG + beforeSequence = adjacentOfSecondVertex.first(); + } + // The complete path of the sequence to simplify is: beforeSequence, , afterSequence + // where beforeSequence and afterSequence are the endpoints where the anchor is inserted + // between. +#if 0 + // ### DEBUG QString strCandidates; - for (int i = 0; i < candidates.count(); ++i) - strCandidates += QString::fromAscii("%1--").arg(candidates.at(i)->toString()); - QString strPath = QString::fromAscii("%1--%2%3").arg(sequenceFirst->toString(), strCandidates, sequenceLast->toString()); - qDebug("simplifying [%s] to [%s--%s]", qPrintable(strPath), qPrintable(sequenceFirst->toString()), qPrintable(sequenceLast->toString())); -*/ + for (i = 0; i < candidates.count(); ++i) + strCandidates += QString::fromAscii("%1 - ").arg(candidates.at(i)->toString()); + QString strPath = QString::fromAscii("%1 - %2%3").arg(beforeSequence->toString(), strCandidates, afterSequence->toString()); + qDebug("candidate list for sequential simplification:\n[%s]", qPrintable(strPath), qPrintable(beforeSequence->toString()), qPrintable(afterSequence->toString())); +#endif + + bool forward; + AnchorVertex *prev = beforeSequence; + int intervalFrom = 0; + int intervalTo = candidates.count() + 1; + bool forwardSet = false; + + // Check for directionality (origin). We don't want to destroy that information, + // thus we only combine anchors with the same direction. + + // "i" is the index *including* the beforeSequence and afterSequence vertices. + for (i = 1; i <= candidates.count() + 1; ++i) { + AnchorVertex *v1 = (i <= candidates.count()) ? candidates.at(i - 1) : afterSequence; + AnchorData *data = g.edgeData(prev, v1); + bool shouldSimplify = false; + if (data) { + if (!forwardSet) { + forward = (prev == data->origin ? true : false); + forwardSet = true; + } else if ((forward != (prev == data->origin))) { + shouldSimplify = true; + } + } else { + shouldSimplify = true; + forwardSet = false; + } - AnchorData *data = g.edgeData(sequenceFirst, candidates.first()); - min += data->minSize; - pref += data->prefSize; - max = checkAdd(max, data->maxSize); - g.removeEdge(sequenceFirst, candidates.first()); - - for (int i = 0; i < candidates.count() - 1; ++i) { - AnchorVertex *v1 = candidates.at(i); - AnchorVertex *v2 = candidates.at(i + 1); - data = g.edgeData(v1, v2); - min += data->minSize; - pref += data->prefSize; - max = checkAdd(max, data->maxSize); - g.removeEdge(v1, v2); + if (shouldSimplify) { + intervalTo = i - 1; + if (intervalTo - intervalFrom >= 2) { + // simplify in the range [intervalFrom, intervalTo] + AnchorVertex *intervalVertexFrom = intervalFrom == 0 ? beforeSequence : candidates.at(intervalFrom - 1); + AnchorVertex *intervalVertexTo = intervalTo <= candidates.count() ? candidates.at(intervalTo - 1) : afterSequence; + QVector subCandidates = candidates.mid(intervalFrom, intervalTo - intervalFrom - 1); + simplifySequentialChunk(&g, intervalVertexFrom, subCandidates, intervalVertexTo); + // finished simplification of chunk with same direction + } + intervalFrom = intervalTo; + forward = !forward; + } + prev = v1; + } + if (intervalTo - intervalFrom >= 2) { + // simplify in the range [intervalFrom, intervalTo] + AnchorVertex *intervalVertexFrom = intervalFrom == 0 ? beforeSequence : candidates.at(intervalFrom - 1); + AnchorVertex *intervalVertexTo = intervalTo <= candidates.count() ? candidates.at(intervalTo - 1) : afterSequence; + QVector subCandidates = candidates.mid(intervalFrom, intervalTo - intervalFrom - 1); + simplifySequentialChunk(&g, intervalVertexFrom, subCandidates, intervalVertexTo); + // finished simplification of chunk with same direction } - - data = g.edgeData(candidates.last(), sequenceLast); - min += data->minSize; - pref += data->prefSize; - max = checkAdd(max, data->maxSize); - g.removeEdge(candidates.last(), sequenceLast); - - // insert new - sequence->minSize = min; - sequence->prefSize = pref; - sequence->maxSize = max; - sequence->m_children = candidates; - sequence->origin = sequenceFirst; - g.createEdge(sequenceFirst, sequenceLast, sequence); - - // start all over again - candidates.clear(); } - if (count != 2) + if (endOfSequence) candidates.clear(); QGraphicsAnchorLayout::Edge centerEdge = pickEdge(QGraphicsAnchorLayout::HCenter, orientation); @@ -241,6 +335,49 @@ void QGraphicsAnchorLayoutPrivate::simplifyGraph(QGraphicsAnchorLayoutPrivate::O } } +void QGraphicsAnchorLayoutPrivate::restoreSimplifiedGraph(Orientation orientation) +{ + Q_Q(QGraphicsAnchorLayout); + Graph &g = graph[orientation]; + AnchorVertex *v = g.rootVertex(); + + if (!v) + return; + QSet visited; + QStack stack; + stack.push(v); + + QGraphicsAnchorLayout::Edge layoutCenterEdge = pickEdge(QGraphicsAnchorLayout::HCenter, orientation); + // walk depth-first. + while (!stack.isEmpty()) { + v = stack.pop(); + QList vertices = g.adjacentVertices(v); + const int count = vertices.count(); + for (int i = 0; i < count; ++i) { + AnchorVertex *next = vertices.at(i); + if (next->m_item == q && next->m_edge == layoutCenterEdge) + continue; + if (visited.contains(next)) + continue; + AnchorData *edge = g.edgeData(v, next); + if (edge->type == AnchorData::Sequential) { + SequentialAnchorData* seqEdge = static_cast(edge); + // restore the sequential anchor + AnchorVertex *prev = v; + for (int i = 0; i < seqEdge->m_edges.count(); ++i) { + AnchorVertex *v1 = (i < seqEdge->m_children.count()) ? seqEdge->m_children.at(i) : next; + AnchorData *data = seqEdge->m_edges.at(i); + g.createEdge(prev, v1, data); + prev = v1; + } + g.removeEdge(v, next); + } + stack.push(next); + } + visited.insert(v); + } +} + QGraphicsAnchorLayoutPrivate::Orientation QGraphicsAnchorLayoutPrivate::edgeOrientation(QGraphicsAnchorLayout::Edge edge) { @@ -613,9 +750,11 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs( setAnchorSizeHintsFromItems(orientation); // ### currently crashes -// q->dumpGraph(); + //q->dumpGraph(); // simplifyGraph(orientation); -// q->dumpGraph(); + //q->dumpGraph(); +// restoreSimplifiedGraph(orientation); // should not be here + //q->dumpGraph(); // Traverse all graph edges and store the possible paths to each vertex findPaths(orientation); diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h index 71c00a2..f945cf7 100644 --- a/src/gui/graphicsview/qgraphicsanchorlayout_p.h +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h @@ -183,6 +183,7 @@ struct SequentialAnchorData : public AnchorData { SequentialAnchorData() : AnchorData(AnchorData::Sequential) {} QVector m_children; // list of vertices in the sequence + QVector m_edges; // keep the list of edges too. }; struct ParallelAnchorData : public AnchorData @@ -294,6 +295,7 @@ public: // Activation methods void simplifyGraph(Orientation orientation); + void restoreSimplifiedGraph(Orientation orientation); void calculateGraphs(); void calculateGraphs(Orientation orientation); void setAnchorSizeHintsFromItems(Orientation orientation); -- cgit v0.12