← Back to branch summary

~ubuntu-branches/ubuntu/wily/qtbase-opensource-src/wily

« back to all changes in this revision

Viewing changes to src/widgets/graphicsview/qgraphicsanchorlayout_p.cpp

  • Committer: Package Import Robot
  • Author(s): Timo Jyrinki
  • Date: 2013-02-05 12:46:17 UTC
  • Revision ID: package-import@ubuntu.com-20130205124617-c8jouts182j002fx
Tags: upstream-5.0.1+dfsg
Import upstream version 5.0.1+dfsg

Show diffs side-by-side

added added

removed removed

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