/*
 * @(#)GeneralPath.java	1.54 00/02/02
 *
 * Copyright 1996-2000 Sun Microsystems, Inc. All Rights Reserved.
 * 
 * This software is the proprietary information of Sun Microsystems, Inc.  
 * Use is subject to license terms.
 * 
 */

package java.awt.geom;

import java.awt.Shape;
import sun.awt.geom.Curve;
import sun.awt.geom.Crossings;

/**
 * The <code>GeneralPath</code> class represents a geometric path 
 * constructed from straight lines, and quadratic and cubic
 * (Bézier) curves.  It can contain multiple subpaths.
 * <p>
 * The winding rule specifies how the interior of a path is
 * determined.  There are two types of winding rules:  
 * EVEN_ODD and NON_ZERO.
 * <p>
 * An EVEN_ODD winding rule means that enclosed regions
 * of the path alternate between interior and exterior areas as
 * traversed from the outside of the path towards a point inside
 * the region.  
 * <p>
 * A NON_ZERO winding rule means that if a ray is 
 * drawn in any direction from a given point to infinity
 * and the places where the path intersects
 * the ray are examined, the point is inside of the path if and only if
 * the number of times that the path crosses the ray from
 * left to right does not equal the  number of times that the path crosses
 * the ray from right to left.  
 * @version 1.54, 02/02/00
 * @author Jim Graham
 */
public final class GeneralPath implements Shape, Cloneable {
    /**
     * An even-odd winding rule for determining the interior of
     * a path.  
     */
    public static final int WIND_EVEN_ODD = PathIterator.WIND_EVEN_ODD;

    /**
     * A non-zero winding rule for determining the interior of a
     * path.  
     */
    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;

    byte[] pointTypes;
    float[] pointCoords;
    int numTypes;
    int numCoords;
    int windingRule;

    static final int INIT_SIZE = 20;
    static final int EXPAND_MAX = 500;

    /**
     * Constructs a new <code>GeneralPath</code> object.
     * If an operation performed on this path requires the
     * interior of the path to be defined then the default NON_ZERO
     * winding rule is used.
     * @see #WIND_NON_ZERO
     */
    public GeneralPath() {
	this(WIND_NON_ZERO, INIT_SIZE, INIT_SIZE);
    }

    /**
     * Constructs a new <code>GeneralPath</code> 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
     */
    public GeneralPath(int rule) {
	this(rule, INIT_SIZE, INIT_SIZE);
    }

    /**
     * Constructs a new <code>GeneralPath</code> object with the specified 
     * winding rule and the specified initial capacity to store path 
     * coordinates. This number is an initial guess as to how many path 
     * segments are in the path, but the storage is expanded 
     * as needed to store whatever path segments are added to this path.
     * @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
     */
    public GeneralPath(int rule, int initialCapacity) {
	this(rule, initialCapacity, initialCapacity);
    }

    /**
     * Constructs a new <code>GeneralPath</code> object with the specified 
     * winding rule and the specified initial capacities to store point types
     * and coordinates.
     * These numbers are an initial guess as to how many path segments
     * and how many points are to be in the path, but the
     * storage is expanded as needed to store whatever path segments are
     * added to this path.
     * @param rule the winding rule
     * @param initialTypes the estimate for the number of path segments
     * in the path
     * @param initialCapacity the estimate for the number of points
     * @see #WIND_EVEN_ODD
     * @see #WIND_NON_ZERO
     */
    GeneralPath(int rule, int initialTypes, int initialCoords) {
	setWindingRule(rule);
	pointTypes = new byte[initialTypes];
	pointCoords = new float[initialCoords * 2];
    }

    /**
     * Constructs a new <code>GeneralPath</code> 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</code> object.
     * @param s the specified <code>Shape</code> object
     */
    public GeneralPath(Shape s) {
	this(WIND_NON_ZERO, INIT_SIZE, INIT_SIZE);
	PathIterator pi = s.getPathIterator(null);
	setWindingRule(pi.getWindingRule());
	append(pi, false);
    }
 
