From d267c0946b65e0c93cb97ebb3dea1035ff390280 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Jan-Arve=20S=C3=A6ther?= Date: Wed, 9 Sep 2009 13:23:31 +0200 Subject: Implement hasConflicts(). --- src/gui/graphicsview/qgraphicsanchorlayout.cpp | 12 ++ src/gui/graphicsview/qgraphicsanchorlayout.h | 1 + src/gui/graphicsview/qgraphicsanchorlayout_p.cpp | 196 ++++++++++++--------- src/gui/graphicsview/qgraphicsanchorlayout_p.h | 8 +- src/gui/graphicsview/qsimplex_p.cpp | 9 +- src/gui/graphicsview/qsimplex_p.h | 2 +- .../tst_qgraphicsanchorlayout.cpp | 44 ++++- 7 files changed, 176 insertions(+), 96 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 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 trunkVariables = getVariables(trunkConstraints); + // ### we calculated variables already a few times, can't we reuse that? + QList 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 partConstraints = parts[i]; - QList 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 partConstraints = parts[i]; + QList 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 -QGraphicsAnchorLayoutPrivate::solveMinMax(QList constraints, - GraphPath path) +bool QGraphicsAnchorLayoutPrivate::solveMinMax(QList constraints, + GraphPath path, qreal *min, qreal *max) { QSimplex simplex; - simplex.setConstraints(constraints); - - // Obtain the objective constraint - QSimplexConstraint objective; - QSet::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 variables = simplex.constraintsVariables(); - for (int i = 0; i < variables.size(); ++i) { - AnchorData *ad = static_cast(variables[i]); - ad->sizeAtMinimum = ad->result; - } + bool feasible = simplex.setConstraints(constraints); + if (feasible) { + // Obtain the objective constraint + QSimplexConstraint objective; + QSet::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 variables = simplex.constraintsVariables(); + for (int i = 0; i < variables.size(); ++i) { + AnchorData *ad = static_cast(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(variables[i]); - ad->sizeAtMaximum = ad->result; + // Save sizeAtMaximum results + for (int i = 0; i < variables.size(); ++i) { + AnchorData *ad = static_cast(variables[i]); + Q_ASSERT(ad->result <= ad->maxSize || qFuzzyCompare(ad->result, ad->maxSize)); + ad->sizeAtMaximum = ad->result; + } } - - return qMakePair(min, max); + return feasible; } -void QGraphicsAnchorLayoutPrivate::solvePreferred(QList constraints) +bool QGraphicsAnchorLayoutPrivate::solvePreferred(QList constraints) { QList variables = getVariables(constraints); QList preferredConstraints; @@ -2228,25 +2240,35 @@ void QGraphicsAnchorLayoutPrivate::solvePreferred(QList 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(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(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(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 solveMinMax(QList constraints, - GraphPath path); - void solvePreferred(QList constraints); + bool solveMinMax(QList constraints, + GraphPath path, qreal *min, qreal *max); + bool solvePreferred(QList 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 newConstraints) +bool QSimplex::setConstraints(const QList 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 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 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 constraintsVariables(); - void setConstraints(const QList constraints); + bool setConstraints(const QList constraints); void setObjective(QSimplexConstraint *objective); void dumpMatrix(); diff --git a/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp b/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp index 5bb3746..f982973 100644 --- a/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp +++ b/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp @@ -65,6 +65,7 @@ private slots: void setSpacing(); void hardComplexS60(); void delete_anchor(); + void conflicts(); }; class RectWidget : public QGraphicsWidget @@ -100,7 +101,7 @@ static void setAnchor(QGraphicsAnchorLayout *l, Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge, - qreal spacing) + qreal spacing = 0) { QGraphicsAnchor *anchor = l->addAnchor(firstItem, firstEdge, secondItem, secondEdge); anchor->setSpacing(spacing); @@ -1102,5 +1103,46 @@ void tst_QGraphicsAnchorLayout::delete_anchor() } +void tst_QGraphicsAnchorLayout::conflicts() +{ + QGraphicsWidget *a = createItem(QSizeF(80,10), QSizeF(90,10), QSizeF(100,10), "a"); + QGraphicsWidget *b = createItem(QSizeF(10,10), QSizeF(20,10), QSizeF(30,10), "b"); + QGraphicsWidget *c = createItem(QSizeF(10,10), QSizeF(20,10), QSizeF(30,10), "c"); + + QGraphicsAnchorLayout *l; + QGraphicsWidget *p = new QGraphicsWidget(0, Qt::Window); + + l = new QGraphicsAnchorLayout; + l->setContentsMargins(0, 0, 0, 0); + + // with the following setup, 'a' cannot be larger than 30 we will first have a Simplex conflict + + // horizontal + setAnchor(l, l, Qt::AnchorLeft, b, Qt::AnchorLeft); + setAnchor(l, b, Qt::AnchorRight, c, Qt::AnchorLeft); + setAnchor(l, c, Qt::AnchorRight, l, Qt::AnchorRight); + setAnchor(l, b, Qt::AnchorHorizontalCenter, a, Qt::AnchorLeft); + setAnchor(l, a, Qt::AnchorRight, c, Qt::AnchorHorizontalCenter); + + // vertical + setAnchor(l, l, Qt::AnchorTop, a, Qt::AnchorTop); + setAnchor(l, a, Qt::AnchorBottom, b, Qt::AnchorTop); + setAnchor(l, a, Qt::AnchorBottom, c, Qt::AnchorTop); + setAnchor(l, b, Qt::AnchorBottom, l, Qt::AnchorBottom); + setAnchor(l, c, Qt::AnchorBottom, l, Qt::AnchorBottom); + + p->setLayout(l); + + QCOMPARE(l->hasConflicts(), true); + + a->setMinimumSize(QSizeF(29,10)); + QCOMPARE(l->hasConflicts(), false); + + // It will currently fail if we uncomment this: + //QEXPECT_FAIL("", "The constraints are just within their bounds in order to be feasible", Continue); + //a->setMinimumSize(QSizeF(30,10)); + //QCOMPARE(l->hasConflicts(), false); +} + QTEST_MAIN(tst_QGraphicsAnchorLayout) #include "tst_qgraphicsanchorlayout.moc" -- cgit v0.12