/* * Copyright (c) 1998, 2003, 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. */ package sun.awt.geom; import java.util.Vector;import java.util.Enumeration;import java.util.Comparator;import java.util.Arrays; public abstract class AreaOp {    public static abstract class CAGOp extends AreaOp {        boolean inLeft;        boolean inRight;        boolean inResult;         public void newRow() {            inLeft = false;            inRight = false;            inResult = false;        }         public int classify(Edge e) {            if (e.getCurveTag() == CTAG_LEFT) {                inLeft = !inLeft;            } else {                inRight = !inRight;            }            boolean newClass = newClassification(inLeft, inRight);            if (inResult == newClass) {                return ETAG_IGNORE;            }            inResult = newClass;            return (newClass ? ETAG_ENTER : ETAG_EXIT);        }         public int getState() {            return (inResult ? RSTAG_INSIDE : RSTAG_OUTSIDE);        }         public abstract boolean newClassification(boolean inLeft,                                                  boolean inRight);    }     public static class AddOp extends CAGOp {        public boolean newClassification(boolean inLeft, boolean inRight) {            return (inLeft || inRight);        }    }     public static class SubOp extends CAGOp {        public boolean newClassification(boolean inLeft, boolean inRight) {            return (inLeft && !inRight);        }    }     public static class IntOp extends CAGOp {        public boolean newClassification(boolean inLeft, boolean inRight) {            return (inLeft && inRight);        }    }     public static class XorOp extends CAGOp {        public boolean newClassification(boolean inLeft, boolean inRight) {            return (inLeft != inRight);        }    }     public static class NZWindOp extends AreaOp {        private int count;         public void newRow() {            count = 0;        }         public int classify(Edge e) {            // Note: the right curves should be an empty set with this op...            // assert(e.getCurveTag() == CTAG_LEFT);            int newCount = count;            int type = (newCount == 0 ? ETAG_ENTER : ETAG_IGNORE);            newCount += e.getCurve().getDirection();            count = newCount;            return (newCount == 0 ? ETAG_EXIT : type);        }         public int getState() {            return ((count == 0) ? RSTAG_OUTSIDE : RSTAG_INSIDE);        }    }     public static class EOWindOp extends AreaOp {        private boolean inside;         public void newRow() {            inside = false;        }         public int classify(Edge e) {            // Note: the right curves should be an empty set with this op...            // assert(e.getCurveTag() == CTAG_LEFT);            boolean newInside = !inside;            inside = newInside;            return (newInside ? ETAG_ENTER : ETAG_EXIT);        }         public int getState() {            return (inside ? RSTAG_INSIDE : RSTAG_OUTSIDE);        }    }     private AreaOp() {    }     /* Constants to tag the left and right curves in the edge list */    public static final int CTAG_LEFT = 0;    public static final int CTAG_RIGHT = 1;     /* Constants to classify edges */    public static final int ETAG_IGNORE = 0;    public static final int ETAG_ENTER = 1;    public static final int ETAG_EXIT = -1;     /* Constants used to classify result state */    public static final int RSTAG_INSIDE = 1;    public static final int RSTAG_OUTSIDE = -1;     public abstract void newRow();     public abstract int classify(Edge e);     public abstract int getState();     public Vector calculate(Vector left, Vector right) {        Vector edges = new Vector();        addEdges(edges, left, AreaOp.CTAG_LEFT);        addEdges(edges, right, AreaOp.CTAG_RIGHT);        edges = pruneEdges(edges);        if (false) {            System.out.println("result: ");            int numcurves = edges.size();            Curve[] curvelist = (Curve[]) edges.toArray(new Curve[numcurves]);            for (int i = 0; i < numcurves; i++) {                System.out.println("curvelist["+i+"] = "+curvelist[i]);            }        }        return edges;    }     private static void addEdges(Vector edges, Vector curves, int curvetag) {        Enumeration enum_ = curves.elements();        while (enum_.hasMoreElements()) {            Curve c = (Curve) enum_.nextElement();            if (c.getOrder() > 0) {                edges.add(new Edge(c, curvetag));            }        }    }     private static Comparator YXTopComparator = new Comparator() {        public int compare(Object o1, Object o2) {            Curve c1 = ((Edge) o1).getCurve();            Curve c2 = ((Edge) o2).getCurve();            double v1, v2;            if ((v1 = c1.getYTop()) == (v2 = c2.getYTop())) {                if ((v1 = c1.getXTop()) == (v2 = c2.getXTop())) {                    return 0;                }            }            if (v1 < v2) {                return -1;            }            return 1;        }    };     private Vector pruneEdges(Vector edges) {        int numedges = edges.size();        if (numedges < 2) {            return edges;        }        Edge[] edgelist = (Edge[]) edges.toArray(new Edge[numedges]);        Arrays.sort(edgelist, YXTopComparator);        if (false) {            System.out.println("pruning: ");            for (int i = 0; i < numedges; i++) {                System.out.println("edgelist["+i+"] = "+edgelist[i]);            }        }        Edge e;        int left = 0;        int right = 0;        int cur = 0;        int next = 0;        double yrange[] = new double[2];        Vector subcurves = new Vector();        Vector chains = new Vector();        Vector links = new Vector();        // Active edges are between left (inclusive) and right (exclusive)        while (left < numedges) {            double y = yrange[0];            // Prune active edges that fall off the top of the active y range            for (cur = next = right - 1; cur >= left; cur--) {                e = edgelist[cur];                if (e.getCurve().getYBot() > y) {                    if (next > cur) {                        edgelist[next] = e;                    }                    next--;                }            }            left = next + 1;            // Grab a new "top of Y range" if the active edges are empty            if (left >= right) {                if (right >= numedges) {                    break;                }                y = edgelist[right].getCurve().getYTop();                if (y > yrange[0]) {                    finalizeSubCurves(subcurves, chains);                }                yrange[0] = y;            }            // Incorporate new active edges that enter the active y range            while (right < numedges) {                e = edgelist[right];                if (e.getCurve().getYTop() > y) {                    break;                }                right++;            }            // Sort the current active edges by their X values and            // determine the maximum valid Y range where the X ordering            // is correct            yrange[1] = edgelist[left].getCurve().getYBot();            if (right < numedges) {                y = edgelist[right].getCurve().getYTop();                if (yrange[1] > y) {                    yrange[1] = y;                }            }            if (false) {                System.out.println("current line: y = ["+                                   yrange[0]+", "+yrange[1]+"]");                for (cur = left; cur < right; cur++) {                    System.out.println("  "+edgelist[cur]);                }            }            // Note: We could start at left+1, but we need to make            // sure that edgelist[left] has its equivalence set to 0.            int nexteq = 1;            for (cur = left; cur < right; cur++) {                e = edgelist[cur];                e.setEquivalence(0);                for (next = cur; next > left; next--) {                    Edge prevedge = edgelist[next-1];                    int ordering = e.compareTo(prevedge, yrange);                    if (yrange[1] <= yrange[0]) {                        throw new InternalError("backstepping to "+yrange[1]+                                                " from "+yrange[0]);                    }                    if (ordering >= 0) {                        if (ordering == 0) {                            // If the curves are equal, mark them to be                            // deleted later if they cancel each other                            // out so that we avoid having extraneous                            // curve segments.                            int eq = prevedge.getEquivalence();                            if (eq == 0) {                                eq = nexteq++;                                prevedge.setEquivalence(eq);                            }                            e.setEquivalence(eq);                        }                        break;                    }                    edgelist[next] = prevedge;                }                edgelist[next] = e;            }            if (false) {                System.out.println("current sorted line: y = ["+                                   yrange[0]+", "+yrange[1]+"]");                for (cur = left; cur < right; cur++) {                    System.out.println("  "+edgelist[cur]);                }            }            // Now prune the active edge list.            // For each edge in the list, determine its classification            // (entering shape, exiting shape, ignore - no change) and            // record the current Y range and its classification in the            // Edge object for use later in constructing the new outline.            newRow();            double ystart = yrange[0];            double yend = yrange[1];            for (cur = left; cur < right; cur++) {                e = edgelist[cur];                int etag;                int eq = e.getEquivalence();                if (eq != 0) {                    // Find one of the segments in the "equal" range                    // with the right transition state and prefer an                    // edge that was either active up until ystart                    // or the edge that extends the furthest downward                    // (i.e. has the most potential for continuation)                    int origstate = getState();                    etag = (origstate == AreaOp.RSTAG_INSIDE                            ? AreaOp.ETAG_EXIT                            : AreaOp.ETAG_ENTER);                    Edge activematch = null;                    Edge longestmatch = e;                    double furthesty = yend;                    do {                        // Note: classify() must be called                        // on every edge we consume here.                        classify(e);                        if (activematch == null &&                            e.isActiveFor(ystart, etag))                        {                            activematch = e;                        }                        y = e.getCurve().getYBot();                        if (y > furthesty) {                            longestmatch = e;                            furthesty = y;                        }                    } while (++cur < right &&                             (e = edgelist[cur]).getEquivalence() == eq);                    --cur;                    if (getState() == origstate) {                        etag = AreaOp.ETAG_IGNORE;                    } else {                        e = (activematch != null ? activematch : longestmatch);                    }                } else {                    etag = classify(e);                }                if (etag != AreaOp.ETAG_IGNORE) {                    e.record(yend, etag);                    links.add(new CurveLink(e.getCurve(), ystart, yend, etag));                }            }            // assert(getState() == AreaOp.RSTAG_OUTSIDE);            if (getState() != AreaOp.RSTAG_OUTSIDE) {                System.out.println("Still inside at end of active edge list!");                System.out.println("num curves = "+(right-left));                System.out.println("num links = "+links.size());                System.out.println("y top = "+yrange[0]);                if (right < numedges) {                    System.out.println("y top of next curve = "+                                       edgelist[right].getCurve().getYTop());                } else {                    System.out.println("no more curves");                }                for (cur = left; cur < right; cur++) {                    e = edgelist[cur];                    System.out.println(e);                    int eq = e.getEquivalence();                    if (eq != 0) {                        System.out.println("  was equal to "+eq+"...");                    }                }            }            if (false) {                System.out.println("new links:");                for (int i = 0; i < links.size(); i++) {                    CurveLink link = (CurveLink) links.elementAt(i);                    System.out.println("  "+link.getSubCurve());                }            }            resolveLinks(subcurves, chains, links);            links.clear();            // Finally capture the bottom of the valid Y range as the top            // of the next Y range.            yrange[0] = yend;        }        finalizeSubCurves(subcurves, chains);        Vector ret = new Vector();        Enumeration enum_ = subcurves.elements();        while (enum_.hasMoreElements()) {            CurveLink link = (CurveLink) enum_.nextElement();            ret.add(link.getMoveto());            CurveLink nextlink = link;            while ((nextlink = nextlink.getNext()) != null) {                if (!link.absorb(nextlink)) {                    ret.add(link.getSubCurve());                    link = nextlink;                }            }            ret.add(link.getSubCurve());        }        return ret;    }     public static void finalizeSubCurves(Vector subcurves, Vector chains) {        int numchains = chains.size();        if (numchains == 0) {            return;        }        if ((numchains & 1) != 0) {            throw new InternalError("Odd number of chains!");        }        ChainEnd[] endlist = new ChainEnd[numchains];        chains.toArray(endlist);        for (int i = 1; i < numchains; i += 2) {            ChainEnd open = endlist[i - 1];            ChainEnd close = endlist[i];            CurveLink subcurve = open.linkTo(close);            if (subcurve != null) {                subcurves.add(subcurve);            }        }        chains.clear();    }     private static CurveLink[] EmptyLinkList = new CurveLink[2];    private static ChainEnd[] EmptyChainList = new ChainEnd[2];     public static void resolveLinks(Vector subcurves,                                    Vector chains,                                    Vector links)    {        int numlinks = links.size();        CurveLink[] linklist;        if (numlinks == 0) {            linklist = EmptyLinkList;        } else {            if ((numlinks & 1) != 0) {                throw new InternalError("Odd number of new curves!");            }            linklist = new CurveLink[numlinks+2];            links.toArray(linklist);        }        int numchains = chains.size();        ChainEnd[] endlist;        if (numchains == 0) {            endlist = EmptyChainList;        } else {            if ((numchains & 1) != 0) {                throw new InternalError("Odd number of chains!");            }            endlist = new ChainEnd[numchains+2];            chains.toArray(endlist);        }        int curchain = 0;        int curlink = 0;        chains.clear();        ChainEnd chain = endlist[0];        ChainEnd nextchain = endlist[1];        CurveLink link = linklist[0];        CurveLink nextlink = linklist[1];        while (chain != null || link != null) {            /*             * Strategy 1:             * Connect chains or links if they are the only things left...             */            boolean connectchains = (link == null);            boolean connectlinks = (chain == null);             if (!connectchains && !connectlinks) {                // assert(link != null && chain != null);                /*                 * Strategy 2:                 * Connect chains or links if they close off an open area...                 */                connectchains = ((curchain & 1) == 0 &&                                 chain.getX() == nextchain.getX());                connectlinks = ((curlink & 1) == 0 &&                                link.getX() == nextlink.getX());                 if (!connectchains && !connectlinks) {                    /*                     * Strategy 3:                     * Connect chains or links if their successor is                     * between them and their potential connectee...                     */                    double cx = chain.getX();                    double lx = link.getX();                    connectchains =

Lines 1–500 of 561. Load more