/*

 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

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

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code 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 General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

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

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.awt.geom;

import java.awt.Shape;

import java.awt.Rectangle;

import sun.awt.geom.Curve;

import java.io.Serializable;

import java.io.StreamCorruptedException;

import java.util.Arrays;

/**

 * The {@code Path2D} class provides a simple, yet flexible

 * shape which represents an arbitrary geometric path.

 * It can fully represent any path which can be iterated by the

 * {@link PathIterator} interface including all of its segment

 * types and winding rules and it implements all of the

 * basic hit testing methods of the {@link Shape} interface.

 * <p>

 * Use {@link Path2D.Float} when dealing with data that can be represented

 * and used with floating point precision.  Use {@link Path2D.Double}

 * for data that requires the accuracy or range of double precision.

 * <p>

 * {@code Path2D} provides exactly those facilities required for

 * basic construction and management of a geometric path and

 * implementation of the above interfaces with little added

 * interpretation.

 * If it is useful to manipulate the interiors of closed

 * geometric shapes beyond simple hit testing then the

 * {@link Area} class provides additional capabilities

 * specifically targeted at closed figures.

 * While both classes nominally implement the {@code Shape}

 * interface, they differ in purpose and together they provide

 * two useful views of a geometric shape where {@code Path2D}

 * deals primarily with a trajectory formed by path segments

 * and {@code Area} deals more with interpretation and manipulation

 * of enclosed regions of 2D geometric space.

 * <p>

 * The {@link PathIterator} interface has more detailed descriptions

 * of the types of segments that make up a path and the winding rules

 * that control how to determine which regions are inside or outside

 * the path.

 *

 * @author Jim Graham

 * @since 1.6

 */

public abstract class Path2D implements Shape, Cloneable {

    /**

     * An even-odd winding rule for determining the interior of

     * a path.

     *

     * @see PathIterator#WIND_EVEN_ODD

     * @since 1.6

     */

    public static final int WIND_EVEN_ODD = PathIterator.WIND_EVEN_ODD;

    /**

     * A non-zero winding rule for determining the interior of a

     * path.

     *

     * @see PathIterator#WIND_NON_ZERO

     * @since 1.6

     */

    public static final int WIND_NON_ZERO = PathIterator.WIND_NON_ZERO;

    // For code simplicity, copy these constants to our namespace

    // and cast them to byte constants for easy storage.

    private static final byte SEG_MOVETO  = (byte) PathIterator.SEG_MOVETO;

    private static final byte SEG_LINETO  = (byte) PathIterator.SEG_LINETO;

    private static final byte SEG_QUADTO  = (byte) PathIterator.SEG_QUADTO;

    private static final byte SEG_CUBICTO = (byte) PathIterator.SEG_CUBICTO;

    private static final byte SEG_CLOSE   = (byte) PathIterator.SEG_CLOSE;

    transient byte[] pointTypes;

    transient int numTypes;

    transient int numCoords;

    transient int windingRule;

    static final int INIT_SIZE = 20;

    static final int EXPAND_MAX = 500;

    /**

     * Constructs a new empty {@code Path2D} object.

     * It is assumed that the package sibling subclass that is

     * defaulting to this constructor will fill in all values.

     *

     * @since 1.6

     */

    /* private protected */

    Path2D() {

    }

    /**

     * Constructs a new {@code Path2D} object from the given

     * specified initial values.

     * This method is only intended for internal use and should

     * not be made public if the other constructors for this class

     * are ever exposed.

     *

     * @param rule the winding rule

     * @param initialTypes the size to make the initial array to

     *                     store the path segment types

     * @since 1.6

     */

    /* private protected */

    Path2D(int rule, int initialTypes) {

        setWindingRule(rule);

        this.pointTypes = new byte[initialTypes];

    }

    abstract float[] cloneCoordsFloat(AffineTransform at);

    abstract double[] cloneCoordsDouble(AffineTransform at);

    abstract void append(float x, float y);

    abstract void append(double x, double y);

    abstract Point2D getPoint(int coordindex);

    abstract void needRoom(boolean needMove, int newCoords);

    abstract int pointCrossings(double px, double py);

