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

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