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

**

** 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 "private/qstroker_p.h"

#include "private/qbezier_p.h"

#include "private/qmath_p.h"

#include "qline.h"

#include "qtransform.h"

#include <qmath.h>

QT_BEGIN_NAMESPACE

// #define QPP_STROKE_DEBUG

class QSubpathForwardIterator

{

public:

    QSubpathForwardIterator(const QDataBuffer<QStrokerOps::Element> *path)

        : m_path(path), m_pos(0) { }

    inline int position() const { return m_pos; }

    inline bool hasNext() const { return m_pos < m_path->size(); }

    inline QStrokerOps::Element next() { Q_ASSERT(hasNext()); return m_path->at(m_pos++); }

private:

    const QDataBuffer<QStrokerOps::Element> *m_path;

    int m_pos;

};

class QSubpathBackwardIterator

{

public:

    QSubpathBackwardIterator(const QDataBuffer<QStrokerOps::Element> *path)

        : m_path(path), m_pos(path->size() - 1) { }

    inline int position() const { return m_pos; }

    inline bool hasNext() const { return m_pos >= 0; }

    inline QStrokerOps::Element next()

    {

        Q_ASSERT(hasNext());

        QStrokerOps::Element ce = m_path->at(m_pos);   // current element

        if (m_pos == m_path->size() - 1) {

            --m_pos;

            ce.type = QPainterPath::MoveToElement;

            return ce;

        }

        const QStrokerOps::Element &pe = m_path->at(m_pos + 1); // previous element

        switch (pe.type) {

        case QPainterPath::LineToElement:

            ce.type = QPainterPath::LineToElement;

            break;

        case QPainterPath::CurveToDataElement:

            // First control point?

            if (ce.type == QPainterPath::CurveToElement) {

                ce.type = QPainterPath::CurveToDataElement;

            } else { // Second control point then

                ce.type = QPainterPath::CurveToElement;

            }

            break;

        case QPainterPath::CurveToElement:

            ce.type = QPainterPath::CurveToDataElement;

            break;

        default:

            qWarning("QSubpathReverseIterator::next: Case %d unhandled", ce.type);

            break;

        }

        --m_pos;

        return ce;

    }

private:

    const QDataBuffer<QStrokerOps::Element> *m_path;

    int m_pos;

};

class QSubpathFlatIterator

{

public:

    QSubpathFlatIterator(const QDataBuffer<QStrokerOps::Element> *path)

        : m_path(path), m_pos(0), m_curve_index(-1) { }

    inline bool hasNext() const { return m_curve_index >= 0 || m_pos < m_path->size(); }

    QStrokerOps::Element next()

    {

        Q_ASSERT(hasNext());

        if (m_curve_index >= 0) {

            QStrokerOps::Element e = { QPainterPath::LineToElement,

                                       qt_real_to_fixed(m_curve.at(m_curve_index).x()),

                                       qt_real_to_fixed(m_curve.at(m_curve_index).y())

                                       };

            ++m_curve_index;

            if (m_curve_index >= m_curve.size())

                m_curve_index = -1;

            return e;

        }

        QStrokerOps::Element e = m_path->at(m_pos);

        if (e.isCurveTo()) {

            Q_ASSERT(m_pos > 0);

            Q_ASSERT(m_pos < m_path->size());

            m_curve = QBezier::fromPoints(QPointF(qt_fixed_to_real(m_path->at(m_pos-1).x),

                                                  qt_fixed_to_real(m_path->at(m_pos-1).y)),

                                          QPointF(qt_fixed_to_real(e.x),

                                                  qt_fixed_to_real(e.y)),

                                          QPointF(qt_fixed_to_real(m_path->at(m_pos+1).x),

                                                  qt_fixed_to_real(m_path->at(m_pos+1).y)),

                                          QPointF(qt_fixed_to_real(m_path->at(m_pos+2).x),

                                                  qt_fixed_to_real(m_path->at(m_pos+2).y))).toPolygon();

            m_curve_index = 1;

            e.type = QPainterPath::LineToElement;

            e.x = m_curve.at(0).x();

            e.y = m_curve.at(0).y();

            m_pos += 2;

        }

        Q_ASSERT(e.isLineTo() || e.isMoveTo());

        ++m_pos;

        return e;

    }

private:

    const QDataBuffer<QStrokerOps::Element> *m_path;

