/*
 * Copyright (c) 2005, 2013, 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.
 */
/*
 * (C) Copyright IBM Corp. 2005, All Rights Reserved.
 */
package sun.font;

//
// This is the 'simple' mapping implementation.  It does things the most
// straightforward way even if that is a bit slow.  It won't
// handle complex paths efficiently, and doesn't handle closed paths.
//

import java.awt.Shape;
import java.awt.font.LayoutPath;
import java.awt.geom.AffineTransform;
import java.awt.geom.GeneralPath;
import java.awt.geom.NoninvertibleTransformException;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.Formatter;
import java.util.ArrayList;

import static java.awt.geom.PathIterator.*;
import static java.lang.Math.abs;
import static java.lang.Math.sqrt;

public abstract class LayoutPathImpl extends LayoutPath {

    //
    // Convenience APIs
    //

    public Point2D pointToPath(double x, double y) {
        Point2D.Double pt = new Point2D.Double(x, y);
        pointToPath(pt, pt);
        return pt;
    }

    public Point2D pathToPoint(double a, double o, boolean preceding) {
        Point2D.Double pt = new Point2D.Double(a, o);
        pathToPoint(pt, preceding, pt);
        return pt;
    }

    public void pointToPath(double x, double y, Point2D pt) {
        pt.setLocation(x, y);
        pointToPath(pt, pt);
    }

    public void pathToPoint(double a, double o, boolean preceding, Point2D pt) {
        pt.setLocation(a, o);
        pathToPoint(pt, preceding, pt);
    }

    //
    // extra utility APIs
    //

    public abstract double start();
    public abstract double end();
    public abstract double length();
    public abstract Shape mapShape(Shape s);

    //
    // debugging flags
    //

    private static final boolean LOGMAP = false;
    private static final Formatter LOG = new Formatter(System.out);

    
Indicate how positions past the start and limit of the
path are treated.  PINNED adjusts these positions so
as to be within start and limit.  EXTENDED ignores the
start and limit and effectively extends the first and
last segments of the path 'infinitely'.  CLOSED wraps
positions around the ends of the path.
/**
     * Indicate how positions past the start and limit of the
     * path are treated.  PINNED adjusts these positions so
     * as to be within start and limit.  EXTENDED ignores the
     * start and limit and effectively extends the first and
     * last segments of the path 'infinitely'.  CLOSED wraps
     * positions around the ends of the path.
     */
    public static enum EndType {
        PINNED, EXTENDED, CLOSED;
        public boolean isPinned() { return this == PINNED; }
        public boolean isExtended() { return this == EXTENDED; }
        public boolean isClosed() { return this == CLOSED; }
    };

