Qt 4.8
qgraphicsanchorlayout_p.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
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 Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/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 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include <QtGui/qwidget.h>
43 #include <QtGui/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 
52 
53 #ifndef QT_NO_GRAPHICSVIEW
55 
56 // To ensure that all variables inside the simplex solver are non-negative,
57 // we limit the size of anchors in the interval [-limit, limit]. Then before
58 // sending them to the simplex solver we add "limit" as an offset, so that
59 // they are actually calculated in the interval [0, 2 * limit]
60 // To avoid numerical errors in platforms where we use single precision,
61 // we use a tighter limit for the variables range.
62 const qreal g_offset = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32;
63 
65  : QObjectPrivate(version), layoutPrivate(0), data(0),
66  sizePolicy(QSizePolicy::Fixed), preferredSize(0),
67  hasSize(true)
68 {
69 }
70 
72 {
73  if (data) {
74  // The QGraphicsAnchor was already deleted at this moment. We must clean
75  // the dangling pointer to avoid double deletion in the AnchorData dtor.
76  data->graphicsAnchor = 0;
77 
79  }
80 }
81 
83 {
84  if (sizePolicy != policy) {
85  sizePolicy = policy;
86  layoutPrivate->q_func()->invalidate();
87  }
88 }
89 
91 {
92  if (!data) {
93  qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
94  return;
95  }
96 
97  if (hasSize && (preferredSize == value))
98  return;
99 
100  // The anchor has an user-defined size
101  hasSize = true;
102  preferredSize = value;
103 
104  layoutPrivate->q_func()->invalidate();
105 }
106 
108 {
109  if (!data) {
110  qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
111  return;
112  }
113 
114  // Return to standard direction
115  hasSize = false;
116 
117  layoutPrivate->q_func()->invalidate();
118 }
119 
121 {
122  if (!data) {
123  qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");
124  return 0;
125  }
126 
127  return preferredSize;
128 }
129 
130 
132  qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint,
133  qreal *minSize, qreal *prefSize,
134  qreal *maxSize)
135 {
136  // minSize, prefSize and maxSize are initialized
137  // with item's preferred Size: this is QSizePolicy::Fixed.
138  //
139  // Then we check each flag to find the resultant QSizePolicy,
140  // according to the following table:
141  //
142  // constant value
143  // QSizePolicy::Fixed 0
144  // QSizePolicy::Minimum GrowFlag
145  // QSizePolicy::Maximum ShrinkFlag
146  // QSizePolicy::Preferred GrowFlag | ShrinkFlag
147  // QSizePolicy::Ignored GrowFlag | ShrinkFlag | IgnoreFlag
148 
149  if (policy & QSizePolicy::ShrinkFlag)
150  *minSize = minSizeHint;
151  else
152  *minSize = prefSizeHint;
153 
154  if (policy & QSizePolicy::GrowFlag)
155  *maxSize = maxSizeHint;
156  else
157  *maxSize = prefSizeHint;
158 
159  // Note that these two initializations are affected by the previous flags
160  if (policy & QSizePolicy::IgnoreFlag)
161  *prefSize = *minSize;
162  else
163  *prefSize = prefSizeHint;
164 }
165 
167 {
168  if (graphicsAnchor) {
169  // Remove reference to ourself to avoid double removal in
170  // QGraphicsAnchorPrivate dtor.
171  graphicsAnchor->d_func()->data = 0;
172 
173  delete graphicsAnchor;
174  }
175 }
176 
177 
179 {
180  QSizePolicy::Policy policy;
181  qreal minSizeHint;
182  qreal prefSizeHint;
183  qreal maxSizeHint;
184 
185  if (item) {
186  // It is an internal anchor, fetch size information from the item
187  if (isLayoutAnchor) {
188  minSize = 0;
189  prefSize = 0;
190  maxSize = QWIDGETSIZE_MAX;
191  if (isCenterAnchor)
192  maxSize /= 2;
193 
194  minPrefSize = prefSize;
195  maxPrefSize = maxSize;
196  return;
197  } else {
198  if (orientation == QGraphicsAnchorLayoutPrivate::Horizontal) {
199  policy = item->sizePolicy().horizontalPolicy();
200  minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).width();
201  prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).width();
202  maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).width();
203  } else {
204  policy = item->sizePolicy().verticalPolicy();
205  minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).height();
206  prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).height();
207  maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).height();
208  }
209 
210  if (isCenterAnchor) {
211  minSizeHint /= 2;
212  prefSizeHint /= 2;
213  maxSizeHint /= 2;
214  }
215  }
216  } else {
217  // It is a user-created anchor, fetch size information from the associated QGraphicsAnchor
218  Q_ASSERT(graphicsAnchor);
219  QGraphicsAnchorPrivate *anchorPrivate = graphicsAnchor->d_func();
220 
221  // Policy, min and max sizes are straightforward
222  policy = anchorPrivate->sizePolicy;
223  minSizeHint = 0;
224  maxSizeHint = QWIDGETSIZE_MAX;
225 
226  // Preferred Size
227  if (anchorPrivate->hasSize) {
228  // Anchor has user-defined size
229  prefSizeHint = anchorPrivate->preferredSize;
230  } else {
231  // Fetch size information from style
233  qreal s = styleInfo->defaultSpacing(orient);
234  if (s < 0) {
235  QSizePolicy::ControlType controlTypeFrom = from->m_item->sizePolicy().controlType();
236  QSizePolicy::ControlType controlTypeTo = to->m_item->sizePolicy().controlType();
237  s = styleInfo->perItemSpacing(controlTypeFrom, controlTypeTo, orient);
238 
239  // ### Currently we do not support negative anchors inside the graph.
240  // To avoid those being created by a negative style spacing, we must
241  // make this test.
242  if (s < 0)
243  s = 0;
244  }
245  prefSizeHint = s;
246  }
247  }
248 
249  // Fill minSize, prefSize and maxSize based on policy and sizeHints
250  applySizePolicy(policy, minSizeHint, prefSizeHint, maxSizeHint,
251  &minSize, &prefSize, &maxSize);
252 
253  minPrefSize = prefSize;
254  maxPrefSize = maxSize;
255 
256  // Set the anchor effective sizes to preferred.
257  //
258  // Note: The idea here is that all items should remain at their
259  // preferred size unless where that's impossible. In cases where
260  // the item is subject to restrictions (anchored to the layout
261  // edges, for instance), the simplex solver will be run to
262  // recalculate and override the values we set here.
263  sizeAtMinimum = prefSize;
264  sizeAtPreferred = prefSize;
265  sizeAtMaximum = prefSize;
266 }
267 
269 {
270  firstEdge->sizeAtMinimum = sizeAtMinimum;
271  firstEdge->sizeAtPreferred = sizeAtPreferred;
272  firstEdge->sizeAtMaximum = sizeAtMaximum;
273 
274  if (secondForward()) {
275  secondEdge->sizeAtMinimum = sizeAtMinimum;
276  secondEdge->sizeAtPreferred = sizeAtPreferred;
277  secondEdge->sizeAtMaximum = sizeAtMaximum;
278  } else {
279  secondEdge->sizeAtMinimum = -sizeAtMinimum;
280  secondEdge->sizeAtPreferred = -sizeAtPreferred;
281  secondEdge->sizeAtMaximum = -sizeAtMaximum;
282  }
283 
284  firstEdge->updateChildrenSizes();
285  secondEdge->updateChildrenSizes();
286 }
287 
288 /*
289  \internal
290 
291  Initialize the parallel anchor size hints using the sizeHint information from
292  its children.
293 
294  Note that parallel groups can lead to unfeasibility, so during calculation, we can
295  find out one unfeasibility. Because of that this method return boolean. This can't
296  happen in sequential, so there the method is void.
297  */
299 {
300  // Normalize second child sizes.
301  // A negative anchor of sizes min, minPref, pref, maxPref and max, is equivalent
302  // to a forward anchor of sizes -max, -maxPref, -pref, -minPref, -min
303  qreal secondMin;
304  qreal secondMinPref;
305  qreal secondPref;
306  qreal secondMaxPref;
307  qreal secondMax;
308 
309  if (secondForward()) {
310  secondMin = secondEdge->minSize;
311  secondMinPref = secondEdge->minPrefSize;
312  secondPref = secondEdge->prefSize;
313  secondMaxPref = secondEdge->maxPrefSize;
314  secondMax = secondEdge->maxSize;
315  } else {
316  secondMin = -secondEdge->maxSize;
317  secondMinPref = -secondEdge->maxPrefSize;
318  secondPref = -secondEdge->prefSize;
319  secondMaxPref = -secondEdge->minPrefSize;
320  secondMax = -secondEdge->minSize;
321  }
322 
323  minSize = qMax(firstEdge->minSize, secondMin);
324  maxSize = qMin(firstEdge->maxSize, secondMax);
325 
326  // This condition means that the maximum size of one anchor being simplified is smaller than
327  // the minimum size of the other anchor. The consequence is that there won't be a valid size
328  // for this parallel setup.
329  if (minSize > maxSize) {
330  return false;
331  }
332 
333  // Preferred size calculation
334  // The calculation of preferred size is done as follows:
335  //
336  // 1) Check whether one of the child anchors is the layout structural anchor
337  // If so, we can simply copy the preferred information from the other child,
338  // after bounding it to our minimum and maximum sizes.
339  // If not, then we proceed with the actual calculations.
340  //
341  // 2) The whole algorithm for preferred size calculation is based on the fact
342  // that, if a given anchor cannot remain at its preferred size, it'd rather
343  // grow than shrink.
344  //
345  // What happens though is that while this affirmative is true for simple
346  // anchors, it may not be true for sequential anchors that have one or more
347  // reversed anchors inside it. That happens because when a sequential anchor
348  // grows, any reversed anchors inside it may be required to shrink, something
349  // we try to avoid, as said above.
350  //
351  // To overcome this, besides their actual preferred size "prefSize", each anchor
352  // exports what we call "minPrefSize" and "maxPrefSize". These two values define
353  // a surrounding interval where, if required to move, the anchor would rather
354  // remain inside.
355  //
356  // For standard anchors, this area simply represents the region between
357  // prefSize and maxSize, which makes sense since our first affirmation.
358  // For composed anchors, these values are calculated as to reduce the global
359  // "damage", that is, to reduce the total deviation and the total amount of
360  // anchors that had to shrink.
361 
362  if (firstEdge->isLayoutAnchor) {
363  prefSize = qBound(minSize, secondPref, maxSize);
364  minPrefSize = qBound(minSize, secondMinPref, maxSize);
365  maxPrefSize = qBound(minSize, secondMaxPref, maxSize);
366  } else if (secondEdge->isLayoutAnchor) {
367  prefSize = qBound(minSize, firstEdge->prefSize, maxSize);
368  minPrefSize = qBound(minSize, firstEdge->minPrefSize, maxSize);
369  maxPrefSize = qBound(minSize, firstEdge->maxPrefSize, maxSize);
370  } else {
371  // Calculate the intersection between the "preferred" regions of each child
372  const qreal lowerBoundary =
373  qBound(minSize, qMax(firstEdge->minPrefSize, secondMinPref), maxSize);
374  const qreal upperBoundary =
375  qBound(minSize, qMin(firstEdge->maxPrefSize, secondMaxPref), maxSize);
376  const qreal prefMean =
377  qBound(minSize, (firstEdge->prefSize + secondPref) / 2, maxSize);
378 
379  if (lowerBoundary < upperBoundary) {
380  // If there is an intersection between the two regions, this intersection
381  // will be used as the preferred region of the parallel anchor itself.
382  // The preferred size will be the bounded average between the two preferred
383  // sizes.
384  prefSize = qBound(lowerBoundary, prefMean, upperBoundary);
385  minPrefSize = lowerBoundary;
386  maxPrefSize = upperBoundary;
387  } else {
388  // If there is no intersection, we have to attribute "damage" to at least
389  // one of the children. The minimum total damage is achieved in points
390  // inside the region that extends from (1) the upper boundary of the lower
391  // region to (2) the lower boundary of the upper region.
392  // Then, we expose this region as _our_ preferred region and once again,
393  // use the bounded average as our preferred size.
394  prefSize = qBound(upperBoundary, prefMean, lowerBoundary);
395  minPrefSize = upperBoundary;
396  maxPrefSize = lowerBoundary;
397  }
398  }
399 
400  // See comment in AnchorData::refreshSizeHints() about sizeAt* values
401  sizeAtMinimum = prefSize;
402  sizeAtPreferred = prefSize;
403  sizeAtMaximum = prefSize;
404 
405  return true;
406 }
407 
416  qreal minPref, qreal pref,
417  qreal maxPref, qreal max)
418 {
420  qreal lower;
421  qreal upper;
422 
423  if (value < minPref) {
425  lower = min;
426  upper = minPref;
427  } else if (value < pref) {
429  lower = minPref;
430  upper = pref;
431  } else if (value < maxPref) {
433  lower = pref;
434  upper = maxPref;
435  } else {
437  lower = maxPref;
438  upper = max;
439  }
440 
441  qreal progress;
442  if (upper == lower) {
443  progress = 0;
444  } else {
445  progress = (value - lower) / (upper - lower);
446  }
447 
448  return qMakePair(interval, progress);
449 }
450 
452  qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)
453 {
454  qreal lower = 0;
455  qreal upper = 0;
456 
457  switch (factor.first) {
459  lower = min;
460  upper = minPref;
461  break;
463  lower = minPref;
464  upper = pref;
465  break;
467  lower = pref;
468  upper = maxPref;
469  break;
471  lower = maxPref;
472  upper = max;
473  break;
474  }
475 
476  return lower + factor.second * (upper - lower);
477 }
478 
480 {
481  // Band here refers if the value is in the Minimum To Preferred
482  // band (the lower band) or the Preferred To Maximum (the upper band).
483 
485  getFactor(sizeAtMinimum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
487  getFactor(sizeAtPreferred, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
489  getFactor(sizeAtMaximum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
490 
491  // XXX This is not safe if Vertex simplification takes place after the sequential
492  // anchor is created. In that case, "prev" will be a group-vertex, different from
493  // "from" or "to", that _contains_ one of them.
494  AnchorVertex *prev = from;
495 
496  for (int i = 0; i < m_edges.count(); ++i) {
497  AnchorData *e = m_edges.at(i);
498 
499  const bool edgeIsForward = (e->from == prev);
500  if (edgeIsForward) {
501  e->sizeAtMinimum = interpolate(minFactor, e->minSize, e->minPrefSize,
502  e->prefSize, e->maxPrefSize, e->maxSize);
503  e->sizeAtPreferred = interpolate(prefFactor, e->minSize, e->minPrefSize,
504  e->prefSize, e->maxPrefSize, e->maxSize);
505  e->sizeAtMaximum = interpolate(maxFactor, e->minSize, e->minPrefSize,
506  e->prefSize, e->maxPrefSize, e->maxSize);
507  prev = e->to;
508  } else {
509  Q_ASSERT(prev == e->to);
510  e->sizeAtMinimum = interpolate(minFactor, e->maxSize, e->maxPrefSize,
511  e->prefSize, e->minPrefSize, e->minSize);
512  e->sizeAtPreferred = interpolate(prefFactor, e->maxSize, e->maxPrefSize,
513  e->prefSize, e->minPrefSize, e->minSize);
514  e->sizeAtMaximum = interpolate(maxFactor, e->maxSize, e->maxPrefSize,
515  e->prefSize, e->minPrefSize, e->minSize);
516  prev = e->from;
517  }
518 
519  e->updateChildrenSizes();
520  }
521 }
522 
524 {
525  minSize = 0;
526  prefSize = 0;
527  maxSize = 0;
528  minPrefSize = 0;
529  maxPrefSize = 0;
530 
531  AnchorVertex *prev = from;
532 
533  for (int i = 0; i < m_edges.count(); ++i) {
534  AnchorData *edge = m_edges.at(i);
535 
536  const bool edgeIsForward = (edge->from == prev);
537  if (edgeIsForward) {
538  minSize += edge->minSize;
539  prefSize += edge->prefSize;
540  maxSize += edge->maxSize;
541  minPrefSize += edge->minPrefSize;
542  maxPrefSize += edge->maxPrefSize;
543  prev = edge->to;
544  } else {
545  Q_ASSERT(prev == edge->to);
546  minSize -= edge->maxSize;
547  prefSize -= edge->prefSize;
548  maxSize -= edge->minSize;
549  minPrefSize -= edge->maxPrefSize;
550  maxPrefSize -= edge->minPrefSize;
551  prev = edge->from;
552  }
553  }
554 
555  // See comment in AnchorData::refreshSizeHints() about sizeAt* values
556  sizeAtMinimum = prefSize;
557  sizeAtPreferred = prefSize;
558  sizeAtMaximum = prefSize;
559 }
560 
561 #ifdef QT_DEBUG
562 void AnchorData::dump(int indent) {
563  if (type == Parallel) {
564  qDebug("%*s type: parallel:", indent, "");
565  ParallelAnchorData *p = static_cast<ParallelAnchorData *>(this);
566  p->firstEdge->dump(indent+2);
567  p->secondEdge->dump(indent+2);
568  } else if (type == Sequential) {
569  SequentialAnchorData *s = static_cast<SequentialAnchorData *>(this);
570  int kids = s->m_edges.count();
571  qDebug("%*s type: sequential(%d):", indent, "", kids);
572  for (int i = 0; i < kids; ++i) {
573  s->m_edges.at(i)->dump(indent+2);
574  }
575  } else {
576  qDebug("%*s type: Normal:", indent, "");
577  }
578 }
579 
580 #endif
581 
583 {
584  // Calculate
585  QSet<AnchorData *> cPositives;
586  QSet<AnchorData *> cNegatives;
587  QSet<AnchorData *> intersection;
588 
589  cPositives = positives + path.negatives;
590  cNegatives = negatives + path.positives;
591 
592  intersection = cPositives & cNegatives;
593 
594  cPositives -= intersection;
595  cNegatives -= intersection;
596 
597  // Fill
600  for (i = cPositives.begin(); i != cPositives.end(); ++i)
601  c->variables.insert(*i, 1.0);
602 
603  for (i = cNegatives.begin(); i != cNegatives.end(); ++i)
604  c->variables.insert(*i, -1.0);
605 
606  return c;
607 }
608 
609 #ifdef QT_DEBUG
611 {
612  QString string(QLatin1String("Path: "));
613  foreach(AnchorData *edge, positives)
614  string += QString::fromAscii(" (+++) %1").arg(edge->toString());
615 
616  foreach(AnchorData *edge, negatives)
617  string += QString::fromAscii(" (---) %1").arg(edge->toString());
618 
619  return string;
620 }
621 #endif
622 
624  : calculateGraphCacheDirty(true), styleInfoDirty(true)
625 {
626  for (int i = 0; i < NOrientations; ++i) {
627  for (int j = 0; j < 3; ++j) {
628  sizeHints[i][j] = -1;
629  }
630  interpolationProgress[i] = -1;
631 
632  spacings[i] = -1;
633  graphHasConflicts[i] = false;
634 
635  layoutFirstVertex[i] = 0;
636  layoutCentralVertex[i] = 0;
637  layoutLastVertex[i] = 0;
638  }
639 }
640 
642 {
643  switch (edge) {
644  case Qt::AnchorLeft:
645  edge = Qt::AnchorRight;
646  break;
647  case Qt::AnchorRight:
648  edge = Qt::AnchorLeft;
649  break;
650  case Qt::AnchorTop:
651  edge = Qt::AnchorBottom;
652  break;
653  case Qt::AnchorBottom:
654  edge = Qt::AnchorTop;
655  break;
656  default:
657  break;
658  }
659  return edge;
660 }
661 
662 
670 inline static qreal checkAdd(qreal a, qreal b)
671 {
672  if (FLT_MAX - b < a)
673  return FLT_MAX;
674  return a + b;
675 }
676 
694 {
695  Orientation orientation = Orientation(newAnchor->orientation);
696  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
697  *feasible = true;
698 
699  // If already exists one anchor where newAnchor is supposed to be, we create a parallel
700  // anchor.
701  if (AnchorData *oldAnchor = g.takeEdge(newAnchor->from, newAnchor->to)) {
702  ParallelAnchorData *parallel = new ParallelAnchorData(oldAnchor, newAnchor);
703 
704  // The parallel anchor will "replace" its children anchors in
705  // every center constraint that they appear.
706 
707  // ### If the dependent (center) anchors had reference(s) to their constraints, we
708  // could avoid traversing all the itemCenterConstraints.
710 
711  AnchorData *children[2] = { oldAnchor, newAnchor };
712  QList<QSimplexConstraint *> *childrenConstraints[2] = { &parallel->m_firstConstraints,
713  &parallel->m_secondConstraints };
714 
715  for (int i = 0; i < 2; ++i) {
716  AnchorData *child = children[i];
717  QList<QSimplexConstraint *> *childConstraints = childrenConstraints[i];
718 
719  // We need to fix the second child constraints if the parallel group will have the
720  // opposite direction of the second child anchor. For the point of view of external
721  // entities, this anchor was reversed. So if at some point we say that the parallel
722  // has a value of 20, this mean that the second child (when reversed) will be
723  // assigned -20.
724  const bool needsReverse = i == 1 && !parallel->secondForward();
725 
726  if (!child->isCenterAnchor)
727  continue;
728 
729  parallel->isCenterAnchor = true;
730 
731  for (int j = 0; j < constraints.count(); ++j) {
732  QSimplexConstraint *c = constraints[j];
733  if (c->variables.contains(child)) {
734  childConstraints->append(c);
735  qreal v = c->variables.take(child);
736  if (needsReverse)
737  v *= -1;
738  c->variables.insert(parallel, v);
739  }
740  }
741  }
742 
743  // At this point we can identify that the parallel anchor is not feasible, e.g. one
744  // anchor minimum size is bigger than the other anchor maximum size.
745  *feasible = parallel->calculateSizeHints();
746  newAnchor = parallel;
747  }
748 
749  g.createEdge(newAnchor->from, newAnchor->to, newAnchor);
750  return newAnchor;
751 }
752 
767  AnchorVertex *before,
768  const QVector<AnchorVertex*> &vertices,
769  AnchorVertex *after)
770 {
771 #if defined(QT_DEBUG) && 0
772  QString strVertices;
773  for (int i = 0; i < vertices.count(); ++i) {
774  strVertices += QString::fromAscii("%1 - ").arg(vertices.at(i)->toString());
775  }
776  QString strPath = QString::fromAscii("%1 - %2%3").arg(before->toString(), strVertices, after->toString());
777  qDebug("simplifying [%s] to [%s - %s]", qPrintable(strPath), qPrintable(before->toString()), qPrintable(after->toString()));
778 #endif
779 
780  AnchorVertex *prev = before;
781  QVector<AnchorData *> edges;
782 
783  // Take from the graph, the edges that will be simplificated
784  for (int i = 0; i < vertices.count(); ++i) {
785  AnchorVertex *next = vertices.at(i);
786  AnchorData *ad = graph->takeEdge(prev, next);
787  Q_ASSERT(ad);
788  edges.append(ad);
789  prev = next;
790  }
791 
792  // Take the last edge (not covered in the loop above)
793  AnchorData *ad = graph->takeEdge(vertices.last(), after);
794  Q_ASSERT(ad);
795  edges.append(ad);
796 
797  // Create sequence
798  SequentialAnchorData *sequence = new SequentialAnchorData(vertices, edges);
799  sequence->from = before;
800  sequence->to = after;
801 
802  sequence->calculateSizeHints();
803 
804  return sequence;
805 }
806 
848 {
849  if (items.isEmpty())
850  return true;
851 
852 #if defined(QT_DEBUG) && 0
853  qDebug("Simplifying Graph for %s",
854  orientation == Horizontal ? "Horizontal" : "Vertical");
855 
856  static int count = 0;
857  if (orientation == Horizontal) {
858  count++;
859  dumpGraph(QString::fromAscii("%1-full").arg(count));
860  }
861 #endif
862 
863  // Vertex simplification
864  if (!simplifyVertices(orientation)) {
865  restoreVertices(orientation);
866  return false;
867  }
868 
869  // Anchor simplification
870  bool dirty;
871  bool feasible = true;
872  do {
873  dirty = simplifyGraphIteration(orientation, &feasible);
874  } while (dirty && feasible);
875 
876  // Note that if we are not feasible, we fallback and make sure that the graph is fully restored
877  if (!feasible) {
878  restoreSimplifiedGraph(orientation);
879  restoreVertices(orientation);
880  return false;
881  }
882 
883 #if defined(QT_DEBUG) && 0
884  dumpGraph(QString::fromAscii("%1-simplified-%2").arg(count).arg(
885  QString::fromAscii(orientation == Horizontal ? "Horizontal" : "Vertical")));
886 #endif
887 
888  return true;
889 }
890 
892 {
893  AnchorVertex *other;
894  if (data->from == oldV) {
895  data->from = newV;
896  other = data->to;
897  } else {
898  data->to = newV;
899  other = data->from;
900  }
901  return other;
902 }
903 
905  AnchorVertex *newV, const QList<AnchorData *> &edges)
906 {
907  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
908  bool feasible = true;
909 
910  for (int i = 0; i < edges.count(); ++i) {
911  AnchorData *ad = edges[i];
912  AnchorVertex *otherV = replaceVertex_helper(ad, oldV, newV);
913 
914 #if defined(QT_DEBUG)
915  ad->name = QString::fromAscii("%1 --to--> %2").arg(ad->from->toString()).arg(ad->to->toString());
916 #endif
917 
918  bool newFeasible;
919  AnchorData *newAnchor = addAnchorMaybeParallel(ad, &newFeasible);
920  feasible &= newFeasible;
921 
922  if (newAnchor != ad) {
923  // A parallel was created, we mark that in the list of anchors created by vertex
924  // simplification. This is needed because we want to restore them in a separate step
925  // from the restoration of anchor simplification.
926  anchorsFromSimplifiedVertices[orientation].append(newAnchor);
927  }
928 
929  g.takeEdge(oldV, otherV);
930  }
931 
932  return feasible;
933 }
934 
939 {
941  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
942 
943  // We'll walk through vertices
945  stack.push(layoutFirstVertex[orientation]);
946  QSet<AnchorVertex *> visited;
947 
948  while (!stack.isEmpty()) {
949  AnchorVertex *v = stack.pop();
950  visited.insert(v);
951 
952  // Each adjacent of 'v' is a possible vertex to be merged. So we traverse all of
953  // them. Since once a merge is made, we might add new adjacents, and we don't want to
954  // pass two times through one adjacent. The 'index' is used to track our position.
955  QList<AnchorVertex *> adjacents = g.adjacentVertices(v);
956  int index = 0;
957 
958  while (index < adjacents.count()) {
959  AnchorVertex *next = adjacents.at(index);
960  index++;
961 
962  AnchorData *data = g.edgeData(v, next);
963  const bool bothLayoutVertices = v->m_item == q && next->m_item == q;
964  const bool zeroSized = !data->minSize && !data->maxSize;
965 
966  if (!bothLayoutVertices && zeroSized) {
967 
968  // Create a new vertex pair, note that we keep a list of those vertices so we can
969  // easily process them when restoring the graph.
970  AnchorVertexPair *newV = new AnchorVertexPair(v, next, data);
971  simplifiedVertices[orientation].append(newV);
972 
973  // Collect the anchors of both vertices, the new vertex pair will take their place
974  // in those anchors
975  const QList<AnchorVertex *> &vAdjacents = g.adjacentVertices(v);
976  const QList<AnchorVertex *> &nextAdjacents = g.adjacentVertices(next);
977 
978  for (int i = 0; i < vAdjacents.count(); ++i) {
979  AnchorVertex *adjacent = vAdjacents.at(i);
980  if (adjacent != next) {
981  AnchorData *ad = g.edgeData(v, adjacent);
982  newV->m_firstAnchors.append(ad);
983  }
984  }
985 
986  for (int i = 0; i < nextAdjacents.count(); ++i) {
987  AnchorVertex *adjacent = nextAdjacents.at(i);
988  if (adjacent != v) {
989  AnchorData *ad = g.edgeData(next, adjacent);
990  newV->m_secondAnchors.append(ad);
991 
992  // We'll also add new vertices to the adjacent list of the new 'v', to be
993  // created as a vertex pair and replace the current one.
994  if (!adjacents.contains(adjacent))
995  adjacents.append(adjacent);
996  }
997  }
998 
999  // ### merge this loop into the ones that calculated m_firstAnchors/m_secondAnchors?
1000  // Make newV take the place of v and next
1001  bool feasible = replaceVertex(orientation, v, newV, newV->m_firstAnchors);
1002  feasible &= replaceVertex(orientation, next, newV, newV->m_secondAnchors);
1003 
1004  // Update the layout vertex information if one of the vertices is a layout vertex.
1005  AnchorVertex *layoutVertex = 0;
1006  if (v->m_item == q)
1007  layoutVertex = v;
1008  else if (next->m_item == q)
1009  layoutVertex = next;
1010 
1011  if (layoutVertex) {
1012  // Layout vertices always have m_item == q...
1013  newV->m_item = q;
1014  changeLayoutVertex(orientation, layoutVertex, newV);
1015  }
1016 
1017  g.takeEdge(v, next);
1018 
1019  // If a non-feasibility is found, we leave early and cancel the simplification
1020  if (!feasible)
1021  return false;
1022 
1023  v = newV;
1024  visited.insert(newV);
1025 
1026  } else if (!visited.contains(next) && !stack.contains(next)) {
1027  // If the adjacent is not fit for merge and it wasn't visited by the outermost
1028  // loop, we add it to the stack.
1029  stack.push(next);
1030  }
1031  }
1032  }
1033 
1034  return true;
1035 }
1036 
1055  bool *feasible)
1056 {
1058  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1059 
1060  QSet<AnchorVertex *> visited;
1062  stack.push(qMakePair(static_cast<AnchorVertex *>(0), layoutFirstVertex[orientation]));
1063  QVector<AnchorVertex*> candidates;
1064 
1065  // Walk depth-first, in the stack we store start of the candidate sequence (beforeSequence)
1066  // and the vertex to be visited.
1067  while (!stack.isEmpty()) {
1069  AnchorVertex *beforeSequence = pair.first;
1070  AnchorVertex *v = pair.second;
1071 
1072  // The basic idea is to determine whether we found an end of sequence,
1073  // if that's the case, we stop adding vertices to the candidate list
1074  // and do a simplification step.
1075  //
1076  // A vertex can trigger an end of sequence if
1077  // (a) it is a layout vertex, we don't simplify away the layout vertices;
1078  // (b) it does not have exactly 2 adjacents;
1079  // (c) its next adjacent is already visited (a cycle in the graph).
1080  // (d) the next anchor is a center anchor.
1081 
1082  const QList<AnchorVertex *> &adjacents = g.adjacentVertices(v);
1083  const bool isLayoutVertex = v->m_item == q;
1084  AnchorVertex *afterSequence = v;
1085  bool endOfSequence = false;
1086 
1087  //
1088  // Identify the end cases.
1089  //
1090 
1091  // Identifies cases (a) and (b)
1092  endOfSequence = isLayoutVertex || adjacents.count() != 2;
1093 
1094  if (!endOfSequence) {
1095  // This is a tricky part. We peek at the next vertex to find out whether
1096  //
1097  // - we already visited the next vertex (c);
1098  // - the next anchor is a center (d).
1099  //
1100  // Those are needed to identify the remaining end of sequence cases. Note that unlike
1101  // (a) and (b), we preempt the end of sequence by looking into the next vertex.
1102 
1103  // Peek at the next vertex
1104  AnchorVertex *after;
1105  if (candidates.isEmpty())
1106  after = (beforeSequence == adjacents.last() ? adjacents.first() : adjacents.last());
1107  else
1108  after = (candidates.last() == adjacents.last() ? adjacents.first() : adjacents.last());
1109 
1110  // ### At this point we assumed that candidates will not contain 'after', this may not hold
1111  // when simplifying FLOATing anchors.
1112  Q_ASSERT(!candidates.contains(after));
1113 
1114  const AnchorData *data = g.edgeData(v, after);
1115  Q_ASSERT(data);
1116  const bool cycleFound = visited.contains(after);
1117 
1118  // Now cases (c) and (d)...
1119  endOfSequence = cycleFound || data->isCenterAnchor;
1120 
1121  if (!endOfSequence) {
1122  // If it's not an end of sequence, then the vertex didn't trigger neither of the
1123  // previously three cases, so it can be added to the candidates list.
1124  candidates.append(v);
1125  } else if (cycleFound && (beforeSequence != after)) {
1126  afterSequence = after;
1127  candidates.append(v);
1128  }
1129  }
1130 
1131  //
1132  // Add next non-visited vertices to the stack.
1133  //
1134  for (int i = 0; i < adjacents.count(); ++i) {
1135  AnchorVertex *next = adjacents.at(i);
1136  if (visited.contains(next))
1137  continue;
1138 
1139  // If current vertex is an end of sequence, and it'll reset the candidates list. So
1140  // the next vertices will build candidates lists with the current vertex as 'before'
1141  // vertex. If it's not an end of sequence, we keep the original 'before' vertex,
1142  // since we are keeping the candidates list.
1143  if (endOfSequence)
1144  stack.push(qMakePair(v, next));
1145  else
1146  stack.push(qMakePair(beforeSequence, next));
1147  }
1148 
1149  visited.insert(v);
1150 
1151  if (!endOfSequence || candidates.isEmpty())
1152  continue;
1153 
1154  //
1155  // Create a sequence for (beforeSequence, candidates, afterSequence).
1156  //
1157 
1158  // One restriction we have is to not simplify half of an anchor and let the other half
1159  // unsimplified. So we remove center edges before and after the sequence.
1160  const AnchorData *firstAnchor = g.edgeData(beforeSequence, candidates.first());
1161  if (firstAnchor->isCenterAnchor) {
1162  beforeSequence = candidates.first();
1163  candidates.remove(0);
1164 
1165  // If there's not candidates to be simplified, leave.
1166  if (candidates.isEmpty())
1167  continue;
1168  }
1169 
1170  const AnchorData *lastAnchor = g.edgeData(candidates.last(), afterSequence);
1171  if (lastAnchor->isCenterAnchor) {
1172  afterSequence = candidates.last();
1173  candidates.remove(candidates.count() - 1);
1174 
1175  if (candidates.isEmpty())
1176  continue;
1177  }
1178 
1179  //
1180  // Add the sequence to the graph.
1181  //
1182 
1183  AnchorData *sequence = createSequence(&g, beforeSequence, candidates, afterSequence);
1184 
1185  // If 'beforeSequence' and 'afterSequence' already had an anchor between them, we'll
1186  // create a parallel anchor between the new sequence and the old anchor.
1187  bool newFeasible;
1188  AnchorData *newAnchor = addAnchorMaybeParallel(sequence, &newFeasible);
1189 
1190  if (!newFeasible) {
1191  *feasible = false;
1192  return false;
1193  }
1194 
1195  // When a new parallel anchor is create in the graph, we finish the iteration and return
1196  // true to indicate a new iteration is needed. This happens because a parallel anchor
1197  // changes the number of adjacents one vertex has, possibly opening up oportunities for
1198  // building candidate lists (when adjacents == 2).
1199  if (newAnchor != sequence)
1200  return true;
1201 
1202  // If there was no parallel simplification, we'll keep walking the graph. So we clear the
1203  // candidates list to start again.
1204  candidates.clear();
1205  }
1206 
1207  return false;
1208 }
1209 
1211 {
1212 #if 0
1213  static const char *anchortypes[] = {"Normal",
1214  "Sequential",
1215  "Parallel"};
1216  qDebug("Restoring %s edge.", anchortypes[int(edge->type)]);
1217 #endif
1218 
1220 
1221  if (edge->type == AnchorData::Normal) {
1222  g.createEdge(edge->from, edge->to, edge);
1223 
1224  } else if (edge->type == AnchorData::Sequential) {
1225  SequentialAnchorData *sequence = static_cast<SequentialAnchorData *>(edge);
1226 
1227  for (int i = 0; i < sequence->m_edges.count(); ++i) {
1228  AnchorData *data = sequence->m_edges.at(i);
1230  }
1231 
1232  delete sequence;
1233 
1234  } else if (edge->type == AnchorData::Parallel) {
1235 
1236  // Skip parallel anchors that were created by vertex simplification, they will be processed
1237  // later, when restoring vertex simplification.
1238  // ### we could improve this check bit having a bit inside 'edge'
1240  return;
1241 
1242  ParallelAnchorData* parallel = static_cast<ParallelAnchorData*>(edge);
1243  restoreSimplifiedConstraints(parallel);
1244 
1245  // ### Because of the way parallel anchors are created in the anchor simplification
1246  // algorithm, we know that one of these will be a sequence, so it'll be safe if the other
1247  // anchor create an edge between the same vertices as the parallel.
1249  || parallel->secondEdge->type == AnchorData::Sequential);
1252 
1253  delete parallel;
1254  }
1255 }
1256 
1258 {
1259  if (!parallel->isCenterAnchor)
1260  return;
1261 
1262  for (int i = 0; i < parallel->m_firstConstraints.count(); ++i) {
1263  QSimplexConstraint *c = parallel->m_firstConstraints.at(i);
1264  qreal v = c->variables[parallel];
1265  c->variables.remove(parallel);
1266  c->variables.insert(parallel->firstEdge, v);
1267  }
1268 
1269  // When restoring, we might have to revert constraints back. See comments on
1270  // addAnchorMaybeParallel().
1271  const bool needsReverse = !parallel->secondForward();
1272 
1273  for (int i = 0; i < parallel->m_secondConstraints.count(); ++i) {
1274  QSimplexConstraint *c = parallel->m_secondConstraints.at(i);
1275  qreal v = c->variables[parallel];
1276  if (needsReverse)
1277  v *= -1;
1278  c->variables.remove(parallel);
1279  c->variables.insert(parallel->secondEdge, v);
1280  }
1281 }
1282 
1284 {
1285 #if 0
1286  qDebug("Restoring Simplified Graph for %s",
1287  orientation == Horizontal ? "Horizontal" : "Vertical");
1288 #endif
1289 
1290  // Restore anchor simplification
1291  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1293  for (int i = 0; i < connections.count(); ++i) {
1294  AnchorVertex *v1 = connections.at(i).first;
1295  AnchorVertex *v2 = connections.at(i).second;
1296  AnchorData *edge = g.edgeData(v1, v2);
1297 
1298  // We restore only sequential anchors and parallels that were not created by
1299  // vertex simplification.
1300  if (edge->type == AnchorData::Sequential
1301  || (edge->type == AnchorData::Parallel &&
1302  !anchorsFromSimplifiedVertices[orientation].contains(edge))) {
1303 
1304  g.takeEdge(v1, v2);
1306  }
1307  }
1308 
1309  restoreVertices(orientation);
1310 }
1311 
1313 {
1315 
1316  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1317  QList<AnchorVertexPair *> &toRestore = simplifiedVertices[orientation];
1318 
1319  // Since we keep a list of parallel anchors and vertices that were created during vertex
1320  // simplification, we can now iterate on those lists instead of traversing the graph
1321  // recursively.
1322 
1323  // First, restore the constraints changed when we created parallel anchors. Note that this
1324  // works at this point because the constraints doesn't depend on vertex information and at
1325  // this point it's always safe to identify whether the second child is forward or backwards.
1326  // In the next step, we'll change the anchors vertices so that would not be possible anymore.
1327  QList<AnchorData *> &parallelAnchors = anchorsFromSimplifiedVertices[orientation];
1328 
1329  for (int i = parallelAnchors.count() - 1; i >= 0; --i) {
1330  ParallelAnchorData *parallel = static_cast<ParallelAnchorData *>(parallelAnchors.at(i));
1331  restoreSimplifiedConstraints(parallel);
1332  }
1333 
1334  // Then, we will restore the vertices in the inverse order of creation, this way we ensure that
1335  // the vertex being restored was not wrapped by another simplification.
1336  for (int i = toRestore.count() - 1; i >= 0; --i) {
1337  AnchorVertexPair *pair = toRestore.at(i);
1338  QList<AnchorVertex *> adjacents = g.adjacentVertices(pair);
1339 
1340  // Restore the removed edge, this will also restore both vertices 'first' and 'second' to
1341  // the graph structure.
1342  AnchorVertex *first = pair->m_first;
1343  AnchorVertex *second = pair->m_second;
1344  g.createEdge(first, second, pair->m_removedAnchor);
1345 
1346  // Restore the anchors for the first child vertex
1347  for (int j = 0; j < pair->m_firstAnchors.count(); ++j) {
1348  AnchorData *ad = pair->m_firstAnchors.at(j);
1349  Q_ASSERT(ad->from == pair || ad->to == pair);
1350 
1351  replaceVertex_helper(ad, pair, first);
1352  g.createEdge(ad->from, ad->to, ad);
1353  }
1354 
1355  // Restore the anchors for the second child vertex
1356  for (int j = 0; j < pair->m_secondAnchors.count(); ++j) {
1357  AnchorData *ad = pair->m_secondAnchors.at(j);
1358  Q_ASSERT(ad->from == pair || ad->to == pair);
1359 
1360  replaceVertex_helper(ad, pair, second);
1361  g.createEdge(ad->from, ad->to, ad);
1362  }
1363 
1364  for (int j = 0; j < adjacents.count(); ++j) {
1365  g.takeEdge(pair, adjacents.at(j));
1366  }
1367 
1368  // The pair simplified a layout vertex, so place back the correct vertex in the variable
1369  // that track layout vertices
1370  if (pair->m_item == q) {
1371  AnchorVertex *layoutVertex = first->m_item == q ? first : second;
1372  Q_ASSERT(layoutVertex->m_item == q);
1373  changeLayoutVertex(orientation, pair, layoutVertex);
1374  }
1375 
1376  delete pair;
1377  }
1378  qDeleteAll(parallelAnchors);
1379  parallelAnchors.clear();
1380  toRestore.clear();
1381 }
1382 
1385 {
1386  return edge > Qt::AnchorRight ? Vertical : Horizontal;
1387 }
1388 
1402 {
1405 
1406  // Horizontal
1407  AnchorData *data = new AnchorData;
1408  addAnchor_helper(layout, Qt::AnchorLeft, layout,
1409  Qt::AnchorRight, data);
1410  data->maxSize = QWIDGETSIZE_MAX;
1411 
1412  // Save a reference to layout vertices
1416 
1417  // Vertical
1418  data = new AnchorData;
1419  addAnchor_helper(layout, Qt::AnchorTop, layout,
1420  Qt::AnchorBottom, data);
1421  data->maxSize = QWIDGETSIZE_MAX;
1422 
1423  // Save a reference to layout vertices
1427 }
1428 
1430 {
1432 
1435 
1440 }
1441 
1443 {
1444  items.append(item);
1445 
1446  // Create horizontal and vertical internal anchors for the item and
1447  // refresh its size hint / policy values.
1448  AnchorData *data = new AnchorData;
1449  addAnchor_helper(item, Qt::AnchorLeft, item, Qt::AnchorRight, data);
1450  data->refreshSizeHints();
1451 
1452  data = new AnchorData;
1453  addAnchor_helper(item, Qt::AnchorTop, item, Qt::AnchorBottom, data);
1454  data->refreshSizeHints();
1455 }
1456 
1472  QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge)
1473 {
1475 
1476  Orientation orientation;
1477  switch (centerEdge) {
1479  orientation = Horizontal;
1480  break;
1482  orientation = Vertical;
1483  break;
1484  default:
1485  // Don't create center edges unless needed
1486  return;
1487  }
1488 
1489  // Check if vertex already exists
1490  if (internalVertex(item, centerEdge))
1491  return;
1492 
1493  // Orientation code
1494  Qt::AnchorPoint firstEdge;
1495  Qt::AnchorPoint lastEdge;
1496 
1497  if (orientation == Horizontal) {
1498  firstEdge = Qt::AnchorLeft;
1499  lastEdge = Qt::AnchorRight;
1500  } else {
1501  firstEdge = Qt::AnchorTop;
1502  lastEdge = Qt::AnchorBottom;
1503  }
1504 
1505  AnchorVertex *first = internalVertex(item, firstEdge);
1506  AnchorVertex *last = internalVertex(item, lastEdge);
1507  Q_ASSERT(first && last);
1508 
1509  // Create new anchors
1511 
1512  AnchorData *data = new AnchorData;
1513  c->variables.insert(data, 1.0);
1514  addAnchor_helper(item, firstEdge, item, centerEdge, data);
1515  data->isCenterAnchor = true;
1517  data->refreshSizeHints();
1518 
1519  data = new AnchorData;
1520  c->variables.insert(data, -1.0);
1521  addAnchor_helper(item, centerEdge, item, lastEdge, data);
1522  data->isCenterAnchor = true;
1523  data->dependency = AnchorData::Slave;
1524  data->refreshSizeHints();
1525 
1526  itemCenterConstraints[orientation].append(c);
1527 
1528  // Remove old one
1529  removeAnchor_helper(first, last);
1530 
1531  if (item == q) {
1532  layoutCentralVertex[orientation] = internalVertex(q, centerEdge);
1533  }
1534 }
1535 
1537  QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge,
1538  bool substitute)
1539 {
1541 
1542  Orientation orientation;
1543  switch (centerEdge) {
1545  orientation = Horizontal;
1546  break;
1548  orientation = Vertical;
1549  break;
1550  default:
1551  // Don't remove edges that not the center ones
1552  return;
1553  }
1554 
1555  // Orientation code
1556  Qt::AnchorPoint firstEdge;
1557  Qt::AnchorPoint lastEdge;
1558 
1559  if (orientation == Horizontal) {
1560  firstEdge = Qt::AnchorLeft;
1561  lastEdge = Qt::AnchorRight;
1562  } else {
1563  firstEdge = Qt::AnchorTop;
1564  lastEdge = Qt::AnchorBottom;
1565  }
1566 
1567  AnchorVertex *center = internalVertex(item, centerEdge);
1568  if (!center)
1569  return;
1570  AnchorVertex *first = internalVertex(item, firstEdge);
1571 
1572  Q_ASSERT(first);
1573  Q_ASSERT(center);
1574 
1575  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
1576 
1577 
1578  AnchorData *oldData = g.edgeData(first, center);
1579  // Remove center constraint
1580  for (int i = itemCenterConstraints[orientation].count() - 1; i >= 0; --i) {
1581  if (itemCenterConstraints[orientation].at(i)->variables.contains(oldData)) {
1582  delete itemCenterConstraints[orientation].takeAt(i);
1583  break;
1584  }
1585  }
1586 
1587  if (substitute) {
1588  // Create the new anchor that should substitute the left-center-right anchors.
1589  AnchorData *data = new AnchorData;
1590  addAnchor_helper(item, firstEdge, item, lastEdge, data);
1591  data->refreshSizeHints();
1592 
1593  // Remove old anchors
1594  removeAnchor_helper(first, center);
1595  removeAnchor_helper(center, internalVertex(item, lastEdge));
1596 
1597  } else {
1598  // this is only called from removeAnchors()
1599  // first, remove all non-internal anchors
1600  QList<AnchorVertex*> adjacents = g.adjacentVertices(center);
1601  for (int i = 0; i < adjacents.count(); ++i) {
1602  AnchorVertex *v = adjacents.at(i);
1603  if (v->m_item != item) {
1605  }
1606  }
1607  // when all non-internal anchors is removed it will automatically merge the
1608  // center anchor into a left-right (or top-bottom) anchor. We must also delete that.
1609  // by this time, the center vertex is deleted and merged into a non-centered internal anchor
1610  removeAnchor_helper(first, internalVertex(item, lastEdge));
1611  }
1612 
1613  if (item == q) {
1614  layoutCentralVertex[orientation] = 0;
1615  }
1616 }
1617 
1618 
1620  Orientation orientation)
1621 {
1622  // Remove the item center constraints associated to this item
1623  // ### This is a temporary solution. We should probably use a better
1624  // data structure to hold items and/or their associated constraints
1625  // so that we can remove those easily
1626 
1627  AnchorVertex *first = internalVertex(item, orientation == Horizontal ?
1628  Qt::AnchorLeft :
1629  Qt::AnchorTop);
1630  AnchorVertex *center = internalVertex(item, orientation == Horizontal ?
1633 
1634  // Skip if no center constraints exist
1635  if (!center)
1636  return;
1637 
1638  Q_ASSERT(first);
1639  AnchorData *internalAnchor = graph[orientation].edgeData(first, center);
1640 
1641  // Look for our anchor in all item center constraints, then remove it
1642  for (int i = 0; i < itemCenterConstraints[orientation].size(); ++i) {
1643  if (itemCenterConstraints[orientation].at(i)->variables.contains(internalAnchor)) {
1644  delete itemCenterConstraints[orientation].takeAt(i);
1645  break;
1646  }
1647  }
1648 }
1649 
1663  Qt::AnchorPoint firstEdge,
1664  QGraphicsLayoutItem *secondItem,
1665  Qt::AnchorPoint secondEdge,
1666  qreal *spacing)
1667 {
1669  if ((firstItem == 0) || (secondItem == 0)) {
1670  qWarning("QGraphicsAnchorLayout::addAnchor(): "
1671  "Cannot anchor NULL items");
1672  return 0;
1673  }
1674 
1675  if (firstItem == secondItem) {
1676  qWarning("QGraphicsAnchorLayout::addAnchor(): "
1677  "Cannot anchor the item to itself");
1678  return 0;
1679  }
1680 
1681  if (edgeOrientation(secondEdge) != edgeOrientation(firstEdge)) {
1682  qWarning("QGraphicsAnchorLayout::addAnchor(): "
1683  "Cannot anchor edges of different orientations");
1684  return 0;
1685  }
1686 
1687  const QGraphicsLayoutItem *parentWidget = q->parentLayoutItem();
1688  if (firstItem == parentWidget || secondItem == parentWidget) {
1689  qWarning("QGraphicsAnchorLayout::addAnchor(): "
1690  "You cannot add the parent of the layout to the layout.");
1691  return 0;
1692  }
1693 
1694  // In QGraphicsAnchorLayout, items are represented in its internal
1695  // graph as four anchors that connect:
1696  // - Left -> HCenter
1697  // - HCenter-> Right
1698  // - Top -> VCenter
1699  // - VCenter -> Bottom
1700 
1701  // Ensure that the internal anchors have been created for both items.
1702  if (firstItem != q && !items.contains(firstItem)) {
1703  createItemEdges(firstItem);
1704  addChildLayoutItem(firstItem);
1705  }
1706  if (secondItem != q && !items.contains(secondItem)) {
1707  createItemEdges(secondItem);
1708  addChildLayoutItem(secondItem);
1709  }
1710 
1711  // Create center edges if needed
1712  createCenterAnchors(firstItem, firstEdge);
1713  createCenterAnchors(secondItem, secondEdge);
1714 
1715  // Use heuristics to find out what the user meant with this anchor.
1716  correctEdgeDirection(firstItem, firstEdge, secondItem, secondEdge);
1717 
1718  AnchorData *data = new AnchorData;
1719  QGraphicsAnchor *graphicsAnchor = acquireGraphicsAnchor(data);
1720 
1721  addAnchor_helper(firstItem, firstEdge, secondItem, secondEdge, data);
1722 
1723  if (spacing) {
1724  graphicsAnchor->setSpacing(*spacing);
1725  } else {
1726  // If firstItem or secondItem is the layout itself, the spacing will default to 0.
1727  // Otherwise, the following matrix is used (questionmark means that the spacing
1728  // is queried from the style):
1729  // from
1730  // to Left HCenter Right
1731  // Left 0 0 ?
1732  // HCenter 0 0 0
1733  // Right ? 0 0
1734  if (firstItem == q
1735  || secondItem == q
1737  || oppositeEdge(firstEdge) != secondEdge) {
1738  graphicsAnchor->setSpacing(0);
1739  } else {
1740  graphicsAnchor->unsetSpacing();
1741  }
1742  }
1743 
1744  return graphicsAnchor;
1745 }
1746 
1747 /*
1748  \internal
1749 
1750  This method adds an AnchorData to the internal graph. It is responsible for doing
1751  the boilerplate part of such task.
1752 
1753  If another AnchorData exists between the mentioned vertices, it is deleted and
1754  the new one is inserted.
1755 */
1757  Qt::AnchorPoint firstEdge,
1758  QGraphicsLayoutItem *secondItem,
1759  Qt::AnchorPoint secondEdge,
1760  AnchorData *data)
1761 {
1763 
1764  const Orientation orientation = edgeOrientation(firstEdge);
1765 
1766  // Create or increase the reference count for the related vertices.
1767  AnchorVertex *v1 = addInternalVertex(firstItem, firstEdge);
1768  AnchorVertex *v2 = addInternalVertex(secondItem, secondEdge);
1769 
1770  // Remove previous anchor
1771  if (graph[orientation].edgeData(v1, v2)) {
1772  removeAnchor_helper(v1, v2);
1773  }
1774 
1775  // If its an internal anchor, set the associated item
1776  if (firstItem == secondItem)
1777  data->item = firstItem;
1778 
1779  data->orientation = orientation;
1780 
1781  // Create a bi-directional edge in the sense it can be transversed both
1782  // from v1 or v2. "data" however is shared between the two references
1783  // so we still know that the anchor direction is from 1 to 2.
1784  data->from = v1;
1785  data->to = v2;
1786 #ifdef QT_DEBUG
1787  data->name = QString::fromAscii("%1 --to--> %2").arg(v1->toString()).arg(v2->toString());
1788 #endif
1789  // ### bit to track internal anchors, since inside AnchorData methods
1790  // we don't have access to the 'q' pointer.
1791  data->isLayoutAnchor = (data->item == q);
1792 
1793  graph[orientation].createEdge(v1, v2, data);
1794 }
1795 
1797  Qt::AnchorPoint firstEdge,
1798  QGraphicsLayoutItem *secondItem,
1799  Qt::AnchorPoint secondEdge)
1800 {
1801  // Do not expose internal anchors
1802  if (firstItem == secondItem)
1803  return 0;
1804 
1805  const Orientation orientation = edgeOrientation(firstEdge);
1806  AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
1807  AnchorVertex *v2 = internalVertex(secondItem, secondEdge);
1808 
1809  QGraphicsAnchor *graphicsAnchor = 0;
1810 
1811  AnchorData *data = graph[orientation].edgeData(v1, v2);
1812  if (data) {
1813  // We could use "acquireGraphicsAnchor" here, but to avoid a regression where
1814  // an internal anchor was wrongly exposed, I want to ensure no new
1815  // QGraphicsAnchor instances are created by this call.
1816  // This assumption must hold because anchors are either user-created (and already
1817  // have their public object created), or they are internal (and must not reach
1818  // this point).
1819  Q_ASSERT(data->graphicsAnchor);
1820  graphicsAnchor = data->graphicsAnchor;
1821  }
1822  return graphicsAnchor;
1823 }
1824 
1832  AnchorVertex *secondVertex)
1833 {
1835 
1836  // Save references to items while it's safe to assume the vertices exist
1837  QGraphicsLayoutItem *firstItem = firstVertex->m_item;
1838  QGraphicsLayoutItem *secondItem = secondVertex->m_item;
1839 
1840  // Delete the anchor (may trigger deletion of center vertices)
1841  removeAnchor_helper(firstVertex, secondVertex);
1842 
1843  // Ensure no dangling pointer is left behind
1844  firstVertex = secondVertex = 0;
1845 
1846  // Checking if the item stays in the layout or not
1847  bool keepFirstItem = false;
1848  bool keepSecondItem = false;
1849 
1851  int refcount = -1;
1852 
1853  if (firstItem != q) {
1854  for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
1855  v = m_vertexList.value(qMakePair(firstItem, static_cast<Qt::AnchorPoint>(i)));
1856  if (v.first) {
1858  refcount = 2;
1859  else
1860  refcount = 1;
1861 
1862  if (v.second > refcount) {
1863  keepFirstItem = true;
1864  break;
1865  }
1866  }
1867  }
1868  } else
1869  keepFirstItem = true;
1870 
1871  if (secondItem != q) {
1872  for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
1873  v = m_vertexList.value(qMakePair(secondItem, static_cast<Qt::AnchorPoint>(i)));
1874  if (v.first) {
1876  refcount = 2;
1877  else
1878  refcount = 1;
1879 
1880  if (v.second > refcount) {
1881  keepSecondItem = true;
1882  break;
1883  }
1884  }
1885  }
1886  } else
1887  keepSecondItem = true;
1888 
1889  if (!keepFirstItem)
1890  q->removeAt(items.indexOf(firstItem));
1891 
1892  if (!keepSecondItem)
1893  q->removeAt(items.indexOf(secondItem));
1894 
1895  // Removing anchors invalidates the layout
1896  q->invalidate();
1897 }
1898 
1899 /*
1900  \internal
1901 
1902  Implements the low level "removeAnchor" feature. Called by
1903  private methods.
1904 */
1906 {
1907  Q_ASSERT(v1 && v2);
1908 
1909  // Remove edge from graph
1910  const Orientation o = edgeOrientation(v1->m_edge);
1911  graph[o].removeEdge(v1, v2);
1912 
1913  // Decrease vertices reference count (may trigger a deletion)
1916 }
1917 
1919  Qt::AnchorPoint edge)
1920 {
1923 
1924  if (!v.first) {
1925  Q_ASSERT(v.second == 0);
1926  v.first = new AnchorVertex(item, edge);
1927  }
1928  v.second++;
1929  m_vertexList.insert(pair, v);
1930  return v.first;
1931 }
1932 
1940  Qt::AnchorPoint edge)
1941 {
1944 
1945  if (!v.first) {
1946  qWarning("This item with this edge is not in the graph");
1947  return;
1948  }
1949 
1950  v.second--;
1951  if (v.second == 0) {
1952  // Remove reference and delete vertex
1953  m_vertexList.remove(pair);
1954  delete v.first;
1955  } else {
1956  // Update reference count
1957  m_vertexList.insert(pair, v);
1958 
1959  if ((v.second == 2) &&
1960  ((edge == Qt::AnchorHorizontalCenter) ||
1961  (edge == Qt::AnchorVerticalCenter))) {
1962  removeCenterAnchors(item, edge, true);
1963  }
1964  }
1965 }
1966 
1968 {
1969  if (AnchorVertex *v = internalVertex(item, edge)) {
1971  const QList<AnchorVertex *> allVertices = graph[edgeOrientation(edge)].adjacentVertices(v);
1972  AnchorVertex *v2;
1973  foreach (v2, allVertices) {
1974  g.removeEdge(v, v2);
1975  removeInternalVertex(item, edge);
1977  }
1978  }
1979 }
1980 
1982 {
1983  // remove the center anchor first!!
1987 
1989  removeVertex(item, Qt::AnchorTop);
1991 }
1992 
2021  Qt::AnchorPoint &firstEdge,
2022  QGraphicsLayoutItem *&secondItem,
2023  Qt::AnchorPoint &secondEdge)
2024 {
2026 
2027  if ((firstItem != q) && (secondItem != q)) {
2028  // If connection is between widgets (not the layout itself)
2029  // Ensure that "right-edges" sit to the left of "left-edges".
2030  if (firstEdge < secondEdge) {
2031  qSwap(firstItem, secondItem);
2032  qSwap(firstEdge, secondEdge);
2033  }
2034  } else if (firstItem == q) {
2035  // If connection involves the right or bottom of a layout, ensure
2036  // the layout is the second item.
2037  if ((firstEdge == Qt::AnchorRight) || (firstEdge == Qt::AnchorBottom)) {
2038  qSwap(firstItem, secondItem);
2039  qSwap(firstEdge, secondEdge);
2040  }
2041  } else if ((secondEdge != Qt::AnchorRight) && (secondEdge != Qt::AnchorBottom)) {
2042  // If connection involves the left, center or top of layout, ensure
2043  // the layout is the first item.
2044  qSwap(firstItem, secondItem);
2045  qSwap(firstEdge, secondEdge);
2046  }
2047 }
2048 
2050 {
2051  if (styleInfoDirty) {
2052  Q_Q(const QGraphicsAnchorLayout);
2053  //### Fix this if QGV ever gets support for Metal style or different Aqua sizes.
2054  QWidget *wid = 0;
2055 
2057  while (parent && parent->isLayout()) {
2058  parent = parent->parentLayoutItem();
2059  }
2060  QGraphicsWidget *w = 0;
2061  if (parent) {
2062  QGraphicsItem *parentItem = parent->graphicsItem();
2063  if (parentItem && parentItem->isWidget())
2064  w = static_cast<QGraphicsWidget*>(parentItem);
2065  }
2066 
2067  QStyle *style = w ? w->style() : QApplication::style();
2068  cachedStyleInfo = QLayoutStyleInfo(style, wid);
2071 
2072  styleInfoDirty = false;
2073  }
2074  return cachedStyleInfo;
2075 }
2076 
2088 {
2090  return;
2093  calculateGraphCacheDirty = false;
2094 }
2095 
2096 // ### Maybe getGraphParts could return the variables when traversing, at least
2097 // for trunk...
2099 {
2100  QSet<AnchorData *> variableSet;
2101  for (int i = 0; i < constraints.count(); ++i) {
2102  const QSimplexConstraint *c = constraints.at(i);
2103  foreach (QSimplexVariable *var, c->variables.keys()) {
2104  variableSet += static_cast<AnchorData *>(var);
2105  }
2106  }
2107  return variableSet.toList();
2108 }
2109 
2138 {
2139 #if defined(QT_DEBUG) || defined(Q_AUTOTEST_EXPORT)
2140  lastCalculationUsedSimplex[orientation] = false;
2141 #endif
2142 
2143  static bool simplificationEnabled = qgetenv("QT_ANCHORLAYOUT_NO_SIMPLIFICATION").isEmpty();
2144 
2145  // Reset the nominal sizes of each anchor based on the current item sizes
2146  refreshAllSizeHints(orientation);
2147 
2148  // Simplify the graph
2149  if (simplificationEnabled && !simplifyGraph(orientation)) {
2150  qWarning("QGraphicsAnchorLayout: anchor setup is not feasible.");
2151  graphHasConflicts[orientation] = true;
2152  return;
2153  }
2154 
2155  // Traverse all graph edges and store the possible paths to each vertex
2156  findPaths(orientation);
2157 
2158  // From the paths calculated above, extract the constraints that the current
2159  // anchor setup impose, to our Linear Programming problem.
2160  constraintsFromPaths(orientation);
2161 
2162  // Split the constraints and anchors into groups that should be fed to the
2163  // simplex solver independently. Currently we find two groups:
2164  //
2165  // 1) The "trunk", that is, the set of anchors (items) that are connected
2166  // to the two opposite sides of our layout, and thus need to stretch in
2167  // order to fit in the current layout size.
2168  //
2169  // 2) The floating or semi-floating anchors (items) that are those which
2170  // are connected to only one (or none) of the layout sides, thus are not
2171  // influenced by the layout size.
2172  QList<QList<QSimplexConstraint *> > parts = getGraphParts(orientation);
2173 
2174  // Now run the simplex solver to calculate Minimum, Preferred and Maximum sizes
2175  // of the "trunk" set of constraints and variables.
2176  // ### does trunk always exist? empty = trunk is the layout left->center->right
2177  QList<QSimplexConstraint *> trunkConstraints = parts.at(0);
2178  QList<AnchorData *> trunkVariables = getVariables(trunkConstraints);
2179 
2180  // For minimum and maximum, use the path between the two layout sides as the
2181  // objective function.
2182  AnchorVertex *v = layoutLastVertex[orientation];
2183  GraphPath trunkPath = graphPaths[orientation].value(v);
2184 
2185  bool feasible = calculateTrunk(orientation, trunkPath, trunkConstraints, trunkVariables);
2186 
2187  // For the other parts that not the trunk, solve only for the preferred size
2188  // that is the size they will remain at, since they are not stretched by the
2189  // layout.
2190 
2191  // Skipping the first (trunk)
2192  for (int i = 1; i < parts.count(); ++i) {
2193  if (!feasible)
2194  break;
2195 
2196  QList<QSimplexConstraint *> partConstraints = parts.at(i);
2197  QList<AnchorData *> partVariables = getVariables(partConstraints);
2198  Q_ASSERT(!partVariables.isEmpty());
2199  feasible &= calculateNonTrunk(partConstraints, partVariables);
2200  }
2201 
2202  // Propagate the new sizes down the simplified graph, ie. tell the
2203  // group anchors to set their children anchors sizes.
2204  updateAnchorSizes(orientation);
2205 
2206  graphHasConflicts[orientation] = !feasible;
2207 
2208  // Clean up our data structures. They are not needed anymore since
2209  // distribution uses just interpolation.
2210  qDeleteAll(constraints[orientation]);
2211  constraints[orientation].clear();
2212  graphPaths[orientation].clear(); // ###
2213 
2214  if (simplificationEnabled)
2215  restoreSimplifiedGraph(orientation);
2216 }
2217 
2229 {
2230  for (int i = 0; i < constraints.count(); ++i) {
2231  QSimplexConstraint *c = constraints.at(i);
2232  qreal multiplier = 0;
2233  foreach (qreal v, c->variables.values()) {
2234  multiplier += v;
2235  }
2236  c->constant += multiplier * amount;
2237  }
2238 }
2239 
2251  const QList<AnchorData *> &variables)
2252 {
2253  bool feasible = true;
2254  bool needsSimplex = !constraints.isEmpty();
2255 
2256 #if 0
2257  qDebug("Simplex %s for trunk of %s", needsSimplex ? "used" : "NOT used",
2258  orientation == Horizontal ? "Horizontal" : "Vertical");
2259 #endif
2260 
2261  if (needsSimplex) {
2262 
2263  QList<QSimplexConstraint *> sizeHintConstraints = constraintsFromSizeHints(variables);
2264  QList<QSimplexConstraint *> allConstraints = constraints + sizeHintConstraints;
2265 
2266  shiftConstraints(allConstraints, g_offset);
2267 
2268  // Solve min and max size hints
2269  qreal min, max;
2270  feasible = solveMinMax(allConstraints, path, &min, &max);
2271 
2272  if (feasible) {
2273  solvePreferred(constraints, variables);
2274 
2275  // Calculate and set the preferred size for the layout,
2276  // from the edge sizes that were calculated above.
2277  qreal pref(0.0);
2278  foreach (const AnchorData *ad, path.positives) {
2279  pref += ad->sizeAtPreferred;
2280  }
2281  foreach (const AnchorData *ad, path.negatives) {
2282  pref -= ad->sizeAtPreferred;
2283  }
2284 
2285  sizeHints[orientation][Qt::MinimumSize] = min;
2286  sizeHints[orientation][Qt::PreferredSize] = pref;
2287  sizeHints[orientation][Qt::MaximumSize] = max;
2288  }
2289 
2290  qDeleteAll(sizeHintConstraints);
2291  shiftConstraints(constraints, -g_offset);
2292 
2293  } else {
2294  // No Simplex is necessary because the path was simplified all the way to a single
2295  // anchor.
2296  Q_ASSERT(path.positives.count() == 1);
2297  Q_ASSERT(path.negatives.count() == 0);
2298 
2299  AnchorData *ad = path.positives.toList()[0];
2300  ad->sizeAtMinimum = ad->minSize;
2301  ad->sizeAtPreferred = ad->prefSize;
2302  ad->sizeAtMaximum = ad->maxSize;
2303 
2304  sizeHints[orientation][Qt::MinimumSize] = ad->sizeAtMinimum;
2305  sizeHints[orientation][Qt::PreferredSize] = ad->sizeAtPreferred;
2306  sizeHints[orientation][Qt::MaximumSize] = ad->sizeAtMaximum;
2307  }
2308 
2309 #if defined(QT_DEBUG) || defined(Q_AUTOTEST_EXPORT)
2310  lastCalculationUsedSimplex[orientation] = needsSimplex;
2311 #endif
2312 
2313  return feasible;
2314 }
2315 
2320  const QList<AnchorData *> &variables)
2321 {
2322  shiftConstraints(constraints, g_offset);
2323  bool feasible = solvePreferred(constraints, variables);
2324 
2325  if (feasible) {
2326  // Propagate size at preferred to other sizes. Semi-floats always will be
2327  // in their sizeAtPreferred.
2328  for (int j = 0; j < variables.count(); ++j) {
2329  AnchorData *ad = variables.at(j);
2330  Q_ASSERT(ad);
2331  ad->sizeAtMinimum = ad->sizeAtPreferred;
2332  ad->sizeAtMaximum = ad->sizeAtPreferred;
2333  }
2334  }
2335 
2336  shiftConstraints(constraints, -g_offset);
2337  return feasible;
2338 }
2339 
2350 {
2351  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
2353 
2354  QLayoutStyleInfo styleInf = styleInfo();
2355  for (int i = 0; i < vertices.count(); ++i) {
2356  AnchorData *data = g.edgeData(vertices.at(i).first, vertices.at(i).second);
2357  data->refreshSizeHints(&styleInf);
2358  }
2359 }
2360 
2375 {
2377 
2378  QSet<AnchorData *> visited;
2379 
2380  AnchorVertex *root = layoutFirstVertex[orientation];
2381 
2382  graphPaths[orientation].insert(root, GraphPath());
2383 
2384  foreach (AnchorVertex *v, graph[orientation].adjacentVertices(root)) {
2385  queue.enqueue(qMakePair(root, v));
2386  }
2387 
2388  while(!queue.isEmpty()) {
2390  AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
2391 
2392  if (visited.contains(edge))
2393  continue;
2394 
2395  visited.insert(edge);
2396  GraphPath current = graphPaths[orientation].value(pair.first);
2397 
2398  if (edge->from == pair.first)
2399  current.positives.insert(edge);
2400  else
2401  current.negatives.insert(edge);
2402 
2403  graphPaths[orientation].insert(pair.second, current);
2404 
2405  foreach (AnchorVertex *v,
2406  graph[orientation].adjacentVertices(pair.second)) {
2407  queue.enqueue(qMakePair(pair.second, v));
2408  }
2409  }
2410 
2411  // We will walk through every reachable items (non-float) store them in a temporary set.
2412  // We them create a set of all items and subtract the non-floating items from the set in
2413  // order to get the floating items. The floating items is then stored in m_floatItems
2414  identifyFloatItems(visited, orientation);
2415 }
2416 
2431 {
2432  foreach (AnchorVertex *vertex, graphPaths[orientation].uniqueKeys())
2433  {
2434  int valueCount = graphPaths[orientation].count(vertex);
2435  if (valueCount == 1)
2436  continue;
2437 
2438  QList<GraphPath> pathsToVertex = graphPaths[orientation].values(vertex);
2439  for (int i = 1; i < valueCount; ++i) {
2440  constraints[orientation] += \
2441  pathsToVertex[0].constraint(pathsToVertex.at(i));
2442  }
2443  }
2444 }
2445 
2450 {
2451  Graph<AnchorVertex, AnchorData> &g = graph[orientation];
2453 
2454  for (int i = 0; i < vertices.count(); ++i) {
2455  AnchorData *ad = g.edgeData(vertices.at(i).first, vertices.at(i).second);
2456  ad->updateChildrenSizes();
2457  }
2458 }
2459 
2467  const QList<AnchorData *> &anchors)
2468 {
2469  if (anchors.isEmpty())
2470  return QList<QSimplexConstraint *>();
2471 
2472  // Look for the layout edge. That can be either the first half in case the
2473  // layout is split in two, or the whole layout anchor.
2474  Orientation orient = Orientation(anchors.first()->orientation);
2475  AnchorData *layoutEdge = 0;
2476  if (layoutCentralVertex[orient]) {
2477  layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutCentralVertex[orient]);
2478  } else {
2479  layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutLastVertex[orient]);
2480  }
2481 
2482  // If maxSize is less then "infinite", that means there are other anchors
2483  // grouped together with this one. We can't ignore its maximum value so we
2484  // set back the variable to NULL to prevent the continue condition from being
2485  // satisfied in the loop below.
2486  const qreal expectedMax = layoutCentralVertex[orient] ? QWIDGETSIZE_MAX / 2 : QWIDGETSIZE_MAX;
2487  qreal actualMax;
2488  if (layoutEdge->from == layoutFirstVertex[orient]) {
2489  actualMax = layoutEdge->maxSize;
2490  } else {
2491  actualMax = -layoutEdge->minSize;
2492  }
2493  if (actualMax != expectedMax) {
2494  layoutEdge = 0;
2495  }
2496 
2497  // For each variable, create constraints based on size hints
2498  QList<QSimplexConstraint *> anchorConstraints;
2499  bool unboundedProblem = true;
2500  for (int i = 0; i < anchors.size(); ++i) {
2501  AnchorData *ad = anchors.at(i);
2502 
2503  // Anchors that have their size directly linked to another one don't need constraints
2504  // For exammple, the second half of an item has exactly the same size as the first half
2505  // thus constraining the latter is enough.
2506  if (ad->dependency == AnchorData::Slave)
2507  continue;
2508 
2509  // To use negative variables inside simplex, we shift them so the minimum negative value is
2510  // mapped to zero before solving. To make sure that it works, we need to guarantee that the
2511  // variables are all inside a certain boundary.
2512  qreal boundedMin = qBound(-g_offset, ad->minSize, g_offset);
2513  qreal boundedMax = qBound(-g_offset, ad->maxSize, g_offset);
2514 
2515  if ((boundedMin == boundedMax) || qFuzzyCompare(boundedMin, boundedMax)) {
2517  c->variables.insert(ad, 1.0);
2518  c->constant = boundedMin;
2520  anchorConstraints += c;
2521  unboundedProblem = false;
2522  } else {
2524  c->variables.insert(ad, 1.0);
2525  c->constant = boundedMin;
2527  anchorConstraints += c;
2528 
2529  // We avoid adding restrictions to the layout internal anchors. That's
2530  // to prevent unnecessary fair distribution from happening due to this
2531  // artificial restriction.
2532  if (ad == layoutEdge)
2533  continue;
2534 
2535  c = new QSimplexConstraint;
2536  c->variables.insert(ad, 1.0);
2537  c->constant = boundedMax;
2539  anchorConstraints += c;
2540  unboundedProblem = false;
2541  }
2542  }
2543 
2544  // If no upper boundary restriction was added, add one to avoid unbounded problem
2545  if (unboundedProblem) {
2547  c->variables.insert(layoutEdge, 1.0);
2548  // The maximum size that the layout can take
2549  c->constant = g_offset;
2551  anchorConstraints += c;
2552  }
2553 
2554  return anchorConstraints;
2555 }
2556 
2562 {
2563  Q_ASSERT(layoutFirstVertex[orientation] && layoutLastVertex[orientation]);
2564 
2565  AnchorData *edgeL1 = 0;
2566  AnchorData *edgeL2 = 0;
2567 
2568  // The layout may have a single anchor between Left and Right or two half anchors
2569  // passing through the center
2570  if (layoutCentralVertex[orientation]) {
2571  edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutCentralVertex[orientation]);
2572  edgeL2 = graph[orientation].edgeData(layoutCentralVertex[orientation], layoutLastVertex[orientation]);
2573  } else {
2574  edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutLastVertex[orientation]);
2575  }
2576 
2577  QLinkedList<QSimplexConstraint *> remainingConstraints;
2578  for (int i = 0; i < constraints[orientation].count(); ++i) {
2579  remainingConstraints += constraints[orientation].at(i);
2580  }
2581  for (int i = 0; i < itemCenterConstraints[orientation].count(); ++i) {
2582  remainingConstraints += itemCenterConstraints[orientation].at(i);
2583  }
2584 
2585  QList<QSimplexConstraint *> trunkConstraints;
2586  QSet<QSimplexVariable *> trunkVariables;
2587 
2588  trunkVariables += edgeL1;
2589  if (edgeL2)
2590  trunkVariables += edgeL2;
2591 
2592  bool dirty;
2593  do {
2594  dirty = false;
2595 
2596  QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
2597  while (it != remainingConstraints.end()) {
2598  QSimplexConstraint *c = *it;
2599  bool match = false;
2600 
2601  // Check if this constraint have some overlap with current
2602  // trunk variables...
2603  foreach (QSimplexVariable *ad, trunkVariables) {
2604  if (c->variables.contains(ad)) {
2605  match = true;
2606  break;
2607  }
2608  }
2609 
2610  // If so, we add it to trunk, and erase it from the
2611  // remaining constraints.
2612  if (match) {
2613  trunkConstraints += c;
2614  trunkVariables += QSet<QSimplexVariable *>::fromList(c->variables.keys());
2615  it = remainingConstraints.erase(it);
2616  dirty = true;
2617  } else {
2618  // Note that we don't erase the constraint if it's not
2619  // a match, since in a next iteration of a do-while we
2620  // can pass on it again and it will be a match.
2621  //
2622  // For example: if trunk share a variable with
2623  // remainingConstraints[1] and it shares with
2624  // remainingConstraints[0], we need a second iteration
2625  // of the do-while loop to match both.
2626  ++it;
2627  }
2628  }
2629  } while (dirty);
2630 
2632  result += trunkConstraints;
2633 
2634  if (!remainingConstraints.isEmpty()) {
2635  QList<QSimplexConstraint *> nonTrunkConstraints;
2636  QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
2637  while (it != remainingConstraints.end()) {
2638  nonTrunkConstraints += *it;
2639  ++it;
2640  }
2641  result += nonTrunkConstraints;
2642  }
2643 
2644  return result;
2645 }
2646 
2656 {
2657  QSet<QGraphicsLayoutItem *> nonFloating;
2658 
2659  foreach (const AnchorData *ad, visited)
2660  identifyNonFloatItems_helper(ad, &nonFloating);
2661 
2662  QSet<QGraphicsLayoutItem *> allItems;
2663  foreach (QGraphicsLayoutItem *item, items)
2664  allItems.insert(item);
2665  m_floatItems[orientation] = allItems - nonFloating;
2666 }
2667 
2668 
2680 {
2682 
2683  switch(ad->type) {
2684  case AnchorData::Normal:
2685  if (ad->item && ad->item != q)
2686  nonFloatingItemsIdentifiedSoFar->insert(ad->item);
2687  break;
2689  foreach (const AnchorData *d, static_cast<const SequentialAnchorData *>(ad)->m_edges)
2690  identifyNonFloatItems_helper(d, nonFloatingItemsIdentifiedSoFar);
2691  break;
2692  case AnchorData::Parallel:
2693  identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->firstEdge, nonFloatingItemsIdentifiedSoFar);
2694  identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->secondEdge, nonFloatingItemsIdentifiedSoFar);
2695  break;
2696  }
2697 }
2698 
2709 {
2711  AnchorVertex *firstH, *secondH, *firstV, *secondV;
2712 
2713  qreal top;
2714  qreal left;
2715  qreal right;
2716 
2717  q->getContentsMargins(&left, &top, &right, 0);
2718  const Qt::LayoutDirection visualDir = visualDirection();
2719  if (visualDir == Qt::RightToLeft)
2720  qSwap(left, right);
2721 
2722  left += geom.left();
2723  top += geom.top();
2724  right = geom.right() - right;
2725 
2726  foreach (QGraphicsLayoutItem *item, items) {
2727  QRectF newGeom;
2728  QSizeF itemPreferredSize = item->effectiveSizeHint(Qt::PreferredSize);
2729  if (m_floatItems[Horizontal].contains(item)) {
2730  newGeom.setLeft(0);
2731  newGeom.setRight(itemPreferredSize.width());
2732  } else {
2733  firstH = internalVertex(item, Qt::AnchorLeft);
2734  secondH = internalVertex(item, Qt::AnchorRight);
2735 
2736  if (visualDir == Qt::LeftToRight) {
2737  newGeom.setLeft(left + firstH->distance);
2738  newGeom.setRight(left + secondH->distance);
2739  } else {
2740  newGeom.setLeft(right - secondH->distance);
2741  newGeom.setRight(right - firstH->distance);
2742  }
2743  }
2744 
2745  if (m_floatItems[Vertical].contains(item)) {
2746  newGeom.setTop(0);
2747  newGeom.setBottom(itemPreferredSize.height());
2748  } else {
2749  firstV = internalVertex(item, Qt::AnchorTop);
2750  secondV = internalVertex(item, Qt::AnchorBottom);
2751 
2752  newGeom.setTop(top + firstV->distance);
2753  newGeom.setBottom(top + secondV->distance);
2754  }
2755 
2756  item->setGeometry(newGeom);
2757  }
2758 }
2759 
2771 {
2773  QSet<AnchorVertex *> visited;
2774 
2775  // Get root vertex
2776  AnchorVertex *root = layoutFirstVertex[orientation];
2777 
2778  root->distance = 0;
2779  visited.insert(root);
2780 
2781  // Add initial edges to the queue
2782  foreach (AnchorVertex *v, graph[orientation].adjacentVertices(root)) {
2783  queue.enqueue(qMakePair(root, v));
2784  }
2785 
2786  // Do initial calculation required by "interpolateEdge()"
2787  setupEdgesInterpolation(orientation);
2788 
2789  // Traverse the graph and calculate vertex positions
2790  while (!queue.isEmpty()) {
2792  AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
2793 
2794  if (visited.contains(pair.second))
2795  continue;
2796 
2797  visited.insert(pair.second);
2798  interpolateEdge(pair.first, edge);
2799 
2800  QList<AnchorVertex *> adjacents = graph[orientation].adjacentVertices(pair.second);
2801  for (int i = 0; i < adjacents.count(); ++i) {
2802  if (!visited.contains(adjacents.at(i)))
2803  queue.enqueue(qMakePair(pair.second, adjacents.at(i)));
2804  }
2805  }
2806 }
2807 
2819  Orientation orientation)
2820 {
2822 
2823  qreal current;
2824  current = (orientation == Horizontal) ? q->contentsRect().width() : q->contentsRect().height();
2825 
2826  QPair<Interval, qreal> result;
2827  result = getFactor(current,
2828  sizeHints[orientation][Qt::MinimumSize],
2829  sizeHints[orientation][Qt::PreferredSize],
2830  sizeHints[orientation][Qt::PreferredSize],
2831  sizeHints[orientation][Qt::PreferredSize],
2832  sizeHints[orientation][Qt::MaximumSize]);
2833 
2834  interpolationInterval[orientation] = result.first;
2835  interpolationProgress[orientation] = result.second;
2836 }
2837 
2857 {
2858  const Orientation orientation = Orientation(edge->orientation);
2859  const QPair<Interval, qreal> factor(interpolationInterval[orientation],
2860  interpolationProgress[orientation]);
2861 
2862  qreal edgeDistance = interpolate(factor, edge->sizeAtMinimum, edge->sizeAtPreferred,
2863  edge->sizeAtPreferred, edge->sizeAtPreferred,
2864  edge->sizeAtMaximum);
2865 
2866  Q_ASSERT(edge->from == base || edge->to == base);
2867 
2868  // Calculate the distance for the vertex opposite to the base
2869  if (edge->from == base) {
2870  edge->to->distance = base->distance + edgeDistance;
2871  } else {
2872  edge->from->distance = base->distance - edgeDistance;
2873  }
2874 }
2875 
2877  GraphPath path, qreal *min, qreal *max)
2878 {
2879  QSimplex simplex;
2880  bool feasible = simplex.setConstraints(constraints);
2881  if (feasible) {
2882  // Obtain the objective constraint
2883  QSimplexConstraint objective;
2885  for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter)
2886  objective.variables.insert(*iter, 1.0);
2887 
2888  for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter)
2889  objective.variables.insert(*iter, -1.0);
2890 
2891  const qreal objectiveOffset = (path.positives.count() - path.negatives.count()) * g_offset;
2892  simplex.setObjective(&objective);
2893 
2894  // Calculate minimum values
2895  *min = simplex.solveMin() - objectiveOffset;
2896 
2897  // Save sizeAtMinimum results
2898  QList<AnchorData *> variables = getVariables(constraints);
2899  for (int i = 0; i < variables.size(); ++i) {
2900  AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
2901  ad->sizeAtMinimum = ad->result - g_offset;
2902  }
2903 
2904  // Calculate maximum values
2905  *max = simplex.solveMax() - objectiveOffset;
2906 
2907  // Save sizeAtMaximum results
2908  for (int i = 0; i < variables.size(); ++i) {
2909  AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
2910  ad->sizeAtMaximum = ad->result - g_offset;
2911  }
2912  }
2913  return feasible;
2914 }
2915 
2916 enum slackType { Grower = -1, Shrinker = 1 };
2918  qreal interval, slackType type)
2919 {
2920  QSimplexVariable *slack = new QSimplexVariable;
2921  sizeConstraint->variables.insert(slack, type);
2922 
2924  limit->variables.insert(slack, 1.0);
2926  limit->constant = interval;
2927 
2928  return qMakePair(slack, limit);
2929 }
2930 
2932  const QList<AnchorData *> &variables)
2933 {
2934  QList<QSimplexConstraint *> preferredConstraints;
2935  QList<QSimplexVariable *> preferredVariables;
2936  QSimplexConstraint objective;
2937 
2938  // Fill the objective coefficients for this variable. In the
2939  // end the objective function will be
2940  //
2941  // z = n * (A_shrinker_hard + A_grower_hard + B_shrinker_hard + B_grower_hard + ...) +
2942  // (A_shrinker_soft + A_grower_soft + B_shrinker_soft + B_grower_soft + ...)
2943  //
2944  // where n is the number of variables that have
2945  // slacks. Note that here we use the number of variables
2946  // as coefficient, this is to mark the "shrinker slack
2947  // variable" less likely to get value than the "grower
2948  // slack variable".
2949 
2950  // This will fill the values for the structural constraints
2951  // and we now fill the values for the slack constraints (one per variable),
2952  // which have this form (the constant A_pref was set when creating the slacks):
2953  //
2954  // A + A_shrinker_hard + A_shrinker_soft - A_grower_hard - A_grower_soft = A_pref
2955  //
2956  for (int i = 0; i < variables.size(); ++i) {
2957  AnchorData *ad = variables.at(i);
2958 
2959  // The layout original structure anchors are not relevant in preferred size calculation
2960  if (ad->isLayoutAnchor)
2961  continue;
2962 
2963  // By default, all variables are equal to their preferred size. If they have room to
2964  // grow or shrink, such flexibility will be added by the additional variables below.
2965  QSimplexConstraint *sizeConstraint = new QSimplexConstraint;
2966  preferredConstraints += sizeConstraint;
2967  sizeConstraint->variables.insert(ad, 1.0);
2968  sizeConstraint->constant = ad->prefSize + g_offset;
2969 
2970  // Can easily shrink
2972  const qreal softShrinkInterval = ad->prefSize - ad->minPrefSize;
2973  if (softShrinkInterval) {
2974  slack = createSlack(sizeConstraint, softShrinkInterval, Shrinker);
2975  preferredVariables += slack.first;
2976  preferredConstraints += slack.second;
2977 
2978  // Add to objective with ratio == 1 (soft)
2979  objective.variables.insert(slack.first, 1.0);
2980  }
2981 
2982  // Can easily grow
2983  const qreal softGrowInterval = ad->maxPrefSize - ad->prefSize;
2984  if (softGrowInterval) {
2985  slack = createSlack(sizeConstraint, softGrowInterval, Grower);
2986  preferredVariables += slack.first;
2987  preferredConstraints += slack.second;
2988 
2989  // Add to objective with ratio == 1 (soft)
2990  objective.variables.insert(slack.first, 1.0);
2991  }
2992 
2993  // Can shrink if really necessary
2994  const qreal hardShrinkInterval = ad->minPrefSize - ad->minSize;
2995  if (hardShrinkInterval) {
2996  slack = createSlack(sizeConstraint, hardShrinkInterval, Shrinker);
2997  preferredVariables += slack.first;
2998  preferredConstraints += slack.second;
2999 
3000  // Add to objective with ratio == N (hard)
3001  objective.variables.insert(slack.first, variables.size());
3002  }
3003 
3004  // Can grow if really necessary
3005  const qreal hardGrowInterval = ad->maxSize - ad->maxPrefSize;
3006  if (hardGrowInterval) {
3007  slack = createSlack(sizeConstraint, hardGrowInterval, Grower);
3008  preferredVariables += slack.first;
3009  preferredConstraints += slack.second;
3010 
3011  // Add to objective with ratio == N (hard)
3012  objective.variables.insert(slack.first, variables.size());
3013  }
3014  }
3015 
3016  QSimplex *simplex = new QSimplex;
3017  bool feasible = simplex->setConstraints(constraints + preferredConstraints);
3018  if (feasible) {
3019  simplex->setObjective(&objective);
3020 
3021  // Calculate minimum values
3022  simplex->solveMin();
3023 
3024  // Save sizeAtPreferred results
3025  for (int i = 0; i < variables.size(); ++i) {
3026  AnchorData *ad = variables.at(i);
3027  ad->sizeAtPreferred = ad->result - g_offset;
3028  }
3029  }
3030 
3031  // Make sure we delete the simplex solver -before- we delete the
3032  // constraints used by it.
3033  delete simplex;
3034 
3035  // Delete constraints and variables we created.
3036  qDeleteAll(preferredConstraints);
3037  qDeleteAll(preferredVariables);
3038 
3039  return feasible;
3040 }
3041 
3053 {
3055  that->calculateGraphs();
3056 
3057  bool floatConflict = !m_floatItems[0].isEmpty() || !m_floatItems[1].isEmpty();
3058 
3059  return graphHasConflicts[0] || graphHasConflicts[1] || floatConflict;
3060 }
3061 
3062 #ifdef QT_DEBUG
3064 {
3065  QFile file(QString::fromAscii("anchorlayout.%1.dot").arg(name));
3067  qWarning("Could not write to %s", file.fileName().toLocal8Bit().constData());
3068 
3069  QString str = QString::fromAscii("digraph anchorlayout {\nnode [shape=\"rect\"]\n%1}");
3070  QString dotContents = graph[0].serializeToDot();
3071  dotContents += graph[1].serializeToDot();
3072  file.write(str.arg(dotContents).toLocal8Bit());
3073 
3074  file.close();
3075 }
3076 #endif
3077 
3079 #endif //QT_NO_GRAPHICSVIEW
double d
Definition: qnumeric_p.h:62
QSizeF effectiveSizeHint(Qt::SizeHint which, const QSizeF &constraint=QSizeF()) const
Returns the effective size hint for this QGraphicsLayoutItem.
QString fileName() const
Returns the name set by setFileName() or to the QFile constructors.
Definition: qfile.cpp:470
void updateAnchorSizes(Orientation orientation)
iterator erase(iterator pos)
Removes the item pointed to by the iterator pos from the list, and returns an iterator to the next it...
Definition: qlinkedlist.h:470
virtual void setGeometry(const QRectF &rect)
This virtual function sets the geometry of the QGraphicsLayoutItem to rect, which is in parent coordi...
QString toString() const
qreal right() const
Returns the x-coordinate of the rectangle&#39;s right edge.
Definition: qrect.h:527
void dumpGraph(const QString &name=QString())
Q_CORE_EXPORT QByteArray qgetenv(const char *varName)
QLayoutStyleInfo & styleInfo() const
Represents an edge (anchor) in the internal graph.
void findPaths(Orientation orientation)
This method walks the graph using a breadth-first search to find paths between the root vertex and ea...
int type
Definition: qmetatype.cpp:239
QGraphicsAnchorPrivate(int version=QObjectPrivateVersion)
double qreal
Definition: qglobal.h:1193
void calculateGraphs()
Called on activation.
unsigned char c[8]
Definition: qnumeric_p.h:62
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
bool setConstraints(const QList< QSimplexConstraint *> constraints)
Sets the new constraints in the simplex solver and returns whether the problem is feasible...
Definition: qsimplex_p.cpp:135
QGraphicsAnchor * acquireGraphicsAnchor(AnchorData *data)
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
The QQueue class is a generic container that provides a queue.
Definition: qcontainerfwd.h:61
static QString fromAscii(const char *, int size=-1)
Returns a QString initialized with the first size characters from the string str. ...
Definition: qstring.cpp:4276
bool simplifyGraphIteration(Orientation orientation, bool *feasible)
One iteration of the simplification algorithm.
void clear()
Removes all items from the hash.
Definition: qhash.h:574
void refreshSizeHints(const QLayoutStyleInfo *styleInfo=0)
int remove(const Key &key)
Removes all the items that have the key from the hash.
Definition: qhash.h:784
QList< QSimplexConstraint * > m_firstConstraints
void remove(int i)
Removes the element at index position i.
Definition: qvector.h:374
void setLeft(qreal pos)
Sets the left edge of the rectangle to the given x coordinate.
Definition: qrect.h:670
bool solveMinMax(const QList< QSimplexConstraint *> &constraints, GraphPath path, qreal *min, qreal *max)
QSet< QGraphicsLayoutItem * > m_floatItems[2]
#define it(className, varName)
QGraphicsItem * graphicsItem() const
Returns the QGraphicsItem that this layout item represents.
QList< QList< QSimplexConstraint * > > getGraphParts(Orientation orientation)
bool open(OpenMode flags)
Opens the file using OpenMode mode, returning true if successful; otherwise false.
Definition: qfile.cpp:1064
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
QGraphicsLayoutItem * item
static int refcount
Definition: proxyconf.cpp:398
qreal solveMax()
Maximize the original objective.
Definition: qsimplex_p.cpp:594
qreal width() const
Returns the width.
Definition: qsize.h:284
iterator begin()
Returns an STL-style iterator pointing to the first item in the list.
Definition: qlinkedlist.h:182
Qt::AnchorPoint m_edge
T & first()
Returns a reference to the first item in the vector.
Definition: qvector.h:260
#define at(className, varName)
const_iterator constEnd() const
Definition: qset.h:171
bool isEmpty() const
Definition: qset.h:77
The QGraphicsAnchor class represents an anchor between two items in a QGraphicsAnchorLayout.
void createLayoutEdges()
Create internal anchors to connect the layout edges (Left to Right and Top to Bottom).
void addChildLayoutItem(QGraphicsLayoutItem *item)
This function is called from subclasses to add a layout item layoutItem to a layout.
The QGraphicsItem class is the base class for all graphical items in a QGraphicsScene.
Definition: qgraphicsitem.h:89
qreal height() const
Returns the height.
Definition: qsize.h:287
int count(const Key &key, const T &value) const
Returns the number of items with the key and value.
Definition: qhash.h:1023
qreal left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:525
T1 first
Definition: qpair.h:65
QHash< QPair< QGraphicsLayoutItem *, Qt::AnchorPoint >, QPair< AnchorVertex *, int > > m_vertexList
#define QWIDGETSIZE_MAX
Defines the maximum size for a QWidget object.
Definition: qwidget.h:1087
The QWidget class is the base class of all user interface objects.
Definition: qwidget.h:150
QMultiHash< AnchorVertex *, GraphPath > graphPaths[2]
QGraphicsAnchor * addAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge, qreal *spacing=0)
T2 second
Definition: qpair.h:66
bool isEmpty() const
Returns true if the list contains no items; otherwise returns false.
Definition: qlinkedlist.h:103
QList< QPair< Vertex *, Vertex * > > connections() const
Definition: qgraph_p.h:212
static Qt::AnchorPoint pickEdge(Qt::AnchorPoint edge, Orientation orientation)
static bool match(const uchar *found, const char *target, uint len)
QList< AnchorData * > getVariables(QList< QSimplexConstraint *> constraints)
void calculateVertexPositions(Orientation orientation)
Calculate the position of each vertex based on the paths to each of them as well as the current edges...
void setTop(qreal pos)
Sets the top edge of the rectangle to the given y coordinate.
Definition: qrect.h:674
const qreal g_offset
void setBottom(qreal pos)
Sets the bottom edge of the rectangle to the given y coordinate.
Definition: qrect.h:676
static Q_DECL_CONSTEXPR bool qFuzzyCompare(double p1, double p2)
Definition: qglobal.h:2030
QLatin1String(DBUS_INTERFACE_DBUS))) Q_GLOBAL_STATIC_WITH_ARGS(QString
The QStack class is a template class that provides a stack.
Definition: qcontainerfwd.h:63
QSimplexConstraint * constraint(const GraphPath &path) const
long ASN1_INTEGER_get ASN1_INTEGER * a
int count(const T &t) const
Returns the number of occurrences of value in the list.
Definition: qlist.h:891
static QStyle * style()
Returns the application&#39;s style object.
static qreal interpolate(const QPair< QGraphicsAnchorLayoutPrivate::Interval, qreal > &factor, qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)
The QString class provides a Unicode character string.
Definition: qstring.h:83
AnchorData * addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible)
Adds newAnchor to the graph.
T take(const Key &key)
Removes the item with the key from the hash and returns the value associated with it...
Definition: qhash.h:807
EdgeData * edgeData(Vertex *first, Vertex *second)
Definition: qgraph_p.h:143
QGraphicsAnchor * graphicsAnchor
void createEdge(Vertex *first, Vertex *second, EdgeData *data)
Definition: qgraph_p.h:148
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
The QVector class is a template class that provides a dynamic array.
Definition: qdatastream.h:64
Representation of a valid path for a given vertex in the graph.
QHash< QSimplexVariable *, qreal > variables
Definition: qsimplex_p.h:91
iterator begin()
Definition: qset.h:166
QGraphicsAnchorLayoutPrivate * layoutPrivate
static const uint base
Definition: qurl.cpp:268
bool contains(const Key &key) const
Returns true if the hash contains an item with the key; otherwise returns false.
Definition: qhash.h:872
The QSizeF class defines the size of a two-dimensional object using floating point precision...
Definition: qsize.h:202
const T value(const Key &key) const
Returns the value associated with the key.
Definition: qhash.h:606
void setRight(qreal pos)
Sets the right edge of the rectangle to the given x coordinate.
Definition: qrect.h:672
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
bool isEmpty() const
Returns true if the list contains no items; otherwise returns false.
Definition: qlist.h:152
iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:753
#define Q_Q(Class)
Definition: qglobal.h:2483
QList< QSimplexConstraint * > m_secondConstraints
T pop()
Removes the top item from the stack and returns it.
Definition: qstack.h:67
AnchorPoint
Definition: qnamespace.h:1586
Q_CORE_EXPORT void qDebug(const char *,...)
static QPair< QGraphicsAnchorLayoutPrivate::Interval, qreal > getFactor(qreal value, qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)
void removeCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge, bool substitute=true)
The QLinkedList class is a template class that provides linked lists.
Definition: qdatastream.h:63
QList< QSimplexConstraint * > constraintsFromSizeHints(const QList< AnchorData *> &anchors)
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
QSet< AnchorData * > negatives
static Qt::AnchorPoint oppositeEdge(Qt::AnchorPoint edge)
void setObjective(QSimplexConstraint *objective)
Definition: qsimplex_p.cpp:332
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
void refreshAllSizeHints(Orientation orientation)
Traverse the graph refreshing the size hints.
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
QString toString() const
QBool contains(const T &t) const
Returns true if the list contains an occurrence of value; otherwise returns false.
Definition: qlist.h:880
static void applySizePolicy(QSizePolicy::Policy policy, qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint, qreal *minSize, qreal *prefSize, qreal *maxSize)
void constraintsFromPaths(Orientation orientation)
Each vertex on the graph that has more than one path to it represents a contra int to the sizes of th...
QList< AnchorData * > anchorsFromSimplifiedVertices[2]
void clear()
Removes all the elements from the vector and releases the memory used by the vector.
Definition: qvector.h:347
bool contains(const T &value) const
Definition: qset.h:91
AnchorVertex * addInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
QList< T > toList() const
Definition: qset.h:296
static AnchorData * createSequence(Graph< AnchorVertex, AnchorData > *graph, AnchorVertex *before, const QVector< AnchorVertex *> &vertices, AnchorVertex *after)
Takes the sequence of vertices described by (before, vertices, after) and removes all anchors connect...
QList< Vertex * > adjacentVertices(Vertex *vertex) const
Definition: qgraph_p.h:195
const char * name
void removeAnchors(QGraphicsLayoutItem *item)
bool simplifyVertices(Orientation orientation)
const T & at(int i) const
Returns the item at index position i in the list.
Definition: qlist.h:468
const char * layout
LayoutDirection
Definition: qnamespace.h:1580
iterator end()
Definition: qset.h:169
void setDefaultSpacing(Qt::Orientation o, qreal spacing)
void append(const T &t)
Inserts value at the end of the vector.
Definition: qvector.h:573
QList< AnchorData * > m_secondAnchors
Q_CORE_EXPORT void qWarning(const char *,...)
const_iterator insert(const T &value)
Definition: qset.h:179
void restoreSimplifiedConstraints(ParallelAnchorData *parallel)
static const char * data(const QByteArray &arr)
static Orientation edgeOrientation(Qt::AnchorPoint edge)
QGraphicsLayoutItem * m_item
The QLinkedList::iterator class provides an STL-style non-const iterator for QLinkedList.
Definition: qlinkedlist.h:118
int count() const
Definition: qset.h:178
The QGraphicsLayoutItem class can be inherited to allow your custom items to be managed by layouts...
QVector< QGraphicsLayoutItem * > items
void clear()
Removes all items from the list.
Definition: qlist.h:764
int indexOf(const T &t, int from=0) const
Returns the index position of the first occurrence of value in the vector, searching forward from ind...
Definition: qvector.h:698
QGraphicsItem * parentItem() const
Returns the parent item of this layout, or 0 if this layout is not installed on any widget...
void removeAnchor_helper(AnchorVertex *v1, AnchorVertex *v2)
void setSpacing(qreal spacing)
QByteArray toLocal8Bit() const Q_REQUIRED_RESULT
Returns the local 8-bit representation of the string as a QByteArray.
Definition: qstring.cpp:4049
qreal perItemSpacing(QSizePolicy::ControlType control1, QSizePolicy::ControlType control2, Qt::Orientation orientation) const
void push(const T &t)
Adds element t to the top of the stack.
Definition: qstack.h:60
void removeCenterConstraints(QGraphicsLayoutItem *item, Orientation orientation)
void addAnchor_helper(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge, AnchorData *data)
QList< AnchorData * > m_firstAnchors
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
The QGraphicsAnchorLayout class provides a layout where one can anchor widgets together in Graphics V...
static QWidget * parentWidget(const QWidget *w)
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the list...
Definition: qlinkedlist.h:185
Q_CORE_EXPORT QTextStream & center(QTextStream &s)
bool isLayout() const
Returns true if this QGraphicsLayoutItem is a layout (e.g., is inherited by an object that arranges o...
T & first()
Returns a reference to the first item in the list.
Definition: qlist.h:282
const char * constData() const
Returns a pointer to the data stored in the byte array.
Definition: qbytearray.h:433
QHash< Key, T >::iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:934
AnchorVertex * to
void removeInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
void restoreSimplifiedAnchor(AnchorData *edge)
void enqueue(const T &t)
Adds value t to the tail of the queue.
Definition: qqueue.h:60
bool calculateNonTrunk(const QList< QSimplexConstraint *> &constraints, const QList< AnchorData *> &variables)
QString arg(qlonglong a, int fieldwidth=0, int base=10, const QChar &fillChar=QLatin1Char(' ')) const Q_REQUIRED_RESULT
Definition: qstring.cpp:7186
Qt::LayoutDirection visualDirection() const
static AnchorVertex * replaceVertex_helper(AnchorData *data, AnchorVertex *oldV, AnchorVertex *newV)
Graph< AnchorVertex, AnchorData > graph[2]
AnchorVertex * from
The QFile class provides an interface for reading from and writing to files.
Definition: qfile.h:65
QSet< AnchorData * > positives
QGraphicsLayoutItem * parentLayoutItem() const
Returns the parent of this QGraphicsLayoutItem, or 0 if there is no parent, or if the parent does not...
QString toString() const
bool solvePreferred(const QList< QSimplexConstraint *> &constraints, const QList< AnchorData *> &variables)
void setSizePolicy(QSizePolicy::Policy policy)
qreal defaultSpacing(Qt::Orientation o) const
QList< T > values() const
Returns a list containing all the values in the hash, in an arbitrary order.
Definition: qhash.h:693
void dump(int indent=2)
Q_OUTOFLINE_TEMPLATE QPair< T1, T2 > qMakePair(const T1 &x, const T2 &y)
Definition: qpair.h:102
bool hasConflicts() const
Returns true if there are no arrangement that satisfies all constraints.
T & last()
Returns a reference to the last item in the vector.
Definition: qvector.h:262
Q_DECL_CONSTEXPR const T & qBound(const T &min, const T &val, const T &max)
Definition: qglobal.h:1219
T & last()
Returns a reference to the last item in the list.
Definition: qlist.h:284
static qreal checkAdd(qreal a, qreal b)
void identifyNonFloatItems_helper(const AnchorData *ad, QSet< QGraphicsLayoutItem *> *nonFloatingItemsIdentifiedSoFar)
Given an anchor, if it is an internal anchor and Normal we must mark it&#39;s item as non-float...
static void shiftConstraints(const QList< QSimplexConstraint *> &constraints, qreal amount)
Shift all the constraints by a certain amount.
int size() const
Returns the number of items in the list.
Definition: qlist.h:137
The QStyle class is an abstract base class that encapsulates the look and feel of a GUI...
Definition: qstyle.h:68
void setItemsGeometries(const QRectF &geom)
Use the current vertices distance to calculate and set the geometry of each item. ...
bool isWidget() const
Returns true if this item is a widget (i.
void identifyFloatItems(const QSet< AnchorData *> &visited, Orientation orientation)
Use all visited Anchors on findPaths() so we can identify non-float Items.
const_iterator constBegin() const
Definition: qset.h:168
QString serializeToDot()
Definition: qgraph_p.h:226
T takeAt(int i)
Removes the item at index position i and returns it.
Definition: qlist.h:484
bool contains(const T &t) const
Returns true if the vector contains an occurrence of value; otherwise returns false.
Definition: qvector.h:731
void removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
quint16 index
QList< QSimplexConstraint * > constraints[2]
void changeLayoutVertex(Orientation orientation, AnchorVertex *oldV, AnchorVertex *newV)
EdgeData * takeEdge(Vertex *first, Vertex *second)
Definition: qgraph_p.h:179
qreal top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:526
The QSimplex class is a Linear Programming problem solver based on the two-phase simplex method...
Definition: qsimplex_p.h:149
bool isEmpty() const
Returns true if the byte array has size 0; otherwise returns false.
Definition: qbytearray.h:421
void correctEdgeDirection(QGraphicsLayoutItem *&firstItem, Qt::AnchorPoint &firstEdge, QGraphicsLayoutItem *&secondItem, Qt::AnchorPoint &secondEdge)
Use heuristics to determine the correct orientation of a given anchor.
QStyle * style() const
Returns a pointer to the widget&#39;s style.
bool isEmpty() const
Returns true if the vector has size 0; otherwise returns false.
Definition: qvector.h:139
bool simplifyGraph(Orientation orientation)
The purpose of this function is to simplify the graph.
bool replaceVertex(Orientation orientation, AnchorVertex *oldV, AnchorVertex *newV, const QList< AnchorData *> &edges)
bool calculateTrunk(Orientation orientation, const GraphPath &trunkPath, const QList< QSimplexConstraint *> &constraints, const QList< AnchorData *> &variables)
Calculate the sizes for all anchors which are part of the trunk.
QList< QSimplexConstraint * > itemCenterConstraints[2]
QGraphicsAnchor * getAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge)
void removeEdge(Vertex *first, Vertex *second)
Definition: qgraph_p.h:165
T dequeue()
Removes the head item in the queue and returns it.
Definition: qqueue.h:61
qint64 write(const char *data, qint64 len)
Writes at most maxSize bytes of data from data to the device.
Definition: qiodevice.cpp:1342
void setupEdgesInterpolation(Orientation orientation)
Calculate interpolation parameters based on current Layout Size.
static QSet< T > fromList(const QList< T > &list)
Definition: qset.h:319
QSizePolicy::Policy sizePolicy
QList< AnchorVertexPair * > simplifiedVertices[2]
AnchorVertex * internalVertex(const QPair< QGraphicsLayoutItem *, Qt::AnchorPoint > &itemEdge) const
void removeAnchor(AnchorVertex *firstVertex, AnchorVertex *secondVertex)
void restoreSimplifiedGraph(Orientation orientation)
virtual void close()
Calls QFile::flush() and closes the file.
Definition: qfile.cpp:1680
Orientation
Definition: qnamespace.h:174
#define qPrintable(string)
Definition: qglobal.h:1750
static QPair< QSimplexVariable *, QSimplexConstraint * > createSlack(QSimplexConstraint *sizeConstraint, qreal interval, slackType type)
void restoreVertices(Orientation orientation)
Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
Definition: qalgorithms.h:319
void createCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge)
By default, each item in the layout is represented internally as a single anchor in each direction...
void interpolateEdge(AnchorVertex *base, AnchorData *edge)
Calculate the current Edge size based on the current Layout size and the size the edge is supposed to...
QList< Key > keys() const
Returns a list containing all the keys in the hash, in an arbitrary order.
Definition: qhash.h:648
QGraphicsAnchorLayout private methods and attributes.
QVector< AnchorData * > m_edges
qreal solveMin()
Minimize the original objective.
Definition: qsimplex_p.cpp:582
QGraphicsLayoutItem * parent
The QList class is a template class that provides lists.
Definition: qdatastream.h:62
void createItemEdges(QGraphicsLayoutItem *item)
virtual void updateChildrenSizes()
The QGraphicsWidget class is the base class for all widget items in a QGraphicsScene.