/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include <QtGui/qwidget.h>

#include <QtGui/qapplication.h>

#include <QtCore/qlinkedlist.h>

#include <QtCore/qstack.h>

#ifdef QT_DEBUG

#include <QtCore/qfile.h>

#endif

#include "qgraphicsanchorlayout_p.h"

#ifndef QT_NO_GRAPHICSVIEW

QT_BEGIN_NAMESPACE

// To ensure that all variables inside the simplex solver are non-negative,

// we limit the size of anchors in the interval [-limit, limit]. Then before

// sending them to the simplex solver we add "limit" as an offset, so that

// they are actually calculated in the interval [0, 2 * limit]

// To avoid numerical errors in platforms where we use single precision,

// we use a tighter limit for the variables range.

const qreal g_offset = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32;

QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version)

    : QObjectPrivate(version), layoutPrivate(0), data(0),

      sizePolicy(QSizePolicy::Fixed), preferredSize(0),

      hasSize(true)

{

}

QGraphicsAnchorPrivate::~QGraphicsAnchorPrivate()

{

    if (data) {

        // The QGraphicsAnchor was already deleted at this moment. We must clean

        // the dangling pointer to avoid double deletion in the AnchorData dtor.

        data->graphicsAnchor = 0;

        layoutPrivate->removeAnchor(data->from, data->to);

    }

}

void QGraphicsAnchorPrivate::setSizePolicy(QSizePolicy::Policy policy)

{

    if (sizePolicy != policy) {

        sizePolicy = policy;

        layoutPrivate->q_func()->invalidate();

    }

}

void QGraphicsAnchorPrivate::setSpacing(qreal value)

{

    if (!data) {

        qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");

        return;

    }

    if (hasSize && (preferredSize == value))

        return;

    // The anchor has an user-defined size

    hasSize = true;

    preferredSize = value;

    layoutPrivate->q_func()->invalidate();

}

void QGraphicsAnchorPrivate::unsetSpacing()

{

    if (!data) {

        qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");

        return;

    }

    // Return to standard direction

    hasSize = false;

    layoutPrivate->q_func()->invalidate();

}

qreal QGraphicsAnchorPrivate::spacing() const

{

    if (!data) {

        qWarning("QGraphicsAnchor::setSpacing: The anchor does not exist.");

        return 0;

    }

    return preferredSize;

}

static void applySizePolicy(QSizePolicy::Policy policy,

                            qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint,

                            qreal *minSize, qreal *prefSize,

                            qreal *maxSize)

{

    // minSize, prefSize and maxSize are initialized

    // with item's preferred Size: this is QSizePolicy::Fixed.

    //

    // Then we check each flag to find the resultant QSizePolicy,

    // according to the following table:

    //

    //      constant               value

    // QSizePolicy::Fixed            0

    // QSizePolicy::Minimum       GrowFlag

    // QSizePolicy::Maximum       ShrinkFlag

    // QSizePolicy::Preferred     GrowFlag | ShrinkFlag

    // QSizePolicy::Ignored       GrowFlag | ShrinkFlag | IgnoreFlag

    if (policy & QSizePolicy::ShrinkFlag)

        *minSize = minSizeHint;

    else

        *minSize = prefSizeHint;

    if (policy & QSizePolicy::GrowFlag)

        *maxSize = maxSizeHint;

    else

        *maxSize = prefSizeHint;

    // Note that these two initializations are affected by the previous flags

    if (policy & QSizePolicy::IgnoreFlag)

        *prefSize = *minSize;

    else

        *prefSize = prefSizeHint;

}

AnchorData::~AnchorData()

{

    if (graphicsAnchor) {

        // Remove reference to ourself to avoid double removal in

        // QGraphicsAnchorPrivate dtor.

        graphicsAnchor->d_func()->data = 0;

        delete graphicsAnchor;

    }

}

void AnchorData::refreshSizeHints(const QLayoutStyleInfo *styleInfo)

