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

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtOpenGL 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 "qtriangulator_p.h"

#include <QtGui/qdialog.h>

#include <QtGui/qevent.h>

#include <QtGui/qpainter.h>

#include <QtGui/qpainterpath.h>

#include <QtGui/private/qbezier_p.h>

#include <QtGui/private/qdatabuffer_p.h>

#include <QtCore/qbitarray.h>

#include <QtCore/qvarlengtharray.h>

#include <QtCore/qqueue.h>

#include <QtCore/qglobal.h>

#include <QtCore/qpoint.h>

#include <QtCore/qalgorithms.h>

#include <QtDebug>

#include <math.h>

QT_BEGIN_NAMESPACE

//#define Q_TRIANGULATOR_DEBUG

#define Q_FIXED_POINT_SCALE 32

// Quick sort.

template <class T, class LessThan>

static void sort(T *array, int count, LessThan lessThan)

{

    // If the number of elements fall below some threshold, use insertion sort.

    const int INSERTION_SORT_LIMIT = 7; // About 7 is fastest on my computer...

    if (count <= INSERTION_SORT_LIMIT) {

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

            T temp = array[i];

            int j = i;

            while (j > 0 && lessThan(temp, array[j - 1])) {

                array[j] = array[j - 1];

                --j;

            }

            array[j] = temp;

        }

        return;

    }

    int high = count - 1;

    int low = 0;

    int mid = high / 2;

    if (lessThan(array[mid], array[low]))

        qSwap(array[mid], array[low]);

    if (lessThan(array[high], array[mid]))

        qSwap(array[high], array[mid]);

    if (lessThan(array[mid], array[low]))

        qSwap(array[mid], array[low]);

    --high;

    ++low;

    qSwap(array[mid], array[high]);

    int pivot = high;

    --high;

    while (low <= high) {

        while (!lessThan(array[pivot], array[low])) {

            ++low;

            if (low > high)

                goto sort_loop_end;

        }

        while (!lessThan(array[high], array[pivot])) {

            --high;

            if (low > high)

                goto sort_loop_end;

        }

        qSwap(array[low], array[high]);

        ++low;

        --high;

    }

sort_loop_end:

    if (low != pivot)

        qSwap(array[pivot], array[low]);

    sort(array, low, lessThan);

    sort(array + low + 1, count - low - 1, lessThan);

}

// Quick sort.

template <class T>

static void sort(T *array, int count)

{

    // If the number of elements fall below some threshold, use insertion sort.

    const int INSERTION_SORT_LIMIT = 25; // About 25 is fastest on my computer...

    if (count <= INSERTION_SORT_LIMIT) {

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

            T temp = array[i];

            int j = i;

            while (j > 0 && (temp < array[j - 1])) {

                array[j] = array[j - 1];

                --j;

            }

            array[j] = temp;

        }

        return;

    }

    int high = count - 1;

    int low = 0;

    int mid = high / 2;

    if ((array[mid] < array[low]))

        qSwap(array[mid], array[low]);

    if ((array[high] < array[mid]))

        qSwap(array[high], array[mid]);

    if ((array[mid] < array[low]))

        qSwap(array[mid], array[low]);

    --high;

    ++low;

    qSwap(array[mid], array[high]);

    int pivot = high;

    --high;

    while (low <= high) {

        while (!(array[pivot] < array[low])) {

            ++low;

            if (low > high)

                goto sort_loop_end;

        }

        while (!(array[high] < array[pivot])) {

            --high;

            if (low > high)

                goto sort_loop_end;

        }

        qSwap(array[low], array[high]);

        ++low;

        --high;

    }

sort_loop_end:

    if (low != pivot)

        qSwap(array[pivot], array[low]);

    sort(array, low);

    sort(array + low + 1, count - low - 1);

}

//============================================================================//

//                                 QFraction                                  //

//============================================================================//

// Fraction must be in the range [0, 1)

struct QFraction

{

    // Comparison operators must not be called on invalid fractions.

    inline bool operator < (const QFraction &other) const;

    inline bool operator == (const QFraction &other) const;

    inline bool operator != (const QFraction &other) const {return !(*this == other);}