    //
    // Top level construction.
    //

    
Return a path representing the path from the origin through the points in order.
/**
     * Return a path representing the path from the origin through the points in order.
     */
    public static LayoutPathImpl getPath(EndType etype, double ... coords) {
        if ((coords.length & 0x1) != 0) {
            throw new IllegalArgumentException("odd number of points not allowed");
        }

        return SegmentPath.get(etype, coords);
    }

    
Use to build a SegmentPath.  This takes the data and preanalyzes it for
information that the SegmentPath needs, then constructs a SegmentPath
from that.  Mainly, this lets SegmentPath cache the lengths along
the path to each line segment, and so avoid calculating them over and over.
/**
     * Use to build a SegmentPath.  This takes the data and preanalyzes it for
     * information that the SegmentPath needs, then constructs a SegmentPath
     * from that.  Mainly, this lets SegmentPath cache the lengths along
     * the path to each line segment, and so avoid calculating them over and over.
     */
    public static final class SegmentPathBuilder {
        private double[] data;
        private int w;
        private double px;
        private double py;
        private double a;
        private boolean pconnect;

        
Construct a SegmentPathBuilder.
/**
         * Construct a SegmentPathBuilder.
         */
        public SegmentPathBuilder() {
        }

        
Reset the builder for a new path.  Datalen is a hint of how many
points will be in the path, and the working buffer will be sized
to accommodate at least this number of points.  If datalen is zero,
the working buffer is freed (it will be allocated on first use).
/**
         * Reset the builder for a new path.  Datalen is a hint of how many
         * points will be in the path, and the working buffer will be sized
         * to accommodate at least this number of points.  If datalen is zero,
         * the working buffer is freed (it will be allocated on first use).
         */
        public void reset(int datalen) {
            if (data == null || datalen > data.length) {
                data = new double[datalen];
            } else if (datalen == 0) {
                data = null;
            }
            w = 0;
            px = py = 0;
            pconnect = false;
        }

        
Automatically build from a list of points represented by pairs of
doubles.  Initial advance is zero.
/**
         * Automatically build from a list of points represented by pairs of
         * doubles.  Initial advance is zero.
         */
        public SegmentPath build(EndType etype, double... pts) {
            assert(pts.length % 2 == 0);

            reset(pts.length / 2 * 3);

            for (int i = 0; i < pts.length; i += 2) {
                nextPoint(pts[i], pts[i+1], i != 0);
            }

            return complete(etype);
        }

        
Move to a new point.  If there is no data, this will become the
first point.  If there is data, and the previous call was a lineTo, this
point is checked against the previous point, and if different, this
starts a new segment at the same advance as the end of the last
segment.  If there is data, and the previous call was a moveTo, this
replaces the point used for that previous call.
Calling this is optional, lineTo will suffice and the initial point
will be set to 0, 0.
/**
         * Move to a new point.  If there is no data, this will become the
         * first point.  If there is data, and the previous call was a lineTo, this
         * point is checked against the previous point, and if different, this
         * starts a new segment at the same advance as the end of the last
         * segment.  If there is data, and the previous call was a moveTo, this
         * replaces the point used for that previous call.
         *
         * Calling this is optional, lineTo will suffice and the initial point
         * will be set to 0, 0.
         */
        public void moveTo(double x, double y) {
            nextPoint(x, y, false);
        }

        
Connect to a new point.  If there is no data, the previous point
is presumed to be 0, 0.  This point is checked against
the previous point, and if different, this point is added to
the path and the advance extended.  If this point is the same as the
previous point, the path remains unchanged.
/**
         * Connect to a new point.  If there is no data, the previous point
         * is presumed to be 0, 0.  This point is checked against
         * the previous point, and if different, this point is added to
         * the path and the advance extended.  If this point is the same as the
         * previous point, the path remains unchanged.
         */
        public void lineTo(double x, double y) {
            nextPoint(x, y, true);
        }

        
Add a new point, and increment advance if connect is true.
This automatically rejects duplicate points and multiple disconnected points.
/**
         * Add a new point, and increment advance if connect is true.
         *
         * This automatically rejects duplicate points and multiple disconnected points.
         */
        private void nextPoint(double x, double y, boolean connect) {

            // if zero length move or line, ignore
            if (x == px && y == py) {
                return;
            }

            if (w == 0) { // this is the first point, make sure we have space
                if (data == null) {
                    data = new double[6];
                }
                if (connect) {
                    w = 3; // default first point to 0, 0
                }
            }

            // if multiple disconnected move, just update position, leave advance alone
            if (w != 0 && !connect && !pconnect) {
                data[w-3] = px = x;
                data[w-2] = py = y;
                return;
            }

            // grow data to deal with new point
            if (w == data.length) {
                double[] t = new double[w * 2];
                System.arraycopy(data, 0, t, 0, w);
                data = t;
            }

            if (connect) {
                double dx = x - px;
                double dy = y - py;
                a += sqrt(dx * dx + dy * dy);
            }

            // update data
            data[w++] = x;
            data[w++] = y;
            data[w++] = a;

            // update state
            px = x;
            py = y;
            pconnect = connect;
        }