    abstract int rectCrossings(double rxmin, double rymin,

                               double rxmax, double rymax);

    /**

     * The {@code Float} class defines a geometric path with

     * coordinates stored in single precision floating point.

     *

     * @since 1.6

     */

    public static class Float extends Path2D implements Serializable {

        transient float floatCoords[];

        /**

         * Constructs a new empty single precision {@code Path2D} object

         * with a default winding rule of {@link #WIND_NON_ZERO}.

         *

         * @since 1.6

         */

        public Float() {

            this(WIND_NON_ZERO, INIT_SIZE);

        }

        /**

         * Constructs a new empty single precision {@code Path2D} object

         * with the specified winding rule to control operations that

         * require the interior of the path to be defined.

         *

         * @param rule the winding rule

         * @see #WIND_EVEN_ODD

         * @see #WIND_NON_ZERO

         * @since 1.6

         */

        public Float(int rule) {

            this(rule, INIT_SIZE);

        }

        /**

         * Constructs a new empty single precision {@code Path2D} object

         * with the specified winding rule and the specified initial

         * capacity to store path segments.

         * This number is an initial guess as to how many path segments

         * will be added to the path, but the storage is expanded as

         * needed to store whatever path segments are added.

         *

         * @param rule the winding rule

         * @param initialCapacity the estimate for the number of path segments

         *                        in the path

         * @see #WIND_EVEN_ODD

         * @see #WIND_NON_ZERO

         * @since 1.6

         */

        public Float(int rule, int initialCapacity) {

            super(rule, initialCapacity);

            floatCoords = new float[initialCapacity * 2];

        }

        /**

         * Constructs a new single precision {@code Path2D} object

         * from an arbitrary {@link Shape} object.

         * All of the initial geometry and the winding rule for this path are

         * taken from the specified {@code Shape} object.

         *

         * @param s the specified {@code Shape} object

         * @since 1.6

         */

        public Float(Shape s) {

            this(s, null);

        }

        /**

         * Constructs a new single precision {@code Path2D} object

         * from an arbitrary {@link Shape} object, transformed by an

         * {@link AffineTransform} object.

         * All of the initial geometry and the winding rule for this path are

         * taken from the specified {@code Shape} object and transformed

         * by the specified {@code AffineTransform} object.

         *

         * @param s the specified {@code Shape} object

         * @param at the specified {@code AffineTransform} object

         * @since 1.6

         */

        public Float(Shape s, AffineTransform at) {

            if (s instanceof Path2D) {

                Path2D p2d = (Path2D) s;

                setWindingRule(p2d.windingRule);

                this.numTypes = p2d.numTypes;

                this.pointTypes = Arrays.copyOf(p2d.pointTypes,

                                                p2d.pointTypes.length);

                this.numCoords = p2d.numCoords;

                this.floatCoords = p2d.cloneCoordsFloat(at);

            } else {

                PathIterator pi = s.getPathIterator(at);

                setWindingRule(pi.getWindingRule());

                this.pointTypes = new byte[INIT_SIZE];

                this.floatCoords = new float[INIT_SIZE * 2];

                append(pi, false);

            }

        }

        float[] cloneCoordsFloat(AffineTransform at) {

            float ret[];

            if (at == null) {

                ret = Arrays.copyOf(this.floatCoords, this.floatCoords.length);

            } else {

                ret = new float[floatCoords.length];

                at.transform(floatCoords, 0, ret, 0, numCoords / 2);

            }

            return ret;

        }

        double[] cloneCoordsDouble(AffineTransform at) {

            double ret[] = new double[floatCoords.length];

            if (at == null) {

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

                    ret[i] = floatCoords[i];

                }

            } else {

                at.transform(floatCoords, 0, ret, 0, numCoords / 2);

            }

            return ret;

        }

        void append(float x, float y) {

            floatCoords[numCoords++] = x;

            floatCoords[numCoords++] = y;

        }

        void append(double x, double y) {

            floatCoords[numCoords++] = (float) x;

            floatCoords[numCoords++] = (float) y;

        }

        Point2D getPoint(int coordindex) {

            return new Point2D.Float(floatCoords[coordindex],

                                     floatCoords[coordindex+1]);

        }

