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

**

** Copyright (C) 2009 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 <QtCore/qlinkedlist.h>

#include <QtCore/qstack.h>

#ifdef QT_DEBUG

#include <QtCore/qfile.h>

#endif

#include "qgraphicsanchorlayout_p.h"

QT_BEGIN_NAMESPACE

QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version)

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

      sizePolicy(QSizePolicy::Fixed)

{

}

QGraphicsAnchorPrivate::~QGraphicsAnchorPrivate()

{

    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) {

        layoutPrivate->setAnchorSize(data, &value);

    } else {

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

    }

}

void QGraphicsAnchorPrivate::unsetSpacing()

{

    if (data) {

        layoutPrivate->setAnchorSize(data, 0);

    } else {

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

    }

}

qreal QGraphicsAnchorPrivate::spacing() const

{

    qreal size = 0;

    if (data) {

        layoutPrivate->anchorSize(data, 0, &size, 0);

    } else {

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

    }

    return size;

}

static void internalSizeHints(QSizePolicy::Policy policy,

                              qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint,

                              qreal *minSize, qreal *prefSize,

                              qreal *expSize, 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;

    if (policy & QSizePolicy::ExpandFlag)

        *expSize = *maxSize;

    else

        *expSize = *prefSize;

}

void AnchorData::refreshSizeHints(qreal effectiveSpacing)

