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
16	QT_BEGIN_NAMESPACE
17
18	using 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.
26	const qreal g_offset = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32;
27
28	QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version)
29	: QObjectPrivate(version), layoutPrivate(nullptr), data(nullptr),
30	sizePolicy(QSizePolicy::Fixed), preferredSize(0),
31	hasSize(true)
32	{
33	}
34
35	QGraphicsAnchorPrivate::~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
46	void QGraphicsAnchorPrivate::setSizePolicy(QSizePolicy::Policy policy)
47	{
48	if (sizePolicy != policy) {
49	sizePolicy = policy;
50	layoutPrivate->q_func()->invalidate();
51	}
52	}
53
54	void 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
71	void 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
84	qreal 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
95	static 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
130	AnchorData::~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
142	void 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
234	void 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	*/
264	bool 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	*/
381	static 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
417	static 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
445	void 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
489	void 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
528	void 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
548	QSimplexConstraint *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
576	QString 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
591	QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()
592	: calculateGraphCacheDirty(true), styleInfoDirty(true)
593	{
594	}
595
596	Qt::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	*/
631	AnchorData *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	*/
701	static 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	*/
780	bool 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
824	static 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
837	bool 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	*/
871	bool 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	*/
984	bool 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
1140	void 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
1188	void 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
1214	void 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
1243	void 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
1314	Qt::Orientation
1315	QGraphicsAnchorLayoutPrivate::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	*/
1329	void 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
1357	void 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
1370	void 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	*/
1396	void 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
1461	void 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
1544	void 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	*/
1587	QGraphicsAnchor *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	*/
1681	void 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
1721	QGraphicsAnchor *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	*/
1756	void 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	*/
1830	void 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
1843	AnchorVertex *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	*/
1864	void 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
1892	void 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
1905	void 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	*/
1941	void 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
1970	QLayoutStyleInfo &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	*/
2005	void 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...
2016	QList<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	*/
2050	void 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	*/
2132	static 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	*/
2147	bool 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	*/
2215	bool 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	*/
2242	void 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	*/
2264	void 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	*/
2316	void 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	*/
2335	void 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	*/
2352	QList<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	*/
2446	QGraphicsAnchorLayoutPrivate::GraphParts
2447	QGraphicsAnchorLayoutPrivate::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	*/
2524	void 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	*/
2547	void 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	*/
2573	void 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	*/
2631	void 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	*/
2676	void 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	*/
2711	void 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
2731	bool 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
2771	enum slackType { Grower = -1, Shrinker = 1 };
2772	static 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
2786	bool 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	*/
2904	bool 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
2915	void 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
2930	QT_END_NAMESPACE
2931