        void needRoom(boolean needMove, int newCoords) {

            if (needMove && numTypes == 0) {

                throw new IllegalPathStateException("missing initial moveto "+

                                                    "in path definition");

            }

            int size = pointTypes.length;

            if (numTypes >= size) {

                int grow = size;

                if (grow > EXPAND_MAX) {

                    grow = EXPAND_MAX;

                }

                pointTypes = Arrays.copyOf(pointTypes, size+grow);

            }

            size = floatCoords.length;

            if (numCoords + newCoords > size) {

                int grow = size;

                if (grow > EXPAND_MAX * 2) {

                    grow = EXPAND_MAX * 2;

                }

                if (grow < newCoords) {

                    grow = newCoords;

                }

                floatCoords = Arrays.copyOf(floatCoords, size+grow);

            }

        }

        /**

         * {@inheritDoc}

         * @since 1.6

         */

        public final synchronized void moveTo(double x, double y) {

            if (numTypes > 0 && pointTypes[numTypes - 1] == SEG_MOVETO) {

                floatCoords[numCoords-2] = (float) x;

                floatCoords[numCoords-1] = (float) y;

            } else {

                needRoom(false, 2);

                pointTypes[numTypes++] = SEG_MOVETO;

                floatCoords[numCoords++] = (float) x;

                floatCoords[numCoords++] = (float) y;

            }

        }

        /**

         * Adds a point to the path by moving to the specified

         * coordinates specified in float precision.

         * <p>

         * This method provides a single precision variant of

         * the double precision {@code moveTo()} method on the

         * base {@code Path2D} class.

         *

         * @param x the specified X coordinate

         * @param y the specified Y coordinate

         * @see Path2D#moveTo

         * @since 1.6

         */

        public final synchronized void moveTo(float x, float y) {

            if (numTypes > 0 && pointTypes[numTypes - 1] == SEG_MOVETO) {

                floatCoords[numCoords-2] = x;

                floatCoords[numCoords-1] = y;

            } else {

                needRoom(false, 2);

                pointTypes[numTypes++] = SEG_MOVETO;

                floatCoords[numCoords++] = x;

                floatCoords[numCoords++] = y;

            }

        }

        /**

         * {@inheritDoc}

         * @since 1.6

         */

        public final synchronized void lineTo(double x, double y) {

            needRoom(true, 2);

            pointTypes[numTypes++] = SEG_LINETO;

            floatCoords[numCoords++] = (float) x;

            floatCoords[numCoords++] = (float) y;

        }

        /**

         * Adds a point to the path by drawing a straight line from the

         * current coordinates to the new specified coordinates

         * specified in float precision.

         * <p>

         * This method provides a single precision variant of

         * the double precision {@code lineTo()} method on the

         * base {@code Path2D} class.

         *

         * @param x the specified X coordinate

         * @param y the specified Y coordinate

         * @see Path2D#lineTo

         * @since 1.6

         */

        public final synchronized void lineTo(float x, float y) {

            needRoom(true, 2);

            pointTypes[numTypes++] = SEG_LINETO;

            floatCoords[numCoords++] = x;

            floatCoords[numCoords++] = y;

        }

        /**

         * {@inheritDoc}

         * @since 1.6

         */

        public final synchronized void quadTo(double x1, double y1,

                                              double x2, double y2)

        {

            needRoom(true, 4);

            pointTypes[numTypes++] = SEG_QUADTO;

            floatCoords[numCoords++] = (float) x1;

            floatCoords[numCoords++] = (float) y1;

            floatCoords[numCoords++] = (float) x2;

            floatCoords[numCoords++] = (float) y2;

        }

        /**

         * Adds a curved segment, defined by two new points, to the path by

         * drawing a Quadratic curve that intersects both the current

         * coordinates and the specified coordinates {@code (x2,y2)},

         * using the specified point {@code (x1,y1)} as a quadratic

         * parametric control point.

         * All coordinates are specified in float precision.

         * <p>

         * This method provides a single precision variant of

         * the double precision {@code quadTo()} method on the

         * base {@code Path2D} class.

         *

         * @param x1 the X coordinate of the quadratic control point

         * @param y1 the Y coordinate of the quadratic control point

         * @param x2 the X coordinate of the final end point

         * @param y2 the Y coordinate of the final end point

         * @see Path2D#quadTo

         * @since 1.6

         */