{

    QSizePolicy::Policy policy;

    qreal minSizeHint;

    qreal prefSizeHint;

    qreal maxSizeHint;

    if (item) {

        // It is an internal anchor, fetch size information from the item

        if (isLayoutAnchor) {

            minSize = 0;

            prefSize = 0;

            maxSize = QWIDGETSIZE_MAX;

            if (isCenterAnchor)

                maxSize /= 2;

            minPrefSize = prefSize;

            maxPrefSize = maxSize;

            return;

        } else {

            if (orientation == QGraphicsAnchorLayoutPrivate::Horizontal) {

                policy = item->sizePolicy().horizontalPolicy();

                minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).width();

                prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).width();

                maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).width();

            } else {

                policy = item->sizePolicy().verticalPolicy();

                minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).height();

                prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).height();

                maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).height();

            }

            if (isCenterAnchor) {

                minSizeHint /= 2;

                prefSizeHint /= 2;

                maxSizeHint /= 2;

            }

        }

    } else {

        // It is a user-created anchor, fetch size information from the associated QGraphicsAnchor

        Q_ASSERT(graphicsAnchor);

        QGraphicsAnchorPrivate *anchorPrivate = graphicsAnchor->d_func();

        // Policy, min and max sizes are straightforward

        policy = anchorPrivate->sizePolicy;

        minSizeHint = 0;

        maxSizeHint = QWIDGETSIZE_MAX;

        // Preferred Size

        if (anchorPrivate->hasSize) {

            // Anchor has user-defined size

            prefSizeHint = anchorPrivate->preferredSize;

        } else {

            // Fetch size information from style

            const Qt::Orientation orient = Qt::Orientation(QGraphicsAnchorLayoutPrivate::edgeOrientation(from->m_edge) + 1);

            qreal s = styleInfo->defaultSpacing(orient);

            if (s < 0) {

                QSizePolicy::ControlType controlTypeFrom = from->m_item->sizePolicy().controlType();

                QSizePolicy::ControlType controlTypeTo = to->m_item->sizePolicy().controlType();

                s = styleInfo->perItemSpacing(controlTypeFrom, controlTypeTo, orient);

                // ### Currently we do not support negative anchors inside the graph.

                // To avoid those being created by a negative style spacing, we must

                // make this test.

                if (s < 0)

                    s = 0;

            }

            prefSizeHint = s;

        }

    }

    // Fill minSize, prefSize and maxSize based on policy and sizeHints

    applySizePolicy(policy, minSizeHint, prefSizeHint, maxSizeHint,

                    &minSize, &prefSize, &maxSize);

    minPrefSize = prefSize;

    maxPrefSize = maxSize;

    // Set the anchor effective sizes to preferred.

    //

    // Note: The idea here is that all items should remain at their

    // preferred size unless where that's impossible.  In cases where

    // the item is subject to restrictions (anchored to the layout

    // edges, for instance), the simplex solver will be run to

    // recalculate and override the values we set here.

    sizeAtMinimum = prefSize;

    sizeAtPreferred = prefSize;

    sizeAtMaximum = prefSize;

}

void ParallelAnchorData::updateChildrenSizes()

{

    firstEdge->sizeAtMinimum = sizeAtMinimum;

    firstEdge->sizeAtPreferred = sizeAtPreferred;

    firstEdge->sizeAtMaximum = sizeAtMaximum;

    if (secondForward()) {

        secondEdge->sizeAtMinimum = sizeAtMinimum;

        secondEdge->sizeAtPreferred = sizeAtPreferred;

        secondEdge->sizeAtMaximum = sizeAtMaximum;

    } else {

        secondEdge->sizeAtMinimum = -sizeAtMinimum;

        secondEdge->sizeAtPreferred = -sizeAtPreferred;

        secondEdge->sizeAtMaximum = -sizeAtMaximum;

    }

    firstEdge->updateChildrenSizes();

    secondEdge->updateChildrenSizes();

}

