/*

 * This file is part of the render object implementation for KHTML.

 *

 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)

 *           (C) 1999 Antti Koivisto (koivisto@kde.org)

 * Copyright (C) 2003 Apple Computer, Inc.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Library General Public

 * License as published by the Free Software Foundation; either

 * version 2 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Library General Public License for more details.

 *

 * You should have received a copy of the GNU Library General Public License

 * along with this library; see the file COPYING.LIB.  If not, write to

 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

 * Boston, MA 02110-1301, USA.

 *

 */

#include "config.h"

#include "RenderFlexibleBox.h"

#include "CharacterNames.h"

#include "RenderLayer.h"

#include "RenderView.h"

using namespace std;

namespace WebCore {

class FlexBoxIterator {

public:

    FlexBoxIterator(RenderFlexibleBox* parent) {

        box = parent;

        if (box->style()->boxOrient() == HORIZONTAL && box->style()->direction() == RTL)

            forward = box->style()->boxDirection() != BNORMAL;

        else

            forward = box->style()->boxDirection() == BNORMAL;

        lastOrdinal = 1; 

        if (!forward) {

            // No choice, since we're going backwards, we have to find out the highest ordinal up front.

            RenderObject* child = box->firstChild();

            while (child) {

                if (child->style()->boxOrdinalGroup() > lastOrdinal)

                    lastOrdinal = child->style()->boxOrdinalGroup();

                child = child->nextSibling();

            }

        }

        reset();

    }

    void reset() {

        current = 0;

        currentOrdinal = forward ? 0 : lastOrdinal+1;

    }

    RenderObject* first() {

        reset();

        return next();

    }

    RenderObject* next() {

        do { 

            if (!current) {

                if (forward) {

                    currentOrdinal++; 

                    if (currentOrdinal > lastOrdinal)

                        return 0;

                    current = box->firstChild();

                } else {

                    currentOrdinal--;

                    if (currentOrdinal == 0)

                        return 0;

                    current = box->lastChild();

                }

            }

            else

                current = forward ? current->nextSibling() : current->previousSibling();

            if (current && current->style()->boxOrdinalGroup() > lastOrdinal)

                lastOrdinal = current->style()->boxOrdinalGroup();

        } while (!current || current->style()->boxOrdinalGroup() != currentOrdinal ||

                 current->style()->visibility() == COLLAPSE);

        return current;

    }

private:

    RenderFlexibleBox* box;

    RenderObject* current;

    bool forward;

    unsigned int currentOrdinal;