        public final synchronized void quadTo(float x1, float y1,

                                              float x2, float y2)

        {

            needRoom(true, 4);

            pointTypes[numTypes++] = SEG_QUADTO;

            floatCoords[numCoords++] = x1;

            floatCoords[numCoords++] = y1;

            floatCoords[numCoords++] = x2;

            floatCoords[numCoords++] = y2;

        }

        /**

         * {@inheritDoc}

         * @since 1.6

         */

        public final synchronized void curveTo(double x1, double y1,

                                               double x2, double y2,

                                               double x3, double y3)

        {

            needRoom(true, 6);

            pointTypes[numTypes++] = SEG_CUBICTO;

            floatCoords[numCoords++] = (float) x1;

            floatCoords[numCoords++] = (float) y1;

            floatCoords[numCoords++] = (float) x2;

            floatCoords[numCoords++] = (float) y2;

            floatCoords[numCoords++] = (float) x3;

            floatCoords[numCoords++] = (float) y3;

        }

        /**

         * Adds a curved segment, defined by three new points, to the path by

         * drawing a Bézier curve that intersects both the current

         * coordinates and the specified coordinates {@code (x3,y3)},

         * using the specified points {@code (x1,y1)} and {@code (x2,y2)} as

         * Bézier control points.

         * All coordinates are specified in float precision.

         * <p>

         * This method provides a single precision variant of

         * the double precision {@code curveTo()} method on the

         * base {@code Path2D} class.

         *

         * @param x1 the X coordinate of the first Bézier control point

         * @param y1 the Y coordinate of the first Bézier control point

         * @param x2 the X coordinate of the second Bézier control point

         * @param y2 the Y coordinate of the second Bézier control point

         * @param x3 the X coordinate of the final end point

         * @param y3 the Y coordinate of the final end point

         * @see Path2D#curveTo

         * @since 1.6

         */

        public final synchronized void curveTo(float x1, float y1,

                                               float x2, float y2,

                                               float x3, float y3)

        {

            needRoom(true, 6);

            pointTypes[numTypes++] = SEG_CUBICTO;

            floatCoords[numCoords++] = x1;

            floatCoords[numCoords++] = y1;

            floatCoords[numCoords++] = x2;

            floatCoords[numCoords++] = y2;

            floatCoords[numCoords++] = x3;

            floatCoords[numCoords++] = y3;

        }

        int pointCrossings(double px, double py) {

            double movx, movy, curx, cury, endx, endy;

            float coords[] = floatCoords;

            curx = movx = coords[0];

            cury = movy = coords[1];

            int crossings = 0;

            int ci = 2;

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

                switch (pointTypes[i]) {

                case PathIterator.SEG_MOVETO:

                    if (cury != movy) {

                        crossings +=

                            Curve.pointCrossingsForLine(px, py,

                                                        curx, cury,

                                                        movx, movy);

                    }

                    movx = curx = coords[ci++];

                    movy = cury = coords[ci++];

                    break;

                case PathIterator.SEG_LINETO:

                    crossings +=

                        Curve.pointCrossingsForLine(px, py,

                                                    curx, cury,

                                                    endx = coords[ci++],

                                                    endy = coords[ci++]);

                    curx = endx;

                    cury = endy;

                    break;

                case PathIterator.SEG_QUADTO:

                    crossings +=

                        Curve.pointCrossingsForQuad(px, py,

                                                    curx, cury,

                                                    coords[ci++],

                                                    coords[ci++],

                                                    endx = coords[ci++],

                                                    endy = coords[ci++],

                                                    0);

                    curx = endx;

                    cury = endy;

                    break;

            case PathIterator.SEG_CUBICTO:

                    crossings +=

                        Curve.pointCrossingsForCubic(px, py,

                                                     curx, cury,

                                                     coords[ci++],

                                                     coords[ci++],

                                                     coords[ci++],

                                                     coords[ci++],

                                                     endx = coords[ci++],

                                                     endy = coords[ci++],

                                                     0);

                    curx = endx;

                    cury = endy;

                    break;