        public SegmentPath complete() {
            return complete(EndType.EXTENDED);
        }

        
Complete building a SegmentPath.  Once this is called, the builder is restored
to its initial state and information about the previous path is released.  The
end type indicates whether to treat the path as closed, extended, or pinned.
/**
         * Complete building a SegmentPath.  Once this is called, the builder is restored
         * to its initial state and information about the previous path is released.  The
         * end type indicates whether to treat the path as closed, extended, or pinned.
         */
        public SegmentPath complete(EndType etype) {
            SegmentPath result;

            if (data == null || w < 6) {
                return null;
            }

            if (w == data.length) {
                result = new SegmentPath(data, etype);
                reset(0); // releases pointer to data
            } else {
                double[] dataToAdopt = new double[w];
                System.arraycopy(data, 0, dataToAdopt, 0, w);
                result = new SegmentPath(dataToAdopt, etype);
                reset(2); // reuses data, since we held on to it
            }

            return result;
        }
    }

    
Represents a path built from segments.  Each segment is
represented by a triple: x, y, and cumulative advance.
These represent the end point of the segment.  The start
point of the first segment is represented by the triple
at position 0.
The path might have breaks in it, e.g. it is not connected.
These will be represented by pairs of triplets that share the
same advance.
The path might be extended, pinned, or closed.  If extended,
the initial and final segments are considered to extend
'indefinitely' past the bounds of the advance.  If pinned,
they end at the bounds of the advance.  If closed,
advances before the start or after the end 'wrap around' the
path.
The start of the path is the initial triple.  This provides
the nominal advance at the given x, y position (typically
zero).  The end of the path is the final triple.  This provides
the advance at the end, the total length of the path is
thus the ending advance minus the starting advance.
Note: We might want to cache more auxiliary data than the
advance, but this seems adequate for now.
/**
     * Represents a path built from segments.  Each segment is
     * represented by a triple: x, y, and cumulative advance.
     * These represent the end point of the segment.  The start
     * point of the first segment is represented by the triple
     * at position 0.
     *
     * The path might have breaks in it, e.g. it is not connected.
     * These will be represented by pairs of triplets that share the
     * same advance.
     *
     * The path might be extended, pinned, or closed.  If extended,
     * the initial and final segments are considered to extend
     * 'indefinitely' past the bounds of the advance.  If pinned,
     * they end at the bounds of the advance.  If closed,
     * advances before the start or after the end 'wrap around' the
     * path.
     *
     * The start of the path is the initial triple.  This provides
     * the nominal advance at the given x, y position (typically
     * zero).  The end of the path is the final triple.  This provides
     * the advance at the end, the total length of the path is
     * thus the ending advance minus the starting advance.
     *
     * Note: We might want to cache more auxiliary data than the
     * advance, but this seems adequate for now.
     */
    public static final class SegmentPath extends LayoutPathImpl {
        private double[] data; // triplets x, y, a
        EndType etype;

        public static SegmentPath get(EndType etype, double... pts) {
            return new SegmentPathBuilder().build(etype, pts);
        }

        
Internal, use SegmentPathBuilder or one of the static
helper functions to construct a SegmentPath.
/**
         * Internal, use SegmentPathBuilder or one of the static
         * helper functions to construct a SegmentPath.
         */
        SegmentPath(double[] data, EndType etype) {
            this.data = data;
            this.etype = etype;
        }

        //
        // LayoutPath API
        //

        public void pathToPoint(Point2D location, boolean preceding, Point2D point) {
            locateAndGetIndex(location, preceding, point);
        }