    unsigned int lastOrdinal;

};

RenderFlexibleBox::RenderFlexibleBox(Node* node)

:RenderBlock(node)

{

    setChildrenInline(false); // All of our children must be block-level

    m_flexingChildren = m_stretchingChildren = false;

}

RenderFlexibleBox::~RenderFlexibleBox()

{

}

void RenderFlexibleBox::calcHorizontalPrefWidths()

{

    RenderObject *child = firstChild();

    while (child) {

        // positioned children don't affect the minmaxwidth

        if (child->isPositioned() || child->style()->visibility() == COLLAPSE) {

            child = child->nextSibling();

            continue;

        }

        // A margin basically has three types: fixed, percentage, and auto (variable).

        // Auto and percentage margins simply become 0 when computing min/max width.

        // Fixed margins can be added in as is.

        Length ml = child->style()->marginLeft();

        Length mr = child->style()->marginRight();

        int margin = 0, marginLeft = 0, marginRight = 0;

        if (ml.isFixed())

            marginLeft += ml.value();

        if (mr.isFixed())

            marginRight += mr.value();

        margin = marginLeft + marginRight;

        m_minPrefWidth += child->minPrefWidth() + margin;

        m_maxPrefWidth += child->maxPrefWidth() + margin;

        child = child->nextSibling();

    }    

}

void RenderFlexibleBox::calcVerticalPrefWidths()

{

    RenderObject *child = firstChild();

    while(child != 0)

    {

        // Positioned children and collapsed children don't affect the min/max width

        if (child->isPositioned() || child->style()->visibility() == COLLAPSE) {

            child = child->nextSibling();

            continue;

        }

        // A margin basically has three types: fixed, percentage, and auto (variable).

        // Auto/percentage margins simply become 0 when computing min/max width.

        // Fixed margins can be added in as is.

        Length ml = child->style()->marginLeft();

        Length mr = child->style()->marginRight();

        int margin = 0;

        if (ml.isFixed())

            margin += ml.value();

        if (mr.isFixed())

            margin += mr.value();

        int w = child->minPrefWidth() + margin;

        m_minPrefWidth = max(w, m_minPrefWidth);

        w = child->maxPrefWidth() + margin;

        m_maxPrefWidth = max(w, m_maxPrefWidth);

        child = child->nextSibling();

    }    

}

void RenderFlexibleBox::calcPrefWidths()

{

    ASSERT(prefWidthsDirty());

    if (style()->width().isFixed() && style()->width().value() > 0)

        m_minPrefWidth = m_maxPrefWidth = calcContentBoxWidth(style()->width().value());

    else {

        m_minPrefWidth = m_maxPrefWidth = 0;

        if (hasMultipleLines() || isVertical())

            calcVerticalPrefWidths();

        else

            calcHorizontalPrefWidths();

        m_maxPrefWidth = max(m_minPrefWidth, m_maxPrefWidth);

    }

    if (style()->minWidth().isFixed() && style()->minWidth().value() > 0) {

        m_maxPrefWidth = max(m_maxPrefWidth, calcContentBoxWidth(style()->minWidth().value()));

        m_minPrefWidth = max(m_minPrefWidth, calcContentBoxWidth(style()->minWidth().value()));

    }

    if (style()->maxWidth().isFixed() && style()->maxWidth().value() != undefinedLength) {

        m_maxPrefWidth = min(m_maxPrefWidth, calcContentBoxWidth(style()->maxWidth().value()));

        m_minPrefWidth = min(m_minPrefWidth, calcContentBoxWidth(style()->maxWidth().value()));

    }

    int toAdd = borderLeft() + borderRight() + paddingLeft() + paddingRight();

    m_minPrefWidth += toAdd;

    m_maxPrefWidth += toAdd;

    setPrefWidthsDirty(false);

}

void RenderFlexibleBox::layoutBlock(bool relayoutChildren)

{

    ASSERT(needsLayout());

    if (!relayoutChildren && layoutOnlyPositionedObjects())

        return;

    IntRect oldBounds;

    IntRect oldOutlineBox;

    bool checkForRepaint = checkForRepaintDuringLayout();

    if (checkForRepaint) {

        oldBounds = absoluteClippedOverflowRect();

        oldOutlineBox = absoluteOutlineBox();

    }

    view()->pushLayoutState(this, IntSize(m_x, m_y));

    int previousWidth = m_width;

    int previousHeight = m_height;

    calcWidth();

    calcHeight();

    m_overflowWidth = m_width;

    if (previousWidth != m_width || previousHeight != m_height ||

        (parent()->isFlexibleBox() && parent()->style()->boxOrient() == HORIZONTAL &&

         parent()->style()->boxAlign() == BSTRETCH))

        relayoutChildren = true;

    m_height = 0;

    m_overflowHeight = 0;

    m_flexingChildren = m_stretchingChildren = false;

    initMaxMarginValues();

    // For overflow:scroll blocks, ensure we have both scrollbars in place always.

    if (scrollsOverflow()) {

        if (style()->overflowX() == OSCROLL)

            m_layer->setHasHorizontalScrollbar(true);

        if (style()->overflowY() == OSCROLL)

            m_layer->setHasVerticalScrollbar(true);

    }

    if (isHorizontal())

        layoutHorizontalBox(relayoutChildren);

    else

        layoutVerticalBox(relayoutChildren);

    int oldHeight = m_height;

    calcHeight();

    if (oldHeight != m_height) {

        // If the block got expanded in size, then increase our overflowheight to match.

        if (m_overflowHeight > m_height)

            m_overflowHeight -= (borderBottom() + paddingBottom() + horizontalScrollbarHeight());

        if (m_overflowHeight < m_height)

            m_overflowHeight = m_height;

    }

    if (previousHeight != m_height)

        relayoutChildren = true;

    layoutPositionedObjects(relayoutChildren || isRoot());

    if (!isFloatingOrPositioned() && m_height == 0) {

        // We are a block with no border and padding and a computed height

        // of 0.  The CSS spec states that zero-height blocks collapse their margins

        // together.

        // When blocks are self-collapsing, we just use the top margin values and set the

        // bottom margin max values to 0.  This way we don't factor in the values

        // twice when we collapse with our previous vertically adjacent and

        // following vertically adjacent blocks.

        int pos = maxTopPosMargin();

        int neg = maxTopNegMargin();

        if (maxBottomPosMargin() > pos)

            pos = maxBottomPosMargin();

        if (maxBottomNegMargin() > neg)

            neg = maxBottomNegMargin();

        setMaxTopMargins(pos, neg);

        setMaxBottomMargins(0, 0);

    }

    // Always ensure our overflow width is at least as large as our width.

    if (m_overflowWidth < m_width)

        m_overflowWidth = m_width;

    if (!hasOverflowClip()) {

        if (ShadowData* boxShadow = style()->boxShadow()) {

            m_overflowLeft = min(m_overflowLeft, boxShadow->x - boxShadow->blur);

            m_overflowWidth = max(m_overflowWidth, m_width + boxShadow->x + boxShadow->blur);

            m_overflowTop = min(m_overflowTop, boxShadow->y - boxShadow->blur);

            m_overflowHeight = max(m_overflowHeight, m_height + boxShadow->y + boxShadow->blur);

        }

    }

    view()->popLayoutState();

    // Update our scrollbars if we're overflow:auto/scroll/hidden now that we know if

    // we overflow or not.

    if (hasOverflowClip())

        m_layer->updateScrollInfoAfterLayout();

    // Repaint with our new bounds if they are different from our old bounds.

    if (checkForRepaint)

        repaintAfterLayoutIfNeeded(oldBounds, oldOutlineBox);

    setNeedsLayout(false);

}

void RenderFlexibleBox::layoutHorizontalBox(bool relayoutChildren)

{

    int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();

    int yPos = borderTop() + paddingTop();

    int xPos = borderLeft() + paddingLeft();

    bool heightSpecified = false;

    int oldHeight = 0;

    unsigned int highestFlexGroup = 0;

    unsigned int lowestFlexGroup = 0;

    bool haveFlex = false;

    int remainingSpace = 0;

    m_overflowHeight = m_height;

    // The first walk over our kids is to find out if we have any flexible children.

    FlexBoxIterator iterator(this);

    RenderObject* child = iterator.next();

    while (child) {

        // Check to see if this child flexes.

        if (!child->isPositioned() && child->style()->boxFlex() > 0.0f) {

            // We always have to lay out flexible objects again, since the flex distribution

            // may have changed, and we need to reallocate space.

            child->setOverrideSize(-1);

            if (!relayoutChildren)

                child->setChildNeedsLayout(true, false);

            haveFlex = true;

            unsigned int flexGroup = child->style()->boxFlexGroup();

            if (lowestFlexGroup == 0)

                lowestFlexGroup = flexGroup;

            if (flexGroup < lowestFlexGroup)

                lowestFlexGroup = flexGroup;

            if (flexGroup > highestFlexGroup)

                highestFlexGroup = flexGroup;

        }

        child = iterator.next();

    }

    // We do 2 passes.  The first pass is simply to lay everyone out at

    // their preferred widths.  The second pass handles flexing the children.

    do {

        // Reset our height.

        m_height = yPos;

        m_overflowHeight = m_height;

        xPos = borderLeft() + paddingLeft();

        // Our first pass is done without flexing.  We simply lay the children

        // out within the box.  We have to do a layout first in order to determine

        // our box's intrinsic height.

        int maxAscent = 0, maxDescent = 0;

        child = iterator.first();

        while (child) {

            // make sure we relayout children if we need it.

            if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent())))

