1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QGRAPHICSANCHORLAYOUT_P_H
5#define QGRAPHICSANCHORLAYOUT_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtWidgets/private/qtwidgetsglobal_p.h>
19#include <QGraphicsWidget>
20#include <private/qobject_p.h>
21
22#include "qgraphicslayout_p.h"
23#include "qgraphicsanchorlayout.h"
24#include "qgraph_p.h"
25#include "qsimplex_p.h"
26
27#include <QtGui/private/qgridlayoutengine_p.h>
28
29#include <array>
30
31QT_REQUIRE_CONFIG(graphicsview);
32
33QT_BEGIN_NAMESPACE
34
35/*
36 The public QGraphicsAnchorLayout interface represents an anchorage point
37 as a pair of a <QGraphicsLayoutItem *> and a <Qt::AnchorPoint>.
38
39 Internally though, it has a graph of anchorage points (vertices) and
40 anchors (edges), represented by the AnchorVertex and AnchorData structs
41 respectively.
42*/
43
44namespace QtGraphicsAnchorLayout {
45/*!
46 \internal
47
48 Represents a vertex (anchorage point) in the internal graph
49*/
50struct AnchorVertex
51{
52 AnchorVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
53 : m_item(item), m_edge(edge) {}
54
55 AnchorVertex()
56 : m_item(nullptr), m_edge(Qt::AnchorPoint(0)) {}
57
58 virtual ~AnchorVertex() = default;
59
60#ifdef QT_DEBUG
61 virtual inline QString toString() const;
62#endif
63
64 QGraphicsLayoutItem *m_item;
65 Qt::AnchorPoint m_edge;
66
67 // Current distance from this vertex to the layout edge (Left or Top)
68 // Value is calculated from the current anchors sizes.
69 qreal distance;
70};
71
72/*!
73 \internal
74
75 Represents an edge (anchor) in the internal graph.
76*/
77struct AnchorData : public QSimplexVariable {
78 enum Type {
79 Normal = 0,
80 Sequential,
81 Parallel
82 };
83
84 enum Dependency {
85 Independent = 0,
86 Master,
87 Slave
88 };
89
90 AnchorData()
91 : QSimplexVariable(), from(nullptr), to(nullptr),
92 minSize(0), prefSize(0), maxSize(0),
93 minPrefSize(0), maxPrefSize(0),
94 sizeAtMinimum(0), sizeAtPreferred(0),
95 sizeAtMaximum(0), item(nullptr), graphicsAnchor(nullptr),
96 type(Normal), isLayoutAnchor(false),
97 isCenterAnchor(false), isVertical(false),
98 dependency(Independent) {}
99 virtual ~AnchorData();
100
101 virtual void updateChildrenSizes() {}
102 void refreshSizeHints(const QLayoutStyleInfo *styleInfo = nullptr);
103
104#ifdef QT_DEBUG
105 void dump(int indent = 2);
106 inline QString toString() const;
107 QString name;
108#endif
109
110 // Anchor is semantically directed
111 AnchorVertex *from;
112 AnchorVertex *to;
113
114 // Nominal sizes
115 // These are the intrinsic size restrictions for a given item. They are
116 // used as input for the calculation of the actual sizes.
117 // These values are filled by the refreshSizeHints method, based on the
118 // anchor size policy, the size hints of the item it (possibly) represents
119 // and the layout spacing information.
120 qreal minSize;
121 qreal prefSize;
122 qreal maxSize;
123
124 qreal minPrefSize;
125 qreal maxPrefSize;
126
127 // Calculated sizes
128 // These attributes define which sizes should that anchor be in when the
129 // layout is at its minimum, preferred or maximum sizes. Values are
130 // calculated by the Simplex solver based on the current layout setup.
131 qreal sizeAtMinimum;
132 qreal sizeAtPreferred;
133 qreal sizeAtMaximum;
134
135 // References to the classes that represent this anchor in the public world
136 // An anchor may represent a LayoutItem, it may also be accessible externally
137 // through a GraphicsAnchor "handler".
138 QGraphicsLayoutItem *item;
139 QGraphicsAnchor *graphicsAnchor;
140
141 uint type : 2; // either Normal, Sequential or Parallel
142 uint isLayoutAnchor : 1; // if this anchor is an internal layout anchor
143 uint isCenterAnchor : 1;
144 uint isVertical : 1;
145 uint dependency : 2; // either Independent, Master or Slave
146};
147
148#ifdef QT_DEBUG
149inline QString AnchorData::toString() const
150{
151 return QString::fromLatin1(ba: "Anchor(%1)").arg(a: name);
152}
153#endif
154
155struct SequentialAnchorData : public AnchorData
156{
157 SequentialAnchorData(const QList<AnchorVertex *> &vertices, const QList<AnchorData *> &edges)
158 : AnchorData(), m_children(vertices), m_edges(edges)
159 {
160 type = AnchorData::Sequential;
161 isVertical = m_edges.at(i: 0)->isVertical;
162#ifdef QT_DEBUG
163 name = QString::fromLatin1(ba: "%1 -- %2").arg(args: vertices.first()->toString(), args: vertices.last()->toString());
164#endif
165 }
166
167 virtual void updateChildrenSizes() override;
168 void calculateSizeHints();
169
170 QList<AnchorVertex *> m_children; // list of vertices in the sequence
171 QList<AnchorData *> m_edges; // keep the list of edges too.
172};
173
174struct ParallelAnchorData : public AnchorData
175{
176 ParallelAnchorData(AnchorData *first, AnchorData *second)
177 : AnchorData(), firstEdge(first), secondEdge(second)
178 {
179 type = AnchorData::Parallel;
180 isVertical = first->isVertical;
181
182 // This assert whether the child anchors share their vertices
183 Q_ASSERT(((first->from == second->from) && (first->to == second->to)) ||
184 ((first->from == second->to) && (first->to == second->from)));
185
186 // Our convention will be that the parallel group anchor will have the same
187 // direction as the first anchor.
188 from = first->from;
189 to = first->to;
190#ifdef QT_DEBUG
191 name = QString::fromLatin1(ba: "%1 | %2").arg(args: first->toString(), args: second->toString());
192#endif
193 }
194
195 virtual void updateChildrenSizes() override;
196 bool calculateSizeHints();
197
198 bool secondForward() const {
199 // We have the convention that the first children will define the direction of the
200 // pararell group. Note that we can't rely on 'this->from' or 'this->to' because they
201 // might be changed by vertex simplification.
202 return firstEdge->from == secondEdge->from;
203 }
204
205 AnchorData* firstEdge;
206 AnchorData* secondEdge;
207
208 QList<QSimplexConstraint *> m_firstConstraints;
209 QList<QSimplexConstraint *> m_secondConstraints;
210};
211
212struct AnchorVertexPair : public AnchorVertex {
213 AnchorVertexPair(AnchorVertex *v1, AnchorVertex *v2, AnchorData *data)
214 : AnchorVertex(), m_first(v1), m_second(v2), m_removedAnchor(data)
215 {
216 }
217
218 AnchorVertex *m_first;
219 AnchorVertex *m_second;
220
221 AnchorData *m_removedAnchor;
222 QList<AnchorData *> m_firstAnchors;
223 QList<AnchorData *> m_secondAnchors;
224
225#ifdef QT_DEBUG
226 inline QString toString() const override
227 {
228 return QString::fromLatin1(ba: "(%1, %2)").arg(args: m_first->toString(), args: m_second->toString());
229 }
230#endif
231};
232
233#ifdef QT_DEBUG
234inline QString AnchorVertex::toString() const
235{
236 using namespace Qt::StringLiterals;
237
238 if (!m_item)
239 return QString::fromLatin1(ba: "NULL_%1").arg(a: quintptr(this));
240
241 QString edge;
242 switch (m_edge) {
243 case Qt::AnchorLeft:
244 edge = "Left"_L1;
245 break;
246 case Qt::AnchorHorizontalCenter:
247 edge = "HorizontalCenter"_L1;
248 break;
249 case Qt::AnchorRight:
250 edge = "Right"_L1;
251 break;
252 case Qt::AnchorTop:
253 edge = "Top"_L1;
254 break;
255 case Qt::AnchorVerticalCenter:
256 edge = "VerticalCenter"_L1;
257 break;
258 case Qt::AnchorBottom:
259 edge = "Bottom"_L1;
260 break;
261 default:
262 edge = "None"_L1;
263 break;
264 }
265 QString itemName;
266 if (m_item->isLayout()) {
267 itemName = "layout"_L1;
268 } else {
269 if (QGraphicsItem *item = m_item->graphicsItem()) {
270 itemName = item->data(key: 0).toString();
271 }
272 }
273 edge.insert(i: 0, s: "%1_"_L1);
274 return edge.arg(a: itemName);
275}
276#endif
277
278/*!
279 \internal
280
281 Representation of a valid path for a given vertex in the graph.
282 In this struct, "positives" is the set of anchors that have been
283 traversed in the forward direction, while "negatives" is the set
284 with the ones walked backwards.
285
286 This paths are compared against each other to produce LP Constraints,
287 the exact order in which the anchors were traversed is not relevant.
288*/
289class GraphPath
290{
291public:
292 GraphPath() {}
293
294 QSimplexConstraint *constraint(const GraphPath &path) const;
295#ifdef QT_DEBUG
296 QString toString() const;
297#endif
298 QSet<AnchorData *> positives;
299 QSet<AnchorData *> negatives;
300};
301} // namespace QtGraphicsAnchorLayout
302using namespace QtGraphicsAnchorLayout;
303
304Q_DECLARE_TYPEINFO(GraphPath, Q_RELOCATABLE_TYPE);
305
306class QGraphicsAnchorLayoutPrivate;
307/*!
308 \internal
309*/
310class QGraphicsAnchorPrivate : public QObjectPrivate
311{
312 Q_DECLARE_PUBLIC(QGraphicsAnchor)
313
314public:
315 explicit QGraphicsAnchorPrivate(int version = QObjectPrivateVersion);
316 ~QGraphicsAnchorPrivate();
317
318 void setSpacing(qreal value);
319 void unsetSpacing();
320 qreal spacing() const;
321
322 void setSizePolicy(QSizePolicy::Policy policy);
323
324 static QGraphicsAnchorPrivate *get(QGraphicsAnchor *q)
325 { return q->d_func(); }
326
327 QGraphicsAnchorLayoutPrivate *layoutPrivate;
328 AnchorData *data;
329
330 // Size information for user controlled anchor
331 QSizePolicy::Policy sizePolicy;
332 qreal preferredSize;
333
334 uint hasSize : 1; // if false, get size from style.
335};
336
337
338
339
340/*!
341 \internal
342
343 QGraphicsAnchorLayout private methods and attributes.
344*/
345class Q_AUTOTEST_EXPORT QGraphicsAnchorLayoutPrivate : public QGraphicsLayoutPrivate
346{
347 Q_DECLARE_PUBLIC(QGraphicsAnchorLayout)
348
349public:
350 // When the layout geometry is different from its Minimum, Preferred
351 // or Maximum values, interpolation is used to calculate the geometries
352 // of the items.
353 //
354 // Interval represents which interpolation interval are we operating in.
355 enum Interval {
356 MinimumToMinPreferred = 0,
357 MinPreferredToPreferred,
358 PreferredToMaxPreferred,
359 MaxPreferredToMaximum
360 };
361
362 typedef Qt::Orientation Orientation [[deprecated]];
363 [[deprecated]] static inline constexpr Qt::Orientation Horizontal = Qt::Horizontal;
364 [[deprecated]] static inline constexpr Qt::Orientation Vertical = Qt::Vertical;
365
366 QGraphicsAnchorLayoutPrivate();
367
368 static QGraphicsAnchorLayoutPrivate *get(QGraphicsAnchorLayout *q)
369 {
370 return q ? q->d_func() : nullptr;
371 }
372
373 static Qt::AnchorPoint oppositeEdge(
374 Qt::AnchorPoint edge);
375
376 static Qt::Orientation edgeOrientation(Qt::AnchorPoint edge) noexcept;
377
378 static Qt::AnchorPoint pickEdge(Qt::AnchorPoint edge, Qt::Orientation orientation)
379 {
380 if (orientation == Qt::Vertical && int(edge) <= 2)
381 return (Qt::AnchorPoint)(edge + 3);
382 else if (orientation == Qt::Horizontal && int(edge) >= 3) {
383 return (Qt::AnchorPoint)(edge - 3);
384 }
385 return edge;
386 }
387
388 // Init methods
389 void createLayoutEdges();
390 void deleteLayoutEdges();
391 void createItemEdges(QGraphicsLayoutItem *item);
392 void createCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge);
393 void removeCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge, bool substitute = true);
394 void removeCenterConstraints(QGraphicsLayoutItem *item, Qt::Orientation orientation);
395
396 QGraphicsAnchor *acquireGraphicsAnchor(AnchorData *data)
397 {
398 Q_Q(QGraphicsAnchorLayout);
399 if (!data->graphicsAnchor) {
400 data->graphicsAnchor = new QGraphicsAnchor(q);
401 data->graphicsAnchor->d_func()->data = data;
402 }
403 return data->graphicsAnchor;
404 }
405
406 // function used by the 4 API functions
407 QGraphicsAnchor *addAnchor(QGraphicsLayoutItem *firstItem,
408 Qt::AnchorPoint firstEdge,
409 QGraphicsLayoutItem *secondItem,
410 Qt::AnchorPoint secondEdge,
411 qreal *spacing = nullptr);
412
413 // Helper for Anchor Manipulation methods
414 void addAnchor_helper(QGraphicsLayoutItem *firstItem,
415 Qt::AnchorPoint firstEdge,
416 QGraphicsLayoutItem *secondItem,
417 Qt::AnchorPoint secondEdge,
418 AnchorData *data);
419
420 QGraphicsAnchor *getAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
421 QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge);
422
423 void removeAnchor(AnchorVertex *firstVertex, AnchorVertex *secondVertex);
424 void removeAnchor_helper(AnchorVertex *v1, AnchorVertex *v2);
425
426 void removeAnchors(QGraphicsLayoutItem *item);
427
428 void removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
429
430 void correctEdgeDirection(QGraphicsLayoutItem *&firstItem,
431 Qt::AnchorPoint &firstEdge,
432 QGraphicsLayoutItem *&secondItem,
433 Qt::AnchorPoint &secondEdge);
434
435 QLayoutStyleInfo &styleInfo() const;
436
437 AnchorData *addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible);
438
439 // Activation
440 void calculateGraphs();
441 void calculateGraphs(Qt::Orientation orientation);
442
443 // Simplification
444 bool simplifyGraph(Qt::Orientation orientation);
445 bool simplifyVertices(Qt::Orientation orientation);
446 bool simplifyGraphIteration(Qt::Orientation orientation, bool *feasible);
447
448 bool replaceVertex(Qt::Orientation orientation, AnchorVertex *oldV,
449 AnchorVertex *newV, const QList<AnchorData *> &edges);
450
451
452 void restoreSimplifiedGraph(Qt::Orientation orientation);
453 void restoreSimplifiedAnchor(AnchorData *edge);
454 void restoreSimplifiedConstraints(ParallelAnchorData *parallel);
455 void restoreVertices(Qt::Orientation orientation);
456
457 bool calculateTrunk(Qt::Orientation orientation, const GraphPath &trunkPath,
458 const QList<QSimplexConstraint *> &constraints,
459 const QList<AnchorData *> &variables);
460 bool calculateNonTrunk(const QList<QSimplexConstraint *> &constraints,
461 const QList<AnchorData *> &variables);
462
463 // Support functions for calculateGraph()
464 void refreshAllSizeHints(Qt::Orientation orientation);
465 void findPaths(Qt::Orientation orientation);
466 void constraintsFromPaths(Qt::Orientation orientation);
467 void updateAnchorSizes(Qt::Orientation orientation);
468 QList<QSimplexConstraint *> constraintsFromSizeHints(const QList<AnchorData *> &anchors);
469 struct GraphParts {
470 QList<QSimplexConstraint *> trunkConstraints;
471 QList<QSimplexConstraint *> nonTrunkConstraints;
472 };
473 GraphParts getGraphParts(Qt::Orientation orientation);
474 void identifyFloatItems(const QSet<AnchorData *> &visited, Qt::Orientation orientation);
475 void identifyNonFloatItems_helper(const AnchorData *ad, QSet<QGraphicsLayoutItem *> *nonFloatingItemsIdentifiedSoFar);
476
477 inline AnchorVertex *internalVertex(const QPair<QGraphicsLayoutItem*, Qt::AnchorPoint> &itemEdge) const
478 {
479 return m_vertexList.value(key: itemEdge).first;
480 }
481
482 inline AnchorVertex *internalVertex(const QGraphicsLayoutItem *item, Qt::AnchorPoint edge) const
483 {
484 return internalVertex(itemEdge: qMakePair(value1: const_cast<QGraphicsLayoutItem *>(item), value2&: edge));
485 }
486
487 inline void changeLayoutVertex(Qt::Orientation orientation, AnchorVertex *oldV, AnchorVertex *newV)
488 {
489 if (layoutFirstVertex[orientation] == oldV)
490 layoutFirstVertex[orientation] = newV;
491 else if (layoutCentralVertex[orientation] == oldV)
492 layoutCentralVertex[orientation] = newV;
493 else if (layoutLastVertex[orientation] == oldV)
494 layoutLastVertex[orientation] = newV;
495 }
496
497
498 AnchorVertex *addInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
499 void removeInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
500
501 // Geometry interpolation methods
502 void setItemsGeometries(const QRectF &geom);
503
504 void calculateVertexPositions(Qt::Orientation orientation);
505 void setupEdgesInterpolation(Qt::Orientation orientation);
506 void interpolateEdge(AnchorVertex *base, AnchorData *edge);
507
508 // Linear Programming solver methods
509 bool solveMinMax(const QList<QSimplexConstraint *> &constraints,
510 const GraphPath &path, qreal *min, qreal *max);
511 bool solvePreferred(const QList<QSimplexConstraint *> &constraints,
512 const QList<AnchorData *> &variables);
513 bool hasConflicts() const;
514
515#ifdef QT_DEBUG
516 void dumpGraph(const QString &name = QString());
517#endif
518
519
520 QHVContainer<qreal> spacings = {-1, -1};
521 // Size hints from simplex engine
522 QHVContainer<std::array<qreal, 3>> sizeHints = {{-1, -1, -1}, {-1, -1, -1}};
523
524 // Items
525 QList<QGraphicsLayoutItem *> items;
526
527 // Mapping between high level anchorage points (Item, Edge) to low level
528 // ones (Graph Vertices)
529
530 QHash<QPair<QGraphicsLayoutItem*, Qt::AnchorPoint>, QPair<AnchorVertex *, int> > m_vertexList;
531
532 // Internal graph of anchorage points and anchors, for both orientations
533 QHVContainer<Graph<AnchorVertex, AnchorData>> graph;
534
535 QHVContainer<AnchorVertex *> layoutFirstVertex = {};
536 QHVContainer<AnchorVertex *> layoutCentralVertex = {};
537 QHVContainer<AnchorVertex *> layoutLastVertex = {};
538
539 // Combined anchors in order of creation
540 QHVContainer<QList<AnchorVertexPair *>> simplifiedVertices;
541 QHVContainer<QList<AnchorData *>> anchorsFromSimplifiedVertices;
542
543 // Graph paths and constraints, for both orientations
544 QHVContainer<QMultiHash<AnchorVertex *, GraphPath>> graphPaths;
545 QHVContainer<QList<QSimplexConstraint *>> constraints;
546 QHVContainer<QList<QSimplexConstraint *>> itemCenterConstraints;
547
548 // The interpolation interval and progress based on the current size
549 // as well as the key values (minimum, preferred and maximum)
550 QHVContainer<Interval> interpolationInterval;
551 QHVContainer<qreal> interpolationProgress = {-1, -1};
552
553 QHVContainer<bool> graphHasConflicts = {};
554 QHVContainer<QSet<QGraphicsLayoutItem *>> m_floatItems;
555
556#if defined(QT_DEBUG) || defined(QT_BUILD_INTERNAL)
557 QHVContainer<bool> lastCalculationUsedSimplex;
558#endif
559
560 uint calculateGraphCacheDirty : 1;
561 mutable uint styleInfoDirty : 1;
562 mutable QLayoutStyleInfo cachedStyleInfo;
563
564 friend class QGraphicsAnchorPrivate;
565};
566
567QT_END_NAMESPACE
568
569#endif
570

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