        // the path consists of line segments, which i'll call
        // 'path vectors'.  call each run of path vectors a 'path segment'.
        // no path vector in a path segment is zero length (in the
        // data, such vectors start a new path segment).
        //
        // for each path segment...
        //
        // for each path vector...
        //
        // we look at the dot product of the path vector and the vector from the
        // origin of the path vector to the test point.  if <0 (case
        // A), the projection of the test point is before the start of
        // the path vector.  if > the square of the length of the path vector
        // (case B), the projection is past the end point of the
        // path vector.  otherwise (case C), it lies on the path vector.
        // determine the closeset point on the path vector.  if case A, it
        // is the start of the path vector.  if case B and this is the last
        // path vector in the path segment, it is the end of the path vector.  If
        // case C, it is the projection onto the path vector.  Otherwise
        // there is no closest point.
        //
        // if we have a closest point, compare the distance from it to
        // the test point against our current closest distance.
        // (culling should be fast, currently i am using distance
        // squared, but there's probably better ways).  if we're
        // closer, save the new point as the current closest point,
        // and record the path vector index so we can determine the final
        // info if this turns out to be the closest point in the end.
        //
        // after we have processed all the segments we will have
        // tested each path vector and each endpoint.  if our point is not on
        // an endpoint, we're done; we can compute the position and
        // offset again, or if we saved it off we can just use it.  if
        // we're on an endpoint we need to see which path vector we should
        // associate with.  if we're at the start or end of a path segment,
        // we're done-- the first or last vector of the segment is the
        // one we associate with.  we project against that vector to
        // get the offset, and pin to that vector to get the length.
        //
        // otherwise, we compute the information as follows.  if the
        // dot product (see above) with the following vector is zero,
        // we associate with that vector.  otherwise, if the dot
        // product with the previous vector is zero, we associate with
        // that vector.  otherwise we're beyond the end of the
        // previous vector and before the start of the current vector.
        // we project against both vectors and get the distance from
        // the test point to the projection (this will be the offset).
        // if they are the same, we take the following vector.
        // otherwise use the vector from which the test point is the
        // _farthest_ (this is because the point lies most clearly in
        // the half of the plane defined by extending that vector).
        //
        // the returned position is the path length to the (possibly
        // pinned) point, the offset is the projection onto the line
        // along the vector, and we have a boolean flag which if false
        // indicates that we associate with the previous vector at a
        // junction (which is necessary when projecting such a
        // location back to a point).

        public boolean pointToPath(Point2D pt, Point2D result) {
            double x = pt.getX();               // test point
            double y = pt.getY();

            double bx = data[0];                // previous point
            double by = data[1];
            double bl = data[2];

            // start with defaults
            double cd2 = Double.MAX_VALUE;       // current best distance from path, squared
            double cx = 0;                       // current best x
            double cy = 0;                       // current best y
            double cl = 0;                       // current best position along path
            int ci = 0;                          // current best index into data

            for (int i = 3; i < data.length; i += 3) {
                double nx = data[i];             // current end point
                double ny = data[i+1];
                double nl = data[i+2];

                double dx = nx - bx;             // vector from previous to current
                double dy = ny - by;
                double dl = nl - bl;

                double px = x - bx;              // vector from previous to test point
                double py = y - by;

                // determine sign of dot product of vectors from bx, by
                // if < 0, we're before the start of this vector

                double dot = dx * px + dy * py;      // dot product
                double vcx, vcy, vcl;                // hold closest point on vector as x, y, l
                int vi;                              // hold index of line, is data.length if last point on path
                do {                                 // use break below, lets us avoid initializing vcx, vcy...
                    if (dl == 0 ||                   // moveto, or
                        (dot < 0 &&                  // before path vector and
                         (!etype.isExtended() ||
                          i != 3))) {                // closest point is start of vector
                        vcx = bx;
                        vcy = by;
                        vcl = bl;
                        vi = i;
                    } else {
                        double l2 = dl * dl;         // aka dx * dx + dy * dy, square of length
                        if (dot <= l2 ||             // closest point is not past end of vector, or
                            (etype.isExtended() &&   // we're extended and at the last segment
                             i == data.length - 3)) {
                            double p = dot / l2;     // get parametric along segment
                            vcx = bx + p * dx;       // compute closest point
                            vcy = by + p * dy;
                            vcl = bl + p * dl;
                            vi = i;
                        } else {
                            if (i == data.length - 3) {
                                vcx = nx;            // special case, always test last point
                                vcy = ny;
                                vcl = nl;
                                vi = data.length;
                            } else {
                                break;               // typical case, skip point, we'll pick it up next iteration
                            }
                        }
                    }

                    double tdx = x - vcx;        // compute distance from (usually pinned) projection to test point
                    double tdy = y - vcy;
                    double td2 = tdx * tdx + tdy * tdy;
                    if (td2 <= cd2) {            // new closest point, record info on it
                        cd2 = td2;
                        cx = vcx;
                        cy = vcy;
                        cl = vcl;
                        ci = vi;
                    }
                } while (false);

                bx = nx;
                by = ny;
                bl = nl;
            }

            // we have our closest point, get the info
            bx = data[ci-3];
            by = data[ci-2];
            if (cx != bx || cy != by) {     // not on endpoint, no need to resolve
                double nx = data[ci];
                double ny = data[ci+1];
                double co = sqrt(cd2);     // have a true perpendicular, so can use distance
                if ((x-cx)*(ny-by) > (y-cy)*(nx-bx)) {
                    co = -co;              // determine sign of offset
                }
                result.setLocation(cl, co);
                return false;
            } else {                        // on endpoint, we need to resolve which segment
                boolean havePrev = ci != 3 && data[ci-1] != data[ci-4];
                boolean haveFoll = ci != data.length && data[ci-1] != data[ci+2];
                boolean doExtend = etype.isExtended() && (ci == 3 || ci == data.length);
                if (havePrev && haveFoll) {
                    Point2D.Double pp = new Point2D.Double(x, y);
                    calcoffset(ci - 3, doExtend, pp);
                    Point2D.Double fp = new Point2D.Double(x, y);
                    calcoffset(ci, doExtend, fp);
                    if (abs(pp.y) > abs(fp.y)) {
                        result.setLocation(pp);
                        return true; // associate with previous
                    } else {
                        result.setLocation(fp);
                        return false; // associate with following
                    }
                } else if (havePrev) {
                    result.setLocation(x, y);
                    calcoffset(ci - 3, doExtend, result);
                    return true;
                } else {
                    result.setLocation(x, y);
                    calcoffset(ci, doExtend, result);
                    return false;
                }
            }
        }

        
Return the location of the point passed in result as mapped to the
line indicated by index.  If doExtend is true, extend the
x value without pinning to the ends of the line.
this assumes that index is valid and references a line that has
non-zero length.
/**
         * Return the location of the point passed in result as mapped to the
         * line indicated by index.  If doExtend is true, extend the
         * x value without pinning to the ends of the line.
         * this assumes that index is valid and references a line that has
         * non-zero length.
         */
        private void calcoffset(int index, boolean doExtend, Point2D result) {
            double bx = data[index-3];
            double by = data[index-2];
            double px = result.getX() - bx;
            double py = result.getY() - by;
            double dx = data[index] - bx;
            double dy = data[index+1] - by;
            double l = data[index+2] - data[index - 1];

            // rx = A dot B / |B|
            // ry = A dot invB / |B|
            double rx = (px * dx + py * dy) / l;
            double ry = (px * -dy + py * dx) / l;
            if (!doExtend) {
                if (rx < 0) rx = 0;
                else if (rx > l) rx = l;
            }
            rx += data[index-1];
            result.setLocation(rx, ry);
        }