/*

  \internal

  Initialize the parallel anchor size hints using the sizeHint information from

  its children.

  Note that parallel groups can lead to unfeasibility, so during calculation, we can

  find out one unfeasibility. Because of that this method return boolean. This can't

  happen in sequential, so there the method is void.

 */

bool ParallelAnchorData::calculateSizeHints()

{

    // Normalize second child sizes.

    // A negative anchor of sizes min, minPref, pref, maxPref and max, is equivalent

    // to a forward anchor of sizes -max, -maxPref, -pref, -minPref, -min

    qreal secondMin;

    qreal secondMinPref;

    qreal secondPref;

    qreal secondMaxPref;

    qreal secondMax;

    if (secondForward()) {

        secondMin = secondEdge->minSize;

        secondMinPref = secondEdge->minPrefSize;

        secondPref = secondEdge->prefSize;

        secondMaxPref = secondEdge->maxPrefSize;

        secondMax = secondEdge->maxSize;

    } else {

        secondMin = -secondEdge->maxSize;

        secondMinPref = -secondEdge->maxPrefSize;

        secondPref = -secondEdge->prefSize;

        secondMaxPref = -secondEdge->minPrefSize;

        secondMax = -secondEdge->minSize;

    }

    minSize = qMax(firstEdge->minSize, secondMin);

    maxSize = qMin(firstEdge->maxSize, secondMax);

    // This condition means that the maximum size of one anchor being simplified is smaller than

    // the minimum size of the other anchor. The consequence is that there won't be a valid size

    // for this parallel setup.

    if (minSize > maxSize) {

        return false;

    }

    // Preferred size calculation

    // The calculation of preferred size is done as follows:

    //

    // 1) Check whether one of the child anchors is the layout structural anchor

    //    If so, we can simply copy the preferred information from the other child,

    //    after bounding it to our minimum and maximum sizes.

    //    If not, then we proceed with the actual calculations.

    //

    // 2) The whole algorithm for preferred size calculation is based on the fact

    //    that, if a given anchor cannot remain at its preferred size, it'd rather

    //    grow than shrink.

    //

    //    What happens though is that while this affirmative is true for simple

    //    anchors, it may not be true for sequential anchors that have one or more

    //    reversed anchors inside it. That happens because when a sequential anchor

    //    grows, any reversed anchors inside it may be required to shrink, something

    //    we try to avoid, as said above.

    //

    //    To overcome this, besides their actual preferred size "prefSize", each anchor

    //    exports what we call "minPrefSize" and "maxPrefSize". These two values define

    //    a surrounding interval where, if required to move, the anchor would rather

    //    remain inside.

    //

    //    For standard anchors, this area simply represents the region between

    //    prefSize and maxSize, which makes sense since our first affirmation.

    //    For composed anchors, these values are calculated as to reduce the global

    //    "damage", that is, to reduce the total deviation and the total amount of

    //    anchors that had to shrink.

    if (firstEdge->isLayoutAnchor) {

        prefSize = qBound(minSize, secondPref, maxSize);

        minPrefSize = qBound(minSize, secondMinPref, maxSize);

        maxPrefSize = qBound(minSize, secondMaxPref, maxSize);

    } else if (secondEdge->isLayoutAnchor) {

        prefSize = qBound(minSize, firstEdge->prefSize, maxSize);

        minPrefSize = qBound(minSize, firstEdge->minPrefSize, maxSize);

        maxPrefSize = qBound(minSize, firstEdge->maxPrefSize, maxSize);

    } else {

        // Calculate the intersection between the "preferred" regions of each child

        const qreal lowerBoundary =

            qBound(minSize, qMax(firstEdge->minPrefSize, secondMinPref), maxSize);

        const qreal upperBoundary =

            qBound(minSize, qMin(firstEdge->maxPrefSize, secondMaxPref), maxSize);

        const qreal prefMean =

            qBound(minSize, (firstEdge->prefSize + secondPref) / 2, maxSize);

        if (lowerBoundary < upperBoundary) {

            // If there is an intersection between the two regions, this intersection

            // will be used as the preferred region of the parallel anchor itself.

            // The preferred size will be the bounded average between the two preferred

            // sizes.

            prefSize = qBound(lowerBoundary, prefMean, upperBoundary);

            minPrefSize = lowerBoundary;

            maxPrefSize = upperBoundary;

        } else {

            // If there is no intersection, we have to attribute "damage" to at least

            // one of the children. The minimum total damage is achieved in points

            // inside the region that extends from (1) the upper boundary of the lower

            // region to (2) the lower boundary of the upper region.

            // Then, we expose this region as _our_ preferred region and once again,

            // use the bounded average as our preferred size.

            prefSize = qBound(upperBoundary, prefMean, lowerBoundary);

            minPrefSize = upperBoundary;

            maxPrefSize = lowerBoundary;

        }

    }

    // See comment in AnchorData::refreshSizeHints() about sizeAt* values

    sizeAtMinimum = prefSize;

    sizeAtPreferred = prefSize;

    sizeAtMaximum = prefSize;

    return true;

}

