/*

 * 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 sun.java2d.pisces;

import java.util.Arrays;

import java.util.Iterator;

import sun.awt.geom.PathConsumer2D;

// TODO: some of the arithmetic here is too verbose and prone to hard to

// debug typos. We should consider making a small Point/Vector class that

// has methods like plus(Point), minus(Point), dot(Point), cross(Point)and such

public class Stroker implements PathConsumer2D {

    private static final int MOVE_TO = 0;

    private static final int DRAWING_OP_TO = 1; // ie. curve, line, or quad

    private static final int CLOSE = 2;

    /**

     * Constant value for join style.

     */

    public static final int JOIN_MITER = 0;

    /**

     * Constant value for join style.

     */

    public static final int JOIN_ROUND = 1;

    /**

     * Constant value for join style.

     */

    public static final int JOIN_BEVEL = 2;

    /**

     * Constant value for end cap style.

     */

    public static final int CAP_BUTT = 0;

    /**

     * Constant value for end cap style.

     */

    public static final int CAP_ROUND = 1;

    /**

     * Constant value for end cap style.

     */

    public static final int CAP_SQUARE = 2;

    private final PathConsumer2D out;

    private final int capStyle;

    private final int joinStyle;

    private final float lineWidth2;

    private final float[][] offset = new float[3][2];

    private final float[] miter = new float[2];

    private final float miterLimitSq;

    private int prev;

    // The starting point of the path, and the slope there.

    private float sx0, sy0, sdx, sdy;

    // the current point and the slope there.

    private float cx0, cy0, cdx, cdy; // c stands for current

    // vectors that when added to (sx0,sy0) and (cx0,cy0) respectively yield the

    // first and last points on the left parallel path. Since this path is

    // parallel, it's slope at any point is parallel to the slope of the

    // original path (thought they may have different directions), so these

    // could be computed from sdx,sdy and cdx,cdy (and vice versa), but that

    // would be error prone and hard to read, so we keep these anyway.

    private float smx, smy, cmx, cmy;

    private final PolyStack reverse = new PolyStack();

    /**

     * Constructs a <code>Stroker</code>.

     *

     * @param pc2d an output <code>PathConsumer2D</code>.

     * @param lineWidth the desired line width in pixels

     * @param capStyle the desired end cap style, one of

     * <code>CAP_BUTT</code>, <code>CAP_ROUND</code> or

     * <code>CAP_SQUARE</code>.

     * @param joinStyle the desired line join style, one of

     * <code>JOIN_MITER</code>, <code>JOIN_ROUND</code> or

     * <code>JOIN_BEVEL</code>.

     * @param miterLimit the desired miter limit

     */

    public Stroker(PathConsumer2D pc2d,

                   float lineWidth,

                   int capStyle,

                   int joinStyle,

                   float miterLimit)

    {

        this.out = pc2d;

        this.lineWidth2 = lineWidth / 2;

        this.capStyle = capStyle;

        this.joinStyle = joinStyle;

        float limit = miterLimit * lineWidth2;

        this.miterLimitSq = limit*limit;

        this.prev = CLOSE;

    }

    private static void computeOffset(final float lx, final float ly,

                                      final float w, final float[] m)

    {

        final float len = (float)Math.hypot(lx, ly);

        if (len == 0) {

            m[0] = m[1] = 0;

        } else {

            m[0] = (ly * w)/len;

            m[1] = -(lx * w)/len;

        }

    }

    // Returns true if the vectors (dx1, dy1) and (dx2, dy2) are

    // clockwise (if dx1,dy1 needs to be rotated clockwise to close

    // the smallest angle between it and dx2,dy2).

    // This is equivalent to detecting whether a point q is on the right side

    // of a line passing through points p1, p2 where p2 = p1+(dx1,dy1) and

    // q = p2+(dx2,dy2), which is the same as saying p1, p2, q are in a

    // clockwise order.

    // NOTE: "clockwise" here assumes coordinates with 0,0 at the bottom left.

    private static boolean isCW(final float dx1, final float dy1,

                                final float dx2, final float dy2)

    {

        return dx1 * dy2 <= dy1 * dx2;

    }

    // pisces used to use fixed point arithmetic with 16 decimal digits. I

    // didn't want to change the values of the constant below when I converted

    // it to floating point, so that's why the divisions by 2^16 are there.

    private static final float ROUND_JOIN_THRESHOLD = 1000/65536f;

    private void drawRoundJoin(float x, float y,

                               float omx, float omy, float mx, float my,

                               boolean rev,

                               float threshold)

    {

        if ((omx == 0 && omy == 0) || (mx == 0 && my == 0)) {

            return;

        }

        float domx = omx - mx;

        float domy = omy - my;

        float len = domx*domx + domy*domy;

        if (len < threshold) {

            return;

        }

        if (rev) {

            omx = -omx;

            omy = -omy;

            mx = -mx;

            my = -my;

        }

        drawRoundJoin(x, y, omx, omy, mx, my, rev);

    }

    private void drawRoundJoin(float cx, float cy,

                               float omx, float omy,

                               float mx, float my,

                               boolean rev)

    {

        // The sign of the dot product of mx,my and omx,omy is equal to the

        // the sign of the cosine of ext

        // (ext is the angle between omx,omy and mx,my).

        double cosext = omx * mx + omy * my;

        // If it is >=0, we know that abs(ext) is <= 90 degrees, so we only

        // need 1 curve to approximate the circle section that joins omx,omy

        // and mx,my.

        final int numCurves = cosext >= 0 ? 1 : 2;

        switch (numCurves) {

        case 1:

            drawBezApproxForArc(cx, cy, omx, omy, mx, my, rev);

            break;

        case 2:

            // we need to split the arc into 2 arcs spanning the same angle.

            // The point we want will be one of the 2 intersections of the

            // perpendicular bisector of the chord (omx,omy)->(mx,my) and the

            // circle. We could find this by scaling the vector

            // (omx+mx, omy+my)/2 so that it has length=lineWidth2 (and thus lies

            // on the circle), but that can have numerical problems when the angle

            // between omx,omy and mx,my is close to 180 degrees. So we compute a

            // normal of (omx,omy)-(mx,my). This will be the direction of the

            // perpendicular bisector. To get one of the intersections, we just scale

            // this vector that its length is lineWidth2 (this works because the

            // perpendicular bisector goes through the origin). This scaling doesn't

            // have numerical problems because we know that lineWidth2 divided by

            // this normal's length is at least 0.5 and at most sqrt(2)/2 (because

            // we know the angle of the arc is > 90 degrees).

            float nx = my - omy, ny = omx - mx;

            float nlen = (float)Math.sqrt(nx*nx + ny*ny);

            float scale = lineWidth2/nlen;

            float mmx = nx * scale, mmy = ny * scale;

            // if (isCW(omx, omy, mx, my) != isCW(mmx, mmy, mx, my)) then we've

            // computed the wrong intersection so we get the other one.

            // The test above is equivalent to if (rev).

            if (rev) {

                mmx = -mmx;

                mmy = -mmy;

            }

            drawBezApproxForArc(cx, cy, omx, omy, mmx, mmy, rev);

            drawBezApproxForArc(cx, cy, mmx, mmy, mx, my, rev);

            break;

        }

    }

    // the input arc defined by omx,omy and mx,my must span <= 90 degrees.

    private void drawBezApproxForArc(final float cx, final float cy,

                                     final float omx, final float omy,

                                     final float mx, final float my,

                                     boolean rev)

    {

        float cosext2 = (omx * mx + omy * my) / (2 * lineWidth2 * lineWidth2);

        // cv is the length of P1-P0 and P2-P3 divided by the radius of the arc

        // (so, cv assumes the arc has radius 1). P0, P1, P2, P3 are the points that

        // define the bezier curve we're computing.

        // It is computed using the constraints that P1-P0 and P3-P2 are parallel

        // to the arc tangents at the endpoints, and that |P1-P0|=|P3-P2|.

        float cv = (float)((4.0 / 3.0) * Math.sqrt(0.5-cosext2) /

                           (1.0 + Math.sqrt(cosext2+0.5)));

        // if clockwise, we need to negate cv.

        if (rev) { // rev is equivalent to isCW(omx, omy, mx, my)

            cv = -cv;

        }

        final float x1 = cx + omx;

        final float y1 = cy + omy;

        final float x2 = x1 - cv * omy;

        final float y2 = y1 + cv * omx;

        final float x4 = cx + mx;

        final float y4 = cy + my;

        final float x3 = x4 + cv * my;

        final float y3 = y4 - cv * mx;

        emitCurveTo(x1, y1, x2, y2, x3, y3, x4, y4, rev);

    }

    private void drawRoundCap(float cx, float cy, float mx, float my) {

        final float C = 0.5522847498307933f;

        // the first and second arguments of the following two calls

        // are really will be ignored by emitCurveTo (because of the false),

        // but we put them in anyway, as opposed to just giving it 4 zeroes,

        // because it's just 4 additions and it's not good to rely on this

        // sort of assumption (right now it's true, but that may change).

        emitCurveTo(cx+mx,      cy+my,

                    cx+mx-C*my, cy+my+C*mx,

                    cx-my+C*mx, cy+mx+C*my,

                    cx-my,      cy+mx,

                    false);

        emitCurveTo(cx-my,      cy+mx,

                    cx-my-C*mx, cy+mx-C*my,

                    cx-mx-C*my, cy-my+C*mx,

                    cx-mx,      cy-my,

                    false);

    }

    // Return the intersection point of the lines (x0, y0) -> (x1, y1)

    // and (x0p, y0p) -> (x1p, y1p) in m[0] and m[1]

    private void computeMiter(final float x0, final float y0,

                              final float x1, final float y1,

                              final float x0p, final float y0p,

                              final float x1p, final float y1p,

                              final float[] m, int off)

    {

        float x10 = x1 - x0;

        float y10 = y1 - y0;

        float x10p = x1p - x0p;

        float y10p = y1p - y0p;

        // if this is 0, the lines are parallel. If they go in the

        // same direction, there is no intersection so m[off] and

        // m[off+1] will contain infinity, so no miter will be drawn.

        // If they go in the same direction that means that the start of the

        // current segment and the end of the previous segment have the same

        // tangent, in which case this method won't even be involved in

        // miter drawing because it won't be called by drawMiter (because

        // (mx == omx && my == omy) will be true, and drawMiter will return

        // immediately).

        float den = x10*y10p - x10p*y10;

        float t = x10p*(y0-y0p) - y10p*(x0-x0p);

        t /= den;

        m[off++] = x0 + t*x10;

        m[off] = y0 + t*y10;

    }

    private void drawMiter(final float pdx, final float pdy,

                           final float x0, final float y0,

                           final float dx, final float dy,

                           float omx, float omy, float mx, float my,

                           boolean rev)

    {

        if ((mx == omx && my == omy) ||

            (pdx == 0 && pdy == 0) ||

            (dx == 0 && dy == 0)) {

            return;

        }

        if (rev) {

            omx = -omx;

            omy = -omy;

            mx = -mx;

            my = -my;

        }

        computeMiter((x0 - pdx) + omx, (y0 - pdy) + omy, x0 + omx, y0 + omy,

                     (dx + x0) + mx, (dy + y0) + my, x0 + mx, y0 + my,

                     miter, 0);

        float lenSq = (miter[0]-x0)*(miter[0]-x0) + (miter[1]-y0)*(miter[1]-y0);

        if (lenSq < miterLimitSq) {

            emitLineTo(miter[0], miter[1], rev);

        }

    }

    public void moveTo(float x0, float y0) {

        if (prev == DRAWING_OP_TO) {

            finish();

        }

        this.sx0 = this.cx0 = x0;

        this.sy0 = this.cy0 = y0;

        this.cdx = this.sdx = 1;

        this.cdy = this.sdy = 0;

        this.prev = MOVE_TO;

    }

    public void lineTo(float x1, float y1) {

        float dx = x1 - cx0;

        float dy = y1 - cy0;

        if (dx == 0f && dy == 0f) {

            dx = 1;

        }

        computeOffset(dx, dy, lineWidth2, offset[0]);

        float mx = offset[0][0];

        float my = offset[0][1];

        drawJoin(cdx, cdy, cx0, cy0, dx, dy, cmx, cmy, mx, my);

        emitLineTo(cx0 + mx, cy0 + my);

        emitLineTo(x1 + mx, y1 + my);

        emitLineTo(cx0 - mx, cy0 - my, true);

        emitLineTo(x1 - mx, y1 - my, true);

        this.cmx = mx;

        this.cmy = my;

        this.cdx = dx;

        this.cdy = dy;

        this.cx0 = x1;

        this.cy0 = y1;

        this.prev = DRAWING_OP_TO;

    }

    public void closePath() {

        if (prev != DRAWING_OP_TO) {

            if (prev == CLOSE) {

                return;

            }

            emitMoveTo(cx0, cy0 - lineWidth2);

            this.cmx = this.smx = 0;

            this.cmy = this.smy = -lineWidth2;

            this.cdx = this.sdx = 1;

            this.cdy = this.sdy = 0;

            finish();

            return;

        }

        if (cx0 != sx0 || cy0 != sy0) {

            lineTo(sx0, sy0);

        }

        drawJoin(cdx, cdy, cx0, cy0, sdx, sdy, cmx, cmy, smx, smy);

        emitLineTo(sx0 + smx, sy0 + smy);

        emitMoveTo(sx0 - smx, sy0 - smy);

        emitReverse();

        this.prev = CLOSE;

        emitClose();

    }

    private void emitReverse() {

        while(!reverse.isEmpty()) {

            reverse.pop(out);

        }

    }

    public void pathDone() {

        if (prev == DRAWING_OP_TO) {

            finish();

        }

        out.pathDone();

        // this shouldn't matter since this object won't be used

        // after the call to this method.

        this.prev = CLOSE;

    }

    private void finish() {

        if (capStyle == CAP_ROUND) {

            drawRoundCap(cx0, cy0, cmx, cmy);

        } else if (capStyle == CAP_SQUARE) {

            emitLineTo(cx0 - cmy + cmx, cy0 + cmx + cmy);

            emitLineTo(cx0 - cmy - cmx, cy0 + cmx - cmy);

        }

        emitReverse();

        if (capStyle == CAP_ROUND) {

            drawRoundCap(sx0, sy0, -smx, -smy);

        } else if (capStyle == CAP_SQUARE) {

            emitLineTo(sx0 + smy - smx, sy0 - smx - smy);

            emitLineTo(sx0 + smy + smx, sy0 - smx + smy);

        }

        emitClose();

    }

    private void emitMoveTo(final float x0, final float y0) {

        out.moveTo(x0, y0);

    }

    private void emitLineTo(final float x1, final float y1) {

        out.lineTo(x1, y1);

    }

    private void emitLineTo(final float x1, final float y1,

                            final boolean rev)

    {

        if (rev) {

            reverse.pushLine(x1, y1);

        } else {

            emitLineTo(x1, y1);

        }

    }

    private void emitQuadTo(final float x0, final float y0,

                            final float x1, final float y1,

                            final float x2, final float y2, final boolean rev)

    {

        if (rev) {

            reverse.pushQuad(x0, y0, x1, y1);

        } else {

            out.quadTo(x1, y1, x2, y2);

        }

    }

    private void emitCurveTo(final float x0, final float y0,

                             final float x1, final float y1,

                             final float x2, final float y2,

                             final float x3, final float y3, final boolean rev)

    {

        if (rev) {

            reverse.pushCubic(x0, y0, x1, y1, x2, y2);

        } else {

            out.curveTo(x1, y1, x2, y2, x3, y3);

        }

    }

    private void emitClose() {

        out.closePath();

    }

    private void drawJoin(float pdx, float pdy,

                          float x0, float y0,

                          float dx, float dy,

                          float omx, float omy,