        //
        // LayoutPathImpl API
        //

        public Shape mapShape(Shape s) {
            return new Mapper().mapShape(s);
        }

        public double start() {
            return data[2];
        }

        public double end() {
            return data[data.length - 1];
        }

        public double length() {
            return data[data.length-1] - data[2];
        }

        //
        // Utilities
        //

        
Get the 'modulus' of an advance on a closed path.
/**
         * Get the 'modulus' of an advance on a closed path.
         */
        private double getClosedAdvance(double a, boolean preceding) {
            if (etype.isClosed()) {
                a -= data[2];
                int count = (int)(a/length());
                a -= count * length();
                if (a < 0 || (a == 0 && preceding)) {
                    a += length();

                }
                a += data[2];
            }
            return a;
        }

        
Return the index of the segment associated with advance. This
points to the start of the triple and is a multiple of 3 between
3 and data.length-3 inclusive.  It never points to a 'moveto' triple.
If the path is closed, 'a' is mapped to
a value between the start and end of the path, inclusive.
If preceding is true, and 'a' lies on a segment boundary,
return the index of the preceding segment, else return the index
of the current segment (if it is not a moveto segment) otherwise
the following segment (which is never a moveto segment).
Note: if the path is not closed, the advance might not actually
lie on the returned segment-- it might be before the first, or
after the last.  The first or last segment (as appropriate)
will be returned in this case.
/**
         * Return the index of the segment associated with advance. This
         * points to the start of the triple and is a multiple of 3 between
         * 3 and data.length-3 inclusive.  It never points to a 'moveto' triple.
         *
         * If the path is closed, 'a' is mapped to
         * a value between the start and end of the path, inclusive.
         * If preceding is true, and 'a' lies on a segment boundary,
         * return the index of the preceding segment, else return the index
         * of the current segment (if it is not a moveto segment) otherwise
         * the following segment (which is never a moveto segment).
         *
         * Note: if the path is not closed, the advance might not actually
         * lie on the returned segment-- it might be before the first, or
         * after the last.  The first or last segment (as appropriate)
         * will be returned in this case.
         */
        private int getSegmentIndexForAdvance(double a, boolean preceding) {
            // must have local advance
            a = getClosedAdvance(a, preceding);

            // note we must avoid 'moveto' segments.  the first segment is
            // always a moveto segment, so we always skip it.
            int i, lim;
            for (i = 5, lim = data.length-1; i < lim; i += 3) {
                double v = data[i];
                if (a < v || (a == v && preceding)) {
                    break;
                }
            }
            return i-2; // adjust to start of segment
        }

        
Map a location based on the provided segment, returning in pt.
Seg must be a valid 'lineto' segment.  Note: if the path is
closed, x must be within the start and end of the path.
/**
         * Map a location based on the provided segment, returning in pt.
         * Seg must be a valid 'lineto' segment.  Note: if the path is
         * closed, x must be within the start and end of the path.
         */
        private void map(int seg, double a, double o, Point2D pt) {
            double dx = data[seg] - data[seg-3];
            double dy = data[seg+1] - data[seg-2];
            double dl = data[seg+2] - data[seg-1];

            double ux = dx/dl; // could cache these, but is it worth it?
            double uy = dy/dl;

            a -= data[seg-1];

            pt.setLocation(data[seg-3] + a * ux - o * uy,
                           data[seg-2] + a * uy + o * ux);
        }

        
Map the point, and return the segment index.
/**
         * Map the point, and return the segment index.
         */
        private int locateAndGetIndex(Point2D loc, boolean preceding, Point2D result) {
            double a = loc.getX();
            double o = loc.getY();
            int seg = getSegmentIndexForAdvance(a, preceding);
            map(seg, a, o, result);

            return seg;
        }

