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

**

** 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 "qglobal.h"

#ifndef QT_NO_GRAPHICSVIEW

#include <math.h>

#include "qgraphicslayoutitem.h"

#include "qgridlayoutengine_p.h"

#include "qstyleoption.h"

#include "qvarlengtharray.h"

#include <QtDebug>

#include <QtCore/qmath.h>

QT_BEGIN_NAMESPACE

template <typename T>

static void insertOrRemoveItems(QVector<T> &items, int index, int delta)

{

    int count = items.count();

    if (index < count) {

        if (delta > 0) {

            items.insert(index, delta, T());

        } else if (delta < 0) {

            items.remove(index, qMin(-delta, count - index));

        }

    }

}

static qreal growthFactorBelowPreferredSize(qreal desired, qreal sumAvailable, qreal sumDesired)

{

    Q_ASSERT(sumDesired != 0.0);

    return desired * qPow(sumAvailable / sumDesired, desired / sumDesired);

}

static qreal fixedDescent(qreal descent, qreal ascent, qreal targetSize)

{

    if (descent < 0.0)

        return -1.0;

    Q_ASSERT(descent >= 0.0);

    Q_ASSERT(ascent >= 0.0);

    Q_ASSERT(targetSize >= ascent + descent);

    qreal extra = targetSize - (ascent + descent);

    return descent + (extra / 2.0);

}

static qreal compare(const QGridLayoutBox &box1, const QGridLayoutBox &box2, int which)

{

    qreal size1 = box1.q_sizes(which);

    qreal size2 = box2.q_sizes(which);

    if (which == MaximumSize) {

        return size2 - size1;

    } else {

        return size1 - size2;

    }

}

void QGridLayoutBox::add(const QGridLayoutBox &other, int stretch, qreal spacing)

{

    Q_ASSERT(q_minimumDescent < 0.0);

    q_minimumSize += other.q_minimumSize + spacing;

    q_preferredSize += other.q_preferredSize + spacing;

    q_maximumSize += ((stretch == 0) ? other.q_preferredSize : other.q_maximumSize) + spacing;

}

void QGridLayoutBox::combine(const QGridLayoutBox &other)

{

    q_minimumDescent = qMax(q_minimumDescent, other.q_minimumDescent);

    q_minimumAscent = qMax(q_minimumAscent, other.q_minimumAscent);

    q_minimumSize = qMax(q_minimumAscent + q_minimumDescent,

                         qMax(q_minimumSize, other.q_minimumSize));

    qreal maxMax;

    if (q_maximumSize == FLT_MAX && other.q_maximumSize != FLT_MAX)

        maxMax = other.q_maximumSize;

    else if (other.q_maximumSize == FLT_MAX && q_maximumSize != FLT_MAX)

        maxMax = q_maximumSize;

    else

        maxMax = qMax(q_maximumSize, other.q_maximumSize);

    q_maximumSize = qMax(q_minimumSize, maxMax);

    q_preferredSize = qBound(q_minimumSize, qMax(q_preferredSize, other.q_preferredSize),

                             q_maximumSize);

}

void QGridLayoutBox::normalize()

{

    q_maximumSize = qMax(qreal(0.0), q_maximumSize);

    q_minimumSize = qBound(qreal(0.0), q_minimumSize, q_maximumSize);

    q_preferredSize = qBound(q_minimumSize, q_preferredSize, q_maximumSize);

    q_minimumDescent = qMin(q_minimumDescent, q_minimumSize);

    Q_ASSERT((q_minimumDescent < 0.0) == (q_minimumAscent < 0.0));

}

#ifdef QT_DEBUG

void QGridLayoutBox::dump(int indent) const

{

    qDebug("%*sBox (%g <= %g <= %g [%g/%g])", indent, "", q_minimumSize, q_preferredSize,

           q_maximumSize, q_minimumAscent, q_minimumDescent);

}

#endif

bool operator==(const QGridLayoutBox &box1, const QGridLayoutBox &box2)

{

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

        if (box1.q_sizes(i) != box2.q_sizes(i))

            return false;

    }

    return box1.q_minimumDescent == box2.q_minimumDescent

           && box1.q_minimumAscent == box2.q_minimumAscent;

}