    private void needRoom(int newTypes, int newCoords, boolean needMove) {
	if (needMove && numTypes == 0) {
	    throw new IllegalPathStateException("missing initial moveto "+
						"in path definition");
	}
	int size = pointCoords.length;
	if (numCoords + newCoords > size) {
	    int grow = size;
	    if (grow > EXPAND_MAX * 2) {
		grow = EXPAND_MAX * 2;
	    }
	    if (grow < newCoords) {
		grow = newCoords;
	    }
	    float[] arr = new float[size + grow];
	    System.arraycopy(pointCoords, 0, arr, 0, numCoords);
	    pointCoords = arr;
	}
	size = pointTypes.length;
	if (numTypes + newTypes > size) {
	    int grow = size;
	    if (grow > EXPAND_MAX) {
		grow = EXPAND_MAX;
	    }
	    if (grow < newTypes) {
		grow = newTypes;
	    }
	    byte[] arr = new byte[size + grow];
	    System.arraycopy(pointTypes, 0, arr, 0, numTypes);
	    pointTypes = arr;
	}
    }

    /**
     * Adds a point to the path by moving to the specified
     * coordinates.
     * @param x, y the specified coordinates
     */
    public synchronized void moveTo(float x, float y) {
	if (numTypes > 0 && pointTypes[numTypes - 1] == SEG_MOVETO) {
	    pointCoords[numCoords - 2] = x;
	    pointCoords[numCoords - 1] = y;
	} else {
	    needRoom(1, 2, false);
	    pointTypes[numTypes++] = SEG_MOVETO;
	    pointCoords[numCoords++] = x;
	    pointCoords[numCoords++] = y;
	}
    }

    /**
     * Adds a point to the path by drawing a straight line from the
     * current coordinates to the new specified coordinates.
     * @param x, y the specified coordinates
     */
    public synchronized void lineTo(float x, float y) {
	needRoom(1, 2, true);
	pointTypes[numTypes++] = SEG_LINETO;
	pointCoords[numCoords++] = x;
	pointCoords[numCoords++] = y;
    }

    /**
     * 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 coordinates (x2, y2), using the 
     * specified point (x1, y1) as a quadratic parametric control
     * point.
     * @param x1, y1 the coordinates of the first quadratic control
     *		point
     * @param x2, y2 the coordinates of the final endpoint
     */
    public synchronized void quadTo(float x1, float y1, float x2, float y2) {
	needRoom(1, 4, true);
	pointTypes[numTypes++] = SEG_QUADTO;
	pointCoords[numCoords++] = x1;
	pointCoords[numCoords++] = y1;
	pointCoords[numCoords++] = x2;
	pointCoords[numCoords++] = y2;
    }

    /**
     * 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 coordinates (x3, y3), using the    
     * specified points (x1, y1) and (x2, y2) as
     * Bézier control points.
     * @param x1, y1 the coordinates of the first Béezier
     *		control point
     * @param x2, y2 the coordinates of the second Bézier
     *		control point
     * @param x3, y3 the coordinates of the final endpoint
     */
    public synchronized void curveTo(float x1, float y1,
				     float x2, float y2,
				     float x3, float y3) {
	needRoom(1, 6, true);
	pointTypes[numTypes++] = SEG_CUBICTO;
	pointCoords[numCoords++] = x1;
	pointCoords[numCoords++] = y1;
	pointCoords[numCoords++] = x2;
	pointCoords[numCoords++] = y2;
	pointCoords[numCoords++] = x3;
	pointCoords[numCoords++] = y3;
    }

    /**
     * Closes the current subpath by drawing a straight line back to
     * the coordinates of the last <code>moveTo</code>.  If the path is already
     * closed then this method has no effect.
     */
    public synchronized void closePath() {
	if (numTypes == 0 || pointTypes[numTypes - 1] != SEG_CLOSE) {
	    needRoom(1, 0, true);
	    pointTypes[numTypes++] = SEG_CLOSE;
	}
    }