/*!

    \internal

    returns the factor in the interval [-1, 1].

    -1 is at Minimum

     0 is at Preferred

     1 is at Maximum

*/

static QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> getFactor(qreal value, qreal min,

                                                                      qreal minPref, qreal pref,

                                                                      qreal maxPref, qreal max)

{

    QGraphicsAnchorLayoutPrivate::Interval interval;

    qreal lower;

    qreal upper;

    if (value < minPref) {

        interval = QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred;

        lower = min;

        upper = minPref;

    } else if (value < pref) {

        interval = QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred;

        lower = minPref;

        upper = pref;

    } else if (value < maxPref) {

        interval = QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred;

        lower = pref;

        upper = maxPref;

    } else {

        interval = QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum;

        lower = maxPref;

        upper = max;

    }

    qreal progress;

    if (upper == lower) {

        progress = 0;

    } else {

        progress = (value - lower) / (upper - lower);

    }

    return qMakePair(interval, progress);

}

static qreal interpolate(const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> &factor,

                         qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)

{

    qreal lower;

    qreal upper;

    switch (factor.first) {

    case QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred:

        lower = min;

        upper = minPref;

        break;

    case QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred:

        lower = minPref;

        upper = pref;

        break;

    case QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred:

        lower = pref;

        upper = maxPref;

        break;

    case QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum:

        lower = maxPref;

        upper = max;

        break;

    }

    return lower + factor.second * (upper - lower);

}

void SequentialAnchorData::updateChildrenSizes()

{

    // Band here refers if the value is in the Minimum To Preferred

    // band (the lower band) or the Preferred To Maximum (the upper band).

    const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> minFactor =

        getFactor(sizeAtMinimum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);

    const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> prefFactor =

        getFactor(sizeAtPreferred, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);

    const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> maxFactor =

        getFactor(sizeAtMaximum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);

    // XXX This is not safe if Vertex simplification takes place after the sequential

    // anchor is created. In that case, "prev" will be a group-vertex, different from

    // "from" or "to", that _contains_ one of them.

    AnchorVertex *prev = from;

    for (int i = 0; i < m_edges.count(); ++i) {

        AnchorData *e = m_edges.at(i);

        const bool edgeIsForward = (e->from == prev);

        if (edgeIsForward) {

            e->sizeAtMinimum = interpolate(minFactor, e->minSize, e->minPrefSize,

                                           e->prefSize, e->maxPrefSize, e->maxSize);

            e->sizeAtPreferred = interpolate(prefFactor, e->minSize, e->minPrefSize,

                                           e->prefSize, e->maxPrefSize, e->maxSize);