void QGridLayoutRowData::reset(int count)

{

    ignore.fill(false, count);

    boxes.fill(QGridLayoutBox(), count);

    multiCellMap.clear();

    stretches.fill(0, count);

    spacings.fill(0.0, count);

    hasIgnoreFlag = false;

}

void QGridLayoutRowData::distributeMultiCells()

{

    MultiCellMap::const_iterator i = multiCellMap.constBegin();

    for (; i != multiCellMap.constEnd(); ++i) {

        int start = i.key().first;

        int span = i.key().second;

        int end = start + span;

        const QGridLayoutBox &box = i.value().q_box;

        int stretch = i.value().q_stretch;

        QGridLayoutBox totalBox = this->totalBox(start, end);

        QVarLengthArray<QGridLayoutBox> extras(span);

        QVarLengthArray<qreal> dummy(span);

        QVarLengthArray<qreal> newSizes(span);

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

            if (extra > 0.0) {

                                    0, totalBox);

                for (int k = 0; k < span; ++k)

                    extras[k].q_sizes(j) = newSizes[k];

            }

        }

        for (int k = 0; k < span; ++k) {

            boxes[start + k].combine(extras[k]);

            stretches[start + k] = qMax(stretches[start + k], stretch);

        }

    }

    multiCellMap.clear();

}

void QGridLayoutRowData::calculateGeometries(int start, int end, qreal targetSize, qreal *positions,

                                             qreal *sizes, qreal *descents,

                                             const QGridLayoutBox &totalBox)