    /**
     * Appends the geometry of the specified <code>Shape</code> object to the
     * path, possibly connecting the new geometry to the existing path
     * segments with a line segment.
     * If the <code>connect</code> parameter is <code>true</code> and the 
     * path is not empty then any initial <code>moveTo</code> in the
     * geometry of the appended <code>Shape</code>
     * is turned into a <code>lineTo</code> segment.
     * If the destination coordinates of such a connecting <code>lineTo</code>
     * segment match the ending coordinates of a currently open
     * subpath then the segment is omitted as superfluous.
     * The winding rule of the specified <code>Shape</code> is ignored
     * and the appended geometry is governed by the winding
     * rule specified for this path.
     * @param s the <code>Shape</code> whose geometry is appended 
     * to this path
     * @param connect a boolean to control whether or not to turn an
     * initial <code>moveTo</code> segment into a <code>lineTo</code>
     * segment to connect the new geometry to the existing path
     */
    public void append(Shape s, boolean connect) {
	PathIterator pi = s.getPathIterator(null);
        append(pi,connect);
    }

    /**
     * Appends the geometry of the specified
     * {@link PathIterator} object 
     * to the path, possibly connecting the new geometry to the existing
     * path segments with a line segment.
     * If the <code>connect</code> parameter is <code>true</code> and the 
     * path is not empty then any initial <code>moveTo</code> in the
     * geometry of the appended <code>Shape</code> is turned into a
     * <code>lineTo</code> segment.
     * If the destination coordinates of such a connecting <code>lineTo</code>
     * segment match the ending coordinates of a currently open
     * subpath then the segment is omitted as superfluous.
     * The winding rule of the specified <code>Shape</code> is ignored
     * and the appended geometry is governed by the winding
     * rule specified for this path.
     * @param pi the <code>PathIterator</code> whose geometry is appended to 
     * this path
     * @param connect a boolean to control whether or not to turn an
     * initial <code>moveTo</code> segment into a <code>lineTo</code> segment
     * to connect the new geometry to the existing path
     */
    public void append(PathIterator pi, boolean connect) {
	float coords[] = new float[6];
	while (!pi.isDone()) {
	    switch (pi.currentSegment(coords)) {
	    case SEG_MOVETO:
		if (!connect || numTypes < 1 || numCoords < 2) {
		    moveTo(coords[0], coords[1]);
		    break;
		}
		if (pointTypes[numTypes - 1] != SEG_CLOSE &&
		    pointCoords[numCoords - 2] == coords[0] &&
		    pointCoords[numCoords - 1] == coords[1])
		{
		    // Collapse out initial moveto/lineto
		    break;
		}
		// NO BREAK;
	    case SEG_LINETO:
		lineTo(coords[0], coords[1]);
		break;
	    case SEG_QUADTO:
		quadTo(coords[0], coords[1],
		       coords[2], coords[3]);
		break;
	    case SEG_CUBICTO:
		curveTo(coords[0], coords[1],
			coords[2], coords[3],
			coords[4], coords[5]);
		break;
	    case SEG_CLOSE:
		closePath();
		break;
	    }
	    pi.next();
	    connect = false;
	}
    }

    /**
     * Returns the fill style winding rule.
     * @return an integer representing the current winding rule.
     * @see #WIND_EVEN_ODD  
     * @see #WIND_NON_ZERO
     */
    public synchronized int getWindingRule() {
        return windingRule;
    }

