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

source code of qtbase/src/widgets/graphicsview/qgraphicsanchorlayout_p.cpp