{

    Q_ASSERT(end > start);

    targetSize = qBound(totalBox.q_minimumSize, targetSize, totalBox.q_maximumSize);

    int n = end - start;

    QVarLengthArray<qreal> newSizes(n);

    QVarLengthArray<qreal> factors(n);

    qreal sumFactors = 0.0;

    int sumStretches = 0;

    qreal sumAvailable;

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

        if (stretches[start + i] > 0)

            sumStretches += stretches[start + i];

    }

    if (targetSize < totalBox.q_preferredSize) {

        stealBox(start, end, MinimumSize, positions, sizes);

        sumAvailable = targetSize - totalBox.q_minimumSize;

        if (sumAvailable > 0.0) {

            qreal sumDesired = totalBox.q_preferredSize - totalBox.q_minimumSize;

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

                if (ignore.testBit(start + i)) {

                    factors[i] = 0.0;

                    continue;

                }

                const QGridLayoutBox &box = boxes.at(start + i);

                qreal desired = box.q_preferredSize - box.q_minimumSize;

                factors[i] = growthFactorBelowPreferredSize(desired, sumAvailable, sumDesired);

                sumFactors += factors[i];

            }

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

                Q_ASSERT(sumFactors > 0.0);

                qreal delta = sumAvailable * factors[i] / sumFactors;

                newSizes[i] = sizes[i] + delta;

            }

        }

    } else {

        stealBox(start, end, PreferredSize, positions, sizes);

        sumAvailable = targetSize - totalBox.q_preferredSize;

        if (sumAvailable > 0.0) {

            bool somethingHasAMaximumSize = false;

            qreal sumPreferredSizes = 0.0;

            for (int i = 0; i < n; ++i)

                sumPreferredSizes += sizes[i];

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

                if (ignore.testBit(start + i)) {

                    newSizes[i] = 0.0;

                    factors[i] = 0.0;

                    continue;

                }

                const QGridLayoutBox &box = boxes.at(start + i);

                qreal desired = box.q_maximumSize - box.q_preferredSize;

                if (desired == 0.0) {

                    newSizes[i] = sizes[i];

                    factors[i] = 0.0;

                } else {

                    Q_ASSERT(desired > 0.0);

                    int stretch = stretches[start + i];

                    if (sumStretches == 0) {

                        if (hasIgnoreFlag) {

                            factors[i] = (stretch < 0) ? 1.0 : 0.0;

                        } else {

                            factors[i] = (stretch < 0) ? sizes[i] : 0.0;

                        }

                    } else if (stretch == sumStretches) {

                        factors[i] = 1.0;

                    } else if (stretch <= 0) {

                        factors[i] = 0.0;

                    } else {

                        qreal ultimatePreferredSize;

                        qreal ultimateSumPreferredSizes;

                        qreal x = ((stretch * sumPreferredSizes)

                                   - (sumStretches * box.q_preferredSize))

                                  / (sumStretches - stretch);

                        if (x >= 0.0) {

                            ultimatePreferredSize = box.q_preferredSize + x;

                            ultimateSumPreferredSizes = sumPreferredSizes + x;

                        } else {

                            ultimatePreferredSize = box.q_preferredSize;

                            ultimateSumPreferredSizes = (sumStretches * box.q_preferredSize)

                                                        / stretch;

                        }

                        /*

                            We multiply these by 1.5 to give some space for a smooth transition

                            (at the expense of the stretch factors, which are not fully respected

                            during the transition).

                        */

                        ultimatePreferredSize = ultimatePreferredSize * 3 / 2;

                        ultimateSumPreferredSizes = ultimateSumPreferredSizes * 3 / 2;

                        qreal ultimateFactor = (stretch * ultimateSumPreferredSizes

                                                / sumStretches)

                                               - (box.q_preferredSize);

                        qreal transitionalFactor = sumAvailable

                                                   * (ultimatePreferredSize - box.q_preferredSize)

                                                   / (ultimateSumPreferredSizes

                                                      - sumPreferredSizes);

                        qreal alpha = qMin(sumAvailable,

                                           ultimateSumPreferredSizes - sumPreferredSizes);

                        qreal beta = ultimateSumPreferredSizes - sumPreferredSizes;

                        factors[i] = ((alpha * ultimateFactor)

                                      + ((beta - alpha) * transitionalFactor)) / beta;

                    }

                    sumFactors += factors[i];

                    if (desired < sumAvailable)

                        somethingHasAMaximumSize = true;

                    newSizes[i] = -1.0;

                }

            }

            bool keepGoing = somethingHasAMaximumSize;

            while (keepGoing) {

                keepGoing = false;

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

                    if (newSizes[i] >= 0.0)

                        continue;

                    const QGridLayoutBox &box = boxes.at(start + i);

                    qreal avail = sumAvailable * factors[i] / sumFactors;

                    if (sizes[i] + avail >= box.q_maximumSize) {

                        newSizes[i] = box.q_maximumSize;

                        sumAvailable -= box.q_maximumSize - sizes[i];

                        sumFactors -= factors[i];

                        keepGoing = (sumAvailable > 0.0);

                        if (!keepGoing)

                            break;

                    }

                }

            }

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

                if (newSizes[i] < 0.0) {

                    qreal delta = (sumFactors == 0.0) ? 0.0

                                                      : sumAvailable * factors[i] / sumFactors;

                    newSizes[i] = sizes[i] + delta;

                }

            }

        }

    }

    if (sumAvailable > 0) {

        qreal offset = 0;

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

            qreal delta = newSizes[i] - sizes[i];

            positions[i] += offset;

            sizes[i] += delta;

            offset += delta;

        }

#if 0 // some "pixel allocation"

        int surplus = targetSize - (positions[n - 1] + sizes[n - 1]);

        Q_ASSERT(surplus >= 0 && surplus <= n);

        int prevSurplus = -1;

        while (surplus > 0 && surplus != prevSurplus) {

            prevSurplus = surplus;

            int offset = 0;

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

                const QGridLayoutBox &box = boxes.at(start + i);

                int delta = (!ignore.testBit(start + i) && surplus > 0

                             && factors[i] > 0 && sizes[i] < box.q_maximumSize)

                    ? 1 : 0;

                positions[i] += offset;

                sizes[i] += delta;

                offset += delta;

                surplus -= delta;

            }

        }

        Q_ASSERT(surplus == 0);

#endif

    }

    if (descents) {

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

            if (ignore.testBit(start + i))

                continue;

            const QGridLayoutBox &box = boxes.at(start + i);

            descents[i] = fixedDescent(box.q_minimumDescent, box.q_minimumAscent, sizes[i]);

        }

    }

}

