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