1 /****************************************************************************
3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
7 ** This file is part of the QtGui module of the Qt Toolkit.
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** No Commercial Usage
11 ** This file contains pre-release code and may not be distributed.
12 ** You may use this file in accordance with the terms and conditions
13 ** contained in the Technology Preview License Agreement accompanying
16 ** GNU Lesser General Public License Usage
17 ** Alternatively, this file may be used under the terms of the GNU Lesser
18 ** General Public License version 2.1 as published by the Free Software
19 ** Foundation and appearing in the file LICENSE.LGPL included in the
20 ** packaging of this file. Please review the following information to
21 ** ensure the GNU Lesser General Public License version 2.1 requirements
22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 ** In addition, as a special exception, Nokia gives you certain additional
25 ** rights. These rights are described in the Nokia Qt LGPL Exception
26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 ** If you have questions regarding the use of this file, please contact
29 ** Nokia at qt-info@nokia.com.
40 ****************************************************************************/
42 #include <QtGui/qwidget.h>
43 #include <QtGui/qapplication.h>
44 #include <QtCore/qlinkedlist.h>
45 #include <QtCore/qstack.h>
48 #include <QtCore/qfile.h>
51 #include "qgraphicsanchorlayout_p.h"
53 #ifndef QT_NO_GRAPHICSVIEW
56 // To ensure that all variables inside the simplex solver are non-negative,
57 // we limit the size of anchors in the interval [-limit, limit]. Then before
58 // sending them to the simplex solver we add "limit" as an offset, so that
59 // they are actually calculated in the interval [0, 2 * limit]
60 // To avoid numerical errors in platforms where we use single precision,
61 // we use a tighter limit for the variables range.
62 const qreal g_offset = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32;
64 QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version)
65 : QObjectPrivate(version), layoutPrivate(0), data(0),
66 sizePolicy(QSizePolicy::Fixed), preferredSize(0),
71 QGraphicsAnchorPrivate::~QGraphicsAnchorPrivate()
74 // The QGraphicsAnchor was already deleted at this moment. We must clean
75 // the dangling pointer to avoid double deletion in the AnchorData dtor.
76 data->graphicsAnchor = 0;
78 layoutPrivate->removeAnchor(data->from, data->to);
82 void QGraphicsAnchorPrivate::setSizePolicy(QSizePolicy::Policy policy)
84 if (sizePolicy != policy) {
86 layoutPrivate->q_func()->invalidate();
90 void QGraphicsAnchorPrivate::setSpacing(qreal value)
93 qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
97 if (hasSize && (preferredSize == value))
100 // The anchor has an user-defined size
102 preferredSize = value;
104 layoutPrivate->q_func()->invalidate();
107 void QGraphicsAnchorPrivate::unsetSpacing()
110 qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
114 // Return to standard direction
117 layoutPrivate->q_func()->invalidate();
120 qreal QGraphicsAnchorPrivate::spacing() const
123 qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
127 return preferredSize;
131 static void applySizePolicy(QSizePolicy::Policy policy,
132 qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint,
133 qreal *minSize, qreal *prefSize,
136 // minSize, prefSize and maxSize are initialized
137 // with item's preferred Size: this is QSizePolicy::Fixed.
139 // Then we check each flag to find the resultant QSizePolicy,
140 // according to the following table:
143 // QSizePolicy::Fixed 0
144 // QSizePolicy::Minimum GrowFlag
145 // QSizePolicy::Maximum ShrinkFlag
146 // QSizePolicy::Preferred GrowFlag | ShrinkFlag
147 // QSizePolicy::Ignored GrowFlag | ShrinkFlag | IgnoreFlag
149 if (policy & QSizePolicy::ShrinkFlag)
150 *minSize = minSizeHint;
152 *minSize = prefSizeHint;
154 if (policy & QSizePolicy::GrowFlag)
155 *maxSize = maxSizeHint;
157 *maxSize = prefSizeHint;
159 // Note that these two initializations are affected by the previous flags
160 if (policy & QSizePolicy::IgnoreFlag)
161 *prefSize = *minSize;
163 *prefSize = prefSizeHint;
166 AnchorData::~AnchorData()
168 if (graphicsAnchor) {
169 // Remove reference to ourself to avoid double removal in
170 // QGraphicsAnchorPrivate dtor.
171 graphicsAnchor->d_func()->data = 0;
173 delete graphicsAnchor;
178 void AnchorData::refreshSizeHints(const QLayoutStyleInfo *styleInfo)
180 QSizePolicy::Policy policy;
186 // It is an internal anchor, fetch size information from the item
187 if (isLayoutAnchor) {
190 maxSize = QWIDGETSIZE_MAX;
194 minPrefSize = prefSize;
195 maxPrefSize = maxSize;
198 if (orientation == QGraphicsAnchorLayoutPrivate::Horizontal) {
199 policy = item->sizePolicy().horizontalPolicy();
200 minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).width();
201 prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).width();
202 maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).width();
204 policy = item->sizePolicy().verticalPolicy();
205 minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).height();
206 prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).height();
207 maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).height();
210 if (isCenterAnchor) {
217 // It is a user-created anchor, fetch size information from the associated QGraphicsAnchor
218 Q_ASSERT(graphicsAnchor);
219 QGraphicsAnchorPrivate *anchorPrivate = graphicsAnchor->d_func();
221 // Policy, min and max sizes are straightforward
222 policy = anchorPrivate->sizePolicy;
224 maxSizeHint = QWIDGETSIZE_MAX;
227 if (anchorPrivate->hasSize) {
228 // Anchor has user-defined size
229 prefSizeHint = anchorPrivate->preferredSize;
231 // Fetch size information from style
232 const Qt::Orientation orient = Qt::Orientation(QGraphicsAnchorLayoutPrivate::edgeOrientation(from->m_edge) + 1);
233 qreal s = styleInfo->defaultSpacing(orient);
235 QSizePolicy::ControlType controlTypeFrom = from->m_item->sizePolicy().controlType();
236 QSizePolicy::ControlType controlTypeTo = to->m_item->sizePolicy().controlType();
237 s = styleInfo->perItemSpacing(controlTypeFrom, controlTypeTo, orient);
239 // ### Currently we do not support negative anchors inside the graph.
240 // To avoid those being created by a negative style spacing, we must
249 // Fill minSize, prefSize and maxSize based on policy and sizeHints
250 applySizePolicy(policy, minSizeHint, prefSizeHint, maxSizeHint,
251 &minSize, &prefSize, &maxSize);
253 minPrefSize = prefSize;
254 maxPrefSize = maxSize;
256 // Set the anchor effective sizes to preferred.
258 // Note: The idea here is that all items should remain at their
259 // preferred size unless where that's impossible. In cases where
260 // the item is subject to restrictions (anchored to the layout
261 // edges, for instance), the simplex solver will be run to
262 // recalculate and override the values we set here.
263 sizeAtMinimum = prefSize;
264 sizeAtPreferred = prefSize;
265 sizeAtMaximum = prefSize;
268 void ParallelAnchorData::updateChildrenSizes()
270 firstEdge->sizeAtMinimum = sizeAtMinimum;
271 firstEdge->sizeAtPreferred = sizeAtPreferred;
272 firstEdge->sizeAtMaximum = sizeAtMaximum;
274 if (secondForward()) {
275 secondEdge->sizeAtMinimum = sizeAtMinimum;
276 secondEdge->sizeAtPreferred = sizeAtPreferred;
277 secondEdge->sizeAtMaximum = sizeAtMaximum;
279 secondEdge->sizeAtMinimum = -sizeAtMinimum;
280 secondEdge->sizeAtPreferred = -sizeAtPreferred;
281 secondEdge->sizeAtMaximum = -sizeAtMaximum;
284 firstEdge->updateChildrenSizes();
285 secondEdge->updateChildrenSizes();
291 Initialize the parallel anchor size hints using the sizeHint information from
294 Note that parallel groups can lead to unfeasibility, so during calculation, we can
295 find out one unfeasibility. Because of that this method return boolean. This can't
296 happen in sequential, so there the method is void.
298 bool ParallelAnchorData::calculateSizeHints()
300 // Normalize second child sizes.
301 // A negative anchor of sizes min, minPref, pref, maxPref and max, is equivalent
302 // to a forward anchor of sizes -max, -maxPref, -pref, -minPref, -min
309 if (secondForward()) {
310 secondMin = secondEdge->minSize;
311 secondMinPref = secondEdge->minPrefSize;
312 secondPref = secondEdge->prefSize;
313 secondMaxPref = secondEdge->maxPrefSize;
314 secondMax = secondEdge->maxSize;
316 secondMin = -secondEdge->maxSize;
317 secondMinPref = -secondEdge->maxPrefSize;
318 secondPref = -secondEdge->prefSize;
319 secondMaxPref = -secondEdge->minPrefSize;
320 secondMax = -secondEdge->minSize;
323 minSize = qMax(firstEdge->minSize, secondMin);
324 maxSize = qMin(firstEdge->maxSize, secondMax);
326 // This condition means that the maximum size of one anchor being simplified is smaller than
327 // the minimum size of the other anchor. The consequence is that there won't be a valid size
328 // for this parallel setup.
329 if (minSize > maxSize) {
333 // Preferred size calculation
334 // The calculation of preferred size is done as follows:
336 // 1) Check whether one of the child anchors is the layout structural anchor
337 // If so, we can simply copy the preferred information from the other child,
338 // after bounding it to our minimum and maximum sizes.
339 // If not, then we proceed with the actual calculations.
341 // 2) The whole algorithm for preferred size calculation is based on the fact
342 // that, if a given anchor cannot remain at its preferred size, it'd rather
345 // What happens though is that while this affirmative is true for simple
346 // anchors, it may not be true for sequential anchors that have one or more
347 // reversed anchors inside it. That happens because when a sequential anchor
348 // grows, any reversed anchors inside it may be required to shrink, something
349 // we try to avoid, as said above.
351 // To overcome this, besides their actual preferred size "prefSize", each anchor
352 // exports what we call "minPrefSize" and "maxPrefSize". These two values define
353 // a surrounding interval where, if required to move, the anchor would rather
356 // For standard anchors, this area simply represents the region between
357 // prefSize and maxSize, which makes sense since our first affirmation.
358 // For composed anchors, these values are calculated as to reduce the global
359 // "damage", that is, to reduce the total deviation and the total amount of
360 // anchors that had to shrink.
362 if (firstEdge->isLayoutAnchor) {
363 prefSize = qBound(minSize, secondPref, maxSize);
364 minPrefSize = qBound(minSize, secondMinPref, maxSize);
365 maxPrefSize = qBound(minSize, secondMaxPref, maxSize);
366 } else if (secondEdge->isLayoutAnchor) {
367 prefSize = qBound(minSize, firstEdge->prefSize, maxSize);
368 minPrefSize = qBound(minSize, firstEdge->minPrefSize, maxSize);
369 maxPrefSize = qBound(minSize, firstEdge->maxPrefSize, maxSize);
371 // Calculate the intersection between the "preferred" regions of each child
372 const qreal lowerBoundary =
373 qBound(minSize, qMax(firstEdge->minPrefSize, secondMinPref), maxSize);
374 const qreal upperBoundary =
375 qBound(minSize, qMin(firstEdge->maxPrefSize, secondMaxPref), maxSize);
376 const qreal prefMean =
377 qBound(minSize, (firstEdge->prefSize + secondPref) / 2, maxSize);
379 if (lowerBoundary < upperBoundary) {
380 // If there is an intersection between the two regions, this intersection
381 // will be used as the preferred region of the parallel anchor itself.
382 // The preferred size will be the bounded average between the two preferred
384 prefSize = qBound(lowerBoundary, prefMean, upperBoundary);
385 minPrefSize = lowerBoundary;
386 maxPrefSize = upperBoundary;
388 // If there is no intersection, we have to attribute "damage" to at least
389 // one of the children. The minimum total damage is achieved in points
390 // inside the region that extends from (1) the upper boundary of the lower
391 // region to (2) the lower boundary of the upper region.
392 // Then, we expose this region as _our_ preferred region and once again,
393 // use the bounded average as our preferred size.
394 prefSize = qBound(upperBoundary, prefMean, lowerBoundary);
395 minPrefSize = upperBoundary;
396 maxPrefSize = lowerBoundary;
400 // See comment in AnchorData::refreshSizeHints() about sizeAt* values
401 sizeAtMinimum = prefSize;
402 sizeAtPreferred = prefSize;
403 sizeAtMaximum = prefSize;
410 returns the factor in the interval [-1, 1].
415 static QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> getFactor(qreal value, qreal min,
416 qreal minPref, qreal pref,
417 qreal maxPref, qreal max)
419 QGraphicsAnchorLayoutPrivate::Interval interval;
423 if (value < minPref) {
424 interval = QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred;
427 } else if (value < pref) {
428 interval = QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred;
431 } else if (value < maxPref) {
432 interval = QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred;
436 interval = QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum;
442 if (upper == lower) {
445 progress = (value - lower) / (upper - lower);
448 return qMakePair(interval, progress);
451 static qreal interpolate(const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> &factor,
452 qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)
457 switch (factor.first) {
458 case QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred:
462 case QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred:
466 case QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred:
470 case QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum:
476 return lower + factor.second * (upper - lower);
479 void SequentialAnchorData::updateChildrenSizes()
481 // Band here refers if the value is in the Minimum To Preferred
482 // band (the lower band) or the Preferred To Maximum (the upper band).
484 const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> minFactor =
485 getFactor(sizeAtMinimum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
486 const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> prefFactor =
487 getFactor(sizeAtPreferred, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
488 const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> maxFactor =
489 getFactor(sizeAtMaximum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
491 // XXX This is not safe if Vertex simplification takes place after the sequential
492 // anchor is created. In that case, "prev" will be a group-vertex, different from
493 // "from" or "to", that _contains_ one of them.
494 AnchorVertex *prev = from;
496 for (int i = 0; i < m_edges.count(); ++i) {
497 AnchorData *e = m_edges.at(i);
499 const bool edgeIsForward = (e->from == prev);
501 e->sizeAtMinimum = interpolate(minFactor, e->minSize, e->minPrefSize,
502 e->prefSize, e->maxPrefSize, e->maxSize);
503 e->sizeAtPreferred = interpolate(prefFactor, e->minSize, e->minPrefSize,
504 e->prefSize, e->maxPrefSize, e->maxSize);
505 e->sizeAtMaximum = interpolate(maxFactor, e->minSize, e->minPrefSize,
506 e->prefSize, e->maxPrefSize, e->maxSize);
509 Q_ASSERT(prev == e->to);
510 e->sizeAtMinimum = interpolate(minFactor, e->maxSize, e->maxPrefSize,
511 e->prefSize, e->minPrefSize, e->minSize);
512 e->sizeAtPreferred = interpolate(prefFactor, e->maxSize, e->maxPrefSize,
513 e->prefSize, e->minPrefSize, e->minSize);
514 e->sizeAtMaximum = interpolate(maxFactor, e->maxSize, e->maxPrefSize,
515 e->prefSize, e->minPrefSize, e->minSize);
519 e->updateChildrenSizes();
523 void SequentialAnchorData::calculateSizeHints()
531 AnchorVertex *prev = from;
533 for (int i = 0; i < m_edges.count(); ++i) {
534 AnchorData *edge = m_edges.at(i);
536 const bool edgeIsForward = (edge->from == prev);
538 minSize += edge->minSize;
539 prefSize += edge->prefSize;
540 maxSize += edge->maxSize;
541 minPrefSize += edge->minPrefSize;
542 maxPrefSize += edge->maxPrefSize;
545 Q_ASSERT(prev == edge->to);
546 minSize -= edge->maxSize;
547 prefSize -= edge->prefSize;
548 maxSize -= edge->minSize;
549 minPrefSize -= edge->maxPrefSize;
550 maxPrefSize -= edge->minPrefSize;
555 // See comment in AnchorData::refreshSizeHints() about sizeAt* values
556 sizeAtMinimum = prefSize;
557 sizeAtPreferred = prefSize;
558 sizeAtMaximum = prefSize;
562 void AnchorData::dump(int indent) {
563 if (type == Parallel) {
564 qDebug("%*s type: parallel:", indent, "");
565 ParallelAnchorData *p = static_cast<ParallelAnchorData *>(this);
566 p->firstEdge->dump(indent+2);
567 p->secondEdge->dump(indent+2);
568 } else if (type == Sequential) {
569 SequentialAnchorData *s = static_cast<SequentialAnchorData *>(this);
570 int kids = s->m_edges.count();
571 qDebug("%*s type: sequential(%d):", indent, "", kids);
572 for (int i = 0; i < kids; ++i) {
573 s->m_edges.at(i)->dump(indent+2);
576 qDebug("%*s type: Normal:", indent, "");
582 QSimplexConstraint *GraphPath::constraint(const GraphPath &path) const
585 QSet<AnchorData *> cPositives;
586 QSet<AnchorData *> cNegatives;
587 QSet<AnchorData *> intersection;
589 cPositives = positives + path.negatives;
590 cNegatives = negatives + path.positives;
592 intersection = cPositives & cNegatives;
594 cPositives -= intersection;
595 cNegatives -= intersection;
598 QSimplexConstraint *c = new QSimplexConstraint;
599 QSet<AnchorData *>::iterator i;
600 for (i = cPositives.begin(); i != cPositives.end(); ++i)
601 c->variables.insert(*i, 1.0);
603 for (i = cNegatives.begin(); i != cNegatives.end(); ++i)
604 c->variables.insert(*i, -1.0);
610 QString GraphPath::toString() const
612 QString string(QLatin1String("Path: "));
613 foreach(AnchorData *edge, positives)
614 string += QString::fromAscii(" (+++) %1").arg(edge->toString());
616 foreach(AnchorData *edge, negatives)
617 string += QString::fromAscii(" (---) %1").arg(edge->toString());
623 QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()
624 : calculateGraphCacheDirty(true), styleInfoDirty(true)
626 for (int i = 0; i < NOrientations; ++i) {
627 for (int j = 0; j < 3; ++j) {
628 sizeHints[i][j] = -1;
630 interpolationProgress[i] = -1;
633 graphHasConflicts[i] = false;
635 layoutFirstVertex[i] = 0;
636 layoutCentralVertex[i] = 0;
637 layoutLastVertex[i] = 0;
641 Qt::AnchorPoint QGraphicsAnchorLayoutPrivate::oppositeEdge(Qt::AnchorPoint edge)
645 edge = Qt::AnchorRight;
647 case Qt::AnchorRight:
648 edge = Qt::AnchorLeft;
651 edge = Qt::AnchorBottom;
653 case Qt::AnchorBottom:
654 edge = Qt::AnchorTop;
666 * helper function in order to avoid overflowing anchor sizes
667 * the returned size will never be larger than FLT_MAX
670 inline static qreal checkAdd(qreal a, qreal b)
680 Adds \a newAnchor to the graph.
682 Returns the newAnchor itself if it could be added without further changes to the graph. If a
683 new parallel anchor had to be created, then returns the new parallel anchor. If a parallel anchor
684 had to be created and it results in an unfeasible setup, \a feasible is set to false, otherwise
687 Note that in the case a new parallel anchor is created, it might also take over some constraints
688 from its children anchors.
690 AnchorData *QGraphicsAnchorLayoutPrivate::addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible)
692 Orientation orientation = Orientation(newAnchor->orientation);
693 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
696 // If already exists one anchor where newAnchor is supposed to be, we create a parallel
698 if (AnchorData *oldAnchor = g.takeEdge(newAnchor->from, newAnchor->to)) {
699 ParallelAnchorData *parallel = new ParallelAnchorData(oldAnchor, newAnchor);
701 // The parallel anchor will "replace" its children anchors in
702 // every center constraint that they appear.
704 // ### If the dependent (center) anchors had reference(s) to their constraints, we
705 // could avoid traversing all the itemCenterConstraints.
706 QList<QSimplexConstraint *> &constraints = itemCenterConstraints[orientation];
708 AnchorData *children[2] = { oldAnchor, newAnchor };
709 QList<QSimplexConstraint *> *childrenConstraints[2] = { ¶llel->m_firstConstraints,
710 ¶llel->m_secondConstraints };
712 for (int i = 0; i < 2; ++i) {
713 AnchorData *child = children[i];
714 QList<QSimplexConstraint *> *childConstraints = childrenConstraints[i];
716 // We need to fix the second child constraints if the parallel group will have the
717 // opposite direction of the second child anchor. For the point of view of external
718 // entities, this anchor was reversed. So if at some point we say that the parallel
719 // has a value of 20, this mean that the second child (when reversed) will be
721 const bool needsReverse = i == 1 && !parallel->secondForward();
723 if (!child->isCenterAnchor)
726 parallel->isCenterAnchor = true;
728 for (int j = 0; j < constraints.count(); ++j) {
729 QSimplexConstraint *c = constraints[j];
730 if (c->variables.contains(child)) {
731 childConstraints->append(c);
732 qreal v = c->variables.take(child);
735 c->variables.insert(parallel, v);
740 // At this point we can identify that the parallel anchor is not feasible, e.g. one
741 // anchor minimum size is bigger than the other anchor maximum size.
742 *feasible = parallel->calculateSizeHints();
743 newAnchor = parallel;
746 g.createEdge(newAnchor->from, newAnchor->to, newAnchor);
753 Takes the sequence of vertices described by (\a before, \a vertices, \a after) and removes
754 all anchors connected to the vertices in \a vertices, returning one simplified anchor between
755 \a before and \a after.
757 Note that this function doesn't add the created anchor to the graph. This should be done by
760 static AnchorData *createSequence(Graph<AnchorVertex, AnchorData> *graph,
761 AnchorVertex *before,
762 const QVector<AnchorVertex*> &vertices,
765 #if defined(QT_DEBUG) && 0
767 for (int i = 0; i < vertices.count(); ++i) {
768 strVertices += QString::fromAscii("%1 - ").arg(vertices.at(i)->toString());
770 QString strPath = QString::fromAscii("%1 - %2%3").arg(before->toString(), strVertices, after->toString());
771 qDebug("simplifying [%s] to [%s - %s]", qPrintable(strPath), qPrintable(before->toString()), qPrintable(after->toString()));
774 AnchorVertex *prev = before;
775 QVector<AnchorData *> edges;
777 // Take from the graph, the edges that will be simplificated
778 for (int i = 0; i < vertices.count(); ++i) {
779 AnchorVertex *next = vertices.at(i);
780 AnchorData *ad = graph->takeEdge(prev, next);
786 // Take the last edge (not covered in the loop above)
787 AnchorData *ad = graph->takeEdge(vertices.last(), after);
792 SequentialAnchorData *sequence = new SequentialAnchorData(vertices, edges);
793 sequence->from = before;
794 sequence->to = after;
796 sequence->calculateSizeHints();
804 The purpose of this function is to simplify the graph.
805 Simplification serves two purposes:
806 1. Reduce the number of edges in the graph, (thus the number of variables to the equation
807 solver is reduced, and the solver performs better).
808 2. Be able to do distribution of sequences of edges more intelligently (esp. with sequential
811 It is essential that it must be possible to restore simplified anchors back to their "original"
812 form. This is done by restoreSimplifiedAnchor().
814 There are two types of simplification that can be done:
815 1. Sequential simplification
816 Sequential simplification means that all sequences of anchors will be merged into one single
817 anchor. Only anhcors that points in the same direction will be merged.
818 2. Parallel simplification
819 If a simplified sequential anchor is about to be inserted between two vertices in the graph
820 and there already exist an anchor between those two vertices, a parallel anchor will be
821 created that serves as a placeholder for the sequential anchor and the anchor that was
822 already between the two vertices.
824 The process of simplification can be described as:
826 1. Simplify all sequences of anchors into one anchor.
827 If no further simplification was done, go to (3)
828 - If there already exist an anchor where the sequential anchor is supposed to be inserted,
829 take that anchor out of the graph
830 - Then create a parallel anchor that holds the sequential anchor and the anchor just taken
835 When creating the parallel anchors, the algorithm might identify unfeasible situations. In this
836 case the simplification process stops and returns false. Otherwise returns true.
838 bool QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
843 #if defined(QT_DEBUG) && 0
844 qDebug("Simplifying Graph for %s",
845 orientation == Horizontal ? "Horizontal" : "Vertical");
847 static int count = 0;
848 if (orientation == Horizontal) {
850 dumpGraph(QString::fromAscii("%1-full").arg(count));
854 // Vertex simplification
855 if (!simplifyVertices(orientation)) {
856 restoreVertices(orientation);
860 // Anchor simplification
862 bool feasible = true;
864 dirty = simplifyGraphIteration(orientation, &feasible);
865 } while (dirty && feasible);
867 // Note that if we are not feasible, we fallback and make sure that the graph is fully restored
869 restoreSimplifiedGraph(orientation);
870 restoreVertices(orientation);
874 #if defined(QT_DEBUG) && 0
875 dumpGraph(QString::fromAscii("%1-simplified-%2").arg(count).arg(
876 QString::fromAscii(orientation == Horizontal ? "Horizontal" : "Vertical")));
882 static AnchorVertex *replaceVertex_helper(AnchorData *data, AnchorVertex *oldV, AnchorVertex *newV)
885 if (data->from == oldV) {
895 bool QGraphicsAnchorLayoutPrivate::replaceVertex(Orientation orientation, AnchorVertex *oldV,
896 AnchorVertex *newV, const QList<AnchorData *> &edges)
898 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
899 bool feasible = true;
901 for (int i = 0; i < edges.count(); ++i) {
902 AnchorData *ad = edges[i];
903 AnchorVertex *otherV = replaceVertex_helper(ad, oldV, newV);
905 #if defined(QT_DEBUG)
906 ad->name = QString::fromAscii("%1 --to--> %2").arg(ad->from->toString()).arg(ad->to->toString());
910 AnchorData *newAnchor = addAnchorMaybeParallel(ad, &newFeasible);
911 feasible &= newFeasible;
913 if (newAnchor != ad) {
914 // A parallel was created, we mark that in the list of anchors created by vertex
915 // simplification. This is needed because we want to restore them in a separate step
916 // from the restoration of anchor simplification.
917 anchorsFromSimplifiedVertices[orientation].append(newAnchor);
920 g.takeEdge(oldV, otherV);
929 bool QGraphicsAnchorLayoutPrivate::simplifyVertices(Orientation orientation)
931 Q_Q(QGraphicsAnchorLayout);
932 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
934 // We'll walk through vertices
935 QStack<AnchorVertex *> stack;
936 stack.push(layoutFirstVertex[orientation]);
937 QSet<AnchorVertex *> visited;
939 while (!stack.isEmpty()) {
940 AnchorVertex *v = stack.pop();
943 // Each adjacent of 'v' is a possible vertex to be merged. So we traverse all of
944 // them. Since once a merge is made, we might add new adjacents, and we don't want to
945 // pass two times through one adjacent. The 'index' is used to track our position.
946 QList<AnchorVertex *> adjacents = g.adjacentVertices(v);
949 while (index < adjacents.count()) {
950 AnchorVertex *next = adjacents.at(index);
953 AnchorData *data = g.edgeData(v, next);
954 const bool bothLayoutVertices = v->m_item == q && next->m_item == q;
955 const bool zeroSized = !data->minSize && !data->maxSize;
957 if (!bothLayoutVertices && zeroSized) {
959 // Create a new vertex pair, note that we keep a list of those vertices so we can
960 // easily process them when restoring the graph.
961 AnchorVertexPair *newV = new AnchorVertexPair(v, next, data);
962 simplifiedVertices[orientation].append(newV);
964 // Collect the anchors of both vertices, the new vertex pair will take their place
966 const QList<AnchorVertex *> &vAdjacents = g.adjacentVertices(v);
967 const QList<AnchorVertex *> &nextAdjacents = g.adjacentVertices(next);
969 for (int i = 0; i < vAdjacents.count(); ++i) {
970 AnchorVertex *adjacent = vAdjacents.at(i);
971 if (adjacent != next) {
972 AnchorData *ad = g.edgeData(v, adjacent);
973 newV->m_firstAnchors.append(ad);
977 for (int i = 0; i < nextAdjacents.count(); ++i) {
978 AnchorVertex *adjacent = nextAdjacents.at(i);
980 AnchorData *ad = g.edgeData(next, adjacent);
981 newV->m_secondAnchors.append(ad);
983 // We'll also add new vertices to the adjacent list of the new 'v', to be
984 // created as a vertex pair and replace the current one.
985 if (!adjacents.contains(adjacent))
986 adjacents.append(adjacent);
990 // ### merge this loop into the ones that calculated m_firstAnchors/m_secondAnchors?
991 // Make newV take the place of v and next
992 bool feasible = replaceVertex(orientation, v, newV, newV->m_firstAnchors);
993 feasible &= replaceVertex(orientation, next, newV, newV->m_secondAnchors);
995 // Update the layout vertex information if one of the vertices is a layout vertex.
996 AnchorVertex *layoutVertex = 0;
999 else if (next->m_item == q)
1000 layoutVertex = next;
1003 // Layout vertices always have m_item == q...
1005 changeLayoutVertex(orientation, layoutVertex, newV);
1008 g.takeEdge(v, next);
1010 // If a non-feasibility is found, we leave early and cancel the simplification
1015 visited.insert(newV);
1017 } else if (!visited.contains(next) && !stack.contains(next)) {
1018 // If the adjacent is not fit for merge and it wasn't visited by the outermost
1019 // loop, we add it to the stack.
1031 One iteration of the simplification algorithm. Returns true if another iteration is needed.
1033 The algorithm walks the graph in depth-first order, and only collects vertices that has two
1034 edges connected to it. If the vertex does not have two edges or if it is a layout edge, it
1035 will take all the previously collected vertices and try to create a simplified sequential
1036 anchor representing all the previously collected vertices. Once the simplified anchor is
1037 inserted, the collected list is cleared in order to find the next sequence to simplify.
1039 Note that there are some catches to this that are not covered by the above explanation, see
1040 the function comments for more details.
1042 bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutPrivate::Orientation orientation,
1045 Q_Q(QGraphicsAnchorLayout);
1046 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1048 QSet<AnchorVertex *> visited;
1049 QStack<QPair<AnchorVertex *, AnchorVertex *> > stack;
1050 stack.push(qMakePair(static_cast<AnchorVertex *>(0), layoutFirstVertex[orientation]));
1051 QVector<AnchorVertex*> candidates;
1053 // Walk depth-first, in the stack we store start of the candidate sequence (beforeSequence)
1054 // and the vertex to be visited.
1055 while (!stack.isEmpty()) {
1056 QPair<AnchorVertex *, AnchorVertex *> pair = stack.pop();
1057 AnchorVertex *beforeSequence = pair.first;
1058 AnchorVertex *v = pair.second;
1060 // The basic idea is to determine whether we found an end of sequence,
1061 // if that's the case, we stop adding vertices to the candidate list
1062 // and do a simplification step.
1064 // A vertex can trigger an end of sequence if
1065 // (a) it is a layout vertex, we don't simplify away the layout vertices;
1066 // (b) it does not have exactly 2 adjacents;
1067 // (c) its next adjacent is already visited (a cycle in the graph).
1068 // (d) the next anchor is a center anchor.
1070 const QList<AnchorVertex *> &adjacents = g.adjacentVertices(v);
1071 const bool isLayoutVertex = v->m_item == q;
1072 AnchorVertex *afterSequence = v;
1073 bool endOfSequence = false;
1076 // Identify the end cases.
1079 // Identifies cases (a) and (b)
1080 endOfSequence = isLayoutVertex || adjacents.count() != 2;
1082 if (!endOfSequence) {
1083 // This is a tricky part. We peek at the next vertex to find out whether
1085 // - we already visited the next vertex (c);
1086 // - the next anchor is a center (d).
1088 // Those are needed to identify the remaining end of sequence cases. Note that unlike
1089 // (a) and (b), we preempt the end of sequence by looking into the next vertex.
1091 // Peek at the next vertex
1092 AnchorVertex *after;
1093 if (candidates.isEmpty())
1094 after = (beforeSequence == adjacents.last() ? adjacents.first() : adjacents.last());
1096 after = (candidates.last() == adjacents.last() ? adjacents.first() : adjacents.last());
1098 // ### At this point we assumed that candidates will not contain 'after', this may not hold
1099 // when simplifying FLOATing anchors.
1100 Q_ASSERT(!candidates.contains(after));
1102 const AnchorData *data = g.edgeData(v, after);
1104 const bool cycleFound = visited.contains(after);
1106 // Now cases (c) and (d)...
1107 endOfSequence = cycleFound || data->isCenterAnchor;
1109 if (!endOfSequence) {
1110 // If it's not an end of sequence, then the vertex didn't trigger neither of the
1111 // previously three cases, so it can be added to the candidates list.
1112 candidates.append(v);
1113 } else if (cycleFound && (beforeSequence != after)) {
1114 afterSequence = after;
1115 candidates.append(v);
1120 // Add next non-visited vertices to the stack.
1122 for (int i = 0; i < adjacents.count(); ++i) {
1123 AnchorVertex *next = adjacents.at(i);
1124 if (visited.contains(next))
1127 // If current vertex is an end of sequence, and it'll reset the candidates list. So
1128 // the next vertices will build candidates lists with the current vertex as 'before'
1129 // vertex. If it's not an end of sequence, we keep the original 'before' vertex,
1130 // since we are keeping the candidates list.
1132 stack.push(qMakePair(v, next));
1134 stack.push(qMakePair(beforeSequence, next));
1139 if (!endOfSequence || candidates.isEmpty())
1143 // Create a sequence for (beforeSequence, candidates, afterSequence).
1146 // One restriction we have is to not simplify half of an anchor and let the other half
1147 // unsimplified. So we remove center edges before and after the sequence.
1148 const AnchorData *firstAnchor = g.edgeData(beforeSequence, candidates.first());
1149 if (firstAnchor->isCenterAnchor) {
1150 beforeSequence = candidates.first();
1151 candidates.remove(0);
1153 // If there's not candidates to be simplified, leave.
1154 if (candidates.isEmpty())
1158 const AnchorData *lastAnchor = g.edgeData(candidates.last(), afterSequence);
1159 if (lastAnchor->isCenterAnchor) {
1160 afterSequence = candidates.last();
1161 candidates.remove(candidates.count() - 1);
1163 if (candidates.isEmpty())
1168 // Add the sequence to the graph.
1171 AnchorData *sequence = createSequence(&g, beforeSequence, candidates, afterSequence);
1173 // If 'beforeSequence' and 'afterSequence' already had an anchor between them, we'll
1174 // create a parallel anchor between the new sequence and the old anchor.
1176 AnchorData *newAnchor = addAnchorMaybeParallel(sequence, &newFeasible);
1183 // When a new parallel anchor is create in the graph, we finish the iteration and return
1184 // true to indicate a new iteration is needed. This happens because a parallel anchor
1185 // changes the number of adjacents one vertex has, possibly opening up oportunities for
1186 // building candidate lists (when adjacents == 2).
1187 if (newAnchor != sequence)
1190 // If there was no parallel simplification, we'll keep walking the graph. So we clear the
1191 // candidates list to start again.
1198 void QGraphicsAnchorLayoutPrivate::restoreSimplifiedAnchor(AnchorData *edge)
1201 static const char *anchortypes[] = {"Normal",
1204 qDebug("Restoring %s edge.", anchortypes[int(edge->type)]);
1207 Graph<AnchorVertex, AnchorData> &g = graph[edge->orientation];
1209 if (edge->type == AnchorData::Normal) {
1210 g.createEdge(edge->from, edge->to, edge);
1212 } else if (edge->type == AnchorData::Sequential) {
1213 SequentialAnchorData *sequence = static_cast<SequentialAnchorData *>(edge);
1215 for (int i = 0; i < sequence->m_edges.count(); ++i) {
1216 AnchorData *data = sequence->m_edges.at(i);
1217 restoreSimplifiedAnchor(data);
1222 } else if (edge->type == AnchorData::Parallel) {
1224 // Skip parallel anchors that were created by vertex simplification, they will be processed
1225 // later, when restoring vertex simplification.
1226 // ### we could improve this check bit having a bit inside 'edge'
1227 if (anchorsFromSimplifiedVertices[edge->orientation].contains(edge))
1230 ParallelAnchorData* parallel = static_cast<ParallelAnchorData*>(edge);
1231 restoreSimplifiedConstraints(parallel);
1233 // ### Because of the way parallel anchors are created in the anchor simplification
1234 // algorithm, we know that one of these will be a sequence, so it'll be safe if the other
1235 // anchor create an edge between the same vertices as the parallel.
1236 Q_ASSERT(parallel->firstEdge->type == AnchorData::Sequential
1237 || parallel->secondEdge->type == AnchorData::Sequential);
1238 restoreSimplifiedAnchor(parallel->firstEdge);
1239 restoreSimplifiedAnchor(parallel->secondEdge);
1245 void QGraphicsAnchorLayoutPrivate::restoreSimplifiedConstraints(ParallelAnchorData *parallel)
1247 if (!parallel->isCenterAnchor)
1250 for (int i = 0; i < parallel->m_firstConstraints.count(); ++i) {
1251 QSimplexConstraint *c = parallel->m_firstConstraints.at(i);
1252 qreal v = c->variables[parallel];
1253 c->variables.remove(parallel);
1254 c->variables.insert(parallel->firstEdge, v);
1257 // When restoring, we might have to revert constraints back. See comments on
1258 // addAnchorMaybeParallel().
1259 const bool needsReverse = !parallel->secondForward();
1261 for (int i = 0; i < parallel->m_secondConstraints.count(); ++i) {
1262 QSimplexConstraint *c = parallel->m_secondConstraints.at(i);
1263 qreal v = c->variables[parallel];
1266 c->variables.remove(parallel);
1267 c->variables.insert(parallel->secondEdge, v);
1271 void QGraphicsAnchorLayoutPrivate::restoreSimplifiedGraph(Orientation orientation)
1274 qDebug("Restoring Simplified Graph for %s",
1275 orientation == Horizontal ? "Horizontal" : "Vertical");
1278 // Restore anchor simplification
1279 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1280 QList<QPair<AnchorVertex*, AnchorVertex*> > connections = g.connections();
1281 for (int i = 0; i < connections.count(); ++i) {
1282 AnchorVertex *v1 = connections.at(i).first;
1283 AnchorVertex *v2 = connections.at(i).second;
1284 AnchorData *edge = g.edgeData(v1, v2);
1286 // We restore only sequential anchors and parallels that were not created by
1287 // vertex simplification.
1288 if (edge->type == AnchorData::Sequential
1289 || (edge->type == AnchorData::Parallel &&
1290 !anchorsFromSimplifiedVertices[orientation].contains(edge))) {
1293 restoreSimplifiedAnchor(edge);
1297 restoreVertices(orientation);
1300 void QGraphicsAnchorLayoutPrivate::restoreVertices(Orientation orientation)
1302 Q_Q(QGraphicsAnchorLayout);
1304 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1305 QList<AnchorVertexPair *> &toRestore = simplifiedVertices[orientation];
1307 // Since we keep a list of parallel anchors and vertices that were created during vertex
1308 // simplification, we can now iterate on those lists instead of traversing the graph
1311 // First, restore the constraints changed when we created parallel anchors. Note that this
1312 // works at this point because the constraints doesn't depend on vertex information and at
1313 // this point it's always safe to identify whether the second child is forward or backwards.
1314 // In the next step, we'll change the anchors vertices so that would not be possible anymore.
1315 QList<AnchorData *> ¶llelAnchors = anchorsFromSimplifiedVertices[orientation];
1317 for (int i = parallelAnchors.count() - 1; i >= 0; --i) {
1318 ParallelAnchorData *parallel = static_cast<ParallelAnchorData *>(parallelAnchors.at(i));
1319 restoreSimplifiedConstraints(parallel);
1322 // Then, we will restore the vertices in the inverse order of creation, this way we ensure that
1323 // the vertex being restored was not wrapped by another simplification.
1324 for (int i = toRestore.count() - 1; i >= 0; --i) {
1325 AnchorVertexPair *pair = toRestore.at(i);
1326 QList<AnchorVertex *> adjacents = g.adjacentVertices(pair);
1328 // Restore the removed edge, this will also restore both vertices 'first' and 'second' to
1329 // the graph structure.
1330 AnchorVertex *first = pair->m_first;
1331 AnchorVertex *second = pair->m_second;
1332 g.createEdge(first, second, pair->m_removedAnchor);
1334 // Restore the anchors for the first child vertex
1335 for (int j = 0; j < pair->m_firstAnchors.count(); ++j) {
1336 AnchorData *ad = pair->m_firstAnchors.at(j);
1337 Q_ASSERT(ad->from == pair || ad->to == pair);
1339 replaceVertex_helper(ad, pair, first);
1340 g.createEdge(ad->from, ad->to, ad);
1343 // Restore the anchors for the second child vertex
1344 for (int j = 0; j < pair->m_secondAnchors.count(); ++j) {
1345 AnchorData *ad = pair->m_secondAnchors.at(j);
1346 Q_ASSERT(ad->from == pair || ad->to == pair);
1348 replaceVertex_helper(ad, pair, second);
1349 g.createEdge(ad->from, ad->to, ad);
1352 for (int j = 0; j < adjacents.count(); ++j) {
1353 g.takeEdge(pair, adjacents.at(j));
1356 // The pair simplified a layout vertex, so place back the correct vertex in the variable
1357 // that track layout vertices
1358 if (pair->m_item == q) {
1359 AnchorVertex *layoutVertex = first->m_item == q ? first : second;
1360 Q_ASSERT(layoutVertex->m_item == q);
1361 changeLayoutVertex(orientation, pair, layoutVertex);
1366 qDeleteAll(parallelAnchors);
1367 parallelAnchors.clear();
1371 QGraphicsAnchorLayoutPrivate::Orientation
1372 QGraphicsAnchorLayoutPrivate::edgeOrientation(Qt::AnchorPoint edge)
1374 return edge > Qt::AnchorRight ? Vertical : Horizontal;
1380 Create internal anchors to connect the layout edges (Left to Right and
1383 These anchors doesn't have size restrictions, that will be enforced by
1384 other anchors and items in the layout.
1386 void QGraphicsAnchorLayoutPrivate::createLayoutEdges()
1388 Q_Q(QGraphicsAnchorLayout);
1389 QGraphicsLayoutItem *layout = q;
1392 AnchorData *data = new AnchorData;
1393 addAnchor_helper(layout, Qt::AnchorLeft, layout,
1394 Qt::AnchorRight, data);
1395 data->maxSize = QWIDGETSIZE_MAX;
1397 // Save a reference to layout vertices
1398 layoutFirstVertex[Horizontal] = internalVertex(layout, Qt::AnchorLeft);
1399 layoutCentralVertex[Horizontal] = 0;
1400 layoutLastVertex[Horizontal] = internalVertex(layout, Qt::AnchorRight);
1403 data = new AnchorData;
1404 addAnchor_helper(layout, Qt::AnchorTop, layout,
1405 Qt::AnchorBottom, data);
1406 data->maxSize = QWIDGETSIZE_MAX;
1408 // Save a reference to layout vertices
1409 layoutFirstVertex[Vertical] = internalVertex(layout, Qt::AnchorTop);
1410 layoutCentralVertex[Vertical] = 0;
1411 layoutLastVertex[Vertical] = internalVertex(layout, Qt::AnchorBottom);
1414 void QGraphicsAnchorLayoutPrivate::deleteLayoutEdges()
1416 Q_Q(QGraphicsAnchorLayout);
1418 Q_ASSERT(!internalVertex(q, Qt::AnchorHorizontalCenter));
1419 Q_ASSERT(!internalVertex(q, Qt::AnchorVerticalCenter));
1421 removeAnchor_helper(internalVertex(q, Qt::AnchorLeft),
1422 internalVertex(q, Qt::AnchorRight));
1423 removeAnchor_helper(internalVertex(q, Qt::AnchorTop),
1424 internalVertex(q, Qt::AnchorBottom));
1427 void QGraphicsAnchorLayoutPrivate::createItemEdges(QGraphicsLayoutItem *item)
1431 // Create horizontal and vertical internal anchors for the item and
1432 // refresh its size hint / policy values.
1433 AnchorData *data = new AnchorData;
1434 addAnchor_helper(item, Qt::AnchorLeft, item, Qt::AnchorRight, data);
1435 data->refreshSizeHints();
1437 data = new AnchorData;
1438 addAnchor_helper(item, Qt::AnchorTop, item, Qt::AnchorBottom, data);
1439 data->refreshSizeHints();
1445 By default, each item in the layout is represented internally as
1446 a single anchor in each direction. For instance, from Left to Right.
1448 However, to support anchorage of items to the center of items, we
1449 must split this internal anchor into two half-anchors. From Left
1450 to Center and then from Center to Right, with the restriction that
1451 these anchors must have the same time at all times.
1453 void QGraphicsAnchorLayoutPrivate::createCenterAnchors(
1454 QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge)
1456 Q_Q(QGraphicsAnchorLayout);
1458 Orientation orientation;
1459 switch (centerEdge) {
1460 case Qt::AnchorHorizontalCenter:
1461 orientation = Horizontal;
1463 case Qt::AnchorVerticalCenter:
1464 orientation = Vertical;
1467 // Don't create center edges unless needed
1471 // Check if vertex already exists
1472 if (internalVertex(item, centerEdge))
1476 Qt::AnchorPoint firstEdge;
1477 Qt::AnchorPoint lastEdge;
1479 if (orientation == Horizontal) {
1480 firstEdge = Qt::AnchorLeft;
1481 lastEdge = Qt::AnchorRight;
1483 firstEdge = Qt::AnchorTop;
1484 lastEdge = Qt::AnchorBottom;
1487 AnchorVertex *first = internalVertex(item, firstEdge);
1488 AnchorVertex *last = internalVertex(item, lastEdge);
1489 Q_ASSERT(first && last);
1491 // Create new anchors
1492 QSimplexConstraint *c = new QSimplexConstraint;
1494 AnchorData *data = new AnchorData;
1495 c->variables.insert(data, 1.0);
1496 addAnchor_helper(item, firstEdge, item, centerEdge, data);
1497 data->isCenterAnchor = true;
1498 data->dependency = AnchorData::Master;
1499 data->refreshSizeHints();
1501 data = new AnchorData;
1502 c->variables.insert(data, -1.0);
1503 addAnchor_helper(item, centerEdge, item, lastEdge, data);
1504 data->isCenterAnchor = true;
1505 data->dependency = AnchorData::Slave;
1506 data->refreshSizeHints();
1508 itemCenterConstraints[orientation].append(c);
1511 removeAnchor_helper(first, last);
1514 layoutCentralVertex[orientation] = internalVertex(q, centerEdge);
1518 void QGraphicsAnchorLayoutPrivate::removeCenterAnchors(
1519 QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge,
1522 Q_Q(QGraphicsAnchorLayout);
1524 Orientation orientation;
1525 switch (centerEdge) {
1526 case Qt::AnchorHorizontalCenter:
1527 orientation = Horizontal;
1529 case Qt::AnchorVerticalCenter:
1530 orientation = Vertical;
1533 // Don't remove edges that not the center ones
1538 Qt::AnchorPoint firstEdge;
1539 Qt::AnchorPoint lastEdge;
1541 if (orientation == Horizontal) {
1542 firstEdge = Qt::AnchorLeft;
1543 lastEdge = Qt::AnchorRight;
1545 firstEdge = Qt::AnchorTop;
1546 lastEdge = Qt::AnchorBottom;
1549 AnchorVertex *center = internalVertex(item, centerEdge);
1552 AnchorVertex *first = internalVertex(item, firstEdge);
1557 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1560 AnchorData *oldData = g.edgeData(first, center);
1561 // Remove center constraint
1562 for (int i = itemCenterConstraints[orientation].count() - 1; i >= 0; --i) {
1563 if (itemCenterConstraints[orientation].at(i)->variables.contains(oldData)) {
1564 delete itemCenterConstraints[orientation].takeAt(i);
1570 // Create the new anchor that should substitute the left-center-right anchors.
1571 AnchorData *data = new AnchorData;
1572 addAnchor_helper(item, firstEdge, item, lastEdge, data);
1573 data->refreshSizeHints();
1575 // Remove old anchors
1576 removeAnchor_helper(first, center);
1577 removeAnchor_helper(center, internalVertex(item, lastEdge));
1580 // this is only called from removeAnchors()
1581 // first, remove all non-internal anchors
1582 QList<AnchorVertex*> adjacents = g.adjacentVertices(center);
1583 for (int i = 0; i < adjacents.count(); ++i) {
1584 AnchorVertex *v = adjacents.at(i);
1585 if (v->m_item != item) {
1586 removeAnchor_helper(center, internalVertex(v->m_item, v->m_edge));
1589 // when all non-internal anchors is removed it will automatically merge the
1590 // center anchor into a left-right (or top-bottom) anchor. We must also delete that.
1591 // by this time, the center vertex is deleted and merged into a non-centered internal anchor
1592 removeAnchor_helper(first, internalVertex(item, lastEdge));
1596 layoutCentralVertex[orientation] = 0;
1601 void QGraphicsAnchorLayoutPrivate::removeCenterConstraints(QGraphicsLayoutItem *item,
1602 Orientation orientation)
1604 // Remove the item center constraints associated to this item
1605 // ### This is a temporary solution. We should probably use a better
1606 // data structure to hold items and/or their associated constraints
1607 // so that we can remove those easily
1609 AnchorVertex *first = internalVertex(item, orientation == Horizontal ?
1612 AnchorVertex *center = internalVertex(item, orientation == Horizontal ?
1613 Qt::AnchorHorizontalCenter :
1614 Qt::AnchorVerticalCenter);
1616 // Skip if no center constraints exist
1621 AnchorData *internalAnchor = graph[orientation].edgeData(first, center);
1623 // Look for our anchor in all item center constraints, then remove it
1624 for (int i = 0; i < itemCenterConstraints[orientation].size(); ++i) {
1625 if (itemCenterConstraints[orientation].at(i)->variables.contains(internalAnchor)) {
1626 delete itemCenterConstraints[orientation].takeAt(i);
1634 * Implements the high level "addAnchor" feature. Called by the public API
1637 * The optional \a spacing argument defines the size of the anchor. If not provided,
1638 * the anchor size is either 0 or not-set, depending on type of anchor created (see
1641 * All anchors that remain with size not-set will assume the standard spacing,
1642 * set either by the layout style or through the "setSpacing" layout API.
1644 QGraphicsAnchor *QGraphicsAnchorLayoutPrivate::addAnchor(QGraphicsLayoutItem *firstItem,
1645 Qt::AnchorPoint firstEdge,
1646 QGraphicsLayoutItem *secondItem,
1647 Qt::AnchorPoint secondEdge,
1650 Q_Q(QGraphicsAnchorLayout);
1651 if ((firstItem == 0) || (secondItem == 0)) {
1652 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1653 "Cannot anchor NULL items");
1657 if (firstItem == secondItem) {
1658 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1659 "Cannot anchor the item to itself");
1663 if (edgeOrientation(secondEdge) != edgeOrientation(firstEdge)) {
1664 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1665 "Cannot anchor edges of different orientations");
1669 const QGraphicsLayoutItem *parentWidget = q->parentLayoutItem();
1670 if (firstItem == parentWidget || secondItem == parentWidget) {
1671 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1672 "You cannot add the parent of the layout to the layout.");
1676 // In QGraphicsAnchorLayout, items are represented in its internal
1677 // graph as four anchors that connect:
1678 // - Left -> HCenter
1679 // - HCenter-> Right
1681 // - VCenter -> Bottom
1683 // Ensure that the internal anchors have been created for both items.
1684 if (firstItem != q && !items.contains(firstItem)) {
1685 createItemEdges(firstItem);
1686 addChildLayoutItem(firstItem);
1688 if (secondItem != q && !items.contains(secondItem)) {
1689 createItemEdges(secondItem);
1690 addChildLayoutItem(secondItem);
1693 // Create center edges if needed
1694 createCenterAnchors(firstItem, firstEdge);
1695 createCenterAnchors(secondItem, secondEdge);
1697 // Use heuristics to find out what the user meant with this anchor.
1698 correctEdgeDirection(firstItem, firstEdge, secondItem, secondEdge);
1700 AnchorData *data = new AnchorData;
1701 QGraphicsAnchor *graphicsAnchor = acquireGraphicsAnchor(data);
1703 addAnchor_helper(firstItem, firstEdge, secondItem, secondEdge, data);
1706 graphicsAnchor->setSpacing(*spacing);
1708 // If firstItem or secondItem is the layout itself, the spacing will default to 0.
1709 // Otherwise, the following matrix is used (questionmark means that the spacing
1710 // is queried from the style):
1712 // to Left HCenter Right
1718 || pickEdge(firstEdge, Horizontal) == Qt::AnchorHorizontalCenter
1719 || oppositeEdge(firstEdge) != secondEdge) {
1720 graphicsAnchor->setSpacing(0);
1722 graphicsAnchor->unsetSpacing();
1726 return graphicsAnchor;
1732 This method adds an AnchorData to the internal graph. It is responsible for doing
1733 the boilerplate part of such task.
1735 If another AnchorData exists between the mentioned vertices, it is deleted and
1736 the new one is inserted.
1738 void QGraphicsAnchorLayoutPrivate::addAnchor_helper(QGraphicsLayoutItem *firstItem,
1739 Qt::AnchorPoint firstEdge,
1740 QGraphicsLayoutItem *secondItem,
1741 Qt::AnchorPoint secondEdge,
1744 Q_Q(QGraphicsAnchorLayout);
1746 const Orientation orientation = edgeOrientation(firstEdge);
1748 // Create or increase the reference count for the related vertices.
1749 AnchorVertex *v1 = addInternalVertex(firstItem, firstEdge);
1750 AnchorVertex *v2 = addInternalVertex(secondItem, secondEdge);
1752 // Remove previous anchor
1753 if (graph[orientation].edgeData(v1, v2)) {
1754 removeAnchor_helper(v1, v2);
1757 // If its an internal anchor, set the associated item
1758 if (firstItem == secondItem)
1759 data->item = firstItem;
1761 data->orientation = orientation;
1763 // Create a bi-directional edge in the sense it can be transversed both
1764 // from v1 or v2. "data" however is shared between the two references
1765 // so we still know that the anchor direction is from 1 to 2.
1769 data->name = QString::fromAscii("%1 --to--> %2").arg(v1->toString()).arg(v2->toString());
1771 // ### bit to track internal anchors, since inside AnchorData methods
1772 // we don't have access to the 'q' pointer.
1773 data->isLayoutAnchor = (data->item == q);
1775 graph[orientation].createEdge(v1, v2, data);
1778 QGraphicsAnchor *QGraphicsAnchorLayoutPrivate::getAnchor(QGraphicsLayoutItem *firstItem,
1779 Qt::AnchorPoint firstEdge,
1780 QGraphicsLayoutItem *secondItem,
1781 Qt::AnchorPoint secondEdge)
1783 // Do not expose internal anchors
1784 if (firstItem == secondItem)
1787 const Orientation orientation = edgeOrientation(firstEdge);
1788 AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
1789 AnchorVertex *v2 = internalVertex(secondItem, secondEdge);
1791 QGraphicsAnchor *graphicsAnchor = 0;
1793 AnchorData *data = graph[orientation].edgeData(v1, v2);
1795 // We could use "acquireGraphicsAnchor" here, but to avoid a regression where
1796 // an internal anchor was wrongly exposed, I want to ensure no new
1797 // QGraphicsAnchor instances are created by this call.
1798 // This assumption must hold because anchors are either user-created (and already
1799 // have their public object created), or they are internal (and must not reach
1801 Q_ASSERT(data->graphicsAnchor);
1802 graphicsAnchor = data->graphicsAnchor;
1804 return graphicsAnchor;
1810 * Implements the high level "removeAnchor" feature. Called by
1811 * the QAnchorData destructor.
1813 void QGraphicsAnchorLayoutPrivate::removeAnchor(AnchorVertex *firstVertex,
1814 AnchorVertex *secondVertex)
1816 Q_Q(QGraphicsAnchorLayout);
1818 // Save references to items while it's safe to assume the vertices exist
1819 QGraphicsLayoutItem *firstItem = firstVertex->m_item;
1820 QGraphicsLayoutItem *secondItem = secondVertex->m_item;
1822 // Delete the anchor (may trigger deletion of center vertices)
1823 removeAnchor_helper(firstVertex, secondVertex);
1825 // Ensure no dangling pointer is left behind
1826 firstVertex = secondVertex = 0;
1828 // Checking if the item stays in the layout or not
1829 bool keepFirstItem = false;
1830 bool keepSecondItem = false;
1832 QPair<AnchorVertex *, int> v;
1835 if (firstItem != q) {
1836 for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
1837 v = m_vertexList.value(qMakePair(firstItem, static_cast<Qt::AnchorPoint>(i)));
1839 if (i == Qt::AnchorHorizontalCenter || i == Qt::AnchorVerticalCenter)
1844 if (v.second > refcount) {
1845 keepFirstItem = true;
1851 keepFirstItem = true;
1853 if (secondItem != q) {
1854 for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
1855 v = m_vertexList.value(qMakePair(secondItem, static_cast<Qt::AnchorPoint>(i)));
1857 if (i == Qt::AnchorHorizontalCenter || i == Qt::AnchorVerticalCenter)
1862 if (v.second > refcount) {
1863 keepSecondItem = true;
1869 keepSecondItem = true;
1872 q->removeAt(items.indexOf(firstItem));
1874 if (!keepSecondItem)
1875 q->removeAt(items.indexOf(secondItem));
1877 // Removing anchors invalidates the layout
1884 Implements the low level "removeAnchor" feature. Called by
1887 void QGraphicsAnchorLayoutPrivate::removeAnchor_helper(AnchorVertex *v1, AnchorVertex *v2)
1891 // Remove edge from graph
1892 const Orientation o = edgeOrientation(v1->m_edge);
1893 graph[o].removeEdge(v1, v2);
1895 // Decrease vertices reference count (may trigger a deletion)
1896 removeInternalVertex(v1->m_item, v1->m_edge);
1897 removeInternalVertex(v2->m_item, v2->m_edge);
1900 AnchorVertex *QGraphicsAnchorLayoutPrivate::addInternalVertex(QGraphicsLayoutItem *item,
1901 Qt::AnchorPoint edge)
1903 QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
1904 QPair<AnchorVertex *, int> v = m_vertexList.value(pair);
1907 Q_ASSERT(v.second == 0);
1908 v.first = new AnchorVertex(item, edge);
1911 m_vertexList.insert(pair, v);
1918 * returns the AnchorVertex that was dereferenced, also when it was removed.
1919 * returns 0 if it did not exist.
1921 void QGraphicsAnchorLayoutPrivate::removeInternalVertex(QGraphicsLayoutItem *item,
1922 Qt::AnchorPoint edge)
1924 QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
1925 QPair<AnchorVertex *, int> v = m_vertexList.value(pair);
1928 qWarning("This item with this edge is not in the graph");
1933 if (v.second == 0) {
1934 // Remove reference and delete vertex
1935 m_vertexList.remove(pair);
1938 // Update reference count
1939 m_vertexList.insert(pair, v);
1941 if ((v.second == 2) &&
1942 ((edge == Qt::AnchorHorizontalCenter) ||
1943 (edge == Qt::AnchorVerticalCenter))) {
1944 removeCenterAnchors(item, edge, true);
1949 void QGraphicsAnchorLayoutPrivate::removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
1951 if (AnchorVertex *v = internalVertex(item, edge)) {
1952 Graph<AnchorVertex, AnchorData> &g = graph[edgeOrientation(edge)];
1953 const QList<AnchorVertex *> allVertices = graph[edgeOrientation(edge)].adjacentVertices(v);
1955 foreach (v2, allVertices) {
1956 g.removeEdge(v, v2);
1957 removeInternalVertex(item, edge);
1958 removeInternalVertex(v2->m_item, v2->m_edge);
1963 void QGraphicsAnchorLayoutPrivate::removeAnchors(QGraphicsLayoutItem *item)
1965 // remove the center anchor first!!
1966 removeCenterAnchors(item, Qt::AnchorHorizontalCenter, false);
1967 removeVertex(item, Qt::AnchorLeft);
1968 removeVertex(item, Qt::AnchorRight);
1970 removeCenterAnchors(item, Qt::AnchorVerticalCenter, false);
1971 removeVertex(item, Qt::AnchorTop);
1972 removeVertex(item, Qt::AnchorBottom);
1978 Use heuristics to determine the correct orientation of a given anchor.
1980 After API discussions, we decided we would like expressions like
1981 anchor(A, Left, B, Right) to mean the same as anchor(B, Right, A, Left).
1982 The problem with this is that anchors could become ambiguous, for
1983 instance, what does the anchor A, B of size X mean?
1985 "pos(B) = pos(A) + X" or "pos(A) = pos(B) + X" ?
1987 To keep the API user friendly and at the same time, keep our algorithm
1988 deterministic, we use an heuristic to determine a direction for each
1989 added anchor and then keep it. The heuristic is based on the fact
1990 that people usually avoid overlapping items, therefore:
1992 "A, RIGHT to B, LEFT" means that B is to the LEFT of A.
1993 "B, LEFT to A, RIGHT" is corrected to the above anchor.
1995 Special correction is also applied when one of the items is the
1996 layout. We handle Layout Left as if it was another items's Right
1997 and Layout Right as another item's Left.
1999 void QGraphicsAnchorLayoutPrivate::correctEdgeDirection(QGraphicsLayoutItem *&firstItem,
2000 Qt::AnchorPoint &firstEdge,
2001 QGraphicsLayoutItem *&secondItem,
2002 Qt::AnchorPoint &secondEdge)
2004 Q_Q(QGraphicsAnchorLayout);
2006 if ((firstItem != q) && (secondItem != q)) {
2007 // If connection is between widgets (not the layout itself)
2008 // Ensure that "right-edges" sit to the left of "left-edges".
2009 if (firstEdge < secondEdge) {
2010 qSwap(firstItem, secondItem);
2011 qSwap(firstEdge, secondEdge);
2013 } else if (firstItem == q) {
2014 // If connection involves the right or bottom of a layout, ensure
2015 // the layout is the second item.
2016 if ((firstEdge == Qt::AnchorRight) || (firstEdge == Qt::AnchorBottom)) {
2017 qSwap(firstItem, secondItem);
2018 qSwap(firstEdge, secondEdge);
2020 } else if ((secondEdge != Qt::AnchorRight) && (secondEdge != Qt::AnchorBottom)) {
2021 // If connection involves the left, center or top of layout, ensure
2022 // the layout is the first item.
2023 qSwap(firstItem, secondItem);
2024 qSwap(firstEdge, secondEdge);
2028 QLayoutStyleInfo &QGraphicsAnchorLayoutPrivate::styleInfo() const
2030 if (styleInfoDirty) {
2031 Q_Q(const QGraphicsAnchorLayout);
2032 //### Fix this if QGV ever gets support for Metal style or different Aqua sizes.
2035 QGraphicsLayoutItem *parent = q->parentLayoutItem();
2036 while (parent && parent->isLayout()) {
2037 parent = parent->parentLayoutItem();
2039 QGraphicsWidget *w = 0;
2041 QGraphicsItem *parentItem = parent->graphicsItem();
2042 if (parentItem && parentItem->isWidget())
2043 w = static_cast<QGraphicsWidget*>(parentItem);
2046 QStyle *style = w ? w->style() : QApplication::style();
2047 cachedStyleInfo = QLayoutStyleInfo(style, wid);
2048 cachedStyleInfo.setDefaultSpacing(Qt::Horizontal, spacings[0]);
2049 cachedStyleInfo.setDefaultSpacing(Qt::Vertical, spacings[1]);
2051 styleInfoDirty = false;
2053 return cachedStyleInfo;
2059 Called on activation. Uses Linear Programming to define minimum, preferred
2060 and maximum sizes for the layout. Also calculates the sizes that each item
2061 should assume when the layout is in one of such situations.
2063 void QGraphicsAnchorLayoutPrivate::calculateGraphs()
2065 if (!calculateGraphCacheDirty)
2067 calculateGraphs(Horizontal);
2068 calculateGraphs(Vertical);
2069 calculateGraphCacheDirty = false;
2072 // ### Maybe getGraphParts could return the variables when traversing, at least
2074 QList<AnchorData *> getVariables(QList<QSimplexConstraint *> constraints)
2076 QSet<AnchorData *> variableSet;
2077 for (int i = 0; i < constraints.count(); ++i) {
2078 const QSimplexConstraint *c = constraints.at(i);
2079 foreach (QSimplexVariable *var, c->variables.keys()) {
2080 variableSet += static_cast<AnchorData *>(var);
2083 return variableSet.toList();
2089 Calculate graphs is the method that puts together all the helper routines
2090 so that the AnchorLayout can calculate the sizes of each item.
2092 In a nutshell it should do:
2094 1) Refresh anchor nominal sizes, that is, the size that each anchor would
2095 have if no other restrictions applied. This is done by quering the
2096 layout style and the sizeHints of the items belonging to the layout.
2098 2) Simplify the graph by grouping together parallel and sequential anchors
2099 into "group anchors". These have equivalent minimum, preferred and maximum
2100 sizeHints as the anchors they replace.
2102 3) Check if we got to a trivial case. In some cases, the whole graph can be
2103 simplified into a single anchor. If so, use this information. If not,
2104 then call the Simplex solver to calculate the anchors sizes.
2106 4) Once the root anchors had its sizes calculated, propagate that to the
2107 anchors they represent.
2109 void QGraphicsAnchorLayoutPrivate::calculateGraphs(
2110 QGraphicsAnchorLayoutPrivate::Orientation orientation)
2112 #if defined(QT_DEBUG) || defined(Q_AUTOTEST_EXPORT)
2113 lastCalculationUsedSimplex[orientation] = false;
2116 static bool simplificationEnabled = qgetenv("QT_ANCHORLAYOUT_NO_SIMPLIFICATION").isEmpty();
2118 // Reset the nominal sizes of each anchor based on the current item sizes
2119 refreshAllSizeHints(orientation);
2121 // Simplify the graph
2122 if (simplificationEnabled && !simplifyGraph(orientation)) {
2123 qWarning("QGraphicsAnchorLayout: anchor setup is not feasible.");
2124 graphHasConflicts[orientation] = true;
2128 // Traverse all graph edges and store the possible paths to each vertex
2129 findPaths(orientation);
2131 // From the paths calculated above, extract the constraints that the current
2132 // anchor setup impose, to our Linear Programming problem.
2133 constraintsFromPaths(orientation);
2135 // Split the constraints and anchors into groups that should be fed to the
2136 // simplex solver independently. Currently we find two groups:
2138 // 1) The "trunk", that is, the set of anchors (items) that are connected
2139 // to the two opposite sides of our layout, and thus need to stretch in
2140 // order to fit in the current layout size.
2142 // 2) The floating or semi-floating anchors (items) that are those which
2143 // are connected to only one (or none) of the layout sides, thus are not
2144 // influenced by the layout size.
2145 QList<QList<QSimplexConstraint *> > parts = getGraphParts(orientation);
2147 // Now run the simplex solver to calculate Minimum, Preferred and Maximum sizes
2148 // of the "trunk" set of constraints and variables.
2149 // ### does trunk always exist? empty = trunk is the layout left->center->right
2150 QList<QSimplexConstraint *> trunkConstraints = parts.at(0);
2151 QList<AnchorData *> trunkVariables = getVariables(trunkConstraints);
2153 // For minimum and maximum, use the path between the two layout sides as the
2154 // objective function.
2155 AnchorVertex *v = layoutLastVertex[orientation];
2156 GraphPath trunkPath = graphPaths[orientation].value(v);
2158 bool feasible = calculateTrunk(orientation, trunkPath, trunkConstraints, trunkVariables);
2160 // For the other parts that not the trunk, solve only for the preferred size
2161 // that is the size they will remain at, since they are not stretched by the
2164 // Skipping the first (trunk)
2165 for (int i = 1; i < parts.count(); ++i) {
2169 QList<QSimplexConstraint *> partConstraints = parts.at(i);
2170 QList<AnchorData *> partVariables = getVariables(partConstraints);
2171 Q_ASSERT(!partVariables.isEmpty());
2172 feasible &= calculateNonTrunk(partConstraints, partVariables);
2175 // Propagate the new sizes down the simplified graph, ie. tell the
2176 // group anchors to set their children anchors sizes.
2177 updateAnchorSizes(orientation);
2179 graphHasConflicts[orientation] = !feasible;
2181 // Clean up our data structures. They are not needed anymore since
2182 // distribution uses just interpolation.
2183 qDeleteAll(constraints[orientation]);
2184 constraints[orientation].clear();
2185 graphPaths[orientation].clear(); // ###
2187 if (simplificationEnabled)
2188 restoreSimplifiedGraph(orientation);
2194 Shift all the constraints by a certain amount. This allows us to deal with negative values in
2195 the linear program if they are bounded by a certain limit. Functions should be careful to
2196 call it again with a negative amount, to shift the constraints back.
2198 static void shiftConstraints(const QList<QSimplexConstraint *> &constraints, qreal amount)
2200 for (int i = 0; i < constraints.count(); ++i) {
2201 QSimplexConstraint *c = constraints.at(i);
2202 qreal multiplier = 0;
2203 foreach (qreal v, c->variables.values()) {
2206 c->constant += multiplier * amount;
2213 Calculate the sizes for all anchors which are part of the trunk. This works
2214 on top of a (possibly) simplified graph.
2216 bool QGraphicsAnchorLayoutPrivate::calculateTrunk(Orientation orientation, const GraphPath &path,
2217 const QList<QSimplexConstraint *> &constraints,
2218 const QList<AnchorData *> &variables)
2220 bool feasible = true;
2221 bool needsSimplex = !constraints.isEmpty();
2224 qDebug("Simplex %s for trunk of %s", needsSimplex ? "used" : "NOT used",
2225 orientation == Horizontal ? "Horizontal" : "Vertical");
2230 QList<QSimplexConstraint *> sizeHintConstraints = constraintsFromSizeHints(variables);
2231 QList<QSimplexConstraint *> allConstraints = constraints + sizeHintConstraints;
2233 shiftConstraints(allConstraints, g_offset);
2235 // Solve min and max size hints
2237 feasible = solveMinMax(allConstraints, path, &min, &max);
2240 solvePreferred(constraints, variables);
2242 // Calculate and set the preferred size for the layout,
2243 // from the edge sizes that were calculated above.
2245 foreach (const AnchorData *ad, path.positives) {
2246 pref += ad->sizeAtPreferred;
2248 foreach (const AnchorData *ad, path.negatives) {
2249 pref -= ad->sizeAtPreferred;
2252 sizeHints[orientation][Qt::MinimumSize] = min;
2253 sizeHints[orientation][Qt::PreferredSize] = pref;
2254 sizeHints[orientation][Qt::MaximumSize] = max;
2257 qDeleteAll(sizeHintConstraints);
2258 shiftConstraints(constraints, -g_offset);
2261 // No Simplex is necessary because the path was simplified all the way to a single
2263 Q_ASSERT(path.positives.count() == 1);
2264 Q_ASSERT(path.negatives.count() == 0);
2266 AnchorData *ad = path.positives.toList()[0];
2267 ad->sizeAtMinimum = ad->minSize;
2268 ad->sizeAtPreferred = ad->prefSize;
2269 ad->sizeAtMaximum = ad->maxSize;
2271 sizeHints[orientation][Qt::MinimumSize] = ad->sizeAtMinimum;
2272 sizeHints[orientation][Qt::PreferredSize] = ad->sizeAtPreferred;
2273 sizeHints[orientation][Qt::MaximumSize] = ad->sizeAtMaximum;
2276 #if defined(QT_DEBUG) || defined(Q_AUTOTEST_EXPORT)
2277 lastCalculationUsedSimplex[orientation] = needsSimplex;
2286 bool QGraphicsAnchorLayoutPrivate::calculateNonTrunk(const QList<QSimplexConstraint *> &constraints,
2287 const QList<AnchorData *> &variables)
2289 shiftConstraints(constraints, g_offset);
2290 bool feasible = solvePreferred(constraints, variables);
2293 // Propagate size at preferred to other sizes. Semi-floats always will be
2294 // in their sizeAtPreferred.
2295 for (int j = 0; j < variables.count(); ++j) {
2296 AnchorData *ad = variables.at(j);
2298 ad->sizeAtMinimum = ad->sizeAtPreferred;
2299 ad->sizeAtMaximum = ad->sizeAtPreferred;
2303 shiftConstraints(constraints, -g_offset);
2310 Traverse the graph refreshing the size hints. Edges will query their associated
2311 item or graphicsAnchor for their size hints.
2313 void QGraphicsAnchorLayoutPrivate::refreshAllSizeHints(Orientation orientation)
2315 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
2316 QList<QPair<AnchorVertex *, AnchorVertex *> > vertices = g.connections();
2318 QLayoutStyleInfo styleInf = styleInfo();
2319 for (int i = 0; i < vertices.count(); ++i) {
2320 AnchorData *data = g.edgeData(vertices.at(i).first, vertices.at(i).second);
2321 data->refreshSizeHints(&styleInf);
2328 This method walks the graph using a breadth-first search to find paths
2329 between the root vertex and each vertex on the graph. The edges
2330 directions in each path are considered and they are stored as a
2331 positive edge (left-to-right) or negative edge (right-to-left).
2333 The list of paths is used later to generate a list of constraints.
2335 void QGraphicsAnchorLayoutPrivate::findPaths(Orientation orientation)
2337 QQueue<QPair<AnchorVertex *, AnchorVertex *> > queue;
2339 QSet<AnchorData *> visited;
2341 AnchorVertex *root = layoutFirstVertex[orientation];
2343 graphPaths[orientation].insert(root, GraphPath());
2345 foreach (AnchorVertex *v, graph[orientation].adjacentVertices(root)) {
2346 queue.enqueue(qMakePair(root, v));
2349 while(!queue.isEmpty()) {
2350 QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
2351 AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
2353 if (visited.contains(edge))
2356 visited.insert(edge);
2357 GraphPath current = graphPaths[orientation].value(pair.first);
2359 if (edge->from == pair.first)
2360 current.positives.insert(edge);
2362 current.negatives.insert(edge);
2364 graphPaths[orientation].insert(pair.second, current);
2366 foreach (AnchorVertex *v,
2367 graph[orientation].adjacentVertices(pair.second)) {
2368 queue.enqueue(qMakePair(pair.second, v));
2372 // We will walk through every reachable items (non-float) store them in a temporary set.
2373 // We them create a set of all items and subtract the non-floating items from the set in
2374 // order to get the floating items. The floating items is then stored in m_floatItems
2375 identifyFloatItems(visited, orientation);
2381 Each vertex on the graph that has more than one path to it
2382 represents a contra int to the sizes of the items in these paths.
2384 This method walks the list of paths to each vertex, generate
2385 the constraints and store them in a list so they can be used later
2386 by the Simplex solver.
2388 void QGraphicsAnchorLayoutPrivate::constraintsFromPaths(Orientation orientation)
2390 foreach (AnchorVertex *vertex, graphPaths[orientation].uniqueKeys())
2392 int valueCount = graphPaths[orientation].count(vertex);
2393 if (valueCount == 1)
2396 QList<GraphPath> pathsToVertex = graphPaths[orientation].values(vertex);
2397 for (int i = 1; i < valueCount; ++i) {
2398 constraints[orientation] += \
2399 pathsToVertex[0].constraint(pathsToVertex.at(i));
2407 void QGraphicsAnchorLayoutPrivate::updateAnchorSizes(Orientation orientation)
2409 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
2410 const QList<QPair<AnchorVertex *, AnchorVertex *> > &vertices = g.connections();
2412 for (int i = 0; i < vertices.count(); ++i) {
2413 AnchorData *ad = g.edgeData(vertices.at(i).first, vertices.at(i).second);
2414 ad->updateChildrenSizes();
2421 Create LP constraints for each anchor based on its minimum and maximum
2422 sizes, as specified in its size hints
2424 QList<QSimplexConstraint *> QGraphicsAnchorLayoutPrivate::constraintsFromSizeHints(
2425 const QList<AnchorData *> &anchors)
2427 if (anchors.isEmpty())
2428 return QList<QSimplexConstraint *>();
2430 // Look for the layout edge. That can be either the first half in case the
2431 // layout is split in two, or the whole layout anchor.
2432 Orientation orient = Orientation(anchors.first()->orientation);
2433 AnchorData *layoutEdge = 0;
2434 if (layoutCentralVertex[orient]) {
2435 layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutCentralVertex[orient]);
2437 layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutLastVertex[orient]);
2440 // If maxSize is less then "infinite", that means there are other anchors
2441 // grouped together with this one. We can't ignore its maximum value so we
2442 // set back the variable to NULL to prevent the continue condition from being
2443 // satisfied in the loop below.
2444 const qreal expectedMax = layoutCentralVertex[orient] ? QWIDGETSIZE_MAX / 2 : QWIDGETSIZE_MAX;
2446 if (layoutEdge->from == layoutFirstVertex[orient]) {
2447 actualMax = layoutEdge->maxSize;
2449 actualMax = -layoutEdge->minSize;
2451 if (actualMax != expectedMax) {
2455 // For each variable, create constraints based on size hints
2456 QList<QSimplexConstraint *> anchorConstraints;
2457 bool unboundedProblem = true;
2458 for (int i = 0; i < anchors.size(); ++i) {
2459 AnchorData *ad = anchors.at(i);
2461 // Anchors that have their size directly linked to another one don't need constraints
2462 // For exammple, the second half of an item has exactly the same size as the first half
2463 // thus constraining the latter is enough.
2464 if (ad->dependency == AnchorData::Slave)
2467 // To use negative variables inside simplex, we shift them so the minimum negative value is
2468 // mapped to zero before solving. To make sure that it works, we need to guarantee that the
2469 // variables are all inside a certain boundary.
2470 qreal boundedMin = qBound(-g_offset, ad->minSize, g_offset);
2471 qreal boundedMax = qBound(-g_offset, ad->maxSize, g_offset);
2473 if ((boundedMin == boundedMax) || qFuzzyCompare(boundedMin, boundedMax)) {
2474 QSimplexConstraint *c = new QSimplexConstraint;
2475 c->variables.insert(ad, 1.0);
2476 c->constant = boundedMin;
2477 c->ratio = QSimplexConstraint::Equal;
2478 anchorConstraints += c;
2479 unboundedProblem = false;
2481 QSimplexConstraint *c = new QSimplexConstraint;
2482 c->variables.insert(ad, 1.0);
2483 c->constant = boundedMin;
2484 c->ratio = QSimplexConstraint::MoreOrEqual;
2485 anchorConstraints += c;
2487 // We avoid adding restrictions to the layout internal anchors. That's
2488 // to prevent unnecessary fair distribution from happening due to this
2489 // artificial restriction.
2490 if (ad == layoutEdge)
2493 c = new QSimplexConstraint;
2494 c->variables.insert(ad, 1.0);
2495 c->constant = boundedMax;
2496 c->ratio = QSimplexConstraint::LessOrEqual;
2497 anchorConstraints += c;
2498 unboundedProblem = false;
2502 // If no upper boundary restriction was added, add one to avoid unbounded problem
2503 if (unboundedProblem) {
2504 QSimplexConstraint *c = new QSimplexConstraint;
2505 c->variables.insert(layoutEdge, 1.0);
2506 // The maximum size that the layout can take
2507 c->constant = g_offset;
2508 c->ratio = QSimplexConstraint::LessOrEqual;
2509 anchorConstraints += c;
2512 return anchorConstraints;
2518 QList< QList<QSimplexConstraint *> >
2519 QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
2521 Q_ASSERT(layoutFirstVertex[orientation] && layoutLastVertex[orientation]);
2523 AnchorData *edgeL1 = 0;
2524 AnchorData *edgeL2 = 0;
2526 // The layout may have a single anchor between Left and Right or two half anchors
2527 // passing through the center
2528 if (layoutCentralVertex[orientation]) {
2529 edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutCentralVertex[orientation]);
2530 edgeL2 = graph[orientation].edgeData(layoutCentralVertex[orientation], layoutLastVertex[orientation]);
2532 edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutLastVertex[orientation]);
2535 QLinkedList<QSimplexConstraint *> remainingConstraints;
2536 for (int i = 0; i < constraints[orientation].count(); ++i) {
2537 remainingConstraints += constraints[orientation].at(i);
2539 for (int i = 0; i < itemCenterConstraints[orientation].count(); ++i) {
2540 remainingConstraints += itemCenterConstraints[orientation].at(i);
2543 QList<QSimplexConstraint *> trunkConstraints;
2544 QSet<QSimplexVariable *> trunkVariables;
2546 trunkVariables += edgeL1;
2548 trunkVariables += edgeL2;
2554 QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
2555 while (it != remainingConstraints.end()) {
2556 QSimplexConstraint *c = *it;
2559 // Check if this constraint have some overlap with current
2560 // trunk variables...
2561 foreach (QSimplexVariable *ad, trunkVariables) {
2562 if (c->variables.contains(ad)) {
2568 // If so, we add it to trunk, and erase it from the
2569 // remaining constraints.
2571 trunkConstraints += c;
2572 trunkVariables += QSet<QSimplexVariable *>::fromList(c->variables.keys());
2573 it = remainingConstraints.erase(it);
2576 // Note that we don't erase the constraint if it's not
2577 // a match, since in a next iteration of a do-while we
2578 // can pass on it again and it will be a match.
2580 // For example: if trunk share a variable with
2581 // remainingConstraints[1] and it shares with
2582 // remainingConstraints[0], we need a second iteration
2583 // of the do-while loop to match both.
2589 QList< QList<QSimplexConstraint *> > result;
2590 result += trunkConstraints;
2592 if (!remainingConstraints.isEmpty()) {
2593 QList<QSimplexConstraint *> nonTrunkConstraints;
2594 QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
2595 while (it != remainingConstraints.end()) {
2596 nonTrunkConstraints += *it;
2599 result += nonTrunkConstraints;
2608 Use all visited Anchors on findPaths() so we can identify non-float Items.
2610 void QGraphicsAnchorLayoutPrivate::identifyFloatItems(const QSet<AnchorData *> &visited, Orientation orientation)
2612 QSet<QGraphicsLayoutItem *> nonFloating;
2614 foreach (const AnchorData *ad, visited)
2615 identifyNonFloatItems_helper(ad, &nonFloating);
2617 QSet<QGraphicsLayoutItem *> allItems;
2618 foreach (QGraphicsLayoutItem *item, items)
2619 allItems.insert(item);
2620 m_floatItems[orientation] = allItems - nonFloating;
2627 Given an anchor, if it is an internal anchor and Normal we must mark it's item as non-float.
2628 If the anchor is Sequential or Parallel, we must iterate on its children recursively until we reach
2629 internal anchors (items).
2631 void QGraphicsAnchorLayoutPrivate::identifyNonFloatItems_helper(const AnchorData *ad, QSet<QGraphicsLayoutItem *> *nonFloatingItemsIdentifiedSoFar)
2633 Q_Q(QGraphicsAnchorLayout);
2636 case AnchorData::Normal:
2637 if (ad->item && ad->item != q)
2638 nonFloatingItemsIdentifiedSoFar->insert(ad->item);
2640 case AnchorData::Sequential:
2641 foreach (const AnchorData *d, static_cast<const SequentialAnchorData *>(ad)->m_edges)
2642 identifyNonFloatItems_helper(d, nonFloatingItemsIdentifiedSoFar);
2644 case AnchorData::Parallel:
2645 identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->firstEdge, nonFloatingItemsIdentifiedSoFar);
2646 identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->secondEdge, nonFloatingItemsIdentifiedSoFar);
2654 Use the current vertices distance to calculate and set the geometry of
2657 void QGraphicsAnchorLayoutPrivate::setItemsGeometries(const QRectF &geom)
2659 Q_Q(QGraphicsAnchorLayout);
2660 AnchorVertex *firstH, *secondH, *firstV, *secondV;
2666 q->getContentsMargins(&left, &top, &right, 0);
2667 const Qt::LayoutDirection visualDir = visualDirection();
2668 if (visualDir == Qt::RightToLeft)
2671 left += geom.left();
2673 right = geom.right() - right;
2675 foreach (QGraphicsLayoutItem *item, items) {
2677 QSizeF itemPreferredSize = item->effectiveSizeHint(Qt::PreferredSize);
2678 if (m_floatItems[Horizontal].contains(item)) {
2680 newGeom.setRight(itemPreferredSize.width());
2682 firstH = internalVertex(item, Qt::AnchorLeft);
2683 secondH = internalVertex(item, Qt::AnchorRight);
2685 if (visualDir == Qt::LeftToRight) {
2686 newGeom.setLeft(left + firstH->distance);
2687 newGeom.setRight(left + secondH->distance);
2689 newGeom.setLeft(right - secondH->distance);
2690 newGeom.setRight(right - firstH->distance);
2694 if (m_floatItems[Vertical].contains(item)) {
2696 newGeom.setBottom(itemPreferredSize.height());
2698 firstV = internalVertex(item, Qt::AnchorTop);
2699 secondV = internalVertex(item, Qt::AnchorBottom);
2701 newGeom.setTop(top + firstV->distance);
2702 newGeom.setBottom(top + secondV->distance);
2705 item->setGeometry(newGeom);
2712 Calculate the position of each vertex based on the paths to each of
2713 them as well as the current edges sizes.
2715 void QGraphicsAnchorLayoutPrivate::calculateVertexPositions(
2716 QGraphicsAnchorLayoutPrivate::Orientation orientation)
2718 QQueue<QPair<AnchorVertex *, AnchorVertex *> > queue;
2719 QSet<AnchorVertex *> visited;
2722 AnchorVertex *root = layoutFirstVertex[orientation];
2725 visited.insert(root);
2727 // Add initial edges to the queue
2728 foreach (AnchorVertex *v, graph[orientation].adjacentVertices(root)) {
2729 queue.enqueue(qMakePair(root, v));
2732 // Do initial calculation required by "interpolateEdge()"
2733 setupEdgesInterpolation(orientation);
2735 // Traverse the graph and calculate vertex positions
2736 while (!queue.isEmpty()) {
2737 QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
2738 AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
2740 if (visited.contains(pair.second))
2743 visited.insert(pair.second);
2744 interpolateEdge(pair.first, edge);
2746 QList<AnchorVertex *> adjacents = graph[orientation].adjacentVertices(pair.second);
2747 for (int i = 0; i < adjacents.count(); ++i) {
2748 if (!visited.contains(adjacents.at(i)))
2749 queue.enqueue(qMakePair(pair.second, adjacents.at(i)));
2757 Calculate interpolation parameters based on current Layout Size.
2758 Must be called once before calling "interpolateEdgeSize()" for
2761 void QGraphicsAnchorLayoutPrivate::setupEdgesInterpolation(
2762 Orientation orientation)
2764 Q_Q(QGraphicsAnchorLayout);
2767 current = (orientation == Horizontal) ? q->contentsRect().width() : q->contentsRect().height();
2769 QPair<Interval, qreal> result;
2770 result = getFactor(current,
2771 sizeHints[orientation][Qt::MinimumSize],
2772 sizeHints[orientation][Qt::PreferredSize],
2773 sizeHints[orientation][Qt::PreferredSize],
2774 sizeHints[orientation][Qt::PreferredSize],
2775 sizeHints[orientation][Qt::MaximumSize]);
2777 interpolationInterval[orientation] = result.first;
2778 interpolationProgress[orientation] = result.second;
2784 Calculate the current Edge size based on the current Layout size and the
2785 size the edge is supposed to have when the layout is at its:
2791 These three key values are calculated in advance using linear
2792 programming (more expensive) or the simplification algorithm, then
2793 subsequential resizes of the parent layout require a simple
2796 void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base, AnchorData *edge)
2798 const Orientation orientation = Orientation(edge->orientation);
2799 const QPair<Interval, qreal> factor(interpolationInterval[orientation],
2800 interpolationProgress[orientation]);
2802 qreal edgeDistance = interpolate(factor, edge->sizeAtMinimum, edge->sizeAtPreferred,
2803 edge->sizeAtPreferred, edge->sizeAtPreferred,
2804 edge->sizeAtMaximum);
2806 Q_ASSERT(edge->from == base || edge->to == base);
2808 // Calculate the distance for the vertex opposite to the base
2809 if (edge->from == base) {
2810 edge->to->distance = base->distance + edgeDistance;
2812 edge->from->distance = base->distance - edgeDistance;
2816 bool QGraphicsAnchorLayoutPrivate::solveMinMax(const QList<QSimplexConstraint *> &constraints,
2817 GraphPath path, qreal *min, qreal *max)
2820 bool feasible = simplex.setConstraints(constraints);
2822 // Obtain the objective constraint
2823 QSimplexConstraint objective;
2824 QSet<AnchorData *>::const_iterator iter;
2825 for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter)
2826 objective.variables.insert(*iter, 1.0);
2828 for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter)
2829 objective.variables.insert(*iter, -1.0);
2831 const qreal objectiveOffset = (path.positives.count() - path.negatives.count()) * g_offset;
2832 simplex.setObjective(&objective);
2834 // Calculate minimum values
2835 *min = simplex.solveMin() - objectiveOffset;
2837 // Save sizeAtMinimum results
2838 QList<AnchorData *> variables = getVariables(constraints);
2839 for (int i = 0; i < variables.size(); ++i) {
2840 AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
2841 ad->sizeAtMinimum = ad->result - g_offset;
2844 // Calculate maximum values
2845 *max = simplex.solveMax() - objectiveOffset;
2847 // Save sizeAtMaximum results
2848 for (int i = 0; i < variables.size(); ++i) {
2849 AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
2850 ad->sizeAtMaximum = ad->result - g_offset;
2856 enum slackType { Grower = -1, Shrinker = 1 };
2857 static QPair<QSimplexVariable *, QSimplexConstraint *> createSlack(QSimplexConstraint *sizeConstraint,
2858 qreal interval, slackType type)
2860 QSimplexVariable *slack = new QSimplexVariable;
2861 sizeConstraint->variables.insert(slack, type);
2863 QSimplexConstraint *limit = new QSimplexConstraint;
2864 limit->variables.insert(slack, 1.0);
2865 limit->ratio = QSimplexConstraint::LessOrEqual;
2866 limit->constant = interval;
2868 return qMakePair(slack, limit);
2871 bool QGraphicsAnchorLayoutPrivate::solvePreferred(const QList<QSimplexConstraint *> &constraints,
2872 const QList<AnchorData *> &variables)
2874 QList<QSimplexConstraint *> preferredConstraints;
2875 QList<QSimplexVariable *> preferredVariables;
2876 QSimplexConstraint objective;
2878 // Fill the objective coefficients for this variable. In the
2879 // end the objective function will be
2881 // z = n * (A_shrinker_hard + A_grower_hard + B_shrinker_hard + B_grower_hard + ...) +
2882 // (A_shrinker_soft + A_grower_soft + B_shrinker_soft + B_grower_soft + ...)
2884 // where n is the number of variables that have
2885 // slacks. Note that here we use the number of variables
2886 // as coefficient, this is to mark the "shrinker slack
2887 // variable" less likely to get value than the "grower
2890 // This will fill the values for the structural constraints
2891 // and we now fill the values for the slack constraints (one per variable),
2892 // which have this form (the constant A_pref was set when creating the slacks):
2894 // A + A_shrinker_hard + A_shrinker_soft - A_grower_hard - A_grower_soft = A_pref
2896 for (int i = 0; i < variables.size(); ++i) {
2897 AnchorData *ad = variables.at(i);
2899 // The layout original structure anchors are not relevant in preferred size calculation
2900 if (ad->isLayoutAnchor)
2903 // By default, all variables are equal to their preferred size. If they have room to
2904 // grow or shrink, such flexibility will be added by the additional variables below.
2905 QSimplexConstraint *sizeConstraint = new QSimplexConstraint;
2906 preferredConstraints += sizeConstraint;
2907 sizeConstraint->variables.insert(ad, 1.0);
2908 sizeConstraint->constant = ad->prefSize + g_offset;
2910 // Can easily shrink
2911 QPair<QSimplexVariable *, QSimplexConstraint *> slack;
2912 const qreal softShrinkInterval = ad->prefSize - ad->minPrefSize;
2913 if (softShrinkInterval) {
2914 slack = createSlack(sizeConstraint, softShrinkInterval, Shrinker);
2915 preferredVariables += slack.first;
2916 preferredConstraints += slack.second;
2918 // Add to objective with ratio == 1 (soft)
2919 objective.variables.insert(slack.first, 1.0);
2923 const qreal softGrowInterval = ad->maxPrefSize - ad->prefSize;
2924 if (softGrowInterval) {
2925 slack = createSlack(sizeConstraint, softGrowInterval, Grower);
2926 preferredVariables += slack.first;
2927 preferredConstraints += slack.second;
2929 // Add to objective with ratio == 1 (soft)
2930 objective.variables.insert(slack.first, 1.0);
2933 // Can shrink if really necessary
2934 const qreal hardShrinkInterval = ad->minPrefSize - ad->minSize;
2935 if (hardShrinkInterval) {
2936 slack = createSlack(sizeConstraint, hardShrinkInterval, Shrinker);
2937 preferredVariables += slack.first;
2938 preferredConstraints += slack.second;
2940 // Add to objective with ratio == N (hard)
2941 objective.variables.insert(slack.first, variables.size());
2944 // Can grow if really necessary
2945 const qreal hardGrowInterval = ad->maxSize - ad->maxPrefSize;
2946 if (hardGrowInterval) {
2947 slack = createSlack(sizeConstraint, hardGrowInterval, Grower);
2948 preferredVariables += slack.first;
2949 preferredConstraints += slack.second;
2951 // Add to objective with ratio == N (hard)
2952 objective.variables.insert(slack.first, variables.size());
2956 QSimplex *simplex = new QSimplex;
2957 bool feasible = simplex->setConstraints(constraints + preferredConstraints);
2959 simplex->setObjective(&objective);
2961 // Calculate minimum values
2962 simplex->solveMin();
2964 // Save sizeAtPreferred results
2965 for (int i = 0; i < variables.size(); ++i) {
2966 AnchorData *ad = variables.at(i);
2967 ad->sizeAtPreferred = ad->result - g_offset;
2970 // Make sure we delete the simplex solver -before- we delete the
2971 // constraints used by it.
2974 // Delete constraints and variables we created.
2975 qDeleteAll(preferredConstraints);
2976 qDeleteAll(preferredVariables);
2983 Returns true if there are no arrangement that satisfies all constraints.
2984 Otherwise returns false.
2988 bool QGraphicsAnchorLayoutPrivate::hasConflicts() const
2990 QGraphicsAnchorLayoutPrivate *that = const_cast<QGraphicsAnchorLayoutPrivate*>(this);
2991 that->calculateGraphs();
2993 bool floatConflict = !m_floatItems[0].isEmpty() || !m_floatItems[1].isEmpty();
2995 return graphHasConflicts[0] || graphHasConflicts[1] || floatConflict;
2999 void QGraphicsAnchorLayoutPrivate::dumpGraph(const QString &name)
3001 QFile file(QString::fromAscii("anchorlayout.%1.dot").arg(name));
3002 if (!file.open(QIODevice::WriteOnly | QIODevice::Text | QIODevice::Truncate))
3003 qWarning("Could not write to %s", file.fileName().toLocal8Bit().constData());
3005 QString str = QString::fromAscii("digraph anchorlayout {\nnode [shape=\"rect\"]\n%1}");
3006 QString dotContents = graph[0].serializeToDot();
3007 dotContents += graph[1].serializeToDot();
3008 file.write(str.arg(dotContents).toLocal8Bit());
3015 #endif //QT_NO_GRAPHICSVIEW