// Copyright 2000-2005 the Contributors, as shown in the revision logs.
// Licensed under the GNU General Public License version 2 ("the License").
// You may not use this file except in compliance with the License.

package org.ibex.graphics;
import java.util.*;
import org.ibex.util.*;

/** an abstract path; may contain splines and arcs */
public class Path {

    public static final float PX_PER_INCH = 72;
    public static final float INCHES_PER_CM = (float)0.3937;
    public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
    private static final int DEFAULT_PATHLEN = 1000;
    private static final int NUMSTEPS = 10;
    private static final float PI = (float)Math.PI;

    boolean closed = false;
    Curve head = null;
    Curve tail = null;
    protected void add(Curve c) {
        if (head==null) { tail=head=c; return; }
        c.prev = tail;
        tail.next = c;
        tail = c;
    }

    public void addTo(Mesh m, boolean evenOdd) {
        for(Curve c = head; c != null; c = c.next) c.addTo(m);
        m.setIn(evenOdd);
    }

    abstract class Curve {
        Curve next, prev;
        float x, y;
        float c1x, c1y, c2x, c2y;
        public Curve() { }
        public abstract void addTo(Mesh ret);
    }

    class Line extends Curve {
        public void addTo(Mesh ret) {
            float rx = next.x;
            float ry = next.y;
            ret.add(rx,ry);
        }
    }

    class Move extends Curve {
        public void addTo(Mesh ret) {
            ret.newcontour();
            if (next==null) return;
            float rx = next.x;
            float ry = next.y;
            ret.add(rx, ry);
        }
    }