        //
        // Mapping classes.
        // Map the path onto each path segment.
        // Record points where the advance 'enters' and 'exits' the path segment, and connect successive
        // points when appropriate.
        //

        
This represents a line segment from the iterator.  Each target segment will
interpret it, and since this process needs slope along the line
segment, this lets us compute it once and pass it around easily.
/**
         * This represents a line segment from the iterator.  Each target segment will
         * interpret it, and since this process needs slope along the line
         * segment, this lets us compute it once and pass it around easily.
         */
        class LineInfo {
            double sx, sy; // start
            double lx, ly; // limit
            double m;      // slope dy/dx

            
Set the lineinfo to this line
/**
             * Set the lineinfo to this line
             */
            void set(double sx, double sy, double lx, double ly) {
                this.sx = sx;
                this.sy = sy;
                this.lx = lx;
                this.ly = ly;
                double dx = lx - sx;
                if (dx == 0) {
                    m = 0; // we'll check for this elsewhere
                } else {
                    double dy = ly - sy;
                    m = dy / dx;
                }
            }

            void set(LineInfo rhs) {
                this.sx = rhs.sx;
                this.sy = rhs.sy;
                this.lx = rhs.lx;
                this.ly = rhs.ly;
                this.m  = rhs.m;
            }

            
Return true if we intersect the infinitely tall rectangle with
lo <= x < hi.  If we do, also return the pinned portion of ourselves in
result.
/**
             * Return true if we intersect the infinitely tall rectangle with
             * lo <= x < hi.  If we do, also return the pinned portion of ourselves in
             * result.
             */
            boolean pin(double lo, double hi, LineInfo result) {
                result.set(this);
                if (lx >= sx) {
                    if (sx < hi && lx >= lo) {
                        if (sx < lo) {
                            if (m != 0) result.sy = sy + m * (lo - sx);
                            result.sx = lo;
                        }
                        if (lx > hi) {
                            if (m != 0) result.ly = ly + m * (hi - lx);
                            result.lx = hi;
                        }
                        return true;
                    }
                } else {
                    if (lx < hi && sx >= lo) {
                        if (lx < lo) {
                            if (m != 0) result.ly = ly + m * (lo - lx);
                            result.lx = lo;
                        }
                        if (sx > hi) {
                            if (m != 0) result.sy = sy + m * (hi - sx);
                            result.sx = hi;
                        }
                        return true;
                    }
                }
                return false;
            }

            
Return true if we intersect the segment at ix.  This takes
the path end type into account and computes the relevant
parameters to pass to pin(double, double, LineInfo).
/**
             * Return true if we intersect the segment at ix.  This takes
             * the path end type into account and computes the relevant
             * parameters to pass to pin(double, double, LineInfo).
             */
            boolean pin(int ix, LineInfo result) {
                double lo = data[ix-1];
                double hi = data[ix+2];
                switch (SegmentPath.this.etype) {
                case PINNED:
                    break;
                case EXTENDED:
                    if (ix == 3) lo = Double.NEGATIVE_INFINITY;
                    if (ix == data.length - 3) hi = Double.POSITIVE_INFINITY;
                    break;
                case CLOSED:
                    // not implemented
                    break;
                }

                return pin(lo, hi, result);
            }
        }

        
Each segment will construct its own general path, mapping the provided lines
into its own simple space.
/**
         * Each segment will construct its own general path, mapping the provided lines
         * into its own simple space.
         */
        class Segment {
            final int ix;        // index into data array for this segment
            final double ux, uy; // unit vector

