Initial import from the monolithic Qt.

This is the beginning of revision history for this module. If you
want to look at revision history older than this, please refer to the
Qt Git wiki for how to use Git history grafting. At the time of
writing, this wiki is located here:

http://qt.gitorious.org/qt/pages/GitIntroductionWithQt

If you have already performed the grafting and you don't see any
history beyond this commit, try running "git log" with the "--follow"
argument.

Branched from the monolithic repo, Qt master branch, at commit
896db169ea224deb96c59ce8af800d019de63f12

1 files changed, 494 insertions, 0 deletions

diff --git a/src/gui/painting/qpathclipper_p.h b/src/gui/painting/qpathclipper_p.h
new file mode 100644
index 0000000000..226c55d29e
--- /dev/null
+++ b/src/gui/painting/qpathclipper_p.h
@@ -0,0 +1,494 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 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$
+**
+****************************************************************************/
+
+#ifndef QPATHCLIPPER_P_H
+#define QPATHCLIPPER_P_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <QtGui/qpainterpath.h>
+#include <QtCore/qlist.h>
+
+#include <private/qbezier_p.h>
+#include <private/qdatabuffer_p.h>
+#include <stdio.h>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Gui)
+
+class QWingedEdge;
+
+class Q_AUTOTEST_EXPORT QPathClipper
+{
+public:
+    enum Operation {
+        BoolAnd,
+        BoolOr,
+        BoolSub,
+        Simplify
+    };
+public:
+    QPathClipper(const QPainterPath &subject,
+                 const QPainterPath &clip);
+
+    QPainterPath clip(Operation op = BoolAnd);
+
+    bool intersect();
+    bool contains();
+
+    static bool pathToRect(const QPainterPath &path, QRectF *rect = 0);
+    static QPainterPath intersect(const QPainterPath &path, const QRectF &rect);
+
+private:
+    Q_DISABLE_COPY(QPathClipper)
+
+    enum ClipperMode {
+        ClipMode, // do the full clip
+        CheckMode // for contains/intersects (only interested in whether the result path is non-empty)
+    };
+
+    bool handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode);
+    bool doClip(QWingedEdge &list, ClipperMode mode);
+
+    QPainterPath subjectPath;
+    QPainterPath clipPath;
+    Operation op;
+
+    int aMask;
+    int bMask;
+};
+
+struct QPathVertex
+{
+public:
+    QPathVertex(const QPointF &p = QPointF(), int e = -1);
+    operator QPointF() const;
+
+    int edge;
+
+    qreal x;
+    qreal y;
+};
+
+class QPathEdge
+{
+public:
+    enum Traversal {
+        RightTraversal,
+        LeftTraversal
+    };
+
+    enum Direction {
+        Forward,
+        Backward
+    };
+
+    enum Type {
+        Line,
+        Curve
+    };
+
+    QPathEdge(int a = -1, int b = -1);
+
+    mutable int flag;
+
+    int windingA;
+    int windingB;
+
+    int first;
+    int second;
+
+    double angle;
+    double invAngle;
+
+    int next(Traversal traversal, Direction direction) const;
+
+    void setNext(Traversal traversal, Direction direction, int next);
+    void setNext(Direction direction, int next);
+
+    Direction directionTo(int vertex) const;
+    int vertex(Direction direction) const;
+
+private:
+    int m_next[2][2];
+};
+
+class QPathSegments
+{
+public:
+    struct Intersection {
+        int vertex;
+        qreal t;
+
+        int next;
+
+        bool operator<(const Intersection &o) const {
+            return t < o.t;
+        }
+    };
+
+    struct Segment {
+        Segment(int pathId, int vertexA, int vertexB)
+            : path(pathId)
+            , va(vertexA)
+            , vb(vertexB)
+            , intersection(-1)
+        {
+        }
+
+        int path;
+
+        // vertices
+        int va;
+        int vb;
+
+        // intersection index
+        int intersection;
+
+        QRectF bounds;
+    };
+
+
+    QPathSegments(int reserve);
+
+    void setPath(const QPainterPath &path);
+    void addPath(const QPainterPath &path);
+
+    int intersections() const;
+    int segments() const;
+    int points() const;
+
+    const Segment &segmentAt(int index) const;
+    const QLineF lineAt(int index) const;
+    const QRectF &elementBounds(int index) const;
+    int pathId(int index) const;
+
+    const QPointF &pointAt(int vertex) const;
+    int addPoint(const QPointF &point);
+
+    const Intersection *intersectionAt(int index) const;
+    void addIntersection(int index, const Intersection &intersection);
+
+    void mergePoints();
+
+private:
+    QDataBuffer<QPointF> m_points;
+    QDataBuffer<Segment> m_segments;
+    QDataBuffer<Intersection> m_intersections;
+
+    int m_pathId;
+};
+
+class Q_AUTOTEST_EXPORT QWingedEdge
+{
+public:
+    struct TraversalStatus
+    {
+        int edge;
+        QPathEdge::Traversal traversal;
+        QPathEdge::Direction direction;
+
+        void flipDirection();
+        void flipTraversal();
+
+        void flip();
+    };
+
+    QWingedEdge();
+    QWingedEdge(const QPainterPath &subject, const QPainterPath &clip);
+
+    void simplify();
+    QPainterPath toPath() const;
+
+    int edgeCount() const;
+
+    QPathEdge *edge(int edge);
+    const QPathEdge *edge(int edge) const;
+
+    int vertexCount() const;
+
+    int addVertex(const QPointF &p);
+
+    QPathVertex *vertex(int vertex);
+    const QPathVertex *vertex(int vertex) const;
+
+    TraversalStatus next(const TraversalStatus &status) const;
+
+    int addEdge(const QPointF &a, const QPointF &b);
+    int addEdge(int vertexA, int vertexB);
+
+    bool isInside(qreal x, qreal y) const;
+
+    static QPathEdge::Traversal flip(QPathEdge::Traversal traversal);
+    static QPathEdge::Direction flip(QPathEdge::Direction direction);
+
+private:
+    void intersectAndAdd();
+
+    void printNode(int i, FILE *handle);
+
+    void removeEdge(int ei);
+
+    int insert(const QPathVertex &vertex);
+    TraversalStatus findInsertStatus(int vertex, int edge) const;
+
+    qreal delta(int vertex, int a, int b) const;
+
+    QDataBuffer<QPathEdge> m_edges;
+    QDataBuffer<QPathVertex> m_vertices;
+
+    QVector<qreal> m_splitPoints;
+
+    QPathSegments m_segments;
+};
+
+inline QPathEdge::QPathEdge(int a, int b)
+    : flag(0)
+    , windingA(0)
+    , windingB(0)
+    , first(a)
+    , second(b)
+    , angle(0)
+    , invAngle(0)
+{
+    m_next[0][0] = -1;
+    m_next[1][0] = -1;
+    m_next[0][0] = -1;
+    m_next[1][0] = -1;
+}
+
+inline int QPathEdge::next(Traversal traversal, Direction direction) const
+{
+    return m_next[int(traversal)][int(direction)];
+}
+
+inline void QPathEdge::setNext(Traversal traversal, Direction direction, int next)
+{
+    m_next[int(traversal)][int(direction)] = next;
+}
+
+inline void QPathEdge::setNext(Direction direction, int next)
+{
+    m_next[0][int(direction)] = next;
+    m_next[1][int(direction)] = next;
+}
+
+inline QPathEdge::Direction QPathEdge::directionTo(int vertex) const
+{
+    return first == vertex ? Backward : Forward;
+}
+
+inline int QPathEdge::vertex(Direction direction) const
+{
+    return direction == Backward ? first : second;
+}
+
+inline QPathVertex::QPathVertex(const QPointF &p, int e)
+    : edge(e)
+    , x(p.x())
+    , y(p.y())
+{
+}
+
+inline QPathVertex::operator QPointF() const
+{
+    return QPointF(x, y);
+}
+
+inline QPathSegments::QPathSegments(int reserve) :
+    m_points(reserve),
+    m_segments(reserve),
+    m_intersections(reserve)
+{
+}
+
+inline int QPathSegments::segments() const
+{
+    return m_segments.size();
+}
+
+inline int QPathSegments::points() const
+{
+    return m_points.size();
+}
+
+inline const QPointF &QPathSegments::pointAt(int i) const
+{
+    return m_points.at(i);
+}
+
+inline int QPathSegments::addPoint(const QPointF &point)
+{
+    m_points << point;
+    return m_points.size() - 1;
+}
+
+inline const QPathSegments::Segment &QPathSegments::segmentAt(int index) const
+{
+    return m_segments.at(index);
+}
+
+inline const QLineF QPathSegments::lineAt(int index) const
+{
+    const Segment &segment = m_segments.at(index);
+    return QLineF(m_points.at(segment.va), m_points.at(segment.vb));
+}
+
+inline const QRectF &QPathSegments::elementBounds(int index) const
+{
+    return m_segments.at(index).bounds;
+}
+
+inline int QPathSegments::pathId(int index) const
+{
+    return m_segments.at(index).path;
+}
+
+inline const QPathSegments::Intersection *QPathSegments::intersectionAt(int index) const
+{
+    const int intersection = m_segments.at(index).intersection;
+    if (intersection < 0)
+        return 0;
+    else
+        return &m_intersections.at(intersection);
+}
+
+inline int QPathSegments::intersections() const
+{
+    return m_intersections.size();
+}
+
+inline void QPathSegments::addIntersection(int index, const Intersection &intersection)
+{
+    m_intersections << intersection;
+
+    Segment &segment = m_segments.at(index);
+    if (segment.intersection < 0) {
+        segment.intersection = m_intersections.size() - 1;
+    } else {
+        Intersection *isect = &m_intersections.at(segment.intersection);
+
+        while (isect->next != 0)
+            isect += isect->next;
+
+        isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data());
+    }
+}
+
+inline void QWingedEdge::TraversalStatus::flipDirection()
+{
+    direction = QWingedEdge::flip(direction);
+}
+
+inline void QWingedEdge::TraversalStatus::flipTraversal()
+{
+    traversal = QWingedEdge::flip(traversal);
+}
+
+inline void QWingedEdge::TraversalStatus::flip()
+{
+    flipDirection();
+    flipTraversal();
+}
+
+inline int QWingedEdge::edgeCount() const
+{
+    return m_edges.size();
+}
+
+inline QPathEdge *QWingedEdge::edge(int edge)
+{
+    return edge < 0 ? 0 : &m_edges.at(edge);
+}
+
+inline const QPathEdge *QWingedEdge::edge(int edge) const
+{
+    return edge < 0 ? 0 : &m_edges.at(edge);
+}
+
+inline int QWingedEdge::vertexCount() const
+{
+    return m_vertices.size();
+}
+
+inline int QWingedEdge::addVertex(const QPointF &p)
+{
+    m_vertices << p;
+    return m_vertices.size() - 1;
+}
+
+inline QPathVertex *QWingedEdge::vertex(int vertex)
+{
+    return vertex < 0 ? 0 : &m_vertices.at(vertex);
+}
+
+inline const QPathVertex *QWingedEdge::vertex(int vertex) const
+{
+    return vertex < 0 ? 0 : &m_vertices.at(vertex);
+}
+
+inline QPathEdge::Traversal QWingedEdge::flip(QPathEdge::Traversal traversal)
+{
+    return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal;
+}
+
+inline QPathEdge::Direction QWingedEdge::flip(QPathEdge::Direction direction)
+{
+    return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward;
+}
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif // QPATHCLIPPER_P_H