1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtWidgets module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qgraphicsanchorlayout_p.h"
41
42#include <QtWidgets/qwidget.h>
43#include <QtWidgets/qapplication.h>
44#include <QtCore/qstack.h>
45
46#ifdef QT_DEBUG
47#include <QtCore/qfile.h>
48#endif
49
50#include <numeric>
51
52QT_BEGIN_NAMESPACE
53
54// To ensure that all variables inside the simplex solver are non-negative,
55// we limit the size of anchors in the interval [-limit, limit]. Then before
56// sending them to the simplex solver we add "limit" as an offset, so that
57// they are actually calculated in the interval [0, 2 * limit]
58// To avoid numerical errors in platforms where we use single precision,
59// we use a tighter limit for the variables range.
60const qreal g_offset = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32;
61
62QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version)
63 : QObjectPrivate(version), layoutPrivate(nullptr), data(nullptr),
64 sizePolicy(QSizePolicy::Fixed), preferredSize(0),
65 hasSize(true)
66{
67}
68
69QGraphicsAnchorPrivate::~QGraphicsAnchorPrivate()
70{
71 if (data) {
72 // The QGraphicsAnchor was already deleted at this moment. We must clean
73 // the dangling pointer to avoid double deletion in the AnchorData dtor.
74 data->graphicsAnchor = nullptr;
75
76 layoutPrivate->removeAnchor(data->from, data->to);
77 }
78}
79
80void QGraphicsAnchorPrivate::setSizePolicy(QSizePolicy::Policy policy)
81{
82 if (sizePolicy != policy) {
83 sizePolicy = policy;
84 layoutPrivate->q_func()->invalidate();
85 }
86}
87
88void QGraphicsAnchorPrivate::setSpacing(qreal value)
89{
90 if (!data) {
91 qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
92 return;
93 }
94
95 if (hasSize && (preferredSize == value))
96 return;
97
98 // The anchor has an user-defined size
99 hasSize = true;
100 preferredSize = value;
101
102 layoutPrivate->q_func()->invalidate();
103}
104
105void QGraphicsAnchorPrivate::unsetSpacing()
106{
107 if (!data) {
108 qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
109 return;
110 }
111
112 // Return to standard direction
113 hasSize = false;
114
115 layoutPrivate->q_func()->invalidate();
116}
117
118qreal QGraphicsAnchorPrivate::spacing() const
119{
120 if (!data) {
121 qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
122 return 0;
123 }
124
125 return preferredSize;
126}
127
128
129static void applySizePolicy(QSizePolicy::Policy policy,
130 qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint,
131 qreal *minSize, qreal *prefSize,
132 qreal *maxSize)
133{
134 // minSize, prefSize and maxSize are initialized
135 // with item's preferred Size: this is QSizePolicy::Fixed.
136 //
137 // Then we check each flag to find the resultant QSizePolicy,
138 // according to the following table:
139 //
140 // constant value
141 // QSizePolicy::Fixed 0
142 // QSizePolicy::Minimum GrowFlag
143 // QSizePolicy::Maximum ShrinkFlag
144 // QSizePolicy::Preferred GrowFlag | ShrinkFlag
145 // QSizePolicy::Ignored GrowFlag | ShrinkFlag | IgnoreFlag
146
147 if (policy & QSizePolicy::ShrinkFlag)
148 *minSize = minSizeHint;
149 else
150 *minSize = prefSizeHint;
151
152 if (policy & QSizePolicy::GrowFlag)
153 *maxSize = maxSizeHint;
154 else
155 *maxSize = prefSizeHint;
156
157 // Note that these two initializations are affected by the previous flags
158 if (policy & QSizePolicy::IgnoreFlag)
159 *prefSize = *minSize;
160 else
161 *prefSize = prefSizeHint;
162}
163
164AnchorData::~AnchorData()
165{
166 if (graphicsAnchor) {
167 // Remove reference to ourself to avoid double removal in
168 // QGraphicsAnchorPrivate dtor.
169 QGraphicsAnchorPrivate::get(graphicsAnchor)->data = nullptr;
170
171 delete graphicsAnchor;
172 }
173}
174
175
176void AnchorData::refreshSizeHints(const QLayoutStyleInfo *styleInfo)
177{
178 QSizePolicy::Policy policy;
179 qreal minSizeHint;
180 qreal prefSizeHint;
181 qreal maxSizeHint;
182
183 if (item) {
184 // It is an internal anchor, fetch size information from the item
185 if (isLayoutAnchor) {
186 minSize = 0;
187 prefSize = 0;
188 maxSize = QWIDGETSIZE_MAX;
189 if (isCenterAnchor)
190 maxSize /= 2;
191
192 minPrefSize = prefSize;
193 maxPrefSize = maxSize;
194 return;
195 } else {
196 if (!isVertical) {
197 policy = item->sizePolicy().horizontalPolicy();
198 minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).width();
199 prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).width();
200 maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).width();
201 } else {
202 policy = item->sizePolicy().verticalPolicy();
203 minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).height();
204 prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).height();
205 maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).height();
206 }
207
208 if (isCenterAnchor) {
209 minSizeHint /= 2;
210 prefSizeHint /= 2;
211 maxSizeHint /= 2;
212 }
213 }
214 } else {
215 // It is a user-created anchor, fetch size information from the associated QGraphicsAnchor
216 Q_ASSERT(graphicsAnchor);
217 QGraphicsAnchorPrivate *anchorPrivate = QGraphicsAnchorPrivate::get(graphicsAnchor);
218
219 // Policy, min and max sizes are straightforward
220 policy = anchorPrivate->sizePolicy;
221 minSizeHint = 0;
222 maxSizeHint = QWIDGETSIZE_MAX;
223
224 // Preferred Size
225 if (anchorPrivate->hasSize) {
226 // Anchor has user-defined size
227 prefSizeHint = anchorPrivate->preferredSize;
228 } else {
229 // Fetch size information from style
230 const Qt::Orientation orient = QGraphicsAnchorLayoutPrivate::edgeOrientation(from->m_edge);
231 qreal s = styleInfo->defaultSpacing(orient);
232 if (s < 0) {
233 QSizePolicy::ControlType controlTypeFrom = from->m_item->sizePolicy().controlType();
234 QSizePolicy::ControlType controlTypeTo = to->m_item->sizePolicy().controlType();
235 s = styleInfo->perItemSpacing(controlTypeFrom, controlTypeTo, orient);
236
237 // ### Currently we do not support negative anchors inside the graph.
238 // To avoid those being created by a negative style spacing, we must
239 // make this test.
240 if (s < 0)
241 s = 0;
242 }
243 prefSizeHint = s;
244 }
245 }
246
247 // Fill minSize, prefSize and maxSize based on policy and sizeHints
248 applySizePolicy(policy, minSizeHint, prefSizeHint, maxSizeHint,
249 &minSize, &prefSize, &maxSize);
250
251 minPrefSize = prefSize;
252 maxPrefSize = maxSize;
253
254 // Set the anchor effective sizes to preferred.
255 //
256 // Note: The idea here is that all items should remain at their
257 // preferred size unless where that's impossible. In cases where
258 // the item is subject to restrictions (anchored to the layout
259 // edges, for instance), the simplex solver will be run to
260 // recalculate and override the values we set here.
261 sizeAtMinimum = prefSize;
262 sizeAtPreferred = prefSize;
263 sizeAtMaximum = prefSize;
264}
265
266void ParallelAnchorData::updateChildrenSizes()
267{
268 firstEdge->sizeAtMinimum = sizeAtMinimum;
269 firstEdge->sizeAtPreferred = sizeAtPreferred;
270 firstEdge->sizeAtMaximum = sizeAtMaximum;
271
272 if (secondForward()) {
273 secondEdge->sizeAtMinimum = sizeAtMinimum;
274 secondEdge->sizeAtPreferred = sizeAtPreferred;
275 secondEdge->sizeAtMaximum = sizeAtMaximum;
276 } else {
277 secondEdge->sizeAtMinimum = -sizeAtMinimum;
278 secondEdge->sizeAtPreferred = -sizeAtPreferred;
279 secondEdge->sizeAtMaximum = -sizeAtMaximum;
280 }
281
282 firstEdge->updateChildrenSizes();
283 secondEdge->updateChildrenSizes();
284}
285
286/*
287 \internal
288
289 Initialize the parallel anchor size hints using the sizeHint information from
290 its children.
291
292 Note that parallel groups can lead to unfeasibility, so during calculation, we can
293 find out one unfeasibility. Because of that this method return boolean. This can't
294 happen in sequential, so there the method is void.
295 */
296bool ParallelAnchorData::calculateSizeHints()
297{
298 // Normalize second child sizes.
299 // A negative anchor of sizes min, minPref, pref, maxPref and max, is equivalent
300 // to a forward anchor of sizes -max, -maxPref, -pref, -minPref, -min
301 qreal secondMin;
302 qreal secondMinPref;
303 qreal secondPref;
304 qreal secondMaxPref;
305 qreal secondMax;
306
307 if (secondForward()) {
308 secondMin = secondEdge->minSize;
309 secondMinPref = secondEdge->minPrefSize;
310 secondPref = secondEdge->prefSize;
311 secondMaxPref = secondEdge->maxPrefSize;
312 secondMax = secondEdge->maxSize;
313 } else {
314 secondMin = -secondEdge->maxSize;
315 secondMinPref = -secondEdge->maxPrefSize;
316 secondPref = -secondEdge->prefSize;
317 secondMaxPref = -secondEdge->minPrefSize;
318 secondMax = -secondEdge->minSize;
319 }
320
321 minSize = qMax(firstEdge->minSize, secondMin);
322 maxSize = qMin(firstEdge->maxSize, secondMax);
323
324 // This condition means that the maximum size of one anchor being simplified is smaller than
325 // the minimum size of the other anchor. The consequence is that there won't be a valid size
326 // for this parallel setup.
327 if (minSize > maxSize) {
328 return false;
329 }
330
331 // Preferred size calculation
332 // The calculation of preferred size is done as follows:
333 //
334 // 1) Check whether one of the child anchors is the layout structural anchor
335 // If so, we can simply copy the preferred information from the other child,
336 // after bounding it to our minimum and maximum sizes.
337 // If not, then we proceed with the actual calculations.
338 //
339 // 2) The whole algorithm for preferred size calculation is based on the fact
340 // that, if a given anchor cannot remain at its preferred size, it'd rather
341 // grow than shrink.
342 //
343 // What happens though is that while this affirmative is true for simple
344 // anchors, it may not be true for sequential anchors that have one or more
345 // reversed anchors inside it. That happens because when a sequential anchor
346 // grows, any reversed anchors inside it may be required to shrink, something
347 // we try to avoid, as said above.
348 //
349 // To overcome this, besides their actual preferred size "prefSize", each anchor
350 // exports what we call "minPrefSize" and "maxPrefSize". These two values define
351 // a surrounding interval where, if required to move, the anchor would rather
352 // remain inside.
353 //
354 // For standard anchors, this area simply represents the region between
355 // prefSize and maxSize, which makes sense since our first affirmation.
356 // For composed anchors, these values are calculated as to reduce the global
357 // "damage", that is, to reduce the total deviation and the total amount of
358 // anchors that had to shrink.
359
360 if (firstEdge->isLayoutAnchor) {
361 prefSize = qBound(minSize, secondPref, maxSize);
362 minPrefSize = qBound(minSize, secondMinPref, maxSize);
363 maxPrefSize = qBound(minSize, secondMaxPref, maxSize);
364 } else if (secondEdge->isLayoutAnchor) {
365 prefSize = qBound(minSize, firstEdge->prefSize, maxSize);
366 minPrefSize = qBound(minSize, firstEdge->minPrefSize, maxSize);
367 maxPrefSize = qBound(minSize, firstEdge->maxPrefSize, maxSize);
368 } else {
369 // Calculate the intersection between the "preferred" regions of each child
370 const qreal lowerBoundary =
371 qBound(minSize, qMax(firstEdge->minPrefSize, secondMinPref), maxSize);
372 const qreal upperBoundary =
373 qBound(minSize, qMin(firstEdge->maxPrefSize, secondMaxPref), maxSize);
374 const qreal prefMean =
375 qBound(minSize, (firstEdge->prefSize + secondPref) / 2, maxSize);
376
377 if (lowerBoundary < upperBoundary) {
378 // If there is an intersection between the two regions, this intersection
379 // will be used as the preferred region of the parallel anchor itself.
380 // The preferred size will be the bounded average between the two preferred
381 // sizes.
382 prefSize = qBound(lowerBoundary, prefMean, upperBoundary);
383 minPrefSize = lowerBoundary;
384 maxPrefSize = upperBoundary;
385 } else {
386 // If there is no intersection, we have to attribute "damage" to at least
387 // one of the children. The minimum total damage is achieved in points
388 // inside the region that extends from (1) the upper boundary of the lower
389 // region to (2) the lower boundary of the upper region.
390 // Then, we expose this region as _our_ preferred region and once again,
391 // use the bounded average as our preferred size.
392 prefSize = qBound(upperBoundary, prefMean, lowerBoundary);
393 minPrefSize = upperBoundary;
394 maxPrefSize = lowerBoundary;
395 }
396 }
397
398 // See comment in AnchorData::refreshSizeHints() about sizeAt* values
399 sizeAtMinimum = prefSize;
400 sizeAtPreferred = prefSize;
401 sizeAtMaximum = prefSize;
402
403 return true;
404}
405
406/*!
407 \internal
408 returns the factor in the interval [-1, 1].
409 -1 is at Minimum
410 0 is at Preferred
411 1 is at Maximum
412*/
413static QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> getFactor(qreal value, qreal min,
414 qreal minPref, qreal pref,
415 qreal maxPref, qreal max)
416{
417 QGraphicsAnchorLayoutPrivate::Interval interval;
418 qreal lower;
419 qreal upper;
420
421 if (value < minPref) {
422 interval = QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred;
423 lower = min;
424 upper = minPref;
425 } else if (value < pref) {
426 interval = QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred;
427 lower = minPref;
428 upper = pref;
429 } else if (value < maxPref) {
430 interval = QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred;
431 lower = pref;
432 upper = maxPref;
433 } else {
434 interval = QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum;
435 lower = maxPref;
436 upper = max;
437 }
438
439 qreal progress;
440 if (upper == lower) {
441 progress = 0;
442 } else {
443 progress = (value - lower) / (upper - lower);
444 }
445
446 return qMakePair(interval, progress);
447}
448
449static qreal interpolate(const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> &factor,
450 qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)
451{
452 qreal lower = 0;
453 qreal upper = 0;
454
455 switch (factor.first) {
456 case QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred:
457 lower = min;
458 upper = minPref;
459 break;
460 case QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred:
461 lower = minPref;
462 upper = pref;
463 break;
464 case QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred:
465 lower = pref;
466 upper = maxPref;
467 break;
468 case QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum:
469 lower = maxPref;
470 upper = max;
471 break;
472 }
473
474 return lower + factor.second * (upper - lower);
475}
476
477void SequentialAnchorData::updateChildrenSizes()
478{
479 // Band here refers if the value is in the Minimum To Preferred
480 // band (the lower band) or the Preferred To Maximum (the upper band).
481
482 const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> minFactor =
483 getFactor(sizeAtMinimum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
484 const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> prefFactor =
485 getFactor(sizeAtPreferred, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
486 const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> maxFactor =
487 getFactor(sizeAtMaximum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
488
489 // XXX This is not safe if Vertex simplification takes place after the sequential
490 // anchor is created. In that case, "prev" will be a group-vertex, different from
491 // "from" or "to", that _contains_ one of them.
492 AnchorVertex *prev = from;
493
494 for (int i = 0; i < m_edges.count(); ++i) {
495 AnchorData *e = m_edges.at(i);
496
497 const bool edgeIsForward = (e->from == prev);
498 if (edgeIsForward) {
499 e->sizeAtMinimum = interpolate(minFactor, e->minSize, e->minPrefSize,
500 e->prefSize, e->maxPrefSize, e->maxSize);
501 e->sizeAtPreferred = interpolate(prefFactor, e->minSize, e->minPrefSize,
502 e->prefSize, e->maxPrefSize, e->maxSize);
503 e->sizeAtMaximum = interpolate(maxFactor, e->minSize, e->minPrefSize,
504 e->prefSize, e->maxPrefSize, e->maxSize);
505 prev = e->to;
506 } else {
507 Q_ASSERT(prev == e->to);
508 e->sizeAtMinimum = interpolate(minFactor, e->maxSize, e->maxPrefSize,
509 e->prefSize, e->minPrefSize, e->minSize);
510 e->sizeAtPreferred = interpolate(prefFactor, e->maxSize, e->maxPrefSize,
511 e->prefSize, e->minPrefSize, e->minSize);
512 e->sizeAtMaximum = interpolate(maxFactor, e->maxSize, e->maxPrefSize,
513 e->prefSize, e->minPrefSize, e->minSize);
514 prev = e->from;
515 }
516
517 e->updateChildrenSizes();
518 }
519}
520
521void SequentialAnchorData::calculateSizeHints()
522{
523 minSize = 0;
524 prefSize = 0;
525 maxSize = 0;
526 minPrefSize = 0;
527 maxPrefSize = 0;
528
529 AnchorVertex *prev = from;
530
531 for (int i = 0; i < m_edges.count(); ++i) {
532 AnchorData *edge = m_edges.at(i);
533
534 const bool edgeIsForward = (edge->from == prev);
535 if (edgeIsForward) {
536 minSize += edge->minSize;
537 prefSize += edge->prefSize;
538 maxSize += edge->maxSize;
539 minPrefSize += edge->minPrefSize;
540 maxPrefSize += edge->maxPrefSize;
541 prev = edge->to;
542 } else {
543 Q_ASSERT(prev == edge->to);
544 minSize -= edge->maxSize;
545 prefSize -= edge->prefSize;
546 maxSize -= edge->minSize;
547 minPrefSize -= edge->maxPrefSize;
548 maxPrefSize -= edge->minPrefSize;
549 prev = edge->from;
550 }
551 }
552
553 // See comment in AnchorData::refreshSizeHints() about sizeAt* values
554 sizeAtMinimum = prefSize;
555 sizeAtPreferred = prefSize;
556 sizeAtMaximum = prefSize;
557}
558
559#ifdef QT_DEBUG
560void AnchorData::dump(int indent) {
561 if (type == Parallel) {
562 qDebug("%*s type: parallel:", indent, "");
563 ParallelAnchorData *p = static_cast<ParallelAnchorData *>(this);
564 p->firstEdge->dump(indent+2);
565 p->secondEdge->dump(indent+2);
566 } else if (type == Sequential) {
567 SequentialAnchorData *s = static_cast<SequentialAnchorData *>(this);
568 int kids = s->m_edges.count();
569 qDebug("%*s type: sequential(%d):", indent, "", kids);
570 for (int i = 0; i < kids; ++i) {
571 s->m_edges.at(i)->dump(indent+2);
572 }
573 } else {
574 qDebug("%*s type: Normal:", indent, "");
575 }
576}
577
578#endif
579
580QSimplexConstraint *GraphPath::constraint(const GraphPath &path) const
581{
582 // Calculate
583 QSet<AnchorData *> cPositives;
584 QSet<AnchorData *> cNegatives;
585 QSet<AnchorData *> intersection;
586
587 cPositives = positives + path.negatives;
588 cNegatives = negatives + path.positives;
589
590 intersection = cPositives & cNegatives;
591
592 cPositives -= intersection;
593 cNegatives -= intersection;
594
595 // Fill
596 QSimplexConstraint *c = new QSimplexConstraint;
597 QSet<AnchorData *>::iterator i;
598 for (i = cPositives.begin(); i != cPositives.end(); ++i)
599 c->variables.insert(*i, 1.0);
600
601 for (i = cNegatives.begin(); i != cNegatives.end(); ++i)
602 c->variables.insert(*i, -1.0);
603
604 return c;
605}
606
607#ifdef QT_DEBUG
608QString GraphPath::toString() const
609{
610 QString string(QLatin1String("Path: "));
611 for (AnchorData *edge : positives)
612 string += QString::fromLatin1(" (+++) %1").arg(edge->toString());
613
614 for (AnchorData *edge : negatives)
615 string += QString::fromLatin1(" (---) %1").arg(edge->toString());
616
617 return string;
618}
619#endif
620
621QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()
622 : calculateGraphCacheDirty(true), styleInfoDirty(true)
623{
624}
625
626Qt::AnchorPoint QGraphicsAnchorLayoutPrivate::oppositeEdge(Qt::AnchorPoint edge)
627{
628 switch (edge) {
629 case Qt::AnchorLeft:
630 edge = Qt::AnchorRight;
631 break;
632 case Qt::AnchorRight:
633 edge = Qt::AnchorLeft;
634 break;
635 case Qt::AnchorTop:
636 edge = Qt::AnchorBottom;
637 break;
638 case Qt::AnchorBottom:
639 edge = Qt::AnchorTop;
640 break;
641 default:
642 break;
643 }
644 return edge;
645}
646
647
648/*!
649 \internal
650
651 Adds \a newAnchor to the graph.
652
653 Returns the newAnchor itself if it could be added without further changes to the graph. If a
654 new parallel anchor had to be created, then returns the new parallel anchor. If a parallel anchor
655 had to be created and it results in an unfeasible setup, \a feasible is set to false, otherwise
656 true.
657
658 Note that in the case a new parallel anchor is created, it might also take over some constraints
659 from its children anchors.
660*/
661AnchorData *QGraphicsAnchorLayoutPrivate::addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible)
662{
663 const Qt::Orientation orientation = newAnchor->isVertical ? Qt::Vertical : Qt::Horizontal;
664 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
665 *feasible = true;
666
667 // If already exists one anchor where newAnchor is supposed to be, we create a parallel
668 // anchor.
669 if (AnchorData *oldAnchor = g.takeEdge(newAnchor->from, newAnchor->to)) {
670 ParallelAnchorData *parallel = new ParallelAnchorData(oldAnchor, newAnchor);
671
672 // The parallel anchor will "replace" its children anchors in
673 // every center constraint that they appear.
674
675 // ### If the dependent (center) anchors had reference(s) to their constraints, we
676 // could avoid traversing all the itemCenterConstraints.
677 QList<QSimplexConstraint *> &constraints = itemCenterConstraints[orientation];
678
679 AnchorData *children[2] = { oldAnchor, newAnchor };
680 QList<QSimplexConstraint *> *childrenConstraints[2] = { &parallel->m_firstConstraints,
681 &parallel->m_secondConstraints };
682
683 for (int i = 0; i < 2; ++i) {
684 AnchorData *child = children[i];
685 QList<QSimplexConstraint *> *childConstraints = childrenConstraints[i];
686
687 // We need to fix the second child constraints if the parallel group will have the
688 // opposite direction of the second child anchor. For the point of view of external
689 // entities, this anchor was reversed. So if at some point we say that the parallel
690 // has a value of 20, this mean that the second child (when reversed) will be
691 // assigned -20.
692 const bool needsReverse = i == 1 && !parallel->secondForward();
693
694 if (!child->isCenterAnchor)
695 continue;
696
697 parallel->isCenterAnchor = true;
698
699 for (int j = 0; j < constraints.count(); ++j) {
700 QSimplexConstraint *c = constraints[j];
701 if (c->variables.contains(child)) {
702 childConstraints->append(c);
703 qreal v = c->variables.take(child);
704 if (needsReverse)
705 v *= -1;
706 c->variables.insert(parallel, v);
707 }
708 }
709 }
710
711 // At this point we can identify that the parallel anchor is not feasible, e.g. one
712 // anchor minimum size is bigger than the other anchor maximum size.
713 *feasible = parallel->calculateSizeHints();
714 newAnchor = parallel;
715 }
716
717 g.createEdge(newAnchor->from, newAnchor->to, newAnchor);
718 return newAnchor;
719}
720
721/*!
722 \internal
723
724 Takes the sequence of vertices described by (\a before, \a vertices, \a after) and removes
725 all anchors connected to the vertices in \a vertices, returning one simplified anchor between
726 \a before and \a after.
727
728 Note that this function doesn't add the created anchor to the graph. This should be done by
729 the caller.
730*/
731static AnchorData *createSequence(Graph<AnchorVertex, AnchorData> *graph, AnchorVertex *before,
732 const QList<AnchorVertex *> &vertices, AnchorVertex *after)
733{
734#if defined(QT_DEBUG) && 0
735 QString strVertices;
736 for (int i = 0; i < vertices.count(); ++i) {
737 strVertices += QString::fromLatin1("%1 - ").arg(vertices.at(i)->toString());
738 }
739 QString strPath = QString::fromLatin1("%1 - %2%3").arg(before->toString(), strVertices, after->toString());
740 qDebug("simplifying [%s] to [%s - %s]", qPrintable(strPath), qPrintable(before->toString()), qPrintable(after->toString()));
741#endif
742
743 AnchorVertex *prev = before;
744 QList<AnchorData *> edges;
745 edges.reserve(vertices.count() + 1);
746
747 const int numVertices = vertices.count();
748 edges.reserve(numVertices + 1);
749 // Take from the graph, the edges that will be simplificated
750 for (int i = 0; i < numVertices; ++i) {
751 AnchorVertex *next = vertices.at(i);
752 AnchorData *ad = graph->takeEdge(prev, next);
753 Q_ASSERT(ad);
754 edges.append(ad);
755 prev = next;
756 }
757
758 // Take the last edge (not covered in the loop above)
759 AnchorData *ad = graph->takeEdge(vertices.last(), after);
760 Q_ASSERT(ad);
761 edges.append(ad);
762
763 // Create sequence
764 SequentialAnchorData *sequence = new SequentialAnchorData(vertices, edges);
765 sequence->from = before;
766 sequence->to = after;
767
768 sequence->calculateSizeHints();
769
770 return sequence;
771}
772
773/*!
774 \internal
775
776 The purpose of this function is to simplify the graph.
777 Simplification serves two purposes:
778 1. Reduce the number of edges in the graph, (thus the number of variables to the equation
779 solver is reduced, and the solver performs better).
780 2. Be able to do distribution of sequences of edges more intelligently (esp. with sequential
781 anchors)
782
783 It is essential that it must be possible to restore simplified anchors back to their "original"
784 form. This is done by restoreSimplifiedAnchor().
785
786 There are two types of simplification that can be done:
787 1. Sequential simplification
788 Sequential simplification means that all sequences of anchors will be merged into one single
789 anchor. Only anhcors that points in the same direction will be merged.
790 2. Parallel simplification
791 If a simplified sequential anchor is about to be inserted between two vertices in the graph
792 and there already exist an anchor between those two vertices, a parallel anchor will be
793 created that serves as a placeholder for the sequential anchor and the anchor that was
794 already between the two vertices.
795
796 The process of simplification can be described as:
797
798 1. Simplify all sequences of anchors into one anchor.
799 If no further simplification was done, go to (3)
800 - If there already exist an anchor where the sequential anchor is supposed to be inserted,
801 take that anchor out of the graph
802 - Then create a parallel anchor that holds the sequential anchor and the anchor just taken
803 out of the graph.
804 2. Go to (1)
805 3. Done
806
807 When creating the parallel anchors, the algorithm might identify unfeasible situations. In this
808 case the simplification process stops and returns \c false. Otherwise returns \c true.
809*/
810bool QGraphicsAnchorLayoutPrivate::simplifyGraph(Qt::Orientation orientation)
811{
812 if (items.isEmpty())
813 return true;
814
815#if defined(QT_DEBUG) && 0
816 qDebug("Simplifying Graph for %s",
817 orientation == Horizontal ? "Horizontal" : "Vertical");
818
819 static int count = 0;
820 if (orientation == Horizontal) {
821 count++;
822 dumpGraph(QString::fromLatin1("%1-full").arg(count));
823 }
824#endif
825
826 // Vertex simplification
827 if (!simplifyVertices(orientation)) {
828 restoreVertices(orientation);
829 return false;
830 }
831
832 // Anchor simplification
833 bool dirty;
834 bool feasible = true;
835 do {
836 dirty = simplifyGraphIteration(orientation, &feasible);
837 } while (dirty && feasible);
838
839 // Note that if we are not feasible, we fallback and make sure that the graph is fully restored
840 if (!feasible) {
841 restoreSimplifiedGraph(orientation);
842 restoreVertices(orientation);
843 return false;
844 }
845
846#if defined(QT_DEBUG) && 0
847 dumpGraph(QString::fromLatin1("%1-simplified-%2").arg(count).arg(
848 QString::fromLatin1(orientation == Horizontal ? "Horizontal" : "Vertical")));
849#endif
850
851 return true;
852}
853
854static AnchorVertex *replaceVertex_helper(AnchorData *data, AnchorVertex *oldV, AnchorVertex *newV)
855{
856 AnchorVertex *other;
857 if (data->from == oldV) {
858 data->from = newV;
859 other = data->to;
860 } else {
861 data->to = newV;
862 other = data->from;
863 }
864 return other;
865}
866
867bool QGraphicsAnchorLayoutPrivate::replaceVertex(Qt::Orientation orientation, AnchorVertex *oldV,
868 AnchorVertex *newV, const QList<AnchorData *> &edges)
869{
870 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
871 bool feasible = true;
872
873 for (int i = 0; i < edges.count(); ++i) {
874 AnchorData *ad = edges[i];
875 AnchorVertex *otherV = replaceVertex_helper(ad, oldV, newV);
876
877#if defined(QT_DEBUG)
878 ad->name = QString::fromLatin1("%1 --to--> %2").arg(ad->from->toString(), ad->to->toString());
879#endif
880
881 bool newFeasible;
882 AnchorData *newAnchor = addAnchorMaybeParallel(ad, &newFeasible);
883 feasible &= newFeasible;
884
885 if (newAnchor != ad) {
886 // A parallel was created, we mark that in the list of anchors created by vertex
887 // simplification. This is needed because we want to restore them in a separate step
888 // from the restoration of anchor simplification.
889 anchorsFromSimplifiedVertices[orientation].append(newAnchor);
890 }
891
892 g.takeEdge(oldV, otherV);
893 }
894
895 return feasible;
896}
897
898/*!
899 \internal
900*/
901bool QGraphicsAnchorLayoutPrivate::simplifyVertices(Qt::Orientation orientation)
902{
903 Q_Q(QGraphicsAnchorLayout);
904 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
905
906 // We'll walk through vertices
907 QStack<AnchorVertex *> stack;
908 stack.push(layoutFirstVertex[orientation]);
909 QSet<AnchorVertex *> visited;
910
911 while (!stack.isEmpty()) {
912 AnchorVertex *v = stack.pop();
913 visited.insert(v);
914
915 // Each adjacent of 'v' is a possible vertex to be merged. So we traverse all of
916 // them. Since once a merge is made, we might add new adjacents, and we don't want to
917 // pass two times through one adjacent. The 'index' is used to track our position.
918 QList<AnchorVertex *> adjacents = g.adjacentVertices(v);
919 int index = 0;
920
921 while (index < adjacents.count()) {
922 AnchorVertex *next = adjacents.at(index);
923 index++;
924
925 AnchorData *data = g.edgeData(v, next);
926 const bool bothLayoutVertices = v->m_item == q && next->m_item == q;
927 const bool zeroSized = !data->minSize && !data->maxSize;
928
929 if (!bothLayoutVertices && zeroSized) {
930
931 // Create a new vertex pair, note that we keep a list of those vertices so we can
932 // easily process them when restoring the graph.
933 AnchorVertexPair *newV = new AnchorVertexPair(v, next, data);
934 simplifiedVertices[orientation].append(newV);
935
936 // Collect the anchors of both vertices, the new vertex pair will take their place
937 // in those anchors
938 const QList<AnchorVertex *> &vAdjacents = g.adjacentVertices(v);
939 const QList<AnchorVertex *> &nextAdjacents = g.adjacentVertices(next);
940
941 for (int i = 0; i < vAdjacents.count(); ++i) {
942 AnchorVertex *adjacent = vAdjacents.at(i);
943 if (adjacent != next) {
944 AnchorData *ad = g.edgeData(v, adjacent);
945 newV->m_firstAnchors.append(ad);
946 }
947 }
948
949 for (int i = 0; i < nextAdjacents.count(); ++i) {
950 AnchorVertex *adjacent = nextAdjacents.at(i);
951 if (adjacent != v) {
952 AnchorData *ad = g.edgeData(next, adjacent);
953 newV->m_secondAnchors.append(ad);
954
955 // We'll also add new vertices to the adjacent list of the new 'v', to be
956 // created as a vertex pair and replace the current one.
957 if (!adjacents.contains(adjacent))
958 adjacents.append(adjacent);
959 }
960 }
961
962 // ### merge this loop into the ones that calculated m_firstAnchors/m_secondAnchors?
963 // Make newV take the place of v and next
964 bool feasible = replaceVertex(orientation, v, newV, newV->m_firstAnchors);
965 feasible &= replaceVertex(orientation, next, newV, newV->m_secondAnchors);
966
967 // Update the layout vertex information if one of the vertices is a layout vertex.
968 AnchorVertex *layoutVertex = nullptr;
969 if (v->m_item == q)
970 layoutVertex = v;
971 else if (next->m_item == q)
972 layoutVertex = next;
973
974 if (layoutVertex) {
975 // Layout vertices always have m_item == q...
976 newV->m_item = q;
977 changeLayoutVertex(orientation, layoutVertex, newV);
978 }
979
980 g.takeEdge(v, next);
981
982 // If a non-feasibility is found, we leave early and cancel the simplification
983 if (!feasible)
984 return false;
985
986 v = newV;
987 visited.insert(newV);
988
989 } else if (!visited.contains(next) && !stack.contains(next)) {
990 // If the adjacent is not fit for merge and it wasn't visited by the outermost
991 // loop, we add it to the stack.
992 stack.push(next);
993 }
994 }
995 }
996
997 return true;
998}
999
1000/*!
1001 \internal
1002
1003 One iteration of the simplification algorithm. Returns \c true if another iteration is needed.
1004
1005 The algorithm walks the graph in depth-first order, and only collects vertices that has two
1006 edges connected to it. If the vertex does not have two edges or if it is a layout edge, it
1007 will take all the previously collected vertices and try to create a simplified sequential
1008 anchor representing all the previously collected vertices. Once the simplified anchor is
1009 inserted, the collected list is cleared in order to find the next sequence to simplify.
1010
1011 Note that there are some catches to this that are not covered by the above explanation, see
1012 the function comments for more details.
1013*/
1014bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(Qt::Orientation orientation,
1015 bool *feasible)
1016{
1017 Q_Q(QGraphicsAnchorLayout);
1018 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1019
1020 QSet<AnchorVertex *> visited;
1021 QStack<QPair<AnchorVertex *, AnchorVertex *> > stack;
1022 stack.push(qMakePair(static_cast<AnchorVertex *>(nullptr), layoutFirstVertex[orientation]));
1023 QList<AnchorVertex *> candidates;
1024
1025 // Walk depth-first, in the stack we store start of the candidate sequence (beforeSequence)
1026 // and the vertex to be visited.
1027 while (!stack.isEmpty()) {
1028 QPair<AnchorVertex *, AnchorVertex *> pair = stack.pop();
1029 AnchorVertex *beforeSequence = pair.first;
1030 AnchorVertex *v = pair.second;
1031
1032 // The basic idea is to determine whether we found an end of sequence,
1033 // if that's the case, we stop adding vertices to the candidate list
1034 // and do a simplification step.
1035 //
1036 // A vertex can trigger an end of sequence if
1037 // (a) it is a layout vertex, we don't simplify away the layout vertices;
1038 // (b) it does not have exactly 2 adjacents;
1039 // (c) its next adjacent is already visited (a cycle in the graph).
1040 // (d) the next anchor is a center anchor.
1041
1042 const QList<AnchorVertex *> &adjacents = g.adjacentVertices(v);
1043 const bool isLayoutVertex = v->m_item == q;
1044 AnchorVertex *afterSequence = v;
1045 bool endOfSequence = false;
1046
1047 //
1048 // Identify the end cases.
1049 //
1050
1051 // Identifies cases (a) and (b)
1052 endOfSequence = isLayoutVertex || adjacents.count() != 2;
1053
1054 if (!endOfSequence) {
1055 // This is a tricky part. We peek at the next vertex to find out whether
1056 //
1057 // - we already visited the next vertex (c);
1058 // - the next anchor is a center (d).
1059 //
1060 // Those are needed to identify the remaining end of sequence cases. Note that unlike
1061 // (a) and (b), we preempt the end of sequence by looking into the next vertex.
1062
1063 // Peek at the next vertex
1064 AnchorVertex *after;
1065 if (candidates.isEmpty())
1066 after = (beforeSequence == adjacents.last() ? adjacents.first() : adjacents.last());
1067 else
1068 after = (candidates.constLast() == adjacents.last() ? adjacents.first() : adjacents.last());
1069
1070 // ### At this point we assumed that candidates will not contain 'after', this may not hold
1071 // when simplifying FLOATing anchors.
1072 Q_ASSERT(!candidates.contains(after));
1073
1074 const AnchorData *data = g.edgeData(v, after);
1075 Q_ASSERT(data);
1076 const bool cycleFound = visited.contains(after);
1077
1078 // Now cases (c) and (d)...
1079 endOfSequence = cycleFound || data->isCenterAnchor;
1080
1081 if (!endOfSequence) {
1082 // If it's not an end of sequence, then the vertex didn't trigger neither of the
1083 // previously three cases, so it can be added to the candidates list.
1084 candidates.append(v);
1085 } else if (cycleFound && (beforeSequence != after)) {
1086 afterSequence = after;
1087 candidates.append(v);
1088 }
1089 }
1090
1091 //
1092 // Add next non-visited vertices to the stack.
1093 //
1094 for (int i = 0; i < adjacents.count(); ++i) {
1095 AnchorVertex *next = adjacents.at(i);
1096 if (visited.contains(next))
1097 continue;
1098
1099 // If current vertex is an end of sequence, and it'll reset the candidates list. So
1100 // the next vertices will build candidates lists with the current vertex as 'before'
1101 // vertex. If it's not an end of sequence, we keep the original 'before' vertex,
1102 // since we are keeping the candidates list.
1103 if (endOfSequence)
1104 stack.push(qMakePair(v, next));
1105 else
1106 stack.push(qMakePair(beforeSequence, next));
1107 }
1108
1109 visited.insert(v);
1110
1111 if (!endOfSequence || candidates.isEmpty())
1112 continue;
1113
1114 //
1115 // Create a sequence for (beforeSequence, candidates, afterSequence).
1116 //
1117
1118 // One restriction we have is to not simplify half of an anchor and let the other half
1119 // unsimplified. So we remove center edges before and after the sequence.
1120 const AnchorData *firstAnchor = g.edgeData(beforeSequence, candidates.constFirst());
1121 if (firstAnchor->isCenterAnchor) {
1122 beforeSequence = candidates.constFirst();
1123 candidates.remove(0);
1124
1125 // If there's not candidates to be simplified, leave.
1126 if (candidates.isEmpty())
1127 continue;
1128 }
1129
1130 const AnchorData *lastAnchor = g.edgeData(candidates.constLast(), afterSequence);
1131 if (lastAnchor->isCenterAnchor) {
1132 afterSequence = candidates.constLast();
1133 candidates.remove(candidates.count() - 1);
1134
1135 if (candidates.isEmpty())
1136 continue;
1137 }
1138
1139 //
1140 // Add the sequence to the graph.
1141 //
1142
1143 AnchorData *sequence = createSequence(&g, beforeSequence, candidates, afterSequence);
1144
1145 // If 'beforeSequence' and 'afterSequence' already had an anchor between them, we'll
1146 // create a parallel anchor between the new sequence and the old anchor.
1147 bool newFeasible;
1148 AnchorData *newAnchor = addAnchorMaybeParallel(sequence, &newFeasible);
1149
1150 if (!newFeasible) {
1151 *feasible = false;
1152 return false;
1153 }
1154
1155 // When a new parallel anchor is create in the graph, we finish the iteration and return
1156 // true to indicate a new iteration is needed. This happens because a parallel anchor
1157 // changes the number of adjacents one vertex has, possibly opening up oportunities for
1158 // building candidate lists (when adjacents == 2).
1159 if (newAnchor != sequence)
1160 return true;
1161
1162 // If there was no parallel simplification, we'll keep walking the graph. So we clear the
1163 // candidates list to start again.
1164 candidates.clear();
1165 }
1166
1167 return false;
1168}
1169
1170void QGraphicsAnchorLayoutPrivate::restoreSimplifiedAnchor(AnchorData *edge)
1171{
1172 const Qt::Orientation orientation = edge->isVertical ? Qt::Vertical : Qt::Horizontal;
1173#if 0
1174 static const char *anchortypes[] = {"Normal",
1175 "Sequential",
1176 "Parallel"};
1177 qDebug("Restoring %s edge.", anchortypes[int(edge->type)]);
1178#endif
1179
1180 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1181
1182 if (edge->type == AnchorData::Normal) {
1183 g.createEdge(edge->from, edge->to, edge);
1184
1185 } else if (edge->type == AnchorData::Sequential) {
1186 SequentialAnchorData *sequence = static_cast<SequentialAnchorData *>(edge);
1187
1188 for (int i = 0; i < sequence->m_edges.count(); ++i) {
1189 AnchorData *data = sequence->m_edges.at(i);
1190 restoreSimplifiedAnchor(data);
1191 }
1192
1193 delete sequence;
1194
1195 } else if (edge->type == AnchorData::Parallel) {
1196
1197 // Skip parallel anchors that were created by vertex simplification, they will be processed
1198 // later, when restoring vertex simplification.
1199 // ### we could improve this check bit having a bit inside 'edge'
1200 if (anchorsFromSimplifiedVertices[orientation].contains(edge))
1201 return;
1202
1203 ParallelAnchorData* parallel = static_cast<ParallelAnchorData*>(edge);
1204 restoreSimplifiedConstraints(parallel);
1205
1206 // ### Because of the way parallel anchors are created in the anchor simplification
1207 // algorithm, we know that one of these will be a sequence, so it'll be safe if the other
1208 // anchor create an edge between the same vertices as the parallel.
1209 Q_ASSERT(parallel->firstEdge->type == AnchorData::Sequential
1210 || parallel->secondEdge->type == AnchorData::Sequential);
1211 restoreSimplifiedAnchor(parallel->firstEdge);
1212 restoreSimplifiedAnchor(parallel->secondEdge);
1213
1214 delete parallel;
1215 }
1216}
1217
1218void QGraphicsAnchorLayoutPrivate::restoreSimplifiedConstraints(ParallelAnchorData *parallel)
1219{
1220 if (!parallel->isCenterAnchor)
1221 return;
1222
1223 for (int i = 0; i < parallel->m_firstConstraints.count(); ++i) {
1224 QSimplexConstraint *c = parallel->m_firstConstraints.at(i);
1225 qreal v = c->variables[parallel];
1226 c->variables.remove(parallel);
1227 c->variables.insert(parallel->firstEdge, v);
1228 }
1229
1230 // When restoring, we might have to revert constraints back. See comments on
1231 // addAnchorMaybeParallel().
1232 const bool needsReverse = !parallel->secondForward();
1233
1234 for (int i = 0; i < parallel->m_secondConstraints.count(); ++i) {
1235 QSimplexConstraint *c = parallel->m_secondConstraints.at(i);
1236 qreal v = c->variables[parallel];
1237 if (needsReverse)
1238 v *= -1;
1239 c->variables.remove(parallel);
1240 c->variables.insert(parallel->secondEdge, v);
1241 }
1242}
1243
1244void QGraphicsAnchorLayoutPrivate::restoreSimplifiedGraph(Qt::Orientation orientation)
1245{
1246#if 0
1247 qDebug("Restoring Simplified Graph for %s",
1248 orientation == Horizontal ? "Horizontal" : "Vertical");
1249#endif
1250
1251 // Restore anchor simplification
1252 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1253 QList<QPair<AnchorVertex *, AnchorVertex *>> connections = g.connections();
1254 for (int i = 0; i < connections.count(); ++i) {
1255 AnchorVertex *v1 = connections.at(i).first;
1256 AnchorVertex *v2 = connections.at(i).second;
1257 AnchorData *edge = g.edgeData(v1, v2);
1258
1259 // We restore only sequential anchors and parallels that were not created by
1260 // vertex simplification.
1261 if (edge->type == AnchorData::Sequential
1262 || (edge->type == AnchorData::Parallel &&
1263 !anchorsFromSimplifiedVertices[orientation].contains(edge))) {
1264
1265 g.takeEdge(v1, v2);
1266 restoreSimplifiedAnchor(edge);
1267 }
1268 }
1269
1270 restoreVertices(orientation);
1271}
1272
1273void QGraphicsAnchorLayoutPrivate::restoreVertices(Qt::Orientation orientation)
1274{
1275 Q_Q(QGraphicsAnchorLayout);
1276
1277 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1278 QList<AnchorVertexPair *> &toRestore = simplifiedVertices[orientation];
1279
1280 // Since we keep a list of parallel anchors and vertices that were created during vertex
1281 // simplification, we can now iterate on those lists instead of traversing the graph
1282 // recursively.
1283
1284 // First, restore the constraints changed when we created parallel anchors. Note that this
1285 // works at this point because the constraints doesn't depend on vertex information and at
1286 // this point it's always safe to identify whether the second child is forward or backwards.
1287 // In the next step, we'll change the anchors vertices so that would not be possible anymore.
1288 QList<AnchorData *> &parallelAnchors = anchorsFromSimplifiedVertices[orientation];
1289
1290 for (int i = parallelAnchors.count() - 1; i >= 0; --i) {
1291 ParallelAnchorData *parallel = static_cast<ParallelAnchorData *>(parallelAnchors.at(i));
1292 restoreSimplifiedConstraints(parallel);
1293 }
1294
1295 // Then, we will restore the vertices in the inverse order of creation, this way we ensure that
1296 // the vertex being restored was not wrapped by another simplification.
1297 for (int i = toRestore.count() - 1; i >= 0; --i) {
1298 AnchorVertexPair *pair = toRestore.at(i);
1299 QList<AnchorVertex *> adjacents = g.adjacentVertices(pair);
1300
1301 // Restore the removed edge, this will also restore both vertices 'first' and 'second' to
1302 // the graph structure.
1303 AnchorVertex *first = pair->m_first;
1304 AnchorVertex *second = pair->m_second;
1305 g.createEdge(first, second, pair->m_removedAnchor);
1306
1307 // Restore the anchors for the first child vertex
1308 for (int j = 0; j < pair->m_firstAnchors.count(); ++j) {
1309 AnchorData *ad = pair->m_firstAnchors.at(j);
1310 Q_ASSERT(ad->from == pair || ad->to == pair);
1311
1312 replaceVertex_helper(ad, pair, first);
1313 g.createEdge(ad->from, ad->to, ad);
1314 }
1315
1316 // Restore the anchors for the second child vertex
1317 for (int j = 0; j < pair->m_secondAnchors.count(); ++j) {
1318 AnchorData *ad = pair->m_secondAnchors.at(j);
1319 Q_ASSERT(ad->from == pair || ad->to == pair);
1320
1321 replaceVertex_helper(ad, pair, second);
1322 g.createEdge(ad->from, ad->to, ad);
1323 }
1324
1325 for (int j = 0; j < adjacents.count(); ++j) {
1326 g.takeEdge(pair, adjacents.at(j));
1327 }
1328
1329 // The pair simplified a layout vertex, so place back the correct vertex in the variable
1330 // that track layout vertices
1331 if (pair->m_item == q) {
1332 AnchorVertex *layoutVertex = first->m_item == q ? first : second;
1333 Q_ASSERT(layoutVertex->m_item == q);
1334 changeLayoutVertex(orientation, pair, layoutVertex);
1335 }
1336
1337 delete pair;
1338 }
1339 qDeleteAll(parallelAnchors);
1340 parallelAnchors.clear();
1341 toRestore.clear();
1342}
1343
1344Qt::Orientation
1345QGraphicsAnchorLayoutPrivate::edgeOrientation(Qt::AnchorPoint edge) noexcept
1346{
1347 return edge > Qt::AnchorRight ? Qt::Vertical : Qt::Horizontal;
1348}
1349
1350/*!
1351 \internal
1352
1353 Create internal anchors to connect the layout edges (Left to Right and
1354 Top to Bottom).
1355
1356 These anchors doesn't have size restrictions, that will be enforced by
1357 other anchors and items in the layout.
1358*/
1359void QGraphicsAnchorLayoutPrivate::createLayoutEdges()
1360{
1361 Q_Q(QGraphicsAnchorLayout);
1362 QGraphicsLayoutItem *layout = q;
1363
1364 // Horizontal
1365 AnchorData *data = new AnchorData;
1366 addAnchor_helper(layout, Qt::AnchorLeft, layout,
1367 Qt::AnchorRight, data);
1368 data->maxSize = QWIDGETSIZE_MAX;
1369
1370 // Save a reference to layout vertices
1371 layoutFirstVertex[Qt::Horizontal] = internalVertex(layout, Qt::AnchorLeft);
1372 layoutCentralVertex[Qt::Horizontal] = nullptr;
1373 layoutLastVertex[Qt::Horizontal] = internalVertex(layout, Qt::AnchorRight);
1374
1375 // Vertical
1376 data = new AnchorData;
1377 addAnchor_helper(layout, Qt::AnchorTop, layout,
1378 Qt::AnchorBottom, data);
1379 data->maxSize = QWIDGETSIZE_MAX;
1380
1381 // Save a reference to layout vertices
1382 layoutFirstVertex[Qt::Vertical] = internalVertex(layout, Qt::AnchorTop);
1383 layoutCentralVertex[Qt::Vertical] = nullptr;
1384 layoutLastVertex[Qt::Vertical] = internalVertex(layout, Qt::AnchorBottom);
1385}
1386
1387void QGraphicsAnchorLayoutPrivate::deleteLayoutEdges()
1388{
1389 Q_Q(QGraphicsAnchorLayout);
1390
1391 Q_ASSERT(!internalVertex(q, Qt::AnchorHorizontalCenter));
1392 Q_ASSERT(!internalVertex(q, Qt::AnchorVerticalCenter));
1393
1394 removeAnchor_helper(internalVertex(q, Qt::AnchorLeft),
1395 internalVertex(q, Qt::AnchorRight));
1396 removeAnchor_helper(internalVertex(q, Qt::AnchorTop),
1397 internalVertex(q, Qt::AnchorBottom));
1398}
1399
1400void QGraphicsAnchorLayoutPrivate::createItemEdges(QGraphicsLayoutItem *item)
1401{
1402 items.append(item);
1403
1404 // Create horizontal and vertical internal anchors for the item and
1405 // refresh its size hint / policy values.
1406 AnchorData *data = new AnchorData;
1407 addAnchor_helper(item, Qt::AnchorLeft, item, Qt::AnchorRight, data);
1408 data->refreshSizeHints();
1409
1410 data = new AnchorData;
1411 addAnchor_helper(item, Qt::AnchorTop, item, Qt::AnchorBottom, data);
1412 data->refreshSizeHints();
1413}
1414
1415/*!
1416 \internal
1417
1418 By default, each item in the layout is represented internally as
1419 a single anchor in each direction. For instance, from Left to Right.
1420
1421 However, to support anchorage of items to the center of items, we
1422 must split this internal anchor into two half-anchors. From Left
1423 to Center and then from Center to Right, with the restriction that
1424 these anchors must have the same time at all times.
1425*/
1426void QGraphicsAnchorLayoutPrivate::createCenterAnchors(
1427 QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge)
1428{
1429 Q_Q(QGraphicsAnchorLayout);
1430
1431 Qt::Orientation orientation;
1432 switch (centerEdge) {
1433 case Qt::AnchorHorizontalCenter:
1434 orientation = Qt::Horizontal;
1435 break;
1436 case Qt::AnchorVerticalCenter:
1437 orientation = Qt::Vertical;
1438 break;
1439 default:
1440 // Don't create center edges unless needed
1441 return;
1442 }
1443
1444 // Check if vertex already exists
1445 if (internalVertex(item, centerEdge))
1446 return;
1447
1448 // Orientation code
1449 Qt::AnchorPoint firstEdge;
1450 Qt::AnchorPoint lastEdge;
1451
1452 if (orientation == Qt::Horizontal) {
1453 firstEdge = Qt::AnchorLeft;
1454 lastEdge = Qt::AnchorRight;
1455 } else {
1456 firstEdge = Qt::AnchorTop;
1457 lastEdge = Qt::AnchorBottom;
1458 }
1459
1460 AnchorVertex *first = internalVertex(item, firstEdge);
1461 AnchorVertex *last = internalVertex(item, lastEdge);
1462 Q_ASSERT(first && last);
1463
1464 // Create new anchors
1465 QSimplexConstraint *c = new QSimplexConstraint;
1466
1467 AnchorData *data = new AnchorData;
1468 c->variables.insert(data, 1.0);
1469 addAnchor_helper(item, firstEdge, item, centerEdge, data);
1470 data->isCenterAnchor = true;
1471 data->dependency = AnchorData::Master;
1472 data->refreshSizeHints();
1473
1474 data = new AnchorData;
1475 c->variables.insert(data, -1.0);
1476 addAnchor_helper(item, centerEdge, item, lastEdge, data);
1477 data->isCenterAnchor = true;
1478 data->dependency = AnchorData::Slave;
1479 data->refreshSizeHints();
1480
1481 itemCenterConstraints[orientation].append(c);
1482
1483 // Remove old one
1484 removeAnchor_helper(first, last);
1485
1486 if (item == q) {
1487 layoutCentralVertex[orientation] = internalVertex(q, centerEdge);
1488 }
1489}
1490
1491void QGraphicsAnchorLayoutPrivate::removeCenterAnchors(
1492 QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge,
1493 bool substitute)
1494{
1495 Q_Q(QGraphicsAnchorLayout);
1496
1497 Qt::Orientation orientation;
1498 switch (centerEdge) {
1499 case Qt::AnchorHorizontalCenter:
1500 orientation = Qt::Horizontal;
1501 break;
1502 case Qt::AnchorVerticalCenter:
1503 orientation = Qt::Vertical;
1504 break;
1505 default:
1506 // Don't remove edges that not the center ones
1507 return;
1508 }
1509
1510 // Orientation code
1511 Qt::AnchorPoint firstEdge;
1512 Qt::AnchorPoint lastEdge;
1513
1514 if (orientation == Qt::Horizontal) {
1515 firstEdge = Qt::AnchorLeft;
1516 lastEdge = Qt::AnchorRight;
1517 } else {
1518 firstEdge = Qt::AnchorTop;
1519 lastEdge = Qt::AnchorBottom;
1520 }
1521
1522 AnchorVertex *center = internalVertex(item, centerEdge);
1523 if (!center)
1524 return;
1525 AnchorVertex *first = internalVertex(item, firstEdge);
1526
1527 Q_ASSERT(first);
1528 Q_ASSERT(center);
1529
1530 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1531
1532
1533 AnchorData *oldData = g.edgeData(first, center);
1534 // Remove center constraint
1535 for (int i = itemCenterConstraints[orientation].count() - 1; i >= 0; --i) {
1536 if (itemCenterConstraints[orientation].at(i)->variables.contains(oldData)) {
1537 delete itemCenterConstraints[orientation].takeAt(i);
1538 break;
1539 }
1540 }
1541
1542 if (substitute) {
1543 // Create the new anchor that should substitute the left-center-right anchors.
1544 AnchorData *data = new AnchorData;
1545 addAnchor_helper(item, firstEdge, item, lastEdge, data);
1546 data->refreshSizeHints();
1547
1548 // Remove old anchors
1549 removeAnchor_helper(first, center);
1550 removeAnchor_helper(center, internalVertex(item, lastEdge));
1551
1552 } else {
1553 // this is only called from removeAnchors()
1554 // first, remove all non-internal anchors
1555 QList<AnchorVertex*> adjacents = g.adjacentVertices(center);
1556 for (int i = 0; i < adjacents.count(); ++i) {
1557 AnchorVertex *v = adjacents.at(i);
1558 if (v->m_item != item) {
1559 removeAnchor_helper(center, internalVertex(v->m_item, v->m_edge));
1560 }
1561 }
1562 // when all non-internal anchors is removed it will automatically merge the
1563 // center anchor into a left-right (or top-bottom) anchor. We must also delete that.
1564 // by this time, the center vertex is deleted and merged into a non-centered internal anchor
1565 removeAnchor_helper(first, internalVertex(item, lastEdge));
1566 }
1567
1568 if (item == q) {
1569 layoutCentralVertex[orientation] = nullptr;
1570 }
1571}
1572
1573
1574void QGraphicsAnchorLayoutPrivate::removeCenterConstraints(QGraphicsLayoutItem *item,
1575 Qt::Orientation orientation)
1576{
1577 // Remove the item center constraints associated to this item
1578 // ### This is a temporary solution. We should probably use a better
1579 // data structure to hold items and/or their associated constraints
1580 // so that we can remove those easily
1581
1582 AnchorVertex *first = internalVertex(item, orientation == Qt::Horizontal ?
1583 Qt::AnchorLeft :
1584 Qt::AnchorTop);
1585 AnchorVertex *center = internalVertex(item, orientation == Qt::Horizontal ?
1586 Qt::AnchorHorizontalCenter :
1587 Qt::AnchorVerticalCenter);
1588
1589 // Skip if no center constraints exist
1590 if (!center)
1591 return;
1592
1593 Q_ASSERT(first);
1594 AnchorData *internalAnchor = graph[orientation].edgeData(first, center);
1595
1596 // Look for our anchor in all item center constraints, then remove it
1597 for (int i = 0; i < itemCenterConstraints[orientation].size(); ++i) {
1598 if (itemCenterConstraints[orientation].at(i)->variables.contains(internalAnchor)) {
1599 delete itemCenterConstraints[orientation].takeAt(i);
1600 break;
1601 }
1602 }
1603}
1604
1605/*!
1606 * \internal
1607 * Implements the high level "addAnchor" feature. Called by the public API
1608 * addAnchor method.
1609 *
1610 * The optional \a spacing argument defines the size of the anchor. If not provided,
1611 * the anchor size is either 0 or not-set, depending on type of anchor created (see
1612 * matrix below).
1613 *
1614 * All anchors that remain with size not-set will assume the standard spacing,
1615 * set either by the layout style or through the "setSpacing" layout API.
1616 */
1617QGraphicsAnchor *QGraphicsAnchorLayoutPrivate::addAnchor(QGraphicsLayoutItem *firstItem,
1618 Qt::AnchorPoint firstEdge,
1619 QGraphicsLayoutItem *secondItem,
1620 Qt::AnchorPoint secondEdge,
1621 qreal *spacing)
1622{
1623 Q_Q(QGraphicsAnchorLayout);
1624 if ((firstItem == nullptr) || (secondItem == nullptr)) {
1625 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1626 "Cannot anchor NULL items");
1627 return nullptr;
1628 }
1629
1630 if (firstItem == secondItem) {
1631 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1632 "Cannot anchor the item to itself");
1633 return nullptr;
1634 }
1635
1636 if (edgeOrientation(secondEdge) != edgeOrientation(firstEdge)) {
1637 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1638 "Cannot anchor edges of different orientations");
1639 return nullptr;
1640 }
1641
1642 const QGraphicsLayoutItem *parentWidget = q->parentLayoutItem();
1643 if (firstItem == parentWidget || secondItem == parentWidget) {
1644 qWarning("QGraphicsAnchorLayout::addAnchor(): "
1645 "You cannot add the parent of the layout to the layout.");
1646 return nullptr;
1647 }
1648
1649 // In QGraphicsAnchorLayout, items are represented in its internal
1650 // graph as four anchors that connect:
1651 // - Left -> HCenter
1652 // - HCenter-> Right
1653 // - Top -> VCenter
1654 // - VCenter -> Bottom
1655
1656 // Ensure that the internal anchors have been created for both items.
1657 if (firstItem != q && !items.contains(firstItem)) {
1658 createItemEdges(firstItem);
1659 addChildLayoutItem(firstItem);
1660 }
1661 if (secondItem != q && !items.contains(secondItem)) {
1662 createItemEdges(secondItem);
1663 addChildLayoutItem(secondItem);
1664 }
1665
1666 // Create center edges if needed
1667 createCenterAnchors(firstItem, firstEdge);
1668 createCenterAnchors(secondItem, secondEdge);
1669
1670 // Use heuristics to find out what the user meant with this anchor.
1671 correctEdgeDirection(firstItem, firstEdge, secondItem, secondEdge);
1672
1673 AnchorData *data = new AnchorData;
1674 QGraphicsAnchor *graphicsAnchor = acquireGraphicsAnchor(data);
1675
1676 addAnchor_helper(firstItem, firstEdge, secondItem, secondEdge, data);
1677
1678 if (spacing) {
1679 graphicsAnchor->setSpacing(*spacing);
1680 } else {
1681 // If firstItem or secondItem is the layout itself, the spacing will default to 0.
1682 // Otherwise, the following matrix is used (questionmark means that the spacing
1683 // is queried from the style):
1684 // from
1685 // to Left HCenter Right
1686 // Left 0 0 ?
1687 // HCenter 0 0 0
1688 // Right ? 0 0
1689 if (firstItem == q
1690 || secondItem == q
1691 || pickEdge(firstEdge, Qt::Horizontal) == Qt::AnchorHorizontalCenter
1692 || oppositeEdge(firstEdge) != secondEdge) {
1693 graphicsAnchor->setSpacing(0);
1694 } else {
1695 graphicsAnchor->unsetSpacing();
1696 }
1697 }
1698
1699 return graphicsAnchor;
1700}
1701
1702/*
1703 \internal
1704
1705 This method adds an AnchorData to the internal graph. It is responsible for doing
1706 the boilerplate part of such task.
1707
1708 If another AnchorData exists between the mentioned vertices, it is deleted and
1709 the new one is inserted.
1710*/
1711void QGraphicsAnchorLayoutPrivate::addAnchor_helper(QGraphicsLayoutItem *firstItem,
1712 Qt::AnchorPoint firstEdge,
1713 QGraphicsLayoutItem *secondItem,
1714 Qt::AnchorPoint secondEdge,
1715 AnchorData *data)
1716{
1717 Q_Q(QGraphicsAnchorLayout);
1718
1719 const Qt::Orientation orientation = edgeOrientation(firstEdge);
1720
1721 // Create or increase the reference count for the related vertices.
1722 AnchorVertex *v1 = addInternalVertex(firstItem, firstEdge);
1723 AnchorVertex *v2 = addInternalVertex(secondItem, secondEdge);
1724
1725 // Remove previous anchor
1726 if (graph[orientation].edgeData(v1, v2)) {
1727 removeAnchor_helper(v1, v2);
1728 }
1729
1730 // If its an internal anchor, set the associated item
1731 if (firstItem == secondItem)
1732 data->item = firstItem;
1733
1734 data->isVertical = orientation == Qt::Vertical;
1735
1736 // Create a bi-directional edge in the sense it can be transversed both
1737 // from v1 or v2. "data" however is shared between the two references
1738 // so we still know that the anchor direction is from 1 to 2.
1739 data->from = v1;
1740 data->to = v2;
1741#ifdef QT_DEBUG
1742 data->name = QString::fromLatin1("%1 --to--> %2").arg(v1->toString(), v2->toString());
1743#endif
1744 // ### bit to track internal anchors, since inside AnchorData methods
1745 // we don't have access to the 'q' pointer.
1746 data->isLayoutAnchor = (data->item == q);
1747
1748 graph[orientation].createEdge(v1, v2, data);
1749}
1750
1751QGraphicsAnchor *QGraphicsAnchorLayoutPrivate::getAnchor(QGraphicsLayoutItem *firstItem,
1752 Qt::AnchorPoint firstEdge,
1753 QGraphicsLayoutItem *secondItem,
1754 Qt::AnchorPoint secondEdge)
1755{
1756 // Do not expose internal anchors
1757 if (firstItem == secondItem)
1758 return nullptr;
1759
1760 const Qt::Orientation orientation = edgeOrientation(firstEdge);
1761 AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
1762 AnchorVertex *v2 = internalVertex(secondItem, secondEdge);
1763
1764 QGraphicsAnchor *graphicsAnchor = nullptr;
1765
1766 AnchorData *data = graph[orientation].edgeData(v1, v2);
1767 if (data) {
1768 // We could use "acquireGraphicsAnchor" here, but to avoid a regression where
1769 // an internal anchor was wrongly exposed, I want to ensure no new
1770 // QGraphicsAnchor instances are created by this call.
1771 // This assumption must hold because anchors are either user-created (and already
1772 // have their public object created), or they are internal (and must not reach
1773 // this point).
1774 Q_ASSERT(data->graphicsAnchor);
1775 graphicsAnchor = data->graphicsAnchor;
1776 }
1777 return graphicsAnchor;
1778}
1779
1780/*!
1781 * \internal
1782 *
1783 * Implements the high level "removeAnchor" feature. Called by
1784 * the QAnchorData destructor.
1785 */
1786void QGraphicsAnchorLayoutPrivate::removeAnchor(AnchorVertex *firstVertex,
1787 AnchorVertex *secondVertex)
1788{
1789 Q_Q(QGraphicsAnchorLayout);
1790
1791 // Save references to items while it's safe to assume the vertices exist
1792 QGraphicsLayoutItem *firstItem = firstVertex->m_item;
1793 QGraphicsLayoutItem *secondItem = secondVertex->m_item;
1794
1795 // Delete the anchor (may trigger deletion of center vertices)
1796 removeAnchor_helper(firstVertex, secondVertex);
1797
1798 // Ensure no dangling pointer is left behind
1799 firstVertex = secondVertex = nullptr;
1800
1801 // Checking if the item stays in the layout or not
1802 bool keepFirstItem = false;
1803 bool keepSecondItem = false;
1804
1805 QPair<AnchorVertex *, int> v;
1806 int refcount = -1;
1807
1808 if (firstItem != q) {
1809 for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
1810 v = m_vertexList.value(qMakePair(firstItem, static_cast<Qt::AnchorPoint>(i)));
1811 if (v.first) {
1812 if (i == Qt::AnchorHorizontalCenter || i == Qt::AnchorVerticalCenter)
1813 refcount = 2;
1814 else
1815 refcount = 1;
1816
1817 if (v.second > refcount) {
1818 keepFirstItem = true;
1819 break;
1820 }
1821 }
1822 }
1823 } else
1824 keepFirstItem = true;
1825
1826 if (secondItem != q) {
1827 for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
1828 v = m_vertexList.value(qMakePair(secondItem, static_cast<Qt::AnchorPoint>(i)));
1829 if (v.first) {
1830 if (i == Qt::AnchorHorizontalCenter || i == Qt::AnchorVerticalCenter)
1831 refcount = 2;
1832 else
1833 refcount = 1;
1834
1835 if (v.second > refcount) {
1836 keepSecondItem = true;
1837 break;
1838 }
1839 }
1840 }
1841 } else
1842 keepSecondItem = true;
1843
1844 if (!keepFirstItem)
1845 q->removeAt(items.indexOf(firstItem));
1846
1847 if (!keepSecondItem)
1848 q->removeAt(items.indexOf(secondItem));
1849
1850 // Removing anchors invalidates the layout
1851 q->invalidate();
1852}
1853
1854/*
1855 \internal
1856
1857 Implements the low level "removeAnchor" feature. Called by
1858 private methods.
1859*/
1860void QGraphicsAnchorLayoutPrivate::removeAnchor_helper(AnchorVertex *v1, AnchorVertex *v2)
1861{
1862 Q_ASSERT(v1 && v2);
1863
1864 // Remove edge from graph
1865 const Qt::Orientation o = edgeOrientation(v1->m_edge);
1866 graph[o].removeEdge(v1, v2);
1867
1868 // Decrease vertices reference count (may trigger a deletion)
1869 removeInternalVertex(v1->m_item, v1->m_edge);
1870 removeInternalVertex(v2->m_item, v2->m_edge);
1871}
1872
1873AnchorVertex *QGraphicsAnchorLayoutPrivate::addInternalVertex(QGraphicsLayoutItem *item,
1874 Qt::AnchorPoint edge)
1875{
1876 QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
1877 QPair<AnchorVertex *, int> v = m_vertexList.value(pair);
1878
1879 if (!v.first) {
1880 Q_ASSERT(v.second == 0);
1881 v.first = new AnchorVertex(item, edge);
1882 }
1883 v.second++;
1884 m_vertexList.insert(pair, v);
1885 return v.first;
1886}
1887
1888/**
1889 * \internal
1890 *
1891 * returns the AnchorVertex that was dereferenced, also when it was removed.
1892 * returns 0 if it did not exist.
1893 */
1894void QGraphicsAnchorLayoutPrivate::removeInternalVertex(QGraphicsLayoutItem *item,
1895 Qt::AnchorPoint edge)
1896{
1897 QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
1898 QPair<AnchorVertex *, int> v = m_vertexList.value(pair);
1899
1900 if (!v.first) {
1901 qWarning("This item with this edge is not in the graph");
1902 return;
1903 }
1904
1905 v.second--;
1906 if (v.second == 0) {
1907 // Remove reference and delete vertex
1908 m_vertexList.remove(pair);
1909 delete v.first;
1910 } else {
1911 // Update reference count
1912 m_vertexList.insert(pair, v);
1913
1914 if ((v.second == 2) &&
1915 ((edge == Qt::AnchorHorizontalCenter) ||
1916 (edge == Qt::AnchorVerticalCenter))) {
1917 removeCenterAnchors(item, edge, true);
1918 }
1919 }
1920}
1921
1922void QGraphicsAnchorLayoutPrivate::removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
1923{
1924 if (AnchorVertex *v = internalVertex(item, edge)) {
1925 Graph<AnchorVertex, AnchorData> &g = graph[edgeOrientation(edge)];
1926 const auto allVertices = g.adjacentVertices(v);
1927 for (auto *v2 : allVertices) {
1928 g.removeEdge(v, v2);
1929 removeInternalVertex(item, edge);
1930 removeInternalVertex(v2->m_item, v2->m_edge);
1931 }
1932 }
1933}
1934
1935void QGraphicsAnchorLayoutPrivate::removeAnchors(QGraphicsLayoutItem *item)
1936{
1937 // remove the center anchor first!!
1938 removeCenterAnchors(item, Qt::AnchorHorizontalCenter, false);
1939 removeVertex(item, Qt::AnchorLeft);
1940 removeVertex(item, Qt::AnchorRight);
1941
1942 removeCenterAnchors(item, Qt::AnchorVerticalCenter, false);
1943 removeVertex(item, Qt::AnchorTop);
1944 removeVertex(item, Qt::AnchorBottom);
1945}
1946
1947/*!
1948 \internal
1949
1950 Use heuristics to determine the correct orientation of a given anchor.
1951
1952 After API discussions, we decided we would like expressions like
1953 anchor(A, Left, B, Right) to mean the same as anchor(B, Right, A, Left).
1954 The problem with this is that anchors could become ambiguous, for
1955 instance, what does the anchor A, B of size X mean?
1956
1957 "pos(B) = pos(A) + X" or "pos(A) = pos(B) + X" ?
1958
1959 To keep the API user friendly and at the same time, keep our algorithm
1960 deterministic, we use an heuristic to determine a direction for each
1961 added anchor and then keep it. The heuristic is based on the fact
1962 that people usually avoid overlapping items, therefore:
1963
1964 "A, RIGHT to B, LEFT" means that B is to the LEFT of A.
1965 "B, LEFT to A, RIGHT" is corrected to the above anchor.
1966
1967 Special correction is also applied when one of the items is the
1968 layout. We handle Layout Left as if it was another items's Right
1969 and Layout Right as another item's Left.
1970*/
1971void QGraphicsAnchorLayoutPrivate::correctEdgeDirection(QGraphicsLayoutItem *&firstItem,
1972 Qt::AnchorPoint &firstEdge,
1973 QGraphicsLayoutItem *&secondItem,
1974 Qt::AnchorPoint &secondEdge)
1975{
1976 Q_Q(QGraphicsAnchorLayout);
1977
1978 if ((firstItem != q) && (secondItem != q)) {
1979 // If connection is between widgets (not the layout itself)
1980 // Ensure that "right-edges" sit to the left of "left-edges".
1981 if (firstEdge < secondEdge) {
1982 qSwap(firstItem, secondItem);
1983 qSwap(firstEdge, secondEdge);
1984 }
1985 } else if (firstItem == q) {
1986 // If connection involves the right or bottom of a layout, ensure
1987 // the layout is the second item.
1988 if ((firstEdge == Qt::AnchorRight) || (firstEdge == Qt::AnchorBottom)) {
1989 qSwap(firstItem, secondItem);
1990 qSwap(firstEdge, secondEdge);
1991 }
1992 } else if ((secondEdge != Qt::AnchorRight) && (secondEdge != Qt::AnchorBottom)) {
1993 // If connection involves the left, center or top of layout, ensure
1994 // the layout is the first item.
1995 qSwap(firstItem, secondItem);
1996 qSwap(firstEdge, secondEdge);
1997 }
1998}
1999
2000QLayoutStyleInfo &QGraphicsAnchorLayoutPrivate::styleInfo() const
2001{
2002 if (styleInfoDirty) {
2003 Q_Q(const QGraphicsAnchorLayout);
2004 //### Fix this if QGV ever gets support for Metal style or different Aqua sizes.
2005 QWidget *wid = nullptr;
2006
2007 QGraphicsLayoutItem *parent = q->parentLayoutItem();
2008 while (parent && parent->isLayout()) {
2009 parent = parent->parentLayoutItem();
2010 }
2011 QGraphicsWidget *w = nullptr;
2012 if (parent) {
2013 QGraphicsItem *parentItem = parent->graphicsItem();
2014 if (parentItem && parentItem->isWidget())
2015 w = static_cast<QGraphicsWidget*>(parentItem);
2016 }
2017
2018 QStyle *style = w ? w->style() : QApplication::style();
2019 cachedStyleInfo = QLayoutStyleInfo(style, wid);
2020 cachedStyleInfo.setDefaultSpacing(Qt::Horizontal, spacings[Qt::Horizontal]);
2021 cachedStyleInfo.setDefaultSpacing(Qt::Vertical, spacings[Qt::Vertical]);
2022
2023 styleInfoDirty = false;
2024 }
2025 return cachedStyleInfo;
2026}
2027
2028/*!
2029 \internal
2030
2031 Called on activation. Uses Linear Programming to define minimum, preferred
2032 and maximum sizes for the layout. Also calculates the sizes that each item
2033 should assume when the layout is in one of such situations.
2034*/
2035void QGraphicsAnchorLayoutPrivate::calculateGraphs()
2036{
2037 if (!calculateGraphCacheDirty)
2038 return;
2039 calculateGraphs(Qt::Horizontal);
2040 calculateGraphs(Qt::Vertical);
2041 calculateGraphCacheDirty = false;
2042}
2043
2044// ### Maybe getGraphParts could return the variables when traversing, at least
2045// for trunk...
2046QList<AnchorData *> getVariables(const QList<QSimplexConstraint *> &constraints)
2047{
2048 QSet<AnchorData *> variableSet;
2049 for (int i = 0; i < constraints.count(); ++i) {
2050 const QSimplexConstraint *c = constraints.at(i);
2051 for (auto it = c->variables.cbegin(), end = c->variables.cend(); it != end; ++it)
2052 variableSet.insert(static_cast<AnchorData *>(it.key()));
2053 }
2054 return variableSet.values();
2055}
2056
2057/*!
2058 \internal
2059
2060 Calculate graphs is the method that puts together all the helper routines
2061 so that the AnchorLayout can calculate the sizes of each item.
2062
2063 In a nutshell it should do:
2064
2065 1) Refresh anchor nominal sizes, that is, the size that each anchor would
2066 have if no other restrictions applied. This is done by quering the
2067 layout style and the sizeHints of the items belonging to the layout.
2068
2069 2) Simplify the graph by grouping together parallel and sequential anchors
2070 into "group anchors". These have equivalent minimum, preferred and maximum
2071 sizeHints as the anchors they replace.
2072
2073 3) Check if we got to a trivial case. In some cases, the whole graph can be
2074 simplified into a single anchor. If so, use this information. If not,
2075 then call the Simplex solver to calculate the anchors sizes.
2076
2077 4) Once the root anchors had its sizes calculated, propagate that to the
2078 anchors they represent.
2079*/
2080void QGraphicsAnchorLayoutPrivate::calculateGraphs(Qt::Orientation orientation)
2081{
2082#if defined(QT_DEBUG) || defined(QT_BUILD_INTERNAL)
2083 lastCalculationUsedSimplex[orientation] = false;
2084#endif
2085
2086 static bool simplificationEnabled = qEnvironmentVariableIsEmpty("QT_ANCHORLAYOUT_NO_SIMPLIFICATION");
2087
2088 // Reset the nominal sizes of each anchor based on the current item sizes
2089 refreshAllSizeHints(orientation);
2090
2091 // Simplify the graph
2092 if (simplificationEnabled && !simplifyGraph(orientation)) {
2093 qWarning("QGraphicsAnchorLayout: anchor setup is not feasible.");
2094 graphHasConflicts[orientation] = true;
2095 return;
2096 }
2097
2098 // Traverse all graph edges and store the possible paths to each vertex
2099 findPaths(orientation);
2100
2101 // From the paths calculated above, extract the constraints that the current
2102 // anchor setup impose, to our Linear Programming problem.
2103 constraintsFromPaths(orientation);
2104
2105 // Split the constraints and anchors into groups that should be fed to the
2106 // simplex solver independently. Currently we find two groups:
2107 //
2108 // 1) The "trunk", that is, the set of anchors (items) that are connected
2109 // to the two opposite sides of our layout, and thus need to stretch in
2110 // order to fit in the current layout size.
2111 //
2112 // 2) The floating or semi-floating anchors (items) that are those which
2113 // are connected to only one (or none) of the layout sides, thus are not
2114 // influenced by the layout size.
2115 const auto parts = getGraphParts(orientation);
2116
2117 // Now run the simplex solver to calculate Minimum, Preferred and Maximum sizes
2118 // of the "trunk" set of constraints and variables.
2119 // ### does trunk always exist? empty = trunk is the layout left->center->right
2120 const QList<AnchorData *> trunkVariables = getVariables(parts.trunkConstraints);
2121
2122 // For minimum and maximum, use the path between the two layout sides as the
2123 // objective function.
2124 AnchorVertex *v = layoutLastVertex[orientation];
2125 GraphPath trunkPath = graphPaths[orientation].value(v);
2126
2127 bool feasible = calculateTrunk(orientation, trunkPath, parts.trunkConstraints, trunkVariables);
2128
2129 // For the other parts that not the trunk, solve only for the preferred size
2130 // that is the size they will remain at, since they are not stretched by the
2131 // layout.
2132
2133 if (feasible && !parts.nonTrunkConstraints.isEmpty()) {
2134 const QList<AnchorData *> partVariables = getVariables(parts.nonTrunkConstraints);
2135 Q_ASSERT(!partVariables.isEmpty());
2136 feasible = calculateNonTrunk(parts.nonTrunkConstraints, partVariables);
2137 }
2138
2139 // Propagate the new sizes down the simplified graph, ie. tell the
2140 // group anchors to set their children anchors sizes.
2141 updateAnchorSizes(orientation);
2142
2143 graphHasConflicts[orientation] = !feasible;
2144
2145 // Clean up our data structures. They are not needed anymore since
2146 // distribution uses just interpolation.
2147 qDeleteAll(constraints[orientation]);
2148 constraints[orientation].clear();
2149 graphPaths[orientation].clear(); // ###
2150
2151 if (simplificationEnabled)
2152 restoreSimplifiedGraph(orientation);
2153}
2154
2155/*!
2156 \internal
2157
2158 Shift all the constraints by a certain amount. This allows us to deal with negative values in
2159 the linear program if they are bounded by a certain limit. Functions should be careful to
2160 call it again with a negative amount, to shift the constraints back.
2161*/
2162static void shiftConstraints(const QList<QSimplexConstraint *> &constraints, qreal amount)
2163{
2164 for (int i = 0; i < constraints.count(); ++i) {
2165 QSimplexConstraint *c = constraints.at(i);
2166 const qreal multiplier = std::accumulate(c->variables.cbegin(), c->variables.cend(), qreal(0));
2167 c->constant += multiplier * amount;
2168 }
2169}
2170
2171/*!
2172 \internal
2173
2174 Calculate the sizes for all anchors which are part of the trunk. This works
2175 on top of a (possibly) simplified graph.
2176*/
2177bool QGraphicsAnchorLayoutPrivate::calculateTrunk(Qt::Orientation orientation, const GraphPath &path,
2178 const QList<QSimplexConstraint *> &constraints,
2179 const QList<AnchorData *> &variables)
2180{
2181 bool feasible = true;
2182 bool needsSimplex = !constraints.isEmpty();
2183
2184#if 0
2185 qDebug("Simplex %s for trunk of %s", needsSimplex ? "used" : "NOT used",
2186 orientation == Qt::Horizontal ? "Horizontal" : "Vertical");
2187#endif
2188
2189 if (needsSimplex) {
2190
2191 QList<QSimplexConstraint *> sizeHintConstraints = constraintsFromSizeHints(variables);
2192 QList<QSimplexConstraint *> allConstraints = constraints + sizeHintConstraints;
2193
2194 shiftConstraints(allConstraints, g_offset);
2195
2196 // Solve min and max size hints
2197 qreal min, max;
2198 feasible = solveMinMax(allConstraints, path, &min, &max);
2199
2200 if (feasible) {
2201 solvePreferred(constraints, variables);
2202
2203 // Calculate and set the preferred size for the layout,
2204 // from the edge sizes that were calculated above.
2205 qreal pref(0.0);
2206 for (const AnchorData *ad : path.positives)
2207 pref += ad->sizeAtPreferred;
2208 for (const AnchorData *ad : path.negatives)
2209 pref -= ad->sizeAtPreferred;
2210
2211 sizeHints[orientation][Qt::MinimumSize] = min;
2212 sizeHints[orientation][Qt::PreferredSize] = pref;
2213 sizeHints[orientation][Qt::MaximumSize] = max;
2214 }
2215
2216 qDeleteAll(sizeHintConstraints);
2217 shiftConstraints(constraints, -g_offset);
2218
2219 } else {
2220 // No Simplex is necessary because the path was simplified all the way to a single
2221 // anchor.
2222 Q_ASSERT(path.positives.count() == 1);
2223 Q_ASSERT(path.negatives.count() == 0);
2224
2225 AnchorData *ad = *path.positives.cbegin();
2226 ad->sizeAtMinimum = ad->minSize;
2227 ad->sizeAtPreferred = ad->prefSize;
2228 ad->sizeAtMaximum = ad->maxSize;
2229
2230 sizeHints[orientation][Qt::MinimumSize] = ad->sizeAtMinimum;
2231 sizeHints[orientation][Qt::PreferredSize] = ad->sizeAtPreferred;
2232 sizeHints[orientation][Qt::MaximumSize] = ad->sizeAtMaximum;
2233 }
2234
2235#if defined(QT_DEBUG) || defined(QT_BUILD_INTERNAL)
2236 lastCalculationUsedSimplex[orientation] = needsSimplex;
2237#endif
2238
2239 return feasible;
2240}
2241
2242/*!
2243 \internal
2244*/
2245bool QGraphicsAnchorLayoutPrivate::calculateNonTrunk(const QList<QSimplexConstraint *> &constraints,
2246 const QList<AnchorData *> &variables)
2247{
2248 shiftConstraints(constraints, g_offset);
2249 bool feasible = solvePreferred(constraints, variables);
2250
2251 if (feasible) {
2252 // Propagate size at preferred to other sizes. Semi-floats always will be
2253 // in their sizeAtPreferred.
2254 for (int j = 0; j < variables.count(); ++j) {
2255 AnchorData *ad = variables.at(j);
2256 Q_ASSERT(ad);
2257 ad->sizeAtMinimum = ad->sizeAtPreferred;
2258 ad->sizeAtMaximum = ad->sizeAtPreferred;
2259 }
2260 }
2261
2262 shiftConstraints(constraints, -g_offset);
2263 return feasible;
2264}
2265
2266/*!
2267 \internal
2268
2269 Traverse the graph refreshing the size hints. Edges will query their associated
2270 item or graphicsAnchor for their size hints.
2271*/
2272void QGraphicsAnchorLayoutPrivate::refreshAllSizeHints(Qt::Orientation orientation)
2273{
2274 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
2275 QList<QPair<AnchorVertex *, AnchorVertex *>> vertices = g.connections();
2276
2277 QLayoutStyleInfo styleInf = styleInfo();
2278 for (int i = 0; i < vertices.count(); ++i) {
2279 AnchorData *data = g.edgeData(vertices.at(i).first, vertices.at(i).second);
2280 data->refreshSizeHints(&styleInf);
2281 }
2282}
2283
2284/*!
2285 \internal
2286
2287 This method walks the graph using a breadth-first search to find paths
2288 between the root vertex and each vertex on the graph. The edges
2289 directions in each path are considered and they are stored as a
2290 positive edge (left-to-right) or negative edge (right-to-left).
2291
2292 The list of paths is used later to generate a list of constraints.
2293 */
2294void QGraphicsAnchorLayoutPrivate::findPaths(Qt::Orientation orientation)
2295{
2296 QQueue<QPair<AnchorVertex *, AnchorVertex *> > queue;
2297
2298 QSet<AnchorData *> visited;
2299
2300 AnchorVertex *root = layoutFirstVertex[orientation];
2301
2302 graphPaths[orientation].insert(root, GraphPath());
2303
2304 const auto adjacentVertices = graph[orientation].adjacentVertices(root);
2305 for (AnchorVertex *v : adjacentVertices)
2306 queue.enqueue(qMakePair(root, v));
2307
2308 while(!queue.isEmpty()) {
2309 QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
2310 AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
2311
2312 if (visited.contains(edge))
2313 continue;
2314
2315 visited.insert(edge);
2316 GraphPath current = graphPaths[orientation].value(pair.first);
2317
2318 if (edge->from == pair.first)
2319 current.positives.insert(edge);
2320 else
2321 current.negatives.insert(edge);
2322
2323 graphPaths[orientation].insert(pair.second, current);
2324
2325 const auto adjacentVertices = graph[orientation].adjacentVertices(pair.second);
2326 for (AnchorVertex *v : adjacentVertices)
2327 queue.enqueue(qMakePair(pair.second, v));
2328 }
2329
2330 // We will walk through every reachable items (non-float) store them in a temporary set.
2331 // We them create a set of all items and subtract the non-floating items from the set in
2332 // order to get the floating items. The floating items is then stored in m_floatItems
2333 identifyFloatItems(visited, orientation);
2334}
2335
2336/*!
2337 \internal
2338
2339 Each vertex on the graph that has more than one path to it
2340 represents a contra int to the sizes of the items in these paths.
2341
2342 This method walks the list of paths to each vertex, generate
2343 the constraints and store them in a list so they can be used later
2344 by the Simplex solver.
2345*/
2346void QGraphicsAnchorLayoutPrivate::constraintsFromPaths(Qt::Orientation orientation)
2347{
2348 const auto vertices = graphPaths[orientation].uniqueKeys();
2349 for (AnchorVertex *vertex : vertices) {
2350 int valueCount = graphPaths[orientation].count(vertex);
2351 if (valueCount == 1)
2352 continue;
2353
2354 QList<GraphPath> pathsToVertex = graphPaths[orientation].values(vertex);
2355 for (int i = 1; i < valueCount; ++i) {
2356 constraints[orientation] += \
2357 pathsToVertex[0].constraint(pathsToVertex.at(i));
2358 }
2359 }
2360}
2361
2362/*!
2363 \internal
2364*/
2365void QGraphicsAnchorLayoutPrivate::updateAnchorSizes(Qt::Orientation orientation)
2366{
2367 Graph<AnchorVertex, AnchorData> &g = graph[orientation];
2368 const QList<QPair<AnchorVertex *, AnchorVertex *>> &vertices = g.connections();
2369
2370 for (int i = 0; i < vertices.count(); ++i) {
2371 AnchorData *ad = g.edgeData(vertices.at(i).first, vertices.at(i).second);
2372 ad->updateChildrenSizes();
2373 }
2374}
2375
2376/*!
2377 \internal
2378
2379 Create LP constraints for each anchor based on its minimum and maximum
2380 sizes, as specified in its size hints
2381*/
2382QList<QSimplexConstraint *> QGraphicsAnchorLayoutPrivate::constraintsFromSizeHints(
2383 const QList<AnchorData *> &anchors)
2384{
2385 if (anchors.isEmpty())
2386 return QList<QSimplexConstraint *>();
2387
2388 // Look for the layout edge. That can be either the first half in case the
2389 // layout is split in two, or the whole layout anchor.
2390 const Qt::Orientation orient = anchors.first()->isVertical ? Qt::Vertical : Qt::Horizontal;
2391 AnchorData *layoutEdge = nullptr;
2392 if (layoutCentralVertex[orient]) {
2393 layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutCentralVertex[orient]);
2394 } else {
2395 layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutLastVertex[orient]);
2396 }
2397
2398 // If maxSize is less then "infinite", that means there are other anchors
2399 // grouped together with this one. We can't ignore its maximum value so we
2400 // set back the variable to NULL to prevent the continue condition from being
2401 // satisfied in the loop below.
2402 const qreal expectedMax = layoutCentralVertex[orient] ? QWIDGETSIZE_MAX / 2 : QWIDGETSIZE_MAX;
2403 qreal actualMax;
2404 if (layoutEdge->from == layoutFirstVertex[orient]) {
2405 actualMax = layoutEdge->maxSize;
2406 } else {
2407 actualMax = -layoutEdge->minSize;
2408 }
2409 if (actualMax != expectedMax) {
2410 layoutEdge = nullptr;
2411 }
2412
2413 // For each variable, create constraints based on size hints
2414 QList<QSimplexConstraint *> anchorConstraints;
2415 bool unboundedProblem = true;
2416 for (int i = 0; i < anchors.size(); ++i) {
2417 AnchorData *ad = anchors.at(i);
2418
2419 // Anchors that have their size directly linked to another one don't need constraints
2420 // For exammple, the second half of an item has exactly the same size as the first half
2421 // thus constraining the latter is enough.
2422 if (ad->dependency == AnchorData::Slave)
2423 continue;
2424
2425 // To use negative variables inside simplex, we shift them so the minimum negative value is
2426 // mapped to zero before solving. To make sure that it works, we need to guarantee that the
2427 // variables are all inside a certain boundary.
2428 qreal boundedMin = qBound(-g_offset, ad->minSize, g_offset);
2429 qreal boundedMax = qBound(-g_offset, ad->maxSize, g_offset);
2430
2431 if ((boundedMin == boundedMax) || qFuzzyCompare(boundedMin, boundedMax)) {
2432 QSimplexConstraint *c = new QSimplexConstraint;
2433 c->variables.insert(ad, 1.0);
2434 c->constant = boundedMin;
2435 c->ratio = QSimplexConstraint::Equal;
2436 anchorConstraints += c;
2437 unboundedProblem = false;
2438 } else {
2439 QSimplexConstraint *c = new QSimplexConstraint;
2440 c->variables.insert(ad, 1.0);
2441 c->constant = boundedMin;
2442 c->ratio = QSimplexConstraint::MoreOrEqual;
2443 anchorConstraints += c;
2444
2445 // We avoid adding restrictions to the layout internal anchors. That's
2446 // to prevent unnecessary fair distribution from happening due to this
2447 // artificial restriction.
2448 if (ad == layoutEdge)
2449 continue;
2450
2451 c = new QSimplexConstraint;
2452 c->variables.insert(ad, 1.0);
2453 c->constant = boundedMax;
2454 c->ratio = QSimplexConstraint::LessOrEqual;
2455 anchorConstraints += c;
2456 unboundedProblem = false;
2457 }
2458 }
2459
2460 // If no upper boundary restriction was added, add one to avoid unbounded problem
2461 if (unboundedProblem) {
2462 QSimplexConstraint *c = new QSimplexConstraint;
2463 c->variables.insert(layoutEdge, 1.0);
2464 // The maximum size that the layout can take
2465 c->constant = g_offset;
2466 c->ratio = QSimplexConstraint::LessOrEqual;
2467 anchorConstraints += c;
2468 }
2469
2470 return anchorConstraints;
2471}
2472
2473/*!
2474 \internal
2475*/
2476QGraphicsAnchorLayoutPrivate::GraphParts
2477QGraphicsAnchorLayoutPrivate::getGraphParts(Qt::Orientation orientation)
2478{
2479 GraphParts result;
2480
2481 Q_ASSERT(layoutFirstVertex[orientation] && layoutLastVertex[orientation]);
2482
2483 AnchorData *edgeL1 = nullptr;
2484 AnchorData *edgeL2 = nullptr;
2485
2486 // The layout may have a single anchor between Left and Right or two half anchors
2487 // passing through the center
2488 if (layoutCentralVertex[orientation]) {
2489 edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutCentralVertex[orientation]);
2490 edgeL2 = graph[orientation].edgeData(layoutCentralVertex[orientation], layoutLastVertex[orientation]);
2491 } else {
2492 edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutLastVertex[orientation]);
2493 }
2494
2495 result.nonTrunkConstraints = constraints[orientation] + itemCenterConstraints[orientation];
2496
2497 QSet<QSimplexVariable *> trunkVariables;
2498
2499 trunkVariables += edgeL1;
2500 if (edgeL2)
2501 trunkVariables += edgeL2;
2502
2503 bool dirty;
2504 auto end = result.nonTrunkConstraints.end();
2505 do {
2506 dirty = false;
2507
2508 auto isMatch = [&result, &trunkVariables](QSimplexConstraint *c) -> bool {
2509 bool match = false;
2510
2511 // Check if this constraint have some overlap with current
2512 // trunk variables...
2513 for (QSimplexVariable *ad : qAsConst(trunkVariables)) {
2514 if (c->variables.contains(ad)) {
2515 match = true;
2516 break;
2517 }
2518 }
2519
2520 // If so, we add it to trunk, and erase it from the
2521 // remaining constraints.
2522 if (match) {
2523 result.trunkConstraints += c;
2524 for (auto jt = c->variables.cbegin(), end = c->variables.cend(); jt != end; ++jt)
2525 trunkVariables.insert(jt.key());
2526 return true;
2527 } else {
2528 // Note that we don't erase the constraint if it's not
2529 // a match, since in a next iteration of a do-while we
2530 // can pass on it again and it will be a match.
2531 //
2532 // For example: if trunk share a variable with
2533 // remainingConstraints[1] and it shares with
2534 // remainingConstraints[0], we need a second iteration
2535 // of the do-while loop to match both.
2536 return false;
2537 }
2538 };
2539 const auto newEnd = std::remove_if(result.nonTrunkConstraints.begin(), end, isMatch);
2540 dirty = newEnd != end;
2541 end = newEnd;
2542 } while (dirty);
2543
2544 result.nonTrunkConstraints.erase(end, result.nonTrunkConstraints.end());
2545
2546 return result;
2547}
2548
2549/*!
2550 \internal
2551
2552 Use all visited Anchors on findPaths() so we can identify non-float Items.
2553*/
2554void QGraphicsAnchorLayoutPrivate::identifyFloatItems(const QSet<AnchorData *> &visited, Qt::Orientation orientation)
2555{
2556 QSet<QGraphicsLayoutItem *> nonFloating;
2557
2558 for (const AnchorData *ad : visited)
2559 identifyNonFloatItems_helper(ad, &nonFloating);
2560
2561 QSet<QGraphicsLayoutItem *> floatItems;
2562 for (QGraphicsLayoutItem *item : qAsConst(items)) {
2563 if (!nonFloating.contains(item))
2564 floatItems.insert(item);
2565 }
2566 m_floatItems[orientation] = std::move(floatItems);
2567}
2568
2569
2570/*!
2571 \internal
2572
2573 Given an anchor, if it is an internal anchor and Normal we must mark it's item as non-float.
2574 If the anchor is Sequential or Parallel, we must iterate on its children recursively until we reach
2575 internal anchors (items).
2576*/
2577void QGraphicsAnchorLayoutPrivate::identifyNonFloatItems_helper(const AnchorData *ad, QSet<QGraphicsLayoutItem *> *nonFloatingItemsIdentifiedSoFar)
2578{
2579 Q_Q(QGraphicsAnchorLayout);
2580
2581 switch(ad->type) {
2582 case AnchorData::Normal:
2583 if (ad->item && ad->item != q)
2584 nonFloatingItemsIdentifiedSoFar->insert(ad->item);
2585 break;
2586 case AnchorData::Sequential:
2587 foreach (const AnchorData *d, static_cast<const SequentialAnchorData *>(ad)->m_edges)
2588 identifyNonFloatItems_helper(d, nonFloatingItemsIdentifiedSoFar);
2589 break;
2590 case AnchorData::Parallel:
2591 identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->firstEdge, nonFloatingItemsIdentifiedSoFar);
2592 identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->secondEdge, nonFloatingItemsIdentifiedSoFar);
2593 break;
2594 }
2595}
2596
2597/*!
2598 \internal
2599
2600 Use the current vertices distance to calculate and set the geometry of
2601 each item.
2602*/
2603void QGraphicsAnchorLayoutPrivate::setItemsGeometries(const QRectF &geom)
2604{
2605 Q_Q(QGraphicsAnchorLayout);
2606 AnchorVertex *firstH, *secondH, *firstV, *secondV;
2607
2608 qreal top;
2609 qreal left;
2610 qreal right;
2611
2612 q->getContentsMargins(&left, &top, &right, nullptr);
2613 const Qt::LayoutDirection visualDir = visualDirection();
2614 if (visualDir == Qt::RightToLeft)
2615 qSwap(left, right);
2616
2617 left += geom.left();
2618 top += geom.top();
2619 right = geom.right() - right;
2620
2621 for (QGraphicsLayoutItem *item : qAsConst(items)) {
2622 QRectF newGeom;
2623 QSizeF itemPreferredSize = item->effectiveSizeHint(Qt::PreferredSize);
2624 if (m_floatItems[Qt::Horizontal].contains(item)) {
2625 newGeom.setLeft(0);
2626 newGeom.setRight(itemPreferredSize.width());
2627 } else {
2628 firstH = internalVertex(item, Qt::AnchorLeft);
2629 secondH = internalVertex(item, Qt::AnchorRight);
2630
2631 if (visualDir == Qt::LeftToRight) {
2632 newGeom.setLeft(left + firstH->distance);
2633 newGeom.setRight(left + secondH->distance);
2634 } else {
2635 newGeom.setLeft(right - secondH->distance);
2636 newGeom.setRight(right - firstH->distance);
2637 }
2638 }
2639
2640 if (m_floatItems[Qt::Vertical].contains(item)) {
2641 newGeom.setTop(0);
2642 newGeom.setBottom(itemPreferredSize.height());
2643 } else {
2644 firstV = internalVertex(item, Qt::AnchorTop);
2645 secondV = internalVertex(item, Qt::AnchorBottom);
2646
2647 newGeom.setTop(top + firstV->distance);
2648 newGeom.setBottom(top + secondV->distance);
2649 }
2650
2651 item->setGeometry(newGeom);
2652 }
2653}
2654
2655/*!
2656 \internal
2657
2658 Calculate the position of each vertex based on the paths to each of
2659 them as well as the current edges sizes.
2660*/
2661void QGraphicsAnchorLayoutPrivate::calculateVertexPositions(Qt::Orientation orientation)
2662{
2663 QQueue<QPair<AnchorVertex *, AnchorVertex *> > queue;
2664 QSet<AnchorVertex *> visited;
2665
2666 // Get root vertex
2667 AnchorVertex *root = layoutFirstVertex[orientation];
2668
2669 root->distance = 0;
2670 visited.insert(root);
2671
2672 // Add initial edges to the queue
2673 const auto adjacentVertices = graph[orientation].adjacentVertices(root);
2674 for (AnchorVertex *v : adjacentVertices)
2675 queue.enqueue(qMakePair(root, v));
2676
2677 // Do initial calculation required by "interpolateEdge()"
2678 setupEdgesInterpolation(orientation);
2679
2680 // Traverse the graph and calculate vertex positions
2681 while (!queue.isEmpty()) {
2682 QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
2683 AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
2684
2685 if (visited.contains(pair.second))
2686 continue;
2687
2688 visited.insert(pair.second);
2689 interpolateEdge(pair.first, edge);
2690
2691 QList<AnchorVertex *> adjacents = graph[orientation].adjacentVertices(pair.second);
2692 for (int i = 0; i < adjacents.count(); ++i) {
2693 if (!visited.contains(adjacents.at(i)))
2694 queue.enqueue(qMakePair(pair.second, adjacents.at(i)));
2695 }
2696 }
2697}
2698
2699/*!
2700 \internal
2701
2702 Calculate interpolation parameters based on current Layout Size.
2703 Must be called once before calling "interpolateEdgeSize()" for
2704 the edges.
2705*/
2706void QGraphicsAnchorLayoutPrivate::setupEdgesInterpolation(
2707 Qt::Orientation orientation)
2708{
2709 Q_Q(QGraphicsAnchorLayout);
2710
2711 qreal current;
2712 current = (orientation == Qt::Horizontal) ? q->contentsRect().width() : q->contentsRect().height();
2713
2714 QPair<Interval, qreal> result;
2715 result = getFactor(current,
2716 sizeHints[orientation][Qt::MinimumSize],
2717 sizeHints[orientation][Qt::PreferredSize],
2718 sizeHints[orientation][Qt::PreferredSize],
2719 sizeHints[orientation][Qt::PreferredSize],
2720 sizeHints[orientation][Qt::MaximumSize]);
2721
2722 interpolationInterval[orientation] = result.first;
2723 interpolationProgress[orientation] = result.second;
2724}
2725
2726/*!
2727 \internal
2728
2729 Calculate the current Edge size based on the current Layout size and the
2730 size the edge is supposed to have when the layout is at its:
2731
2732 - minimum size,
2733 - preferred size,
2734 - maximum size.
2735
2736 These three key values are calculated in advance using linear
2737 programming (more expensive) or the simplification algorithm, then
2738 subsequential resizes of the parent layout require a simple
2739 interpolation.
2740*/
2741void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base, AnchorData *edge)
2742{
2743 const Qt::Orientation orientation = edge->isVertical ? Qt::Vertical : Qt::Horizontal;
2744 const QPair<Interval, qreal> factor(interpolationInterval[orientation],
2745 interpolationProgress[orientation]);
2746
2747 qreal edgeDistance = interpolate(factor, edge->sizeAtMinimum, edge->sizeAtPreferred,
2748 edge->sizeAtPreferred, edge->sizeAtPreferred,
2749 edge->sizeAtMaximum);
2750
2751 Q_ASSERT(edge->from == base || edge->to == base);
2752
2753 // Calculate the distance for the vertex opposite to the base
2754 if (edge->from == base) {
2755 edge->to->distance = base->distance + edgeDistance;
2756 } else {
2757 edge->from->distance = base->distance - edgeDistance;
2758 }
2759}
2760
2761bool QGraphicsAnchorLayoutPrivate::solveMinMax(const QList<QSimplexConstraint *> &constraints,
2762 const GraphPath &path, qreal *min, qreal *max)
2763{
2764 QSimplex simplex;
2765 bool feasible = simplex.setConstraints(constraints);
2766 if (feasible) {
2767 // Obtain the objective constraint
2768 QSimplexConstraint objective;
2769 QSet<AnchorData *>::const_iterator iter;
2770 for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter)
2771 objective.variables.insert(*iter, 1.0);
2772
2773 for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter)
2774 objective.variables.insert(*iter, -1.0);
2775
2776 const qreal objectiveOffset = (path.positives.count() - path.negatives.count()) * g_offset;
2777 simplex.setObjective(&objective);
2778
2779 // Calculate minimum values
2780 *min = simplex.solveMin() - objectiveOffset;
2781
2782 // Save sizeAtMinimum results
2783 QList<AnchorData *> variables = getVariables(constraints);
2784 for (int i = 0; i < variables.size(); ++i) {
2785 AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
2786 ad->sizeAtMinimum = ad->result - g_offset;
2787 }
2788
2789 // Calculate maximum values
2790 *max = simplex.solveMax() - objectiveOffset;
2791
2792 // Save sizeAtMaximum results
2793 for (int i = 0; i < variables.size(); ++i) {
2794 AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
2795 ad->sizeAtMaximum = ad->result - g_offset;
2796 }
2797 }
2798 return feasible;
2799}
2800
2801enum slackType { Grower = -1, Shrinker = 1 };
2802static QPair<QSimplexVariable *, QSimplexConstraint *> createSlack(QSimplexConstraint *sizeConstraint,
2803 qreal interval, slackType type)
2804{
2805 QSimplexVariable *slack = new QSimplexVariable;
2806 sizeConstraint->variables.insert(slack, type);
2807
2808 QSimplexConstraint *limit = new QSimplexConstraint;
2809 limit->variables.insert(slack, 1.0);
2810 limit->ratio = QSimplexConstraint::LessOrEqual;
2811 limit->constant = interval;
2812
2813 return qMakePair(slack, limit);
2814}
2815
2816bool QGraphicsAnchorLayoutPrivate::solvePreferred(const QList<QSimplexConstraint *> &constraints,
2817 const QList<AnchorData *> &variables)
2818{
2819 QList<QSimplexConstraint *> preferredConstraints;
2820 QList<QSimplexVariable *> preferredVariables;
2821 QSimplexConstraint objective;
2822
2823 // Fill the objective coefficients for this variable. In the
2824 // end the objective function will be
2825 //
2826 // z = n * (A_shrinker_hard + A_grower_hard + B_shrinker_hard + B_grower_hard + ...) +
2827 // (A_shrinker_soft + A_grower_soft + B_shrinker_soft + B_grower_soft + ...)
2828 //
2829 // where n is the number of variables that have
2830 // slacks. Note that here we use the number of variables
2831 // as coefficient, this is to mark the "shrinker slack
2832 // variable" less likely to get value than the "grower
2833 // slack variable".
2834
2835 // This will fill the values for the structural constraints
2836 // and we now fill the values for the slack constraints (one per variable),
2837 // which have this form (the constant A_pref was set when creating the slacks):
2838 //
2839 // A + A_shrinker_hard + A_shrinker_soft - A_grower_hard - A_grower_soft = A_pref
2840 //
2841 for (int i = 0; i < variables.size(); ++i) {
2842 AnchorData *ad = variables.at(i);
2843
2844 // The layout original structure anchors are not relevant in preferred size calculation
2845 if (ad->isLayoutAnchor)
2846 continue;
2847
2848 // By default, all variables are equal to their preferred size. If they have room to
2849 // grow or shrink, such flexibility will be added by the additional variables below.
2850 QSimplexConstraint *sizeConstraint = new QSimplexConstraint;
2851 preferredConstraints += sizeConstraint;
2852 sizeConstraint->variables.insert(ad, 1.0);
2853 sizeConstraint->constant = ad->prefSize + g_offset;
2854
2855 // Can easily shrink
2856 QPair<QSimplexVariable *, QSimplexConstraint *> slack;
2857 const qreal softShrinkInterval = ad->prefSize - ad->minPrefSize;
2858 if (softShrinkInterval) {
2859 slack = createSlack(sizeConstraint, softShrinkInterval, Shrinker);
2860 preferredVariables += slack.first;
2861 preferredConstraints += slack.second;
2862
2863 // Add to objective with ratio == 1 (soft)
2864 objective.variables.insert(slack.first, 1.0);
2865 }
2866
2867 // Can easily grow
2868 const qreal softGrowInterval = ad->maxPrefSize - ad->prefSize;
2869 if (softGrowInterval) {
2870 slack = createSlack(sizeConstraint, softGrowInterval, Grower);
2871 preferredVariables += slack.first;
2872 preferredConstraints += slack.second;
2873
2874 // Add to objective with ratio == 1 (soft)
2875 objective.variables.insert(slack.first, 1.0);
2876 }
2877
2878 // Can shrink if really necessary
2879 const qreal hardShrinkInterval = ad->minPrefSize - ad->minSize;
2880 if (hardShrinkInterval) {
2881 slack = createSlack(sizeConstraint, hardShrinkInterval, Shrinker);
2882 preferredVariables += slack.first;
2883 preferredConstraints += slack.second;
2884
2885 // Add to objective with ratio == N (hard)
2886 objective.variables.insert(slack.first, variables.size());
2887 }
2888
2889 // Can grow if really necessary
2890 const qreal hardGrowInterval = ad->maxSize - ad->maxPrefSize;
2891 if (hardGrowInterval) {
2892 slack = createSlack(sizeConstraint, hardGrowInterval, Grower);
2893 preferredVariables += slack.first;
2894 preferredConstraints += slack.second;
2895
2896 // Add to objective with ratio == N (hard)
2897 objective.variables.insert(slack.first, variables.size());
2898 }
2899 }
2900
2901 QSimplex *simplex = new QSimplex;
2902 bool feasible = simplex->setConstraints(constraints + preferredConstraints);
2903 if (feasible) {
2904 simplex->setObjective(&objective);
2905
2906 // Calculate minimum values
2907 simplex->solveMin();
2908
2909 // Save sizeAtPreferred results
2910 for (int i = 0; i < variables.size(); ++i) {
2911 AnchorData *ad = variables.at(i);
2912 ad->sizeAtPreferred = ad->result - g_offset;
2913 }
2914 }
2915
2916 // Make sure we delete the simplex solver -before- we delete the
2917 // constraints used by it.
2918 delete simplex;
2919
2920 // Delete constraints and variables we created.
2921 qDeleteAll(preferredConstraints);
2922 qDeleteAll(preferredVariables);
2923
2924 return feasible;
2925}
2926
2927/*!
2928 \internal
2929 Returns \c true if there are no arrangement that satisfies all constraints.
2930 Otherwise returns \c false.
2931
2932 \sa addAnchor()
2933*/
2934bool QGraphicsAnchorLayoutPrivate::hasConflicts() const
2935{
2936 QGraphicsAnchorLayoutPrivate *that = const_cast<QGraphicsAnchorLayoutPrivate*>(this);
2937 that->calculateGraphs();
2938
2939 bool floatConflict = !m_floatItems[Qt::Horizontal].isEmpty() || !m_floatItems[Qt::Vertical].isEmpty();
2940
2941 return graphHasConflicts[Qt::Horizontal] || graphHasConflicts[Qt::Vertical] || floatConflict;
2942}
2943
2944#ifdef QT_DEBUG
2945void QGraphicsAnchorLayoutPrivate::dumpGraph(const QString &name)
2946{
2947 QFile file(QString::fromLatin1("anchorlayout.%1.dot").arg(name));
2948 if (!file.open(QIODevice::WriteOnly | QIODevice::Text | QIODevice::Truncate))
2949 qWarning("Could not write to %ls", qUtf16Printable(file.fileName()));
2950
2951 QString str = QString::fromLatin1("digraph anchorlayout {\nnode [shape=\"rect\"]\n%1}");
2952 QString dotContents = graph[Qt::Horizontal].serializeToDot();
2953 dotContents += graph[Qt::Vertical].serializeToDot();
2954 file.write(str.arg(dotContents).toLocal8Bit());
2955
2956 file.close();
2957}
2958#endif
2959
2960QT_END_NAMESPACE
2961