    inline bool operator > (const QFraction &other) const {return other < *this;}

    inline bool operator >= (const QFraction &other) const {return !(*this < other);}

    inline bool operator <= (const QFraction &other) const {return !(*this > other);}

    inline bool isValid() const {return denominator != 0;}

    // numerator and denominator must not have common denominators.

    quint64 numerator, denominator;

};

static inline quint64 gcd(quint64 x, quint64 y)

{

    while (y != 0) {

        quint64 z = y;

        y = x % y;

        x = z;

    }

    return x;

}

static inline int compare(quint64 a, quint64 b)

{

    return (a > b) - (a < b);

}

// Compare a/b with c/d.

// Return negative if less, 0 if equal, positive if greater.

// a < b, c < d

static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d)

{

    const quint64 LIMIT = Q_UINT64_C(0x100000000);

    for (;;) {

        // If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared.

        if (b < LIMIT && d < LIMIT)

            return compare(a * d, b * c);

        if (a == 0 || c == 0)

            return compare(a, c);

        // a/b < c/d  <=>  d/c < b/a

        quint64 b_div_a = b / a;

        quint64 d_div_c = d / c;

        if (b_div_a != d_div_c)

            return compare(d_div_c, b_div_a);

        // floor(d/c) == floor(b/a)

        // frac(d/c) < frac(b/a) ?

        // frac(x/y) = (x%y)/y

        d -= d_div_c * c; //d %= c;

        b -= b_div_a * a; //b %= a;

        qSwap(a, d);

        qSwap(b, c);

    }

}

// Fraction must be in the range [0, 1)

// Assume input is valid.

static QFraction qFraction(quint64 n, quint64 d) {

    QFraction result;

    if (n == 0) {

        result.numerator = 0;

        result.denominator = 1;

    } else {

        quint64 g = gcd(n, d);

        result.numerator = n / g;

        result.denominator = d / g;

    }

    return result;

}

inline bool QFraction::operator < (const QFraction &other) const

{

    return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;

}

inline bool QFraction::operator == (const QFraction &other) const

{

    return numerator == other.numerator && denominator == other.denominator;

}

//============================================================================//

//                                 QPodPoint                                  //

//============================================================================//

struct QPodPoint

{

    inline bool operator < (const QPodPoint &other) const

    {

        if (y != other.y)

            return y < other.y;

        return x < other.x;

    }

    inline bool operator > (const QPodPoint &other) const {return other < *this;}

    inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}

    inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}

    inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}

    inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}

    inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}

    inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}

    inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}

    inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}

    int x;

    int y;

};

static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v)

{

    return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);

}

static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v)

{

    return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);

}

// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the

// line and zero if exactly on the line.

// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',

// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).

static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)

{

    return qCross(v2 - v1, p - v1);

}

static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)

{

    return qPointDistanceFromLine(p, v1, v2) < 0;

}

// Return:

// -1 if u < v

//  0 if u == v

//  1 if u > v

static int comparePoints(const QPodPoint &u, const QPodPoint &v)

{

    if (u.y < v.y)

        return -1;

    if (u.y > v.y)

        return 1;

    if (u.x < v.x)

        return -1;

    if (u.x > v.x)

        return 1;

    return 0;

}

//============================================================================//

//                             QIntersectionPoint                             //

//============================================================================//

struct QIntersectionPoint

{

    inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}

    QPodPoint round() const;

    inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}

    bool operator < (const QIntersectionPoint &other) const;

    bool operator == (const QIntersectionPoint &other) const;

    inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}

    inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}

    inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}

    inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}

    bool isOnLine(const QPodPoint &u, const QPodPoint &v) const;

    QPodPoint upperLeft;

    QFraction xOffset;

    QFraction yOffset;

};

static inline QIntersectionPoint qIntersectionPoint(const QPodPoint &point)

{

    // upperLeft = point, xOffset = 0/1, yOffset = 0/1.

    QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};

    return p;

}

static inline QIntersectionPoint qIntersectionPoint(int x, int y)

{

    // upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1.

    QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};

    return p;

}

static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2)

