/*

 * 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.Rectangle;

import java.awt.Shape;

import java.io.Serializable;

import java.io.StreamCorruptedException;

import java.util.Arrays;

import sun.awt.geom.Curve;

/**

 * 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;

    static final int EXPAND_MAX_COORDS = EXPAND_MAX * 2;

    static final int EXPAND_MIN = 10; // ensure > 6 (cubics)

    /**

     * 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);

    static byte[] expandPointTypes(byte[] oldPointTypes, int needed) {

        final int oldSize = oldPointTypes.length;

        final int newSizeMin = oldSize + needed;

        if (newSizeMin < oldSize) {

            // hard overflow failure - we can't even accommodate

            // new items without overflowing

            throw new ArrayIndexOutOfBoundsException(

                          "pointTypes exceeds maximum capacity !");

        }

        // growth algorithm computation

        int grow = oldSize;

        if (grow > EXPAND_MAX) {

            grow = Math.max(EXPAND_MAX, oldSize >> 3); // 1/8th min

        } else if (grow < EXPAND_MIN) {

            grow = EXPAND_MIN;

        }

        assert grow > 0;

        int newSize = oldSize + grow;

        if (newSize < newSizeMin) {

            // overflow in growth algorithm computation

            newSize = Integer.MAX_VALUE;

        }

        while (true) {

            try {

                // try allocating the larger array

                return Arrays.copyOf(oldPointTypes, newSize);

            } catch (OutOfMemoryError oome) {

                if (newSize == newSizeMin) {

                    throw oome;

                }

            }

            newSize = newSizeMin + (newSize - newSizeMin) / 2;

        }

    }

    /**

     * 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;

                // trim arrays:

                this.pointTypes = Arrays.copyOf(p2d.pointTypes, p2d.numTypes);

                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);

            }

        }

        @Override

        public final void trimToSize() {

            // trim arrays:

            if (numTypes < pointTypes.length) {

                this.pointTypes = Arrays.copyOf(pointTypes, numTypes);

            }

            if (numCoords < floatCoords.length) {

                this.floatCoords = Arrays.copyOf(floatCoords, numCoords);

            }

        }

        @Override

        float[] cloneCoordsFloat(AffineTransform at) {

            // trim arrays:

            float[] ret;

            if (at == null) {

                ret = Arrays.copyOf(floatCoords, numCoords);

            } else {

                ret = new float[numCoords];

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

            }

            return ret;

        }

        @Override

        double[] cloneCoordsDouble(AffineTransform at) {

            // trim arrays:

            double[] ret = new double[numCoords];

            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]);

        }

        @Override

        void needRoom(boolean needMove, int newCoords) {

            if ((numTypes == 0) && needMove) {

                throw new IllegalPathStateException("missing initial moveto "+

                                                    "in path definition");

            }

            if (numTypes >= pointTypes.length) {

                pointTypes = expandPointTypes(pointTypes, 1);

            }

            if (numCoords > (floatCoords.length - newCoords)) {

                floatCoords = expandCoords(floatCoords, newCoords);

            }

        }

        static float[] expandCoords(float[] oldCoords, int needed) {

            final int oldSize = oldCoords.length;

            final int newSizeMin = oldSize + needed;

            if (newSizeMin < oldSize) {

                // hard overflow failure - we can't even accommodate

                // new items without overflowing

                throw new ArrayIndexOutOfBoundsException(

                              "coords exceeds maximum capacity !");

            }

            // growth algorithm computation

            int grow = oldSize;

            if (grow > EXPAND_MAX_COORDS) {

                grow = Math.max(EXPAND_MAX_COORDS, oldSize >> 3); // 1/8th min

            } else if (grow < EXPAND_MIN) {

                grow = EXPAND_MIN;

            }

            assert grow > needed;

            int newSize = oldSize + grow;

            if (newSize < newSizeMin) {

                // overflow in growth algorithm computation

                newSize = Integer.MAX_VALUE;

            }

            while (true) {

                try {

                    // try allocating the larger array

                    return Arrays.copyOf(oldCoords, newSize);

                } catch (OutOfMemoryError oome) {

                    if (newSize == newSizeMin) {

                        throw oome;

                    }

                }

                newSize = newSizeMin + (newSize - newSizeMin) / 2;

            }

        }

        /**

         * {@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;

        }

        /**