Implement hasConflicts().

6 files changed, 133 insertions, 95 deletions

diff --git a/src/gui/graphicsview/qgraphicsanchorlayout.cpp b/src/gui/graphicsview/qgraphicsanchorlayout.cpp
index efad259..12124ab 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout.cpp
+++ b/src/gui/graphicsview/qgraphicsanchorlayout.cpp
@@ -288,6 +288,18 @@ void QGraphicsAnchorLayout::addAnchors(QGraphicsLayoutItem *firstItem,
 }
 
 /*!
+    Returns true if there are no arrangement that satisfies all constraints.
+    Otherwise returns false.
+
+    \sa addAnchor()
+*/
+bool QGraphicsAnchorLayout::hasConflicts() const
+{
+    Q_D(const QGraphicsAnchorLayout);
+    return d->hasConflicts();
+}
+
+/*!
     Sets the default horizontal spacing for the anchor layout to \a spacing.
 
     \sa horizontalSpacing(), setVerticalSpacing(), setSpacing()
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout.h b/src/gui/graphicsview/qgraphicsanchorlayout.h
index d9a87ba..44074d1 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout.h
+++ b/src/gui/graphicsview/qgraphicsanchorlayout.h
@@ -93,6 +93,7 @@ public:
                     QGraphicsLayoutItem *secondItem,
                     Qt::Orientations orientations = Qt::Horizontal | Qt::Vertical);
 
+    bool hasConflicts() const;
     void setHorizontalSpacing(qreal spacing);
     void setVerticalSpacing(qreal spacing);
     void setSpacing(qreal spacing);
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
index b02adf4..23601f9 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
@@ -332,6 +332,7 @@ QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()
     for (int i = 0; i < NOrientations; ++i) {
         spacings[i] = -1;
         graphSimplified[i] = false;
+        graphHasConflicts[i] = false;
     }
 }
 
@@ -1587,6 +1588,7 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs(
     AnchorVertex *v = internalVertex(q, pickEdge(Qt::AnchorRight, orientation));
     GraphPath trunkPath = graphPaths[orientation].value(v);
 
+    bool feasible = true;
     if (!trunkConstraints.isEmpty()) {
 #if 0
         qDebug("Simplex used for trunk of %s",
@@ -1594,33 +1596,37 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs(
 #endif
 
         // Solve min and max size hints for trunk
-        QPair<qreal, qreal> minMax = solveMinMax(trunkConstraints, trunkPath);
-        sizeHints[orientation][Qt::MinimumSize] = minMax.first;
-        sizeHints[orientation][Qt::MaximumSize] = minMax.second;
+        qreal min, max;
+        feasible = solveMinMax(trunkConstraints, trunkPath, &min, &max);
 
         // Solve for preferred. The objective function is calculated from the constraints
         // and variables internally.
-        solvePreferred(trunkConstraints);
+        feasible &= solvePreferred(trunkConstraints);
 
-        // Propagate the new sizes down the simplified graph, ie. tell the
-        // group anchors to set their children anchors sizes.
+        if (feasible) {
+            // Propagate the new sizes down the simplified graph, ie. tell the
+            // group anchors to set their children anchors sizes.
 
-        // ### we calculated variables already a few times, can't we reuse that?
-        QList<AnchorData *> trunkVariables = getVariables(trunkConstraints);
+            // ### we calculated variables already a few times, can't we reuse that?
+            QList<AnchorData *> trunkVariables = getVariables(trunkConstraints);
 
-        for (int i = 0; i < trunkVariables.count(); ++i)
-            trunkVariables.at(i)->updateChildrenSizes();
+            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.
+            qreal pref(0.0);
+            foreach (const AnchorData *ad, trunkPath.positives) {
+                pref += ad->sizeAtPreferred;
+            }
+            foreach (const AnchorData *ad, trunkPath.negatives) {
+                pref -= ad->sizeAtPreferred;
+            }
+            sizeHints[orientation][Qt::MinimumSize] = min;
+            sizeHints[orientation][Qt::PreferredSize] = pref;
+            sizeHints[orientation][Qt::MaximumSize] = max;
 
-        // Calculate and set the preferred size for the layout from the edge sizes that
-        // were calculated above.
-        qreal pref(0.0);
-        foreach (const AnchorData *ad, trunkPath.positives) {
-            pref += ad->sizeAtPreferred;
-        }
-        foreach (const AnchorData *ad, trunkPath.negatives) {
-            pref -= ad->sizeAtPreferred;
         }
-        sizeHints[orientation][Qt::PreferredSize] = pref;
     } else {
 #if 0
         qDebug("Simplex NOT used for trunk of %s",
@@ -1654,29 +1660,34 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs(
     // layout.
 
     // Solve the other only for preferred, skip trunk
-    for (int i = 1; i < parts.count(); ++i) {
-        QList<QSimplexConstraint *> partConstraints = parts[i];
-        QList<AnchorData *> partVariables = getVariables(partConstraints);
-        Q_ASSERT(!partVariables.isEmpty());
-
-        sizeHintConstraints = constraintsFromSizeHints(partVariables);
-        partConstraints += sizeHintConstraints;
-        solvePreferred(partConstraints);
-
-        // Propagate size at preferred to other sizes. Semi-floats
-        // always will be in their sizeAtPreferred.
-        for (int j = 0; j < partVariables.count(); ++j) {
-            AnchorData *ad = partVariables[j];
-            Q_ASSERT(ad);
-            ad->sizeAtMinimum = ad->sizeAtPreferred;
-            ad->sizeAtMaximum = ad->sizeAtPreferred;
-            ad->updateChildrenSizes();
-        }
+    if (feasible) {
+        for (int i = 1; i < parts.count(); ++i) {
+            QList<QSimplexConstraint *> partConstraints = parts[i];
+            QList<AnchorData *> partVariables = getVariables(partConstraints);
+            Q_ASSERT(!partVariables.isEmpty());
+
+            sizeHintConstraints = constraintsFromSizeHints(partVariables);
+            partConstraints += sizeHintConstraints;
+            feasible &= solvePreferred(partConstraints);
+            if (!feasible)
+                break;
+
+            // Propagate size at preferred to other sizes. Semi-floats
+            // always will be in their sizeAtPreferred.
+            for (int j = 0; j < partVariables.count(); ++j) {
+                AnchorData *ad = partVariables[j];
+                Q_ASSERT(ad);
+                ad->sizeAtMinimum = ad->sizeAtPreferred;
+                ad->sizeAtMaximum = ad->sizeAtPreferred;
+                ad->updateChildrenSizes();
+            }
 
-        // Delete the constraints, we won't use them anymore.
-        qDeleteAll(sizeHintConstraints);
-        sizeHintConstraints.clear();
+            // Delete the constraints, we won't use them anymore.
+            qDeleteAll(sizeHintConstraints);
+            sizeHintConstraints.clear();
+        }
     }
+    graphHasConflicts[orientation] = !feasible;
 
     // Clean up our data structures. They are not needed anymore since
     // distribution uses just interpolation.
@@ -2141,47 +2152,48 @@ void QGraphicsAnchorLayoutPrivate::interpolateSequentialEdges(
         interpolateEdge(prev, data->m_edges.last(), orientation);
 }
 
-QPair<qreal, qreal>
-QGraphicsAnchorLayoutPrivate::solveMinMax(QList<QSimplexConstraint *> constraints,
-                                          GraphPath path)
+bool QGraphicsAnchorLayoutPrivate::solveMinMax(QList<QSimplexConstraint *> constraints,
+                                               GraphPath path, qreal *min, qreal *max)
 {
     QSimplex simplex;
-    simplex.setConstraints(constraints);
-
-    // Obtain the objective constraint
-    QSimplexConstraint objective;
-    QSet<AnchorData *>::const_iterator iter;
-    for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter)
-        objective.variables.insert(*iter, 1.0);
-
-    for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter)
-        objective.variables.insert(*iter, -1.0);
-
-    simplex.setObjective(&objective);
-
-    // Calculate minimum values
-    qreal min = simplex.solveMin();
-
-    // Save sizeAtMinimum results
-    QList<QSimplexVariable *> variables = simplex.constraintsVariables();
-    for (int i = 0; i < variables.size(); ++i) {
-        AnchorData *ad = static_cast<AnchorData *>(variables[i]);
-        ad->sizeAtMinimum = ad->result;
-    }
+    bool feasible = simplex.setConstraints(constraints);
+    if (feasible) {
+        // Obtain the objective constraint
+        QSimplexConstraint objective;
+        QSet<AnchorData *>::const_iterator iter;
+        for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter)
+            objective.variables.insert(*iter, 1.0);
+
+        for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter)
+            objective.variables.insert(*iter, -1.0);
+
+        simplex.setObjective(&objective);
+
+        // Calculate minimum values
+        *min = simplex.solveMin();
+
+        // Save sizeAtMinimum results
+        QList<QSimplexVariable *> variables = simplex.constraintsVariables();
+        for (int i = 0; i < variables.size(); ++i) {
+            AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+            Q_ASSERT(ad->result >= ad->minSize || qFuzzyCompare(ad->result, ad->minSize));
+            ad->sizeAtMinimum = ad->result;
+        }
 
-    // Calculate maximum values
-    qreal max = simplex.solveMax();
+        // Calculate maximum values
+        *max = simplex.solveMax();
 
-    // Save sizeAtMaximum results
-    for (int i = 0; i < variables.size(); ++i) {
-        AnchorData *ad = static_cast<AnchorData *>(variables[i]);
-        ad->sizeAtMaximum = ad->result;
+        // Save sizeAtMaximum results
+        for (int i = 0; i < variables.size(); ++i) {
+            AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+            Q_ASSERT(ad->result <= ad->maxSize || qFuzzyCompare(ad->result, ad->maxSize));
+            ad->sizeAtMaximum = ad->result;
+        }
     }
-
-    return qMakePair<qreal, qreal>(min, max);
+    return feasible;
 }
 
-void QGraphicsAnchorLayoutPrivate::solvePreferred(QList<QSimplexConstraint *> constraints)
+bool QGraphicsAnchorLayoutPrivate::solvePreferred(QList<QSimplexConstraint *> constraints)
 {
     QList<AnchorData *> variables = getVariables(constraints);
     QList<QSimplexConstraint *> preferredConstraints;
@@ -2228,25 +2240,35 @@ void QGraphicsAnchorLayoutPrivate::solvePreferred(QList<QSimplexConstraint *> co
 
 
     QSimplex *simplex = new QSimplex;
-    simplex->setConstraints(constraints + preferredConstraints);
-    simplex->setObjective(&objective);
+    bool feasible = simplex->setConstraints(constraints + preferredConstraints);
+    if (feasible) {
+        simplex->setObjective(&objective);
 
-    // Calculate minimum values
-    simplex->solveMin();
-
-    // Save sizeAtPreferred results
-    for (int i = 0; i < variables.size(); ++i) {
-        AnchorData *ad = static_cast<AnchorData *>(variables[i]);
-        ad->sizeAtPreferred = ad->result;
-    }
+        // Calculate minimum values
+        simplex->solveMin();
 
-    // Make sure we delete the simplex solver -before- we delete the
-    // constraints used by it.
-    delete simplex;
+        // Save sizeAtPreferred results
+        for (int i = 0; i < variables.size(); ++i) {
+            AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+            ad->sizeAtPreferred = ad->result;
+        }
 
+        // Make sure we delete the simplex solver -before- we delete the
+        // constraints used by it.
+        delete simplex;
+    }
     // Delete constraints and variables we created.
     qDeleteAll(preferredConstraints);
     qDeleteAll(preferredVariables);
+
+    return feasible;
+}
+
+bool QGraphicsAnchorLayoutPrivate::hasConflicts() const
+{
+    QGraphicsAnchorLayoutPrivate *that = const_cast<QGraphicsAnchorLayoutPrivate*>(this);
+    that->calculateGraphs();
+    return graphHasConflicts[0] || graphHasConflicts[1];
 }
 
 #ifdef QT_DEBUG
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
index 4d746bf..4e1bcd4 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.h
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
@@ -478,9 +478,10 @@ public:
                                   Orientation orientation);
 
     // Linear Programming solver methods
-    QPair<qreal, qreal> solveMinMax(QList<QSimplexConstraint *> constraints,
-                                    GraphPath path);
-    void solvePreferred(QList<QSimplexConstraint *> constraints);
+    bool solveMinMax(QList<QSimplexConstraint *> constraints,
+                     GraphPath path, qreal *min, qreal *max);
+    bool solvePreferred(QList<QSimplexConstraint *> constraints);
+    bool hasConflicts() const;
 
 #ifdef QT_DEBUG
     void dumpGraph();
@@ -514,6 +515,7 @@ public:
 
     // ###
     bool graphSimplified[2];
+    bool graphHasConflicts[2];
 
     uint calculateGraphCacheDirty : 1;
 };
diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp
index 3bd6b5a..e3a991e 100644
--- a/src/gui/graphicsview/qsimplex_p.cpp
+++ b/src/gui/graphicsview/qsimplex_p.cpp
@@ -84,12 +84,12 @@ void QSimplex::clearDataStructures()
     objective = 0;
 }
 
-void QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
+bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
 {
     clearDataStructures();
 
     if (newConstraints.isEmpty())
-        return;
+        return true;    // we are ok with no constraints
     constraints = newConstraints;
 
     // Set Variables direct mapping
@@ -153,7 +153,7 @@ void QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
     matrix = (qreal *)malloc(sizeof(qreal) * columns * rows);
     if (!matrix) {
         qWarning() << "QSimplex: Unable to allocate memory!";
-        return;
+        return false;
     }
     for (int i = columns * rows - 1; i >= 0; --i)
         matrix[i] = 0.0;
@@ -198,11 +198,12 @@ void QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
     if (valueAt(0, columns - 1) != 0.0) {
         qWarning() << "QSimplex: No feasible solution!";
         clearDataStructures();
-        return;
+        return false;
     }
 
     // Remove artificial variables
     clearColumns(firstArtificial, columns - 2);
+    return true;
 }
 
 void QSimplex::solveMaxHelper()
diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h
index 805ef4a..54b080d 100644
--- a/src/gui/graphicsview/qsimplex_p.h
+++ b/src/gui/graphicsview/qsimplex_p.h
@@ -107,7 +107,7 @@ public:
     qreal solveMax();
     QList<QSimplexVariable *> constraintsVariables();
 
-    void setConstraints(const QList<QSimplexConstraint *> constraints);
+    bool setConstraints(const QList<QSimplexConstraint *> constraints);
     void setObjective(QSimplexConstraint *objective);
 
     void dumpMatrix();