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.

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 <QWidget>
 #include <QLinkedList>
+#include <QtCore/qstack.h>
 
 #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<AnchorVertex, AnchorData> &g = graph[orientation];
+    AnchorVertex *v = g.rootVertex();
+    QGraphicsAnchorLayout::Edge layoutEdge = oppositeEdge(v->m_edge);
+
+    if (!v)
+        return;
+    QSet<AnchorVertex*> visited;
+    QStack<AnchorVertex *> stack;
+    stack.push(v);
+    QVector<AnchorVertex*> candidates;
+
+    // walk depth-first.
+    while (!stack.isEmpty()) {
+        v = stack.pop();
+        QList<AnchorVertex *> 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<AnchorVertex *> 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, <candidates>, 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<AnchorVertex*> m_children;          // list of vertices in the sequence
+};
+
+struct ParallelAnchorData : public AnchorData
+{
+    ParallelAnchorData() : AnchorData(AnchorData::Parallel) {}
+    QVector<AnchorData*> 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);