    class Arc extends Curve {
        public void addTo(Mesh ret) {
            System.out.println("ARC!");
            float rx = c1x;
            float ry = c1y;
            float phi = c2x;
            float fa = ((int)c2y) >> 1;
            float fs = ((int)c2y) & 1;
            float x1 = x;
            float y1 = y;
            float x2 = next.x;
            float y2 = next.y;

            // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
            float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
            float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
            float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
                                         (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
            float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
            float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
            float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
            float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
            
            // F.6.4 Conversion from center to endpoint parameterization
            float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
            float det = ux * vy - uy * vx;
            float theta1 = (det < 0 ? -1 : 1) *
                (float)Math.acos((ux * vx + uy * vy) / 
                                 ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
            ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
            vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
            det = ux * vy - uy * vx;
            float dtheta = (det < 0 ? -1 : 1) *
                (float)Math.acos((ux * vx + uy * vy) / 
                                 ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
            dtheta = dtheta % (float)(2 * Math.PI);
            
            if (fs == 0 && dtheta > 0) theta1 -= 2 * PI; 
            if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
            
            if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
            else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);

            // FIXME: integrate F.6.6
            // FIXME: isn't quite ending where it should...

            // F.6.3: Parameterization alternatives
            float theta = theta1;
            for(int j=0; j<NUMSTEPS; j++) {
                float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
                    ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
                float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
                    ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
                ret.add(rasterx, rastery);
                theta += dtheta / NUMSTEPS;
            }
        }
    }

    class Bezier extends Curve {
        float cx, cy;
        public void addTo(Mesh ret) {
            float ax = next.x - 3 * c2x + 3 * c1x - x;
            float bx = 3 * c2x - 6 * c1x + 3 * x;
            float cx = 3 * c1x - 3 * x;
            float dx = x;
            float ay = next.y - 3 * c2y + 3 * c1y - y;
            float by = 3 * c2y - 6 * c1y + 3 * y;
            float cy = 3 * c1y - 3 * y;
            float dy = y;
            
            float x0 = x;
            float y0 = y;
            float x1 = next.x;
            float y1 = next.y;
            float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
            
            //for(float t=0; t<1; t += 0.5) {
            for(float t=0; t<1; t += 1/(steps/20)) {
                float rx = ax * t * t * t + bx * t * t + cx * t + dx;
                float ry = ay * t * t * t + by * t * t + cy * t + dy;
                ret.add(rx,ry);
            }
        }
    }

    class QuadBezier extends Curve {
        float cx, cy, cx2, cy2;
        public void addTo(Mesh ret) {
            throw new Error("doesn't work yet");
            /*
            float bx = next.x - 2 * c1x + x;
            float cx = 2 * c1x - 2 * x;
            float dx = x;
            float by = next.y - 2 * c1y + y;
            float cy = 2 * c1y - 2 * y;
            float dy = y;
		    	
            float x0 = a.multiply_px(x, y);
            float y0 = a.multiply_py(x, y);
            float x1 = a.multiply_px(next.x, next.y);
            float y1 = a.multiply_py(next.x, next.y);
            float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );

            for(float t=0; t<1; t += 1 / (steps/20)) {
                float rx = bx * t * t + cx * t + dx;
                float ry = by * t * t + cy * t + dy;
                ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
            }
            */
        }
    }

    public Path(String s) {
        //this.toString = s;
        Tokenizer t = new Tokenizer(s);
        char last_command = 'M';
        boolean first = true;
        while(t.hasMoreTokens()) {
            char command = t.parseCommand();
            if (first && command == 'm') command = 'M';
            if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
            first = false;
            boolean relative = Character.toLowerCase(command) == command;
            command = Character.toLowerCase(command);
            parseSingleCommandAndArguments(t, command, relative);
            last_command = command;
        }
    }

    public long boundingBox(Affine a) {
        long hb = horizontalBounds(a);
        long vb = verticalBounds(a);
        return Encode.twoFloatsToLong(Math.abs(Encode.longToFloat1(hb) - Encode.longToFloat2(hb)),
                                      Math.abs(Encode.longToFloat1(vb) - Encode.longToFloat2(vb)));
    }

    //#repeat width/height multiply_px/multiply_py horizontalBounds/verticalBounds
    public long horizontalBounds(Affine a) {
        // FIXME wrong
        float min = Float.MAX_VALUE;
        float max = Float.MIN_VALUE;
        for(Curve c = head; c != null; c = c.next) {
            min = Math.min(min, a.multiply_px(c.x, c.y));
            max = Math.max(max, a.multiply_px(c.x, c.y));
        }
        return Encode.twoFloatsToLong(max, min);
    }
    //#end

    public long transform(Affine a, boolean forReal) { return transform(a, forReal, true); }
    public long transform(Affine a, boolean forReal, boolean widthheight) {
        float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
        float maxx = Integer.MIN_VALUE; float maxy = Integer.MIN_VALUE;
        for(Curve c = head; c != null; c = c.next) {
            if (c instanceof Arc) { /* FIXME!!! WRONG!!!! */ continue; }
            float x   = a.multiply_px(c.x,   c.y);    if (x>maxx) maxx = x; if (x<minx) minx = x;
            float y   = a.multiply_py(c.x,   c.y);    if (y>maxy) maxy = y; if (y<miny) miny = y;
            float c1x = a.multiply_px(c.c1x, c.c1y);  if (c1x>maxx) maxx = c1x; if (c1x<minx) minx = c1x;
            float c1y = a.multiply_py(c.c1x, c.c1y);  if (c1y>maxy) maxy = c1y; if (c1y<miny) miny = c1y;
            float c2x = a.multiply_px(c.c2x, c.c2y);  if (c2x>maxx) maxx = c2x; if (c2x<minx) minx = c2x;
            float c2y = a.multiply_py(c.c2x, c.c2y);  if (c2y>maxy) maxy = c2y; if (c2y<miny) miny = c2y;
            if (forReal) {
                c.x = x; c.y = y;
                c.c1x = c1x; c.c1y = c1y;
                c.c2x = c2x; c.c2y = c2y;
            }
        }
        if (widthheight) return ((((long)Float.floatToIntBits(maxx - minx)) << 32) | ((long)Float.floatToIntBits(maxy - miny)));
        else return ((((long)Float.floatToIntBits(minx)) << 32) | ((long)Float.floatToIntBits(miny)));
    }

    public void alignToOrigin() {
        float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
        for(Curve c = head; c != null; c = c.next) { if (c.x < minx) minx = c.x; if (c.y < miny) miny = c.y; }
        for(Curve c = head; c != null; c = c.next) {
            c.x -= minx; c.y -= miny;
            if (c instanceof Arc) continue;
            c.c1x -= minx; c.c2x -= minx; c.c1y -= miny; c.c2y -= miny;
        }
    }

    public static class Tokenizer {
        // FIXME: check array bounds exception for improperly terminated string
        String s;
        int i = 0;
        char lastCommand = 'M';
        public Tokenizer(String s) { this.s = s; }
            
        public static Path parse(String s) {
            if (s == null) return null;
            Tokenizer t = new Tokenizer(s);
            Path ret = new Path(s);
            return ret;/*
            char last_command = 'M';
            boolean first = true;
            while(t.hasMoreTokens()) {
                char command = t.parseCommand();
                if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
                first = false;
                boolean relative = Character.toLowerCase(command) == command;
                command = Character.toLowerCase(command);
                ret.parseSingleCommandAndArguments(t, command, relative);
                last_command = command;
            }
            return ret;*/
        }
        private void consumeWhitespace() {
            while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
            if (i < s.length() && s.charAt(i) == ',') i++;
            while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
        }
        public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
        public char parseCommand() {
            consumeWhitespace();
            char c = s.charAt(i);
            if (!Character.isLetter(c)) return lastCommand;
            i++;
            return lastCommand = c;
        }
        public float parseFloat() {
            consumeWhitespace();
            int start = i;
            float multiplier = 1;
            for(; i < s.length(); i++) {
                char c = s.charAt(i);
                if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
                if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
                    if (c == '%') {                                // FIXME
                    } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
                    } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
                    } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
                    } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
                    } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
                    } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
                    } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
                    } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
                    } else if (Character.isLetter(c)) break;
                    throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
                }
            }
            //if (start == i) throw new RuntimeException("FIXME");
            if (start == i) return (float)0.0;
            try {
                return Float.parseFloat(s.substring(start, i)) * multiplier;
            } catch (NumberFormatException nfe) {
                Log.warn(Path.class, "offending string was \"" + s.substring(start, i) + "\"");
                throw nfe;
            }
        }
    }

    protected void parseSingleCommandAndArguments(Tokenizer t, char command, boolean relative) {
        if (tail==null && command!='m') throw new RuntimeException("first command MUST be an 'm', not a " + command);
        switch(command) {
            case 'z': {
                Curve c;
                for(c = tail.prev; c != null && !(c instanceof Move); c = c.prev);
                Line ret = new Line();
                ret.x = c.x;
                ret.y = c.y;
                add(ret);
                Move mov = new Move();
                mov.x = ret.x;
                mov.y = ret.y;
                add(mov);
                closed = true;
                // FIXME: actually, we should search back to the last 'z' or 'm', not just 'm'
                break;
            }

            case 'm': {
                // feature: collapse consecutive movetos
                Move ret = new Move();
                ret.x = t.parseFloat() + (relative ? tail.y : 0);
                ret.y = t.parseFloat() + (relative ? tail.y : 0);
                add(ret);
                break;
            }

            case 'l': case 'h': case 'v': {
                float first = t.parseFloat(), second;
                if (command == 'h')      second = relative ? 0 : tail.y;
                else if (command == 'v') { second = first; first = relative ? 0 : tail.x; }
                else                     second = t.parseFloat();
                Line ret = new Line();
                ret.x = first + (relative ? tail.x : 0);
                ret.y = second + (relative ? tail.y : 0);
                add(ret);
                break;
            }
            
            case 'a': {
                Arc ret = new Arc();
                ret.c1x = t.parseFloat() + (relative ? tail.x : 0);
                ret.c1y = t.parseFloat() + (relative ? tail.y : 0);
                ret.c2x = (t.parseFloat() / 360) * 2 * PI;
                ret.c2y = t.parseFloat();
                ret.x = t.parseFloat() + (relative ? tail.x : 0);
                ret.y = t.parseFloat() + (relative ? tail.y : 0);
                add(ret);
                break;
            }

            case 's': case 'c': {
                Bezier ret = new Bezier();
                if (command == 'c') {
                    tail.c1x = t.parseFloat() + (relative ? tail.x : 0);
                    tail.c1y = t.parseFloat() + (relative ? tail.y : 0);
                } else if (head != null && tail instanceof Bezier) {
                    tail.c1x = 2 * tail.x-((Bezier)tail).c2x;
                    tail.c1y = 2 * tail.y-((Bezier)tail).c2x;
                } else {
                    tail.c1x = tail.x;
                    tail.c1y = tail.y;
                }
                tail.c2x = t.parseFloat() + (relative ? tail.x : 0);
                tail.c2y = t.parseFloat() + (relative ? tail.y : 0);
		ret.x = t.parseFloat() + (relative ? tail.x : 0);
		ret.y = t.parseFloat() + (relative ? tail.y : 0);
                add(ret);
                break;
            }

            case 't': case 'q': {
                QuadBezier ret = new QuadBezier();
                if (command == 'q') {
                    tail.c1x = t.parseFloat() + (relative ? tail.x : 0);
                    tail.c1y = t.parseFloat() + (relative ? tail.y : 0);
                } else if (head != null && tail instanceof QuadBezier) {
                    tail.c1x = 2 * tail.x-((QuadBezier)tail).c1x;
                    tail.c1y = 2 * tail.y-((QuadBezier)tail).c1y;
                } else {
                    tail.c1x = tail.x;
                    tail.c1y = tail.y;
                }
                ret.x = t.parseFloat() + (relative ? tail.x : 0);
                ret.y = t.parseFloat() + (relative ? tail.y : 0);
                add(ret);
                break;
            }

            default:
        }

    }

}