            final LineInfo temp; // working line info

            boolean broken;      // true if a moveto has occurred since we last added to our path
            double cx, cy;       // last point in gp
            GeneralPath gp;      // path built for this segment

            Segment(int ix) {
                this.ix = ix;
                double len = data[ix+2] - data[ix-1];
                this.ux = (data[ix] - data[ix-3]) / len;
                this.uy = (data[ix+1] - data[ix-2]) / len;
                this.temp = new LineInfo();
            }

            void init() {
                if (LOGMAP) LOG.format("s(%d) init\n", ix);
                broken = true;
                cx = cy = Double.MIN_VALUE;
                this.gp = new GeneralPath();
            }

            void move() {
                if (LOGMAP) LOG.format("s(%d) move\n", ix);
                broken = true;
            }

            void close() {
                if (!broken) {
                    if (LOGMAP) LOG.format("s(%d) close\n[cp]\n", ix);
                    gp.closePath();
                }
            }

            void line(LineInfo li) {
                if (LOGMAP) LOG.format("s(%d) line %g, %g to %g, %g\n", ix, li.sx, li.sy, li.lx, li.ly);

                if (li.pin(ix, temp)) {
                    if (LOGMAP) LOG.format("pin: %g, %g to %g, %g\n", temp.sx, temp.sy, temp.lx, temp.ly);

                    temp.sx -= data[ix-1];
                    double sx = data[ix-3] + temp.sx * ux - temp.sy * uy;
                    double sy = data[ix-2] + temp.sx * uy + temp.sy * ux;
                    temp.lx -= data[ix-1];
                    double lx = data[ix-3] + temp.lx * ux - temp.ly * uy;
                    double ly = data[ix-2] + temp.lx * uy + temp.ly * ux;

                    if (LOGMAP) LOG.format("points: %g, %g to %g, %g\n", sx, sy, lx, ly);

                    if (sx != cx || sy != cy) {
                        if (broken) {
                            if (LOGMAP) LOG.format("[mt %g, %g]\n", sx, sy);
                            gp.moveTo((float)sx, (float)sy);
                        } else {
                            if (LOGMAP) LOG.format("[lt %g, %g]\n", sx, sy);
                            gp.lineTo((float)sx, (float)sy);
                        }
                    }
                    if (LOGMAP) LOG.format("[lt %g, %g]\n", lx, ly);
                    gp.lineTo((float)lx, (float)ly);

                    broken = false;
                    cx = lx;
                    cy = ly;
                }
            }
        }

        class Mapper {
            final LineInfo li;                 // working line info
            final ArrayList<Segment> segments; // cache additional data on segments, working objects
            final Point2D.Double mpt;          // last moveto source point
            final Point2D.Double cpt;          // current source point
            boolean haveMT;                    // true when last op was a moveto

