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