From f5dc6a07fb9eb99211eb1fa3056a51b933ac3430 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Jan-Arve=20S=C3=A6ther?= Date: Tue, 9 Jun 2009 13:49:06 +0200 Subject: Simplify the graph by replacing a sequence of anchors with one anchor. We insert a special SequentialAnchorData. This anchor's min/pref/maxSize will be the sum of the sizes of all the anchors it is replacing. This should make the equation solver faster, and will enable us to do distribution properly just like a linear layout would do. --- src/gui/graphicsview/qgraphicsanchorlayout_p.cpp | 135 +++++++++++++++++++++++ src/gui/graphicsview/qgraphicsanchorlayout_p.h | 39 ++++++- 2 files changed, 172 insertions(+), 2 deletions(-) diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp index add2db3..62d2d9a 100644 --- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp @@ -41,6 +41,7 @@ #include #include +#include #include "qgraphicsanchorlayout_p.h" @@ -111,6 +112,135 @@ QGraphicsAnchorLayout::Edge QGraphicsAnchorLayoutPrivate::oppositeEdge( return edge; } + +/*! + * \internal + * + * helper function in order to avoid overflowing anchor sizes + * the returned size will never be larger than FLT_MAX + * + */ +inline static qreal checkAdd(qreal a, qreal b) +{ + if (FLT_MAX - b < a) + return FLT_MAX; + return a + b; +} +/*! + * \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: + * + * 1. Simplify all sequence 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 + * + * Notes: + * * 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. + * + */ +void QGraphicsAnchorLayoutPrivate::simplifyGraph(QGraphicsAnchorLayoutPrivate::Orientation orientation) +{ + Q_Q(QGraphicsAnchorLayout); + Graph &g = graph[orientation]; + AnchorVertex *v = g.rootVertex(); + QGraphicsAnchorLayout::Edge layoutEdge = oppositeEdge(v->m_edge); + + if (!v) + return; + QSet visited; + QStack stack; + stack.push(v); + QVector candidates; + + // walk depth-first. + while (!stack.isEmpty()) { + v = stack.pop(); + QList vertices = g.adjacentVertices(v); + const int count = vertices.count(); + if (count == 2 && v->m_item != q) { + candidates.append(v); + } + 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; + QList adjacentOfSecondVertex = g.adjacentVertices(candidates.first()); + Q_ASSERT(adjacentOfSecondVertex.count() == 2); + if (adjacentOfSecondVertex.first() == candidates.at(1)) + sequenceFirst = 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 + 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())); +*/ + + 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); + } + + 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) + candidates.clear(); + + QGraphicsAnchorLayout::Edge centerEdge = pickEdge(QGraphicsAnchorLayout::HCenter, orientation); + for (int i = 0; i < count; ++i) { + AnchorVertex *next = vertices.at(i); + if (next->m_item == q && next->m_edge == centerEdge) + continue; + if (visited.contains(next)) + continue; + stack.push(next); + } + visited.insert(v); + } +} + QGraphicsAnchorLayoutPrivate::Orientation QGraphicsAnchorLayoutPrivate::edgeOrientation(QGraphicsAnchorLayout::Edge edge) { @@ -482,6 +612,11 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs( // Reset the nominal sizes of each anchor based on the current item sizes setAnchorSizeHintsFromItems(orientation); +// ### currently crashes +// q->dumpGraph(); +// simplifyGraph(orientation); +// 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 f2dd796..71c00a2 100644 --- a/src/gui/graphicsview/qgraphicsanchorlayout_p.h +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h @@ -124,16 +124,21 @@ inline QString AnchorVertex::toString() const Represents an edge (anchor) in the internal graph. */ struct AnchorData : public QSimplexVariable { + enum Type { + Normal = 0, + Sequential, + Parallel + }; AnchorData(qreal minimumSize, qreal preferredSize, qreal maximumSize) : QSimplexVariable(), minSize(minimumSize), prefSize(preferredSize), maxSize(maximumSize), sizeAtMinimum(preferredSize), sizeAtPreferred(preferredSize), sizeAtMaximum(preferredSize), - skipInPreferred(0) {} + skipInPreferred(0), type(Normal) {} AnchorData(qreal size = 0) : QSimplexVariable(), minSize(size), prefSize(size), maxSize(size), sizeAtMinimum(size), sizeAtPreferred(size), sizeAtMaximum(size), - skipInPreferred(0) {} + skipInPreferred(0), type(Normal) {} inline QString toString() const; QString name; @@ -157,6 +162,13 @@ struct AnchorData : public QSimplexVariable { qreal sizeAtMaximum; uint skipInPreferred : 1; + uint type : 2; // either Normal, Sequential or Parallel +protected: + AnchorData(Type type, qreal size = 0) + : QSimplexVariable(), minSize(size), prefSize(size), + maxSize(size), sizeAtMinimum(size), + sizeAtPreferred(size), sizeAtMaximum(size), + skipInPreferred(0), type(type) {} }; inline QString AnchorData::toString() const @@ -167,6 +179,18 @@ inline QString AnchorData::toString() const } +struct SequentialAnchorData : public AnchorData +{ + SequentialAnchorData() : AnchorData(AnchorData::Sequential) {} + QVector m_children; // list of vertices in the sequence +}; + +struct ParallelAnchorData : public AnchorData +{ + ParallelAnchorData() : AnchorData(AnchorData::Parallel) {} + QVector children; // list of parallel edges +}; + /*! \internal @@ -229,6 +253,16 @@ public: static Orientation edgeOrientation(QGraphicsAnchorLayout::Edge edge); + static QGraphicsAnchorLayout::Edge pickEdge(QGraphicsAnchorLayout::Edge edge, Orientation orientation) + { + if (orientation == Vertical && int(edge) <= 2) + return (QGraphicsAnchorLayout::Edge)(edge + 3); + else if (orientation == Horizontal && int(edge) >= 3) { + return (QGraphicsAnchorLayout::Edge)(edge - 3); + } + return edge; + } + // Init methods void createLayoutEdges(); void deleteLayoutEdges(); @@ -259,6 +293,7 @@ public: void addChildItem(QGraphicsLayoutItem *child); // Activation methods + void simplifyGraph(Orientation orientation); void calculateGraphs(); void calculateGraphs(Orientation orientation); void setAnchorSizeHintsFromItems(Orientation orientation); -- cgit v0.12