            Mapper() {
                li = new LineInfo();
                segments = new ArrayList<Segment>();
                for (int i = 3; i < data.length; i += 3) {
                    if (data[i+2] != data[i-1]) { // a new segment
                        segments.add(new Segment(i));
                    }
                }

                mpt = new Point2D.Double();
                cpt = new Point2D.Double();
            }

            void init() {
                if (LOGMAP) LOG.format("init\n");
                haveMT = false;
                for (Segment s: segments) {
                    s.init();
                }
            }

            void moveTo(double x, double y) {
                if (LOGMAP) LOG.format("moveto %g, %g\n", x, y);
                mpt.x = x;
                mpt.y = y;
                haveMT = true;
            }

            void lineTo(double x, double y) {
                if (LOGMAP) LOG.format("lineto %g, %g\n", x, y);

                if (haveMT) {
                    // prepare previous point for no-op check
                    cpt.x = mpt.x;
                    cpt.y = mpt.y;
                }

                if (x == cpt.x && y == cpt.y) {
                    // lineto is a no-op
                    return;
                }

                if (haveMT) {
                    // current point is the most recent moveto point
                    haveMT = false;
                    for (Segment s: segments) {
                        s.move();
                    }
                }

                li.set(cpt.x, cpt.y, x, y);
                for (Segment s: segments) {
                    s.line(li);
                }

                cpt.x = x;
                cpt.y = y;
            }

            void close() {
                if (LOGMAP) LOG.format("close\n");
                lineTo(mpt.x, mpt.y);
                for (Segment s: segments) {
                    s.close();
                }
            }

            public Shape mapShape(Shape s) {
                if (LOGMAP) LOG.format("mapshape on path: %s\n", LayoutPathImpl.SegmentPath.this);
                PathIterator pi = s.getPathIterator(null, 1); // cheap way to handle curves.

                if (LOGMAP) LOG.format("start\n");
                init();

                final double[] coords = new double[2];
                while (!pi.isDone()) {
                    switch (pi.currentSegment(coords)) {
                    case SEG_CLOSE: close(); break;
                    case SEG_MOVETO: moveTo(coords[0], coords[1]); break;
                    case SEG_LINETO: lineTo(coords[0], coords[1]); break;
                    default: break;
                    }

                    pi.next();
                }
                if (LOGMAP) LOG.format("finish\n\n");

                GeneralPath gp = new GeneralPath();
                for (Segment seg: segments) {
                    gp.append(seg.gp, false);
                }
                return gp;
            }
        }

        //
        // for debugging
        //

        public String toString() {
            StringBuilder b = new StringBuilder();
            b.append("{");
            b.append(etype.toString());
            b.append(" ");
            for (int i = 0; i < data.length; i += 3) {
                if (i > 0) {
                    b.append(",");
                }
                float x = ((int)(data[i] * 100))/100.0f;
                float y = ((int)(data[i+1] * 100))/100.0f;
                float l = ((int)(data[i+2] * 10))/10.0f;
                b.append("{");
                b.append(x);
                b.append(",");
                b.append(y);
                b.append(",");
                b.append(l);
                b.append("}");
            }
            b.append("}");
            return b.toString();
        }
    }


    public static class EmptyPath extends LayoutPathImpl {
        private AffineTransform tx;

        public EmptyPath(AffineTransform tx) {
            this.tx = tx;
        }

        public void pathToPoint(Point2D location, boolean preceding, Point2D point) {
            if (tx != null) {
                tx.transform(location, point);
            } else {
                point.setLocation(location);
            }
        }

        public boolean pointToPath(Point2D pt, Point2D result) {
            result.setLocation(pt);
            if (tx != null) {
                try {
                    tx.inverseTransform(pt, result);
                }
                catch (NoninvertibleTransformException ex) {
                }
            }
            return result.getX() > 0;
        }

        public double start() { return 0; }

        public double end() { return 0; }

        public double length() { return 0; }

        public Shape mapShape(Shape s) {
            if (tx != null) {
                return tx.createTransformedShape(s);
            }
            return s;
        }
    }
}