/*

 * This file is part of the WebKit open source project.

 *

 * Copyright (C) 2006, 2007 Eric Seidel (eric@webkit.org)

 *

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

#include "Path.h"

#include <math.h>

#if PLATFORM(SYMBIAN)

#include <e32math.h>

#endif

namespace WebCore {

static const float kPathSegmentLengthTolerance = 0.00001f;

static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)

{

    return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);

}

static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)

{

#if PLATFORM(SYMBIAN)

    TReal trg;

    TReal src((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));

    Math::Sqrt(trg, src);

    return trg;

#else

    return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));

#endif

}

struct QuadraticBezier {

    QuadraticBezier() { }

    QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)

        : start(s)

        , control(c)

        , end(e)

    {

    }

    float approximateDistance() const

    {

        return distanceLine(start, control) + distanceLine(control, end);

    }

    void split(QuadraticBezier& left, QuadraticBezier& right) const

    {

        left.control = midPoint(start, control);

        right.control = midPoint(control, end);

        FloatPoint leftControlToRightControl = midPoint(left.control, right.control);

        left.end = leftControlToRightControl;

        right.start = leftControlToRightControl;

        left.start = start;

        right.end = end;

    }

    FloatPoint start;

    FloatPoint control;

    FloatPoint end;

};

struct CubicBezier {

    CubicBezier() { }

    CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)

        : start(s)

        , control1(c1)

        , control2(c2)

        , end(e)

    {

    }

    float approximateDistance() const

    {

        return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);

    }

    void split(CubicBezier& left, CubicBezier& right) const

    {    

        FloatPoint startToControl1 = midPoint(control1, control2);

        left.start = start;

        left.control1 = midPoint(start, control1);

        left.control2 = midPoint(left.control1, startToControl1);

        right.control2 = midPoint(control2, end);

        right.control1 = midPoint(right.control2, startToControl1);

        right.end = end;

        FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);

        left.end = leftControl2ToRightControl1;

        right.start = leftControl2ToRightControl1;

    }

    FloatPoint start;

    FloatPoint control1;

    FloatPoint control2;

    FloatPoint end;

};

// FIXME: This function is possibly very slow due to the ifs required for proper path measuring

// A simple speed-up would be to use an additional boolean template parameter to control whether

// to use the "fast" version of this function with no PathTraversalState updating, vs. the slow

// version which does update the PathTraversalState.  We'll have to shark it to see if that's necessary.

// Another check which is possible up-front (to send us down the fast path) would be to check if

// approximateDistance() + current total distance > desired distance

template<class CurveType>

static float curveLength(PathTraversalState& traversalState, CurveType curve)

{

    Vector<CurveType> curveStack;

    curveStack.append(curve);

    float totalLength = 0.0f;

    do {

        float length = curve.approximateDistance();

        if ((length - distanceLine((const FloatPoint&)curve.start, (const FloatPoint&)curve.end)) > kPathSegmentLengthTolerance) {

            CurveType left, right;

            curve.split(left, right);

            curve = left;

            curveStack.append(right);

        } else {

            totalLength += length;

            if (traversalState.m_action == PathTraversalState::TraversalPointAtLength

             || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {

                traversalState.m_previous = curve.start;

                traversalState.m_current = curve.end;

                if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)

                    return totalLength;

            }

            curve = curveStack.last();

            curveStack.removeLast();

        }

    } while (!curveStack.isEmpty());

    return totalLength;

}

PathTraversalState::PathTraversalState(PathTraversalAction action)

    : m_action(action)

    , m_success(false)

    , m_totalLength(0.0f)

    , m_segmentIndex(0)

    , m_desiredLength(0.0f)

    , m_normalAngle(0.0f)

{

}

float PathTraversalState::closeSubpath()

{

    float distance = distanceLine(m_current, m_start);

    m_start = m_control1 = m_control2 = m_current;

    return distance;

}

float PathTraversalState::moveTo(const FloatPoint& point)

{

    m_current = m_start = m_control1 = m_control2 = point;

    return 0.0f;

}

float PathTraversalState::lineTo(const FloatPoint& point)

{

    float distance = distanceLine(m_current, point);

    m_current = m_control1 = m_control2 = point;

    return distance;

}

float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)

{

    float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));

    m_control1 = newControl;

    m_control2 = newEnd;

    if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) 

        m_current = newEnd;

    return distance;

}

float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)

{

    float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));

    m_control1 = newEnd;

    m_control2 = newControl2;

    if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) 

        m_current = newEnd;

    return distance;

}

}