    /**
     * Sets the winding rule for this path to the specified value.
     * @param rule an integer representing the specified 
     * winding rule
     * @exception <code>IllegalArgumentException</code> if 
     *		<code>rule</code> is not either 
     *		<code>WIND_EVEN_ODD</code> or
     *		<code>WIND_NON_ZERO</code>
     * @see #WIND_EVEN_ODD  
     * @see #WIND_NON_ZERO
     */
    public void setWindingRule(int rule) {
	if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO) {
	    throw new IllegalArgumentException("winding rule must be "+
					       "WIND_EVEN_ODD or "+
					       "WIND_NON_ZERO");
	}
	windingRule = rule;
    }

    /**
     * Returns the coordinates most recently added to the end of the path
     * as a {@link Point2D} object.
     * @return a <code>Point2D</code> object containing the ending 
     * coordinates of the path or <code>null</code> if there are no points
     * in the path.
     */
    public synchronized Point2D getCurrentPoint() {
	if (numTypes < 1 || numCoords < 2) {
	    return null;
	}
	int index = numCoords;
	if (pointTypes[numTypes - 1] == SEG_CLOSE) {
	loop:
	    for (int i = numTypes - 2; i > 0; i--) {
		switch (pointTypes[i]) {
		case SEG_MOVETO:
		    break loop;
		case SEG_LINETO:
		    index -= 2;
		    break;
		case SEG_QUADTO:
		    index -= 4;
		    break;
		case SEG_CUBICTO:
		    index -= 6;
		    break;
		case SEG_CLOSE:
		    break;
		}
	    }
	}
	return new Point2D.Float(pointCoords[index - 2],
				 pointCoords[index - 1]);
    }

    /**
     * Resets the path to empty.  The append position is set back to the
     * beginning of the path and all coordinates and point types are
     * forgotten.
     */
    public synchronized void reset() {
	numTypes = numCoords = 0;
    }

    /**
     * Transforms the geometry of this path using the specified 
     * {@link AffineTransform}.
     * The geometry is transformed in place, which permanently changes the
     * boundary defined by this object.
     * @param at the <code>AffineTransform</code> used to transform the area
     */
    public void transform(AffineTransform at) {
	at.transform(pointCoords, 0, pointCoords, 0, numCoords / 2);
    }

    /**
     * Returns a new transformed <code>Shape</code>.
     * @param at the <code>AffineTransform</code> used to transform a 
     * new <code>Shape</code>.
     * @return a new <code>Shape</code>, transformed with the specified 
     * <code>AffineTransform</code>.
     */
    public synchronized Shape createTransformedShape(AffineTransform at) {
	GeneralPath gp = (GeneralPath) clone();
	if (at != null) {
	    gp.transform(at);
	}
	return gp;
    }

    /**
     * Return the bounding box of the path.
     * @return a {@link java.awt.Rectangle} object that
     * bounds the current path.
     */
    public java.awt.Rectangle getBounds() {
	return getBounds2D().getBounds();
    }

    /**
     * Returns the bounding box of the path.
     * @return a {@link Rectangle2D} object that
     *          bounds the current path.
     */
    public synchronized Rectangle2D getBounds2D() {
	float x1, y1, x2, y2;
	int i = numCoords;
	if (i > 0) {
	    y1 = y2 = pointCoords[--i];
	    x1 = x2 = pointCoords[--i];
	    while (i > 0) {
		float y = pointCoords[--i];
		float x = pointCoords[--i];
		if (x < x1) x1 = x;
		if (y < y1) y1 = y;
		if (x > x2) x2 = x;
		if (y > y2) y2 = y;
	    }
	} else {
	    x1 = y1 = x2 = y2 = 0.0f;
	}
	return new Rectangle2D.Float(x1, y1, x2 - x1, y2 - y1);
    }

    /**
     * Tests if the specified coordinates are inside the boundary of 
     * this <code>Shape</code>.
     * @param x, y the specified coordinates
     * @return <code>true</code> if the specified coordinates are inside this 
     * <code>Shape</code> <code>false</code> otherwise
     */
    public boolean contains(double x, double y) {
	if (numTypes < 2) {
	    return false;
	}
	int cross = Curve.crossingsForPath(getPathIterator(null), x, y);
	if (windingRule == WIND_NON_ZERO) {
	    return (cross != 0);
	} else {
	    return ((cross & 1) != 0);
	}
    }

    /**
     * Tests if the specified <code>Point2D</code> is inside the boundary
     * of this <code>Shape</code>.
     * @param p the specified <code>Point2D</code>
     * @return <code>true</code> if this <code>Shape</code> contains the 
     * specified <code>Point2D</code>, <code>false</code> otherwise.
     */
    public boolean contains(Point2D p) {
	return contains(p.getX(), p.getY());
    }

    /**
     * Tests if the specified rectangular area is inside the boundary of
     * this <code>Shape</code>.
     * @param x, y the specified coordinates
     * @param w the width of the specified rectangular area
     * @param h the height of the specified rectangular area
     * @return <code>true</code> if this <code>Shape</code> contains 
     * the specified rectangluar area; <code>false</code> otherwise.
     */
    public boolean contains(double x, double y, double w, double h) {
	Crossings c = Crossings.findCrossings(getPathIterator(null),
					      x, y, x+w, y+h);
	return (c != null && c.covers(y, y+h));
    }

    /**
     * Tests if the specified <code>Rectangle2D</code>
     * is inside the boundary of this <code>Shape</code>.
     * @param r a specified <code>Rectangle2D</code>
     * @return <code>true</code> if this <code>Shape</code> bounds the 
     * specified <code>Rectangle2D</code> <code>false</code> otherwise.
     */
    public boolean contains(Rectangle2D r) {
	return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
    }

    /**
     * Tests if the interior of this <code>Shape</code> intersects the 
     * interior of a specified set of rectangular coordinates.
     * @param x, y the specified coordinates
     * @param w the width of the specified rectangular coordinates
     * @param h the height of the specified rectangular coordinates
     * @return <code>true</code> if this <code>Shape</code> and the 
     * interior of the specified set of rectangular coordinates intersect
     * each other; <code>false</code> otherwise.
     */
    public boolean intersects(double x, double y, double w, double h) {
	Crossings c = Crossings.findCrossings(getPathIterator(null),
					      x, y, x+w, y+h);
	return (c == null || !c.isEmpty());
    }

    /**
     * Tests if the interior of this <code>Shape</code> intersects the 
     * interior of a specified <code>Rectangle2D</code>.
     * @param r the specified <code>Rectangle2D</code>
     * @return <code>true</code> if this <code>Shape</code> and the interior 
     * 		of the specified <code>Rectangle2D</code> intersect each
     * 		other; <code>false</code> otherwise.
     */
    public boolean intersects(Rectangle2D r) {
	return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
    }

    /**
     * Returns a <code>PathIterator</code> object that iterates along the 
     * boundary of this <code>Shape</code> and provides access to the 
     * geometry of the outline of this <code>Shape</code>.
     * The iterator for this class is not multi-threaded safe,
     * which means that this <code>GeneralPath</code> class does not
     * guarantee that modifications to the geometry of this
     * <code>GeneralPath</code> object do not affect any iterations of
     * that geometry that are already in process.
     * @param at an <code>AffineTransform</code> 
     * @return a new <code>PathIterator</code> that iterates along the 
     * boundary of this <code>Shape</code> and provides access to the 
     * geometry of this <code>Shape</code>'s outline
     */
    public PathIterator getPathIterator(AffineTransform at) {
	return new GeneralPathIterator(this, at);
    }

    /**
     * Returns a <code>PathIterator</code> object that iterates along the 
     * boundary of the flattened <code>Shape</code> and provides access to the 
     * geometry of the outline of the <code>Shape</code>.
     * The iterator for this class is not multi-threaded safe,
     * which means that this <code>GeneralPath</code> class does not
     * guarantee that modifications to the geometry of this
     * <code>GeneralPath</code> object do not affect any iterations of
     * that geometry that are already in process. 
     * @param at an <code>AffineTransform</code>
     * @param flatness the maximum distance that the line segments used to
     *		approximate the curved segments are allowed to deviate
     *		from any point on the original curve    
     * @return a new <code>PathIterator</code> that iterates along the flattened
     * <code>Shape</code> boundary.
     */
    public PathIterator getPathIterator(AffineTransform at, double flatness) {
	return new FlatteningPathIterator(getPathIterator(at), flatness);
    }

    /**
     * Creates a new object of the same class as this object.
     *
     * @return     a clone of this instance.
     * @exception  OutOfMemoryError            if there is not enough memory.
     * @see        java.lang.Cloneable
     * @since      1.2
     */
    public Object clone() {
	try {
	    GeneralPath copy = (GeneralPath) super.clone();
	    copy.pointTypes = (byte[]) pointTypes.clone();
	    copy.pointCoords = (float[]) pointCoords.clone();
	    return copy;
	} catch (CloneNotSupportedException e) {
	    // this shouldn't happen, since we are Cloneable
	    throw new InternalError();
	}
    }
}