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