{

    const bool isInternalAnchor = from->m_item == to->m_item;

    QSizePolicy::Policy policy;

    qreal minSizeHint;

    qreal prefSizeHint;

    qreal maxSizeHint;

    if (isInternalAnchor) {

        const QGraphicsAnchorLayoutPrivate::Orientation orient =

            QGraphicsAnchorLayoutPrivate::edgeOrientation(from->m_edge);

        const Qt::AnchorPoint centerEdge =

            QGraphicsAnchorLayoutPrivate::pickEdge(Qt::AnchorHorizontalCenter, orient);

        bool hasCenter = (from->m_edge == centerEdge || to->m_edge == centerEdge);

        if (isLayoutAnchor) {

            minSize = 0;

            prefSize = 0;

            expSize = 0;

            maxSize = QWIDGETSIZE_MAX;

            if (hasCenter)

                maxSize /= 2;

            return;

        } else {

            QGraphicsLayoutItem *item = from->m_item;

            if (orient == 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 (hasCenter) {

                minSizeHint /= 2;

                prefSizeHint /= 2;

                maxSizeHint /= 2;

            }

        }

    } else {

        Q_ASSERT(graphicsAnchor);

        policy = graphicsAnchor->sizePolicy();

        minSizeHint = 0;

        if (hasSize) {

            // One can only configure the preferred size of a normal anchor. Their minimum and

            // maximum "size hints" are always 0 and QWIDGETSIZE_MAX, correspondingly. However,

            // their effective size hints might be narrowed down due to their size policies.

            prefSizeHint = prefSize;

        } else {

            prefSizeHint = effectiveSpacing;

        }

        maxSizeHint = QWIDGETSIZE_MAX;

    }

    internalSizeHints(policy, minSizeHint, prefSizeHint, maxSizeHint, 

                      &minSize, &prefSize, &expSize, &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;

    sizeAtExpanding = prefSize;

    sizeAtMaximum = prefSize;

}

void ParallelAnchorData::updateChildrenSizes()

{

    firstEdge->sizeAtMinimum = secondEdge->sizeAtMinimum = sizeAtMinimum;

    firstEdge->sizeAtPreferred = secondEdge->sizeAtPreferred = sizeAtPreferred;

    firstEdge->sizeAtExpanding = secondEdge->sizeAtExpanding = sizeAtExpanding;

    firstEdge->sizeAtMaximum = secondEdge->sizeAtMaximum = sizeAtMaximum;

    firstEdge->updateChildrenSizes();

    secondEdge->updateChildrenSizes();

}

void ParallelAnchorData::refreshSizeHints(qreal effectiveSpacing)

{

    refreshSizeHints_helper(effectiveSpacing);

}

void ParallelAnchorData::refreshSizeHints_helper(qreal effectiveSpacing,

                                                 bool refreshChildren)

{

    if (refreshChildren) {

        firstEdge->refreshSizeHints(effectiveSpacing);

        secondEdge->refreshSizeHints(effectiveSpacing);

    }

    // ### should we warn if the parallel connection is invalid?

    // e.g. 1-2-3 with 10-20-30, the minimum of the latter is

    // bigger than the maximum of the former.

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

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

    expSize = qMax(firstEdge->expSize, secondEdge->expSize);

    expSize = qMin(expSize, maxSize);

    prefSize = qMax(firstEdge->prefSize, secondEdge->prefSize);

    prefSize = qMin(prefSize, expSize);

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

    sizeAtMinimum = prefSize;

    sizeAtPreferred = prefSize;

    sizeAtExpanding = prefSize;

    sizeAtMaximum = prefSize;

}

/*!

    \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 pref, qreal exp,

                                                                      qreal max)

{

    QGraphicsAnchorLayoutPrivate::Interval interval;

    qreal lower;

    qreal upper;

    if (value < pref) {

        interval = QGraphicsAnchorLayoutPrivate::MinToPreferred;

        lower = min;

        upper = pref;

    } else if (value < exp) {

        interval = QGraphicsAnchorLayoutPrivate::PreferredToExpanding;

        lower = pref;

        upper = exp;

    } else {

        interval = QGraphicsAnchorLayoutPrivate::ExpandingToMax;

        lower = exp;

        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 pref,

                         qreal exp, qreal max)

{

    qreal lower;

    qreal upper;

    switch (factor.first) {

    case QGraphicsAnchorLayoutPrivate::MinToPreferred:

        lower = min;

        upper = pref;

        break;

    case QGraphicsAnchorLayoutPrivate::PreferredToExpanding:

        lower = pref;

        upper = exp;

        break;

    case QGraphicsAnchorLayoutPrivate::ExpandingToMax:

        lower = exp;

        upper = max;

        break;

    }

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

}

void SequentialAnchorData::updateChildrenSizes()

{

    // ### REMOVE ME

    // ### check whether we are guarantee to get those or we need to warn stuff at this

    // point.

    Q_ASSERT(sizeAtMinimum > minSize || qFuzzyCompare(sizeAtMinimum, minSize));

    Q_ASSERT(sizeAtMinimum < maxSize || qFuzzyCompare(sizeAtMinimum, maxSize));

    Q_ASSERT(sizeAtPreferred > minSize || qFuzzyCompare(sizeAtPreferred, minSize));

    Q_ASSERT(sizeAtPreferred < maxSize || qFuzzyCompare(sizeAtPreferred, maxSize));

    Q_ASSERT(sizeAtExpanding > minSize || qFuzzyCompare(sizeAtExpanding, minSize));

    Q_ASSERT(sizeAtExpanding < maxSize || qFuzzyCompare(sizeAtExpanding, maxSize));

    Q_ASSERT(sizeAtMaximum > minSize || qFuzzyCompare(sizeAtMaximum, minSize));

    Q_ASSERT(sizeAtMaximum < maxSize || qFuzzyCompare(sizeAtMaximum, maxSize));

    // 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, prefSize, expSize, maxSize);

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

        getFactor(sizeAtPreferred, minSize, prefSize, expSize, maxSize);

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

        getFactor(sizeAtExpanding, minSize, prefSize, expSize, maxSize);

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

        getFactor(sizeAtMaximum, minSize, prefSize, expSize, maxSize);

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

        AnchorData *e = m_edges.at(i);

        e->sizeAtMinimum = interpolate(minFactor, e->minSize, e->prefSize, e->expSize, e->maxSize);

        e->sizeAtPreferred = interpolate(prefFactor, e->minSize, e->prefSize, e->expSize, e->maxSize);

        e->sizeAtExpanding = interpolate(expFactor, e->minSize, e->prefSize, e->expSize, e->maxSize);

        e->sizeAtMaximum = interpolate(maxFactor, e->minSize, e->prefSize, e->expSize, e->maxSize);

        e->updateChildrenSizes();

    }

}

void SequentialAnchorData::refreshSizeHints(qreal effectiveSpacing)

{

    refreshSizeHints_helper(effectiveSpacing);

}

void SequentialAnchorData::refreshSizeHints_helper(qreal effectiveSpacing,

                                                   bool refreshChildren)

{

    minSize = 0;

    prefSize = 0;

    expSize = 0;

    maxSize = 0;

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

        AnchorData *edge = m_edges.at(i);

        // If it's the case refresh children information first

        if (refreshChildren)

            edge->refreshSizeHints(effectiveSpacing);

        minSize += edge->minSize;

        prefSize += edge->prefSize;

        expSize += edge->expSize;

        maxSize += edge->maxSize;

    }

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

    sizeAtMinimum = prefSize;

    sizeAtPreferred = prefSize;

    sizeAtExpanding = prefSize;

    sizeAtMaximum = prefSize;

}

#ifdef QT_DEBUG

void AnchorData::dump(int indent) {

    if (type == Parallel) {

        qDebug("%*s type: parallel:", indent, "");

        ParallelAnchorData *p = static_cast<ParallelAnchorData *>(this);

        p->firstEdge->dump(indent+2);

        p->secondEdge->dump(indent+2);

    } else if (type == Sequential) {

        SequentialAnchorData *s = static_cast<SequentialAnchorData *>(this);

        int kids = s->m_edges.count();

        qDebug("%*s type: sequential(%d):", indent, "", kids);

        for (int i = 0; i < kids; ++i) {

            s->m_edges.at(i)->dump(indent+2);

        }

    } else {

        qDebug("%*s type: Normal:", indent, "");

    }

}

#endif

QSimplexConstraint *GraphPath::constraint(const GraphPath &path) const

{

    // Calculate

    QSet<AnchorData *> cPositives;

    QSet<AnchorData *> cNegatives;

    QSet<AnchorData *> intersection;

    cPositives = positives + path.negatives;

    cNegatives = negatives + path.positives;

    intersection = cPositives & cNegatives;

    cPositives -= intersection;

    cNegatives -= intersection;

    // Fill

    QSimplexConstraint *c = new QSimplexConstraint;

    QSet<AnchorData *>::iterator i;

    for (i = cPositives.begin(); i != cPositives.end(); ++i)

        c->variables.insert(*i, 1.0);

    for (i = cNegatives.begin(); i != cNegatives.end(); ++i)

        c->variables.insert(*i, -1.0);

    return c;

}

#ifdef QT_DEBUG

QString GraphPath::toString() const

{

    QString string(QLatin1String("Path: "));

    foreach(AnchorData *edge, positives)

        string += QString::fromAscii(" (+++) %1").arg(edge->toString());

    foreach(AnchorData *edge, negatives)

        string += QString::fromAscii(" (---) %1").arg(edge->toString());

    return string;

}

#endif

QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()

    : calculateGraphCacheDirty(1)

{

    for (int i = 0; i < NOrientations; ++i) {

        for (int j = 0; j < 3; ++j) {

            sizeHints[i][j] = -1;

        }

        sizeAtExpanding[i] = -1;

        interpolationProgress[i] = -1;

        spacings[i] = -1;

        graphSimplified[i] = false;

        graphHasConflicts[i] = false;

    }

}

Qt::AnchorPoint QGraphicsAnchorLayoutPrivate::oppositeEdge(Qt::AnchorPoint edge)

{

    switch (edge) {

    case Qt::AnchorLeft:

        edge = Qt::AnchorRight;

        break;

    case Qt::AnchorRight:

        edge = Qt::AnchorLeft;

        break;

    case Qt::AnchorTop:

        edge = Qt::AnchorBottom;

        break;

    case Qt::AnchorBottom:

        edge = Qt::AnchorTop;

        break;

    default:

        break;

    }

    return edge;

}

/*!

 * \internal

 *

 * helper function in order to avoid overflowing anchor sizes

 * the returned size will never be larger than FLT_MAX

 *

 */

inline static qreal checkAdd(qreal a, qreal b)

{

    if (FLT_MAX - b  < a)

        return FLT_MAX;

    return a + b;

}

/*!

 * \internal

 *

 * Takes the sequence of vertices described by (\a before, \a vertices, \a after) and replaces

 * all anchors connected to the vertices in \a vertices with one simplified anchor between

 * \a before and \a after. The simplified anchor will be a placeholder for all the previous

 * anchors between \a before and \a after, and can be restored back to the anchors it is a

 * placeholder for.

 */

static bool simplifySequentialChunk(Graph<AnchorVertex, AnchorData> *graph,

                                    AnchorVertex *before,

                                    const QVector<AnchorVertex*> &vertices,

                                    AnchorVertex *after)

{

    AnchorData *data = graph->edgeData(before, vertices.first());

    Q_ASSERT(data);