QGridLayoutBox QGridLayoutRowData::totalBox(int start, int end) const

{

    QGridLayoutBox result;

    if (start < end) {

        result.q_maximumSize = 0.0;

        qreal nextSpacing = 0.0;

        for (int i = start; i < end; ++i) {

            result.add(boxes.at(i), stretches.at(i), nextSpacing);

            nextSpacing = spacings.at(i);

        }

    }

    return result;

}

void QGridLayoutRowData::stealBox(int start, int end, int which, qreal *positions, qreal *sizes)

{

    qreal offset = 0.0;

    qreal nextSpacing = 0.0;

    for (int i = start; i < end; ++i) {

        qreal avail = 0.0;

        if (!ignore.testBit(i)) {

            const QGridLayoutBox &box = boxes.at(i);

            avail = box.q_sizes(which);

            offset += nextSpacing;

            nextSpacing = spacings.at(i);

        }

        *positions++ = offset;

        *sizes++ = avail;

        offset += avail;

    }

}

#ifdef QT_DEBUG

void QGridLayoutRowData::dump(int indent) const

{

    qDebug("%*sData", indent, "");

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

        qDebug("%*s Row %d (stretch %d, spacing %g)", indent, "", i, stretches.at(i),

               spacings.at(i));

        if (ignore.testBit(i))

            qDebug("%*s  Ignored", indent, "");

        boxes.at(i).dump(indent + 2);

    }

    MultiCellMap::const_iterator it = multiCellMap.constBegin();

    while (it != multiCellMap.constEnd()) {

        qDebug("%*s Multi-cell entry <%d, %d> (stretch %d)", indent, "", it.key().first,

               it.key().second, it.value().q_stretch);

        it.value().q_box.dump(indent + 2);

    }

}

#endif

QGridLayoutItem::QGridLayoutItem(QGridLayoutEngine *engine, QGraphicsLayoutItem *layoutItem,

                                 int row, int column, int rowSpan, int columnSpan,

                                 Qt::Alignment alignment, int itemAtIndex)

    : q_engine(engine), q_layoutItem(layoutItem), q_alignment(alignment)

{

    q_firstRows[Hor] = column;

    q_firstRows[Ver] = row;

    q_rowSpans[Hor] = columnSpan;

    q_rowSpans[Ver] = rowSpan;

    q_stretches[Hor] = -1;

    q_stretches[Ver] = -1;

    q_engine->insertItem(this, itemAtIndex);

}

int QGridLayoutItem::firstRow(Qt::Orientation orientation) const

{

    return q_firstRows[orientation == Qt::Vertical];

}

int QGridLayoutItem::firstColumn(Qt::Orientation orientation) const

{

    return q_firstRows[orientation == Qt::Horizontal];

}

int QGridLayoutItem::lastRow(Qt::Orientation orientation) const

{

    return firstRow(orientation) + rowSpan(orientation) - 1;

}

int QGridLayoutItem::lastColumn(Qt::Orientation orientation) const

{

    return firstColumn(orientation) + columnSpan(orientation) - 1;

}

int QGridLayoutItem::rowSpan(Qt::Orientation orientation) const

{

    return q_rowSpans[orientation == Qt::Vertical];

}

int QGridLayoutItem::columnSpan(Qt::Orientation orientation) const

{

    return q_rowSpans[orientation == Qt::Horizontal];

}

void QGridLayoutItem::setFirstRow(int row, Qt::Orientation orientation)

{

    q_firstRows[orientation == Qt::Vertical] = row;

}

void QGridLayoutItem::setRowSpan(int rowSpan, Qt::Orientation orientation)

{

    q_rowSpans[orientation == Qt::Vertical] = rowSpan;

}

int QGridLayoutItem::stretchFactor(Qt::Orientation orientation) const

{

    int stretch = q_stretches[orientation == Qt::Vertical];

    if (stretch >= 0)

        return stretch;

    QSizePolicy::Policy policy = sizePolicy(orientation);

    if (policy & QSizePolicy::ExpandFlag) {

        return 1;