{

    QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};

    QPodPoint u = u2 - u1;

    QPodPoint v = v2 - v1;

    qint64 d1 = qCross(u, v1 - u1);

    qint64 d2 = qCross(u, v2 - u1);

    qint64 det = d2 - d1;

    qint64 d3 = qCross(v, u1 - v1);

    qint64 d4 = d3 - det; //qCross(v, u2 - v1);

    // Check that the math is correct.

    Q_ASSERT(d4 == qCross(v, u2 - v1));

    // The intersection point can be expressed as:

    // v1 - v * d1/det

    // v2 - v * d2/det

    // u1 + u * d3/det

    // u2 + u * d4/det

    // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.

    if (det == 0)

        return result;

    if (det < 0) {

        det = -det;

        d1 = -d1;

        d2 = -d2;

        d3 = -d3;

        d4 = -d4;

    }

    // I'm only interested in lines intersecting at their interior, not at their end points.

    // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.

    if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)

        return result;

    // Calculate the intersection point as follows:

    // v1 - v * d1/det | v1 <= v2 (component-wise)

    // v2 - v * d2/det | v2 < v1 (component-wise)

    // Assuming 21 bits per vector component.

    // TODO: Make code path for 31 bits per vector component.

    if (v.x >= 0) {

        result.upperLeft.x = v1.x + (-v.x * d1) / det;

        result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));

    } else {

        result.upperLeft.x = v2.x + (-v.x * d2) / det;

        result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));

    }

    if (v.y >= 0) {

        result.upperLeft.y = v1.y + (-v.y * d1) / det;

        result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));

    } else {

        result.upperLeft.y = v2.y + (-v.y * d2) / det;

        result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));

    }

    Q_ASSERT(result.xOffset.isValid());

    Q_ASSERT(result.yOffset.isValid());

    return result;

}

QPodPoint QIntersectionPoint::round() const

{

    QPodPoint result = upperLeft;

    if (2 * xOffset.numerator >= xOffset.denominator)

        ++result.x;

    if (2 * yOffset.numerator >= yOffset.denominator)

        ++result.y;

    return result;

}

bool QIntersectionPoint::operator < (const QIntersectionPoint &other) const

{

    if (upperLeft.y != other.upperLeft.y)

        return upperLeft.y < other.upperLeft.y;

    if (yOffset != other.yOffset)

        return yOffset < other.yOffset;

    if (upperLeft.x != other.upperLeft.x)

        return upperLeft.x < other.upperLeft.x;

    return xOffset < other.xOffset;

}

bool QIntersectionPoint::operator == (const QIntersectionPoint &other) const

{

    return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;

}

// Returns true if this point is on the infinite line passing through 'u' and 'v'.

bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const

{

    // TODO: Make code path for coordinates with more than 21 bits.

    const QPodPoint p = upperLeft - u;

    const QPodPoint q = v - u;

    bool isHorizontal = p.y == 0 && yOffset.numerator == 0;

    bool isVertical = p.x == 0 && xOffset.numerator == 0;

    if (isHorizontal && isVertical)

        return true;

    if (isHorizontal)

        return q.y == 0;

    if (q.y == 0)

        return false;

    if (isVertical)

        return q.x == 0;

    if (q.x == 0)

        return false;

    // At this point, 'p+offset' and 'q' cannot lie on the x or y axis.

    if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))

        return false; // 'p + offset' and 'q' pass through different quadrants.

    // Move all coordinates into the first quadrant.

    quint64 nx, ny;

    if (p.x < 0)

        nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;

    else

        nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;

    if (p.y < 0)

        ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;

    else

        ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;

    return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);

}

//============================================================================//

//                                  QMaxHeap                                  //

//============================================================================//

template <class T>

class QMaxHeap

{

public:

    QMaxHeap() : m_data(0) {}

    inline int size() const {return m_data.size();}

    inline bool empty() const {return m_data.isEmpty();}

    inline bool isEmpty() const {return m_data.isEmpty();}

    void push(const T &x);

    T pop();

    inline const T &top() const {return m_data.first();}

private:

    static inline int parent(int i) {return (i - 1) / 2;}

    static inline int left(int i) {return 2 * i + 1;}

    static inline int right(int i) {return 2 * i + 2;}

    QDataBuffer<T> m_data;

};

template <class T>