QGraphicsAnchorLayout: Enabling Simplex support for Expanding size policy

To support the expanding size policy we had to change the way the setup
process work. Previously we used to calculate three key-frames using
the simplex solver:

 - sizeAtMinimum: the value an anchor should be in when the layout is
                  at its minimum size. Calculated using simplex solver
	          to minimize the layout size.
 - sizeAtPreferred: the value an anchor should be in when the layout is
                    at its preferred size. Calculated using simplex solver
	            to minimize the deviation from the items preferred
	            sizes.
 - sizeAtMaximum: the value an anchor should be in when the layout is
	          at its maximum size. Calculated using simplex solver
                  to maximize the layout size.

That worked fine but didn't diferentiate standard items from the
"expanding" ones. In other words, all items would grow from their
sizeAtPreferred to their sizeAtMaximum at the same rate.

To support the idea of "expanding" items, ie. items that should grow
faster than the others, we added a fourth state, between preferred
and maximum.

Now we have the following interpolation order:

 sizeAtMinimum -> sizeAtPreferred -> sizeAtExpanding -> sizeAtMaximum.

The definition of the "expanding" state is that all "expanding" items
should have grown all the way to their "sizeAtMaximum" values whereas
non expanding items should have kept their preferred sizes. The only
exception is that non-expanding items are allowed to grow if that is
necessary to allow the "expanding" items to reach their sizeAtMaximum.

So, the visual result is that if the layout is resized from its
preferred size to its maximum size, the expanding items will grow
first and then, in a second phase, the other items will grow.

This commit adds QGALPrivate::solveExpanding() and calls it from
calculateGraphs().

Signed-off-by: Eduardo M. Fleury <eduardo.fleury@openbossa.org>
Reviewed-by: Artur Duque de Souza <artur.souza@openbossa.org>

2 files changed, 88 insertions, 11 deletions

diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
index fc3bc8a..93ccf83 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
@@ -1635,11 +1635,18 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs(
         qreal min, max;
         feasible = solveMinMax(trunkConstraints, trunkPath, &min, &max);
 
-        // Solve for preferred. The objective function is calculated from the constraints
-        // and variables internally.
-        feasible &= solvePreferred(trunkConstraints);
-
         if (feasible) {
+            // Solve for preferred. The objective function is calculated from the constraints
+            // and variables internally.
+            solvePreferred(trunkConstraints);
+
+            // remove sizeHintConstraints from trunkConstraints
+            trunkConstraints = parts[0];
+
+            // Solve for expanding. The objective function and the constraints from items
+            // are calculated internally.
+            solveExpanding(trunkConstraints);
+
             // Propagate the new sizes down the simplified graph, ie. tell the
             // group anchors to set their children anchors sizes.
 
@@ -1649,23 +1656,23 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs(
             for (int i = 0; i < trunkVariables.count(); ++i)
                 trunkVariables.at(i)->updateChildrenSizes();
 
-            // Calculate and set the preferred size for the layout from the edge sizes that
-            // were calculated above.
+            // Calculate and set the preferred and expanding sizes for the layout,
+            // from the edge sizes that were calculated above.
             qreal pref(0.0);
+            qreal expanding(0.0);
             foreach (const AnchorData *ad, trunkPath.positives) {
                 pref += ad->sizeAtPreferred;
+                expanding += ad->sizeAtExpanding;
             }
             foreach (const AnchorData *ad, trunkPath.negatives) {
                 pref -= ad->sizeAtPreferred;
+                expanding -= ad->sizeAtExpanding;
             }
+
             sizeHints[orientation][Qt::MinimumSize] = min;
             sizeHints[orientation][Qt::PreferredSize] = pref;
             sizeHints[orientation][Qt::MaximumSize] = max;
-
-            // XXX implement Expanding simplex
-            for (int i = 0; i < trunkVariables.count(); ++i)
-                trunkVariables.at(i)->sizeAtExpanding = trunkVariables.at(i)->sizeAtPreferred;
-            sizeAtExpanding[orientation] = pref;
+            sizeAtExpanding[orientation] = expanding;
         }
     } else {
 #if 0
@@ -2315,6 +2322,75 @@ bool QGraphicsAnchorLayoutPrivate::solvePreferred(QList<QSimplexConstraint *> co
     return feasible;
 }
 
+void QGraphicsAnchorLayoutPrivate::solveExpanding(QList<QSimplexConstraint *> constraints)
+{
+    QList<AnchorData *> variables = getVariables(constraints);
+    QList<QSimplexConstraint *> itemConstraints;
+    QSimplexConstraint *objective = new QSimplexConstraint;
+
+    // Use all items that belong to trunk to:
+    //  - add solveExpanding-specific item constraints
+    //  - create the objective function
+    for (int i = 0; i < variables.size(); ++i) {
+        AnchorData *ad = variables[i];
+        if (ad->isExpanding) {
+            // Add constraint to lock expanding anchor in its sizeAtMaximum
+            QSimplexConstraint *itemC = new QSimplexConstraint;
+            itemC->ratio = QSimplexConstraint::Equal;
+            itemC->variables.insert(ad, 1.0);
+            itemC->constant = ad->sizeAtMaximum;
+            itemConstraints << itemC;
+        } else {
+            // Add constraints to lock anchor between their sizeAtPreferred and sizeAtMaximum
+            QSimplexConstraint *itemC = new QSimplexConstraint;
+            itemC->ratio = QSimplexConstraint::MoreOrEqual;
+            itemC->variables.insert(ad, 1.0);
+            itemC->constant = qMin(ad->sizeAtPreferred, ad->sizeAtMaximum);
+            itemConstraints << itemC;
+
+            itemC = new QSimplexConstraint;
+            itemC->ratio = QSimplexConstraint::LessOrEqual;
+            itemC->variables.insert(ad, 1.0);
+            itemC->constant = qMax(ad->sizeAtPreferred, ad->sizeAtMaximum);
+            itemConstraints << itemC;
+
+            // Add anchor to objective function
+            if (ad->sizeAtPreferred < ad->sizeAtMaximum) {
+                // Try to shrink this variable towards its sizeAtPreferred value
+                objective->variables.insert(ad, 1.0);
+            } else {
+                // Try to grow this variable towards its sizeAtPreferred value
+                objective->variables.insert(ad, -1.0);
+            }
+        }
+    }
+
+    // Solve
+    if (objective->variables.size() == variables.size()) {
+        // If no anchors are expanding, we don't need to run the simplex
+        // Set all variables to their preferred size
+        for (int i = 0; i < variables.size(); ++i) {
+            variables[i]->sizeAtExpanding = variables[i]->sizeAtPreferred;
+        }
+    } else {
+        // Run simplex
+        QSimplex simplex;
+        bool feasible = simplex.setConstraints(constraints + itemConstraints);
+        Q_ASSERT(feasible);
+
+        simplex.setObjective(objective);
+        simplex.solveMin();
+
+        // Collect results
+        for (int i = 0; i < variables.size(); ++i) {
+            variables[i]->sizeAtExpanding = variables[i]->result;
+        }
+    }
+
+    delete objective;
+    qDeleteAll(itemConstraints);
+}
+
 /*!
     \internal
     Returns true if there are no arrangement that satisfies all constraints.
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
index 4c6c2aa..47df786 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.h
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
@@ -495,6 +495,7 @@ public:
     bool solveMinMax(QList<QSimplexConstraint *> constraints,
                      GraphPath path, qreal *min, qreal *max);
     bool solvePreferred(QList<QSimplexConstraint *> constraints);
+    void solveExpanding(QList<QSimplexConstraint *> constraints);
     bool hasConflicts() const;
 
 #ifdef QT_DEBUG