                child->setChildNeedsLayout(true, false);

            if (child->isPositioned()) {

                child = iterator.next();

                continue;

            }

            // Compute the child's vertical margins.

            child->calcVerticalMargins();

            // Now do the layout.

            child->layoutIfNeeded();

            // Update our height and overflow height.

            if (style()->boxAlign() == BBASELINE) {

                int ascent = child->marginTop() + child->getBaselineOfFirstLineBox();

                if (ascent == -1)

                    ascent = child->marginTop() + child->height() + child->marginBottom();

                int descent = (child->marginTop() + child->height() + child->marginBottom()) - ascent;

                // Update our maximum ascent.

                maxAscent = max(maxAscent, ascent);

                // Update our maximum descent.

                maxDescent = max(maxDescent, descent);

                // Now update our height.

                m_height = max(yPos + maxAscent + maxDescent, m_height);

            }

            else

                m_height = max(m_height, yPos + child->marginTop() + child->height() + child->marginBottom());

            child = iterator.next();

        }

        if (!iterator.first() && hasLineIfEmpty())

            m_height += lineHeight(true, true);

        m_height += toAdd;

        // Always make sure our overflowheight is at least our height.

        if (m_overflowHeight < m_height)

            m_overflowHeight = m_height;

        oldHeight = m_height;

        calcHeight();

        relayoutChildren = false;

        if (oldHeight != m_height)

            heightSpecified = true;

        // Now that our height is actually known, we can place our boxes.

        m_stretchingChildren = (style()->boxAlign() == BSTRETCH);

        child = iterator.first();

        while (child) {

            if (child->isPositioned()) {

                child->containingBlock()->insertPositionedObject(child);

                if (child->hasStaticX()) {

                    if (style()->direction() == LTR)

                        child->setStaticX(xPos);

                    else child->setStaticX(width() - xPos);

                }

                if (child->hasStaticY())

                    child->setStaticY(yPos);

                child = iterator.next();

                continue;

            }

            // We need to see if this child's height has changed, since we make block elements

            // fill the height of a containing box by default.

            // Now do a layout.

            int oldChildHeight = child->height();

            static_cast<RenderBox*>(child)->calcHeight();

            if (oldChildHeight != child->height())

                child->setChildNeedsLayout(true, false);

            child->layoutIfNeeded();

            // We can place the child now, using our value of box-align.

            xPos += child->marginLeft();

            int childY = yPos;

            switch (style()->boxAlign()) {

                case BCENTER:

                    childY += child->marginTop() + max(0, (contentHeight() - (child->height() + child->marginTop() + child->marginBottom()))/2);

                    break;

                case BBASELINE: {

                    int ascent = child->marginTop() + child->getBaselineOfFirstLineBox();

                    if (ascent == -1)

                        ascent = child->marginTop() + child->height() + child->marginBottom();

                    childY += child->marginTop() + (maxAscent - ascent);

                    break;

                }

                case BEND:

                    childY += contentHeight() - child->marginBottom() - child->height();

                    break;

                default: // BSTART

                    childY += child->marginTop();

                    break;

            }

            placeChild(child, xPos, childY);

            if (child->isRenderBlock())

                static_cast<RenderBlock*>(child)->addVisualOverflow(static_cast<RenderBlock*>(child)->floatRect());

            m_overflowHeight = max(m_overflowHeight, childY + child->overflowHeight(false));

            m_overflowTop = min(m_overflowTop, child->yPos() + child->overflowTop(false));

            xPos += child->width() + child->marginRight();

            child = iterator.next();

        }

        remainingSpace = borderLeft() + paddingLeft() + contentWidth() - xPos;

        m_stretchingChildren = false;

        if (m_flexingChildren)

            haveFlex = false; // We're done.

        else if (haveFlex) {

            // We have some flexible objects.  See if we need to grow/shrink them at all.

            if (!remainingSpace)

                break;

            // Allocate the remaining space among the flexible objects.  If we are trying to

            // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,

            // we go from the highest flex group to the lowest group.

            bool expanding = remainingSpace > 0;

            unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;

            unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;

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

                // Always start off by assuming the group can get all the remaining space.

                int groupRemainingSpace = remainingSpace;

                do {

                    // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width

                    // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and

                    // computing the allowed growth before an object hits its min/max width (and thus

                    // forces a totalFlex recomputation).

                    int groupRemainingSpaceAtBeginning = groupRemainingSpace;

                    float totalFlex = 0.0f;

                    child = iterator.first();

                    while (child) {

                        if (allowedChildFlex(child, expanding, i))

                            totalFlex += child->style()->boxFlex();

                        child = iterator.next();

                    }

                    child = iterator.first();

                    int spaceAvailableThisPass = groupRemainingSpace;

                    while (child) {

                        int allowedFlex = allowedChildFlex(child, expanding, i);

                        if (allowedFlex) {

                            int projectedFlex = (allowedFlex == INT_MAX) ? allowedFlex : (int)(allowedFlex * (totalFlex / child->style()->boxFlex()));

                            spaceAvailableThisPass = expanding ? min(spaceAvailableThisPass, projectedFlex) : max(spaceAvailableThisPass, projectedFlex);

                        }

                        child = iterator.next();

                    }

                    // The flex groups may not have any flexible objects this time around. 

                    if (!spaceAvailableThisPass || totalFlex == 0.0f) {

                        // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.

                        groupRemainingSpace = 0;

                        continue;

                    }