    int m_pos;

    QPolygonF m_curve;

    int m_curve_index;

};

template <class Iterator> bool qt_stroke_side(Iterator *it, QStroker *stroker,

                                              bool capFirst, QLineF *startTangent);

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

 * QLineF::angle gives us the smalles angle between two lines. Here we

 * want to identify the line's angle direction on the unit circle.

 */

static inline qreal adapted_angle_on_x(const QLineF &line)

{

    qreal angle = line.angle(QLineF(0, 0, 1, 0));

    if (line.dy() > 0)

        angle = 360 - angle;

    return angle;

}

QStrokerOps::QStrokerOps()

    : m_customData(0), m_moveTo(0), m_lineTo(0), m_cubicTo(0)

{

}

QStrokerOps::~QStrokerOps()

{

}

/*!

    Prepares the stroker. Call this function once before starting a

    stroke by calling moveTo, lineTo or cubicTo.

    The \a customData is passed back through that callback functions

    and can be used by the user to for instance maintain state

    information.

*/

void QStrokerOps::begin(void *customData)

{

    m_customData = customData;

    m_elements.reset();

}

/*!

    Finishes the stroke. Call this function once when an entire

    primitive has been stroked.

*/

void QStrokerOps::end()

{

    if (m_elements.size() > 1)

        processCurrentSubpath();

    m_customData = 0;

}

/*!

    Convenience function that decomposes \a path into begin(),

    moveTo(), lineTo(), curevTo() and end() calls.

    The \a customData parameter is used in the callback functions

    The \a matrix is used to transform the points before input to the

    stroker.

    \sa begin()

*/

void QStrokerOps::strokePath(const QPainterPath &path, void *customData, const QTransform &matrix)

{

    if (path.isEmpty())

        return;

    begin(customData);

    int count = path.elementCount();

    if (matrix.isIdentity()) {

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

            const QPainterPath::Element &e = path.elementAt(i);

            switch (e.type) {

            case QPainterPath::MoveToElement:

                moveTo(qt_real_to_fixed(e.x), qt_real_to_fixed(e.y));

                break;

            case QPainterPath::LineToElement:

                lineTo(qt_real_to_fixed(e.x), qt_real_to_fixed(e.y));

                break;

            case QPainterPath::CurveToElement:

                {

                    const QPainterPath::Element &cp2 = path.elementAt(++i);

                    const QPainterPath::Element &ep = path.elementAt(++i);

                    cubicTo(qt_real_to_fixed(e.x), qt_real_to_fixed(e.y),

                            qt_real_to_fixed(cp2.x), qt_real_to_fixed(cp2.y),

                            qt_real_to_fixed(ep.x), qt_real_to_fixed(ep.y));

                }

                break;

            default:

                break;

            }

        }

    } else {

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

            const QPainterPath::Element &e = path.elementAt(i);

            QPointF pt = QPointF(e.x, e.y) * matrix;

            switch (e.type) {

            case QPainterPath::MoveToElement:

                moveTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()));

                break;

            case QPainterPath::LineToElement:

                lineTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()));

                break;

            case QPainterPath::CurveToElement:

                {

                    QPointF cp2 = ((QPointF) path.elementAt(++i)) * matrix;

                    QPointF ep = ((QPointF) path.elementAt(++i)) * matrix;

                    cubicTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()),

                            qt_real_to_fixed(cp2.x()), qt_real_to_fixed(cp2.y()),

                            qt_real_to_fixed(ep.x()), qt_real_to_fixed(ep.y()));

                }

                break;

            default:

                break;

            }

        }

    }

    end();

}

/*!

    Convenience function for stroking a polygon of the \a pointCount

    first points in \a points. If \a implicit_close is set to true a

    line is implictly drawn between the first and last point in the

    polygon. Typically true for polygons and false for polylines.

    The \a matrix is used to transform the points before they enter the

    stroker.

    \sa begin()

*/

void QStrokerOps::strokePolygon(const QPointF *points, int pointCount, bool implicit_close,

                                void *data, const QTransform &matrix)

{

    if (!pointCount)

        return;

    begin(data);

    if (matrix.isIdentity()) {

        moveTo(qt_real_to_fixed(points[0].x()), qt_real_to_fixed(points[0].y()));

        for (int i=1; i<pointCount; ++i)

            lineTo(qt_real_to_fixed(points[i].x()),

                   qt_real_to_fixed(points[i].y()));

        if (implicit_close)

            lineTo(qt_real_to_fixed(points[0].x()), qt_real_to_fixed(points[0].y()));

    } else {

        QPointF start = points[0] * matrix;

        moveTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y()));

        for (int i=1; i<pointCount; ++i) {

            QPointF pt = points[i] * matrix;

            lineTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()));

        }

        if (implicit_close)

            lineTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y()));

    }

    end();

}

/*!

    Convenience function for stroking an ellipse with bounding rect \a

    rect. The \a matrix is used to transform the coordinates before

    they enter the stroker.

*/

void QStrokerOps::strokeEllipse(const QRectF &rect, void *data, const QTransform &matrix)

{

    int count = 0;

    QPointF pts[12];

    QPointF start = qt_curves_for_arc(rect, 0, -360, pts, &count);

    Q_ASSERT(count == 12); // a perfect circle..

    if (!matrix.isIdentity()) {

        start = start * matrix;

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

            pts[i] = pts[i] * matrix;

        }

    }

    begin(data);

    moveTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y()));

    for (int i=0; i<12; i+=3) {

        cubicTo(qt_real_to_fixed(pts[i].x()), qt_real_to_fixed(pts[i].y()),

                qt_real_to_fixed(pts[i+1].x()), qt_real_to_fixed(pts[i+1].y()),

                qt_real_to_fixed(pts[i+2].x()), qt_real_to_fixed(pts[i+2].y()));

    }

    end();

}

QStroker::QStroker()

    : m_capStyle(SquareJoin), m_joinStyle(FlatJoin),

      m_back1X(0), m_back1Y(0),

      m_back2X(0), m_back2Y(0)

{

    m_strokeWidth = qt_real_to_fixed(1);

    m_miterLimit = qt_real_to_fixed(2);

    m_curveThreshold = qt_real_to_fixed(0.25);

}

QStroker::~QStroker()

{

}

Qt::PenCapStyle QStroker::capForJoinMode(LineJoinMode mode)

{

    if (mode == FlatJoin) return Qt::FlatCap;

    else if (mode == SquareJoin) return Qt::SquareCap;

    else return Qt::RoundCap;

}

QStroker::LineJoinMode QStroker::joinModeForCap(Qt::PenCapStyle style)

{

    if (style == Qt::FlatCap) return FlatJoin;

    else if (style == Qt::SquareCap) return SquareJoin;

    else return RoundCap;

}

Qt::PenJoinStyle QStroker::joinForJoinMode(LineJoinMode mode)

{

    if (mode == FlatJoin) return Qt::BevelJoin;

    else if (mode == MiterJoin) return Qt::MiterJoin;

    else if (mode == SvgMiterJoin) return Qt::SvgMiterJoin;

    else return Qt::RoundJoin;

}

QStroker::LineJoinMode QStroker::joinModeForJoin(Qt::PenJoinStyle joinStyle)

{

    if (joinStyle == Qt::BevelJoin) return FlatJoin;

    else if (joinStyle == Qt::MiterJoin) return MiterJoin;

    else if (joinStyle == Qt::SvgMiterJoin) return SvgMiterJoin;

    else return RoundJoin;

}

/*!

    This function is called to stroke the currently built up

    subpath. The subpath is cleared when the function completes.

*/

void QStroker::processCurrentSubpath()

{

    Q_ASSERT(!m_elements.isEmpty());

    Q_ASSERT(m_elements.first().type == QPainterPath::MoveToElement);

    Q_ASSERT(m_elements.size() > 1);

    QSubpathForwardIterator fwit(&m_elements);

    QSubpathBackwardIterator bwit(&m_elements);

    QLineF fwStartTangent, bwStartTangent;

    bool fwclosed = qt_stroke_side(&fwit, this, false, &fwStartTangent);

    bool bwclosed = qt_stroke_side(&bwit, this, !fwclosed, &bwStartTangent);

    if (!bwclosed)

        joinPoints(m_elements.at(0).x, m_elements.at(0).y, fwStartTangent, m_capStyle);

}

/*!

    \internal

*/

void QStroker::joinPoints(qfixed focal_x, qfixed focal_y, const QLineF &nextLine, LineJoinMode join)

{

#ifdef QPP_STROKE_DEBUG

    printf(" -----> joinPoints: around=(%.0f, %.0f), next_p1=(%.0f, %.f) next_p2=(%.0f, %.f)\n",

           qt_fixed_to_real(focal_x),

           qt_fixed_to_real(focal_y),

           nextLine.x1(), nextLine.y1(), nextLine.x2(), nextLine.y2());

#endif

    // points connected already, don't join

#if !defined (QFIXED_26_6) && !defined (Q_FIXED_32_32)

    if (qFuzzyCompare(m_back1X, nextLine.x1()) && qFuzzyCompare(m_back1Y, nextLine.y1()))

        return;

#else

    if (m_back1X == qt_real_to_fixed(nextLine.x1())

        && m_back1Y == qt_real_to_fixed(nextLine.y1())) {

        return;

    }

#endif

    if (join == FlatJoin) {

        emitLineTo(qt_real_to_fixed(nextLine.x1()),

                   qt_real_to_fixed(nextLine.y1()));

    } else {

        QLineF prevLine(qt_fixed_to_real(m_back2X), qt_fixed_to_real(m_back2Y),

                        qt_fixed_to_real(m_back1X), qt_fixed_to_real(m_back1Y));

        QPointF isect;

        QLineF::IntersectType type = prevLine.intersect(nextLine, &isect);

        if (join == MiterJoin) {

            qreal appliedMiterLimit = qt_fixed_to_real(m_strokeWidth * m_miterLimit);

            // If we are on the inside, do the short cut...

            QLineF shortCut(prevLine.p2(), nextLine.p1());

            qreal angle = shortCut.angleTo(prevLine);

            if (type == QLineF::BoundedIntersection || (angle > 90 && !qFuzzyCompare(angle, (qreal)90))) {

                emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

                return;

            }

            QLineF miterLine(QPointF(qt_fixed_to_real(m_back1X),

                                     qt_fixed_to_real(m_back1Y)), isect);

            if (type == QLineF::NoIntersection || miterLine.length() > appliedMiterLimit) {

                QLineF l1(prevLine);

                l1.setLength(appliedMiterLimit);

                l1.translate(prevLine.dx(), prevLine.dy());

                QLineF l2(nextLine);

                l2.setLength(appliedMiterLimit);

                l2.translate(-l2.dx(), -l2.dy());

                emitLineTo(qt_real_to_fixed(l1.x2()), qt_real_to_fixed(l1.y2()));

                emitLineTo(qt_real_to_fixed(l2.x1()), qt_real_to_fixed(l2.y1()));

                emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

            } else {

                emitLineTo(qt_real_to_fixed(isect.x()), qt_real_to_fixed(isect.y()));

                emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

            }

        } else if (join == SquareJoin) {

            qfixed offset = m_strokeWidth / 2;

            QLineF l1(prevLine);

            l1.translate(l1.dx(), l1.dy());

            l1.setLength(qt_fixed_to_real(offset));

            QLineF l2(nextLine.p2(), nextLine.p1());

            l2.translate(l2.dx(), l2.dy());

            l2.setLength(qt_fixed_to_real(offset));

            emitLineTo(qt_real_to_fixed(l1.x2()), qt_real_to_fixed(l1.y2()));

            emitLineTo(qt_real_to_fixed(l2.x2()), qt_real_to_fixed(l2.y2()));

            emitLineTo(qt_real_to_fixed(l2.x1()), qt_real_to_fixed(l2.y1()));

        } else if (join == RoundJoin) {

            qfixed offset = m_strokeWidth / 2;

            QLineF shortCut(prevLine.p2(), nextLine.p1());

            qreal angle = prevLine.angle(shortCut);

            if (type == QLineF::BoundedIntersection || (angle > 90 && !qFuzzyCompare(angle, (qreal)90))) {

                emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

                return;

            }

            qreal l1_on_x = adapted_angle_on_x(prevLine);

            qreal l2_on_x = adapted_angle_on_x(nextLine);

            qreal sweepLength = qAbs(l2_on_x - l1_on_x);

            int point_count;

            QPointF curves[15];

            QPointF curve_start =

                qt_curves_for_arc(QRectF(qt_fixed_to_real(focal_x - offset),

                                         qt_fixed_to_real(focal_y - offset),

                                         qt_fixed_to_real(offset * 2),