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