//
//  PoliSim.java-- emulate several candidates running in an election,
//                 using a 2-D model of political positions.
//
//  jsm-- could I speed up by making some methods "final"?
//

import java.applet.* ;
import java.awt.* ;
import java.awt.image.* ;

public class PoliSim extends Applet implements Runnable {
    Candidate cand[] ;
    BorderSeg bordersegs[][] ;
    boolean isuptodate ;

    // panel components
    int fieldmax ;
    FieldCanvas mainfield ;
    BarGraphCanvas bargraph= new BarGraphCanvas(160, 260, true) ;
    Button animator= new Button("Run automatically") ;
    TextField numcandentry= new TextField(4) ;
    Button newcandstart= new Button("Go") ;
    Button upone= new Button("Add 1") ;
    Button downone= new Button("Remove 1") ;
    Button buffertoggle= new Button() ;

    int round= 0 ;
    boolean hasbeenmoved= false ;
    // hack to get right space allocation
    Label rounddisplay= new Label("Round "+round+(hasbeenmoved?"*":"")+"          ") ;
    Button resetround= new Button("Reset rounds") ;

    // applet parameters
    int numtests ;
    double angles[] ;

    private double t ;
    static private int framespersecond= 20 ;
    Thread PoliSimThread ;
    Image doubleBuffer ;
    boolean autopilot= false ;


    public void init() {
        // get field size and create related components
        int fieldsize= getIntParameter("fieldsize", 400) ;
        fieldmax= fieldsize-1 ;
        mainfield= new FieldCanvas(fieldsize, fieldsize, true) ;

        // generate candidate list
        int numcands= getIntParameter("numcands", 4) ;
        cand= newcandlist(numcands) ;
        isuptodate= false ;

        // get any other applet parameters
        numtests= getIntParameter("numtests", 5) ;
        angles= getangles(numtests) ;

        // add components to main panel
        setLayout(new FlowLayout(FlowLayout.LEFT)) ;
        add(mainfield) ;
        Panel p= new Panel() ;
            p.setLayout(new BorderLayout()) ;
            p.add("North", bargraph) ;
            p.add("South", animator) ;
            Panel p2= new Panel() ;
                p2.add(resetround) ;
                p2.add(rounddisplay) ;
            p.add("West", p2) ;
        add(p) ;
        p= new Panel() ;
            p.add(new Label("Enter number of candidates:")) ;
            p.add(numcandentry) ;
            p.add(newcandstart) ;
            p.add(upone) ;
            p.add(downone) ;
        add(p) ;
        add(buffertoggle) ;

        // set various component fields
        if (mainfield.isbuffered) buffertoggle.setLabel("Increase Speed") ;
        else                      buffertoggle.setLabel("Reduce flicker") ;
        numcandentry.setText(Integer.toString(numcands)) ;
    }


    // generate new candidate list
    // ensure there's always at least one candidate
    public Candidate[] newcandlist(int numcands) {
        if (numcands<1) numcands= 1 ;
        Candidate newcand[]= new Candidate[numcands] ;
        float hue= (float)Math.random() ;
        for (int i=0; i<newcand.length; i++, hue+= 1.0/newcand.length) {
            if (hue>1) hue-= 1 ;
            newcand[i]= new Candidate(Math.random()*(fieldmax+1),
                                      Math.random()*(fieldmax+1),
                                      Color.getHSBColor
                                        (hue, (float)1.0, (float)1.0) ) ;
        }
        return newcand ;
    }


    // calculate all new data, based on new candidate positions
    public void calculate() {
        // return immediately if allowed
        if (!isuptodate) {
            // otherwise, only allow one calculation at a time
            synchronized (this) {
                // if a thread waited, don't make it recalculate
                if (!isuptodate) {
                    bordersegs= getbordersegs(cand) ;
                    calcareas(cand,bordersegs) ;
                    isuptodate= true ;
                }
            }
        }
    }


    // create list of perpendicular bisectors, plus framing lines
    // assumes no candidates are EXACTLY the same point.
    private BorderLine[] getborders(Candidate cand[]) {
        Point2D midpt ;
        Line2D connector ;
        BorderLine borders[]=
            new BorderLine[(cand.length*(cand.length-1))/2+4] ;
        int numborders= 0 ;
        for (int i=0; i<cand.length-1; i++) {
            for (int j=i+1; j<cand.length; j++) {
                connector= new Line2D(cand[i].pos,cand[j].pos) ;
                midpt= cand[i].pos.midpoint(cand[j].pos) ;
                borders[numborders++]=
                   new BorderLine(connector.perpendicular(midpt),
                                   cand[i], cand[j]) ;
            }
        }

        // add framers to border list
        System.arraycopy(mainfield.framers, 0, borders, numborders, 4) ;

        return borders ;
    }


    // create 2-D list of border segments
    // format of array is borderseg[border#][segment#]
    private BorderSeg[][] getbordersegs(Candidate cand[]) {
        BorderLine borders[]= getborders(cand) ;
        BorderSeg segs[][]= new BorderSeg[borders.length][borders.length] ;

        // iterate for each border line
        for (int i=0; i<borders.length; i++) {

            // first, create list of intersecting points
            // leave out points with NaN
            Point2D p[]= new Point2D[borders.length+3] ; // intersections
            int numpoints= 0 ;
            for (int j=0; j<borders.length; j++) {
                if (i!=j) {
                    Point2D newp= new Point2D(borders[i],borders[j]) ;
                    if (!Double.isNaN(newp.x) && !Double.isNaN(newp.y))
                        p[numpoints++]= newp ;
                }
            }
            // OK, we have list of intersecting points

            // sort points by x, or by y if is vertical; remove duplicates
            p= Point2D.binsortpartu(p, 0, numpoints-1) ;
            numpoints= p.length ;


            // create line segments between the points
            // jsm-- this could be improved more, collapsed with next
            //      two blocks.
            int numsegs=0 ;
            BorderSeg newseg ;
            for (int k=0; k<numpoints-1; k++) {
                if  (p[k].inside(0,0,fieldmax,fieldmax)
                  && p[k+1].inside(0,0,fieldmax,fieldmax)) {
                    newseg=
                        new BorderSeg(p[k],p[k+1],borders[i].c1,borders[i].c2) ;
                    newseg.checkisgood(cand) ;
                    if (newseg.isgood) segs[i][numsegs++]= newseg ;

                }
            }


            // Consolidate the list of segments into one segment (relies
            //   on truncating, below)
            // Improves time a little for large number of candidates
            // Note that only the borders between points can be
            //   consolidated, not the surrounding frames.  Actually, the
            //   frames could be consolidated, but with a different
            //   algorithm.
            if (numsegs>0 && borders[i].c1!=null && borders[i].c2!=null) {
                Point2D startpoint= segs[i][0].p1 ;
                Point2D endpoint= segs[i][numsegs-1].p2 ;
                segs[i][0]= new BorderSeg(startpoint, endpoint,
                                          borders[i].c1,borders[i].c2) ;
                segs[i][0].isgood= true ;
                numsegs= 1 ;
            }


            // truncate the segment array
            BorderSeg seglist[]= new BorderSeg[numsegs] ;
            System.arraycopy(segs[i], 0, seglist, 0, numsegs) ;
            segs[i]= seglist ;
            // OK, line segments are now created

/*

            BorderSeg newseg ;
            Point2D startpoint, endpoint ;
            for (int k=0; k<numpoints-1; k++) {
                if  (p[k].inside(0,0,fieldmax,fieldmax)
                  && p[k+1].inside(0,0,fieldmax,fieldmax)) {
                    // new, shorter method?
                    newseg=
                        new BorderSeg(p[k],p[k+1],borders[i].c1,borders[i].c2) ;
                    newseg.checkisgood(cand) ;
                    if (newseg.isgood && startpoint==null) {
                        startpoint= p[k] ;
                    }
                    if (newseg.isgood) endpoint= p[k+1] ;
                }
            }
            if (startpoint!=null && endpoint!=null) {
                segs[i][0]= new BorderSeg(startpoint, endpoint,
                                           borders[i].c1,borders[i].c2) ;
                segs[i][0].isgood= true ;
                // truncate the segment array
                BorderSeg seglist[]= new BorderSeg[1] ;
                System.arraycopy(segs[i], 0, seglist, 0, 1) ;
                segs[i]= seglist ;
                // OK, line segments are now created
            } else {
                segs[i]= new BorderSeg[0] ;
            }
// */

        }

        return segs ;
    }


    // calculate areas for all candidates
    private void calcareas(Candidate cand[], BorderSeg bordersegs[][]) {
        Candidate bestcand ;
        BorderSeg curseg ;

        for (int i=0; i<cand.length; i++) cand[i].area=0 ;

        for (int i=0; i<bordersegs.length; i++) {
            for (int j=0; j<bordersegs[i].length; j++) {
                curseg= bordersegs[i][j] ;
                if (curseg.isgood) {
                    if (curseg.c1==null) {
                        bestcand= curseg.closest(cand) ;
                        bestcand.area+= curseg.triarea(bestcand.pos) ;
                    } else {
                        curseg.c1.area+= curseg.triarea(curseg.c1.pos) ;
                        curseg.c2.area+= curseg.triarea(curseg.c2.pos) ;
                    }
                }
            }
        }
    }


    // calculate area for one candidate (takes almost as long as calcareas())
    private double calconearea(Candidate cand[], BorderSeg bordersegs[][],
                             Candidate c) {
        BorderSeg curseg ;
        double total=0 ;
        for (int i=0; i<bordersegs.length; i++) {
            for (int j=0; j<bordersegs[i].length; j++) {
                curseg= bordersegs[i][j] ;
                if (curseg.isgood) {
                    if (curseg.c1==null) {
                        if (c==curseg.closest(cand))
                            total+= curseg.triarea(c.pos) ;
                    } else {
                        if (c==curseg.c1 || c==curseg.c2)
                            total+= curseg.triarea(c.pos) ;
                    }
                }
            }
        }
        return total ;
    }


    // see if a new position is any better than the old one
    private double testarea(Candidate c, Point2D newpos) {
        Point2D oldpos= c.pos ;
        c.pos= newpos ;
        BorderSeg testsegs[][]= getbordersegs(cand) ;
        double result= calconearea(cand, testsegs, c) ;
        c.pos= oldpos ;
        return result ;
    }


    // move candidates to their advantage
    public void movecands(Candidate cand[]) {
        // first, find center of all points
        double xtotal=0, ytotal=0 ;
        for (int i=0; i<cand.length; i++) {
            xtotal+= cand[i].pos.x ;
            ytotal+= cand[i].pos.y ;
        }
        Point2D center= new Point2D(xtotal/cand.length, ytotal/cand.length) ;

        // then, test each candidate for the best direction to go in.
        // allocate these vars outside the loop for efficiency.
        Point2D newpos[]= new Point2D[cand.length] ;
        double dist, bestarea, newarea ;
        Point2D bestpt ;
        // move one candidate at a time, while maintaining others' positions
        for (int i=0; i<cand.length; i++) {
            dist= Math.max(cand[i].pos.distance(center)/20, 2) ; // provide a minimum
            bestarea= cand[i].area ;
            bestpt= cand[i].pos ;
            for (int j=0; j<numtests; j++) {
                Point2D newpt= new Point2D(cand[i].pos.x+dist*Math.cos(angles[j]),
                                           cand[i].pos.y+dist*Math.sin(angles[j]) ) ;
                newpt.constrain(Math.random(), Math.random(),
                                fieldmax-Math.random(),
                                fieldmax-Math.random() ) ;
                if ( (newarea= testarea(cand[i], newpt)) > bestarea ) {
                    bestarea= newarea ;
                    bestpt= newpt ;
                }
                // not strictly thread-safe, but safe enough for this app?
                PoliSimThread.yield() ;
            }
            newpos[i]= bestpt ;  // save best location
        }
        // after testing all, set locations to new locations
        for (int i=0; i<cand.length; i++) cand[i].pos= newpos[i] ;
        isuptodate= false ;
    }

    // return a list of angles dividing a circle into equal parts
    private double[] getangles(int numangles) {
        double[] angle= new double[numangles] ;
        for (int j=0; j<numangles; j++) {
            angle[j]= j*2*Math.PI/numangles ;
        }
        return angle ;
    }



    // Event routines
    public boolean mouseDown(Event e, int x, int y) {
        printcands(cand) ;
        return true ;
    }

    public boolean action(Event e, Object arg) {
        if (e.target==animator) {
            autopilot= !autopilot ;
            if (autopilot) {
                animator.setLabel("Stop automation") ;
                if (PoliSimThread==null) {
                    PoliSimThread= new Thread(this) ;
                    // Don't hog resources.  (Does this really do anything?)
                    PoliSimThread.setPriority(3) ;
                    PoliSimThread.start() ;
                } else {
                    System.err.println("ERROR: thread already exists") ;
                }
            } else {
                animator.setLabel("Run automatically") ;
                if (PoliSimThread!=null) {
                    PoliSimThread.stop() ;
                    PoliSimThread= null ;
                } else {
                    System.err.println("ERROR: thread doesn't exist") ;
                }
            }
            return true ;
        } else if (e.target==buffertoggle) {
            mainfield.isbuffered= !mainfield.isbuffered ;
            if (mainfield.isbuffered) buffertoggle.setLabel("Increase Speed") ;
            else                      buffertoggle.setLabel("Reduce flicker") ;
            return true ;
        } else if (e.target==newcandstart || e.target==numcandentry) {
            int numcands= Integer.parseInt(numcandentry.getText()) ;
            newstart(numcands) ;
            return true ;
        } else if (e.target==upone) {
            newstart(cand.length+1) ;
            return(true) ;
        } else if (e.target==downone) {
            newstart(cand.length-1) ;
            return(true) ;
        } else if (e.target== resetround) {
            setround(0,false) ;
        }
        return false ;
    }


    // create a new field with given number of candidates
    private void newstart(int numcands) {
        cand= newcandlist(numcands) ;
        numcandentry.setText(Integer.toString(cand.length)) ;
        isuptodate= false ;
        setround(0,false) ;
        repaint() ;
    }



    // Thread-related routines
    public void start() {
        System.err.println("in PoliSim.start()") ;
        if (autopilot && PoliSimThread==null) {
            PoliSimThread= new Thread(this) ;
            // Don't hog resources.  (Does this really do anything?)
            PoliSimThread.setPriority(3) ;
            PoliSimThread.start() ;
        }
    }

    public void stop() {
        System.err.println("in PoliSim.stop()") ;
        if (PoliSimThread!=null) {
            PoliSimThread.stop() ;
            PoliSimThread= null ;
        }
    }

    public void run() {
        while (true) {
            movecands(cand) ;
            setround(round+1, hasbeenmoved) ;
            repaint() ;
            PoliSimThread.yield() ;
        }
    }


    // override for more flexibility
    public void update(Graphics g) {
        Graphics g2 ;

        // update each component
        mainfield.update(g2= mainfield.getGraphics()) ;
        g2.dispose() ;
        bargraph.update(g2= bargraph.getGraphics()) ;
        g2.dispose() ;
    }


    // set round, hasbeenmoved, and related processing
    public void setround(int round, boolean hasbeenmoved) {
        this.round= round ;
        this.hasbeenmoved= hasbeenmoved ;
        rounddisplay.setText("Round "+round+(hasbeenmoved?"*":"")) ;
    }


    // print candidate's information to stdout
    public void printcands(Candidate cand[]) {
        for (int i=0; i<cand.length; i++) {
            System.out.println(i+": "+cand[i]) ;
        }
    }


    // getParameter(), allowing default
    private String getParameter(String name, String def) {
        String value= getParameter(name) ;
        return (value!=null) ? value : def ;
    }

    // getParameter(), converting to integer, allowing default
    private int getIntParameter(String name, int def) {
        String value= getParameter(name) ;
        return (value!=null) ? Integer.parseInt(value) : def ;
    }


    public String[][] getParameterInfo() {
        String[][] info= {
            {"fieldsize", "integer", "size in pixels of the main field"},
            {"numcands", "integer", "number of initial candidates"},
            {"numtests", "integer", "number of new positions to check each round"}
        } ;
        return info ;
    }

    public String getAppletInfo() {
        return "PoliSim, (c) October 1996 James Marshall (james@jmarshall.com)" ;
    }


}



class Candidate {
    Point2D pos ;
    Color color ;
    double area ;

    public Candidate(double x, double y, Color color) {
        pos= new Point2D(x,y) ;
        this.color= color ;
    }

    public String toString() {
        return pos.toString()+" area="+area ;
    }
}



// canvas to represent political field
class FieldCanvas extends BufferedCanvas {
    PoliPoint lastmouse ;
    Candidate curcand ;
    Image doubleBuffer ;
    int fieldmax ;
    BorderLine framers[]= new BorderLine[4] ;

    public FieldCanvas(int w, int h, boolean isbuffered) {
        super(w,h,isbuffered) ;
        fieldmax= w-1 ;
        framers[0]= new BorderLine(0,0,0,fieldmax,null,null) ;
        framers[1]= new BorderLine(0,0,fieldmax,0,null,null) ;
        framers[2]= new BorderLine(fieldmax,0,fieldmax,fieldmax,null,null) ;
        framers[3]= new BorderLine(0,fieldmax,fieldmax,fieldmax,null,null) ;
    }


    // clear() is such that clear()+paint() guarantees correct update
    public void clear(Graphics g) {
        g.setColor(getBackground()) ;
        // for some weird reason, it works differently on back buffer
        //   than front screen.
        int margin= isbuffered ? 2:3 ;
        g.fillRect(1, 1, size().width-margin, size().height-margin) ;
    }

    public void paint(Graphics g) {
        ((PoliSim)getParent()).calculate() ;
        Candidate cand[]= ((PoliSim)getParent()).cand ;
        BorderSeg bordersegs[][]= ((PoliSim)getParent()).bordersegs ;
        // draw candidates
        for (int i=0; i<cand.length; i++) {
            g.setColor(cand[i].color) ;
            g.fillOval((int)(cand[i].pos.x)-3, (int)(cand[i].pos.y)-3, 6, 6) ;
        }
        // draw segments
        for (int i=0; i<bordersegs.length; i++) {
            for (int j=0; j<bordersegs[i].length; j++) {
                if (bordersegs[i][j].isgood) {
                    bordersegs[i][j].draw(g) ;
                }
            }
        }
    }


    // Mouse routines
    public boolean mouseDown(Event e, int x, int y) {
        lastmouse= new PoliPoint(x,y) ;
        curcand= lastmouse.closest(((PoliSim)getParent()).cand) ;
        return true ;
    }

    public boolean mouseDrag(Event e, int x, int y) {
        PoliSim app= (PoliSim)getParent() ;
        curcand.pos.x+= x-lastmouse.x ;
        curcand.pos.y+= y-lastmouse.y ;
        // the Math.random() is a cheap way to avoid overlapping points
        curcand.pos.constrain(Math.random(), Math.random(),
                              fieldmax-Math.random(),
                              fieldmax-Math.random() ) ;
        app.isuptodate= false ;
        lastmouse.x= x ;
        lastmouse.y= y ;
        app.setround(app.round, true) ;
        app.repaint() ;
        return true ;
    }

}


// canvas to draw bar graph
class BarGraphCanvas extends BufferedCanvas {
    int barspace= 4 ;
    int graphheight ;

    public BarGraphCanvas(int w, int h, boolean isbuffered) {
        super(w,h,isbuffered) ;
        graphheight= h-60 ;     // bottom margin for text
    }


    // draw bar graph of candidates' percentages
    public void paint(Graphics g) {
        Component c= getParent() ;
        while (!(c instanceof PoliSim)) c= c.getParent() ;
        PoliSim app= (PoliSim)c ;
        app.calculate() ;
        FontMetrics metrics= g.getFontMetrics() ;
        // draw edges
        g.setColor(Color.white) ;
        g.drawRect(0, 0, size().width-1, graphheight) ;
        g.setColor(new Color(16,96,16)) ;
        String caption= "Percentage of Total Votes" ;
        int strx= ( size().width - metrics.stringWidth(caption) ) / 2 ;
        g.drawString(caption, strx, graphheight+40) ;
        // draw bars and text
        // jsm-- bug here: barwidth should be real, not int (try 20 candidates)
        int barwidth= (size().width-barspace)/(app.cand.length)-barspace ;
        double totalarea= 0 ;
        for (int i=0; i<app.cand.length; i++) totalarea+= app.cand[i].area ;
        for (int i=0; i<app.cand.length; i++) {
            double fraction= app.cand[i].area/totalarea ;
            g.setColor(app.cand[i].color) ;
            g.fill3DRect(barspace+i*(barwidth+barspace),
                         (int)Math.round(graphheight*(1-fraction)),
                         barwidth,
                         (int)Math.round(graphheight*fraction),
                         true) ;
            String percval= Double.toString(Math.round(fraction*1000)/10.0) ;
            strx= (barwidth - metrics.stringWidth(percval)) / 2 ;
            g.drawString(percval, barspace+i*(barwidth+barspace)+strx,
                         graphheight+20) ;
            // clear out tops of old bars
//            g.setColor(getBackground()) ;
//            g.fillRect(barspace+i*(barwidth+barspace), 0,
//                       barwidth, (int)Math.round(graphheight*(1-fraction)) ) ;
        }
    }

}



// a Canvas that implements double-buffering
class BufferedCanvas extends Canvas {
    boolean isbuffered ;
    Image doubleBuffer ;

    // required for any subclassing
    public BufferedCanvas() { super() ; }

    public BufferedCanvas(int w, int h, boolean isbuffered) {
        resize(w,h) ;
        this.isbuffered= isbuffered ;
    }


    public void update(Graphics g) {
        if (isbuffered) {
            // add these two lines at beginning for double-buffering
            if (doubleBuffer==null)
                doubleBuffer= createImage(size().width, size().height) ;
            Graphics g2= doubleBuffer.getGraphics() ;

            clear(g2) ;
            paint(g2) ;

            // add these two lines at end for double-buffering
            g.drawImage(doubleBuffer,0,0,this) ;
            g2.dispose() ;

        } else {
            clear(g) ;
            paint(g) ;
        }
    }


    // clear() is such that clear()+paint() guarantees correct update
    // override this for more efficient clearing
    public void clear(Graphics g) {
        g.setColor(getBackground()) ;
        g.fillRect(0, 0, size().width, size().height) ;
    }

}


/////////////////////////////////////////////////////////////////////////

// Point in the political plane (created mostly for closest())
class PoliPoint extends Point2D {

    public PoliPoint(double x, double y) {
        super(x,y) ;
    }

    public PoliPoint(int x,int y) {
        super(x,y) ;
    }

    // closest candidate to this point
    public Candidate closest(Candidate cand[]) {
        double d= this.distance2(cand[0].pos) ;
        int best= 0 ;
        double newd ;
        for (int i=1; i<cand.length; i++) {
            if ((newd= this.distance2(cand[i].pos))<d) {
                d= newd ;
                best= i ;
            }
        }
        return cand[best] ;
    }

}



// Line that is a potential boundary between areas
class BorderLine extends Line2D {
    Candidate c1, c2 ;    // which candidates define this border line
                          // use null for framing border lines

    public BorderLine(Point2D p1, Point2D p2, Candidate c1, Candidate c2) {
        super(p1,p2) ;
        this.c1= c1 ;
        this.c2= c2 ;
    }

    public BorderLine(Line2D l, Candidate c1, Candidate c2) {
        this.m= l.m ;
        this.b= l.b ;
        this.c1= c1 ;
        this.c2= c2 ;
    }

    public BorderLine(int x1, int y1, int x2, int y2, Candidate c1, Candidate c2) {
        super(x1,y1,x2,y2) ;
        this.c1= c1 ;
        this.c2= c2 ;
    }
}



// Line segment that is a potential boundary between areas
class BorderSeg extends LineSeg2D {
    Candidate c1, c2 ;    // which candidates define this border segment
    Color color ;
    boolean isgood ;

    public BorderSeg(Point2D p1, Point2D p2, Candidate c1, Candidate c2) {
        super(p1,p2) ;
        this.c1= c1 ;
        this.c2= c2 ;
        if (c1!=null)
            color= new Color((c1.color.getRed()  +c2.color.getRed())  /2,
                             (c1.color.getGreen()+c2.color.getGreen())/2,
                             (c1.color.getBlue() +c2.color.getBlue()) /2) ;
        else color= new Color(0,0,0) ;
    }


    // check to see if this segment matters, i.e. if the two closest
    //   candidates are the candidates that define it, or if it's a
    //   frame segment (for which both c1 and c2 are null).
    public void checkisgood(Candidate cand[]) {
        isgood=true ;
        Point2D midpt = p1.midpoint(p2) ;
        if (c1!=null) {
            double d= Math.max(midpt.distance2(c1.pos),
                               midpt.distance2(c2.pos)) ;
            for (int i=0; i<cand.length; i++) {
                if (cand[i]!=c1 && cand[i]!=c2) {
                    if (midpt.distance2(cand[i].pos)<d) {
                        isgood= false ;
                        break ;
                    }
                }
            }
        }
    }


    // closest candidate to this segment; used mostly for framers
    public Candidate closest(Candidate cand[]) {
        Point2D midpt= p1.midpoint(p2) ;
        return (new PoliPoint(midpt.x,midpt.y)).closest(cand) ;
    }


    public void draw(Graphics g) {
        g.setColor(color) ;
        super.draw(g) ;
    }


}


/////////////////////////////////////////////////////////////////////////

// Line segment, in two dimensions
class LineSeg2D {
    Point2D p1, p2 ;

    // required for any subclassing
    public LineSeg2D() { super() ; }

    public LineSeg2D(double x1, double y1, double x2, double y2) {
        p1= new Point2D(x1,y1) ;
        p2= new Point2D(x2,y2) ;
    }

    public LineSeg2D(int x1, int y1, int x2, int y2) {
        this((double)x1, (double)y1, (double)x2, (double)y2) ;
    }

    public LineSeg2D(Point2D p1, Point2D p2) {
        this(p1.x, p1.y, p2.x, p2.y) ;
    }

    // midpoint of line segment
    public Point2D midpoint() {
        return p1.midpoint(p2) ;
    }

    // area of triangle defined by this segment and a point
    public double triarea(Point2D p) {
        double d1= p.distance(p1),
               d2= p.distance(p2),
               d3= p1.distance(p2) ;
        double x= (d1+d2+d3)/2 ;
        double area2= x*(x-d1)*(x-d2)*(x-d3) ;
        // guard against rounding errors that cause failure
        if (area2<0) return 0 ;
        return Math.sqrt(area2) ;
    }

    public void draw(Graphics g) {
        g.drawLine((int)Math.round(p1.x), (int)Math.round(p1.y),
                   (int)Math.round(p2.x), (int)Math.round(p2.y) ) ;
    }

    public String toString() {
        return p1+"-"+p2 ;
    }

}


// Line, in two dimensions.
// Some methods could be condensed to take advantage of infinite arithmetic.
// A more robust representation might be with a,b (x- and y- intercepts).
class Line2D {
    double m ;  // slope; may be Double.POSITIVE_INFINITY for vertical lines
    double b ;  // y-intercept; if m is infinite, is x-intercept instead

    // required for any subclassing
    public Line2D() { super() ; }

    public Line2D(double m, double b) { this.m=m ; this.b=b ; }

    // line connecting two points-- RETURNS NaN if points are the same
    public Line2D(double x1, double y1, double x2, double y2) {
        if (x1==x2 && y1==y2) {
            m= Double.NaN ;
            b= Double.NaN ;
        } else if (x1==x2) {
            m= Double.POSITIVE_INFINITY ;
            b= x1 ;
        } else {
            m= (y1-y2)/(x1-x2) ;
            b= y1-m*x1 ;
        }
    }

    public Line2D(int x1, int y1, int x2, int y2) {
        this((double)x1, (double)y1, (double)x2, (double)y2) ;
    }

    public Line2D(Point2D p1, Point2D p2) {
        this(p1.x, p1.y, p2.x, p2.y) ;
    }

    public Line2D(LineSeg2D seg) {
        this(seg.p1, seg.p2) ;
    }


    // intersection of two lines-- RETURNS NaN if lines don't intersect
    public Point2D intersect(Line2D l) {
        return new Point2D(this,l) ;
    }

    // perpendicular, passing through given point
    public Line2D perpendicular(Point2D p) {
        if (m==Double.POSITIVE_INFINITY) {
            return new Line2D(0,p.y) ;
        } else if (m==0) {
            return new Line2D(Double.POSITIVE_INFINITY,p.x) ;
        } else {
            return new Line2D(-1/m, p.y+p.x/m) ;
        }
    }

/*    public void draw(Graphics g) {
        if (m==Double.POSITIVE_INFINITY) {
            g.drawLine((int)Math.round(b), 0,
                       (int)Math.round(b), PoliSim.fieldmax) ;
        } else {
            g.drawLine(0, (int)Math.round(b),
                       PoliSim.fieldmax, (int)Math.round(m*PoliSim.fieldmax+b)) ;
        }
    }*/


}


// Point, in two dimensions
class Point2D implements Cloneable, Sortable {
    double x,y ;

    // required for any subclassing
    public Point2D() { super() ; }

    public Point2D(double x, double y) { this.x=x ; this.y=y ; }

    public Point2D(int x, int y) { this.x= (double)x ; this.y= (double)y ; }

    // intersection of two lines
    public Point2D(Line2D l1, Line2D l2) {
        if (l1.m==l2.m) {
            x= Double.NaN ;
            y= Double.NaN ;
        } else if (l1.m==Double.POSITIVE_INFINITY) {
            x= l1.b ;
            y= l2.m*x+l2.b ;
        } else if (l2.m==Double.POSITIVE_INFINITY) {
            x= l2.b ;
            y= l1.m*l2.b+l1.b ;
        } else {
            x= (l1.b-l2.b)/(l2.m-l1.m) ;
            y= l1.m*x+l1.b ;
        }
    }


    public boolean equals(Point2D p) {
        return ((Math.abs(x-p.x)<0.001)
             && (Math.abs(y-p.y)<0.001)) ;
    }

    public Object clone() {
        return new Point2D(x,y) ;
    }

    public String toString() {
        return "("+x+","+y+")" ;
    }


    // jsm-- should account for NaN, etc.
    public double cmp(Object pobj) {
        Point2D p2= (Point2D)pobj ;
        // hmm, using within() not perfect either
        if (Util.within(this.x,p2.x,0.001)) return this.y-p2.y ;
        else                                return this.x-p2.x ;
    }


    // true if point is inside rectangle (corners must be in order)
    public boolean inside(int x1, int y1, int x2, int y2) {
        return (Math.round(x)>=x1 && Math.round(x)<=x2
             && Math.round(y)>=y1 && Math.round(y)<=y2) ;
    }

    // make sure point is inside given rectangle
    public void constrain(double x1, double y1, double x2, double y2) {
        if      (x<x1) x= x1 ;
        else if (x>x2) x= x2 ;
        if      (y<y1) y= y1 ;
        else if (y>y2) y= y2 ;
    }

    // distance between two points
    public double distance(Point2D p) {
        double dx= p.x-this.x ;
        double dy= p.y-this.y ;
        return Math.sqrt(dx*dx+dy*dy) ;
    }

    // distance squared (faster, and often sufficient)
    public double distance2(Point2D p) {
        double dx= p.x-this.x ;
        double dy= p.y-this.y ;
        return dx*dx+dy*dy ;
    }

    // midpoint between two points
    public Point2D midpoint(Point2D p) {
        return new Point2D((this.x+p.x)/2, (this.y+p.y)/2) ;
    }

    // line connecting two points
    public Line2D connect(Point2D p) {
        return new Line2D(this,p) ;
    }


//////////////////////////////////////////////////////////////////////
// hard-coded sort routine, until I get the general one working

    // binary sort an array; requires cmp() routine
    public static Point2D[] binsort(Point2D a[]) {
        return binsortpart(a, 0, a.length) ;
    }

    // binary sort part of an array (used by binsort())
    public static Point2D[] binsortpart(Point2D a[], int start, int end) {
        // guard against bad input
        if (start>end) return null ;

        // first, if start=end, return that element
        if (start==end) {
            Point2D result[]= { a[start] } ;
            return result ;
        }

        // otherwise:  sort two halves, and merge them
        int mid= (start+end)/2 ;
        Point2D[] a1= binsortpart(a, start, mid) ;
        Point2D[] a2= binsortpart(a, mid+1, end) ;
        return binmerge(a1,a2) ;
    }

    // merge two sorted lists (used by binsortpart())
    public static Point2D[] binmerge(Point2D a1[], Point2D a2[]) {
        Point2D result[]= new Point2D[a1.length+a2.length] ;
        int sofar= 0 ;
        int i1=0, i2=0 ;
        while (sofar<result.length) {
            if (i1==a1.length)              result[sofar++]= a2[i2++] ;
            else if (i2==a2.length)         result[sofar++]= a1[i1++] ;
            else if (a1[i1].cmp(a2[i2])<0)  result[sofar++]= a1[i1++] ;
            else                            result[sofar++]= a2[i2++] ;
        }
        return result ;
    }

    // binary sort part of an array, removing duplicates (used by binsort())
    public static Point2D[] binsortpartu(Point2D a[], int start, int end) {
        // guard against bad input
        if (start>end) return null ;

        // first, if start=end, return that element
        if (start==end) {
            Point2D result[]= { a[start] } ;
            return result ;
        }

        // otherwise:  sort two halves, and merge them
        int mid= (start+end)/2 ;
        Point2D[] a1= binsortpart(a, start, mid) ;
        Point2D[] a2= binsortpart(a, mid+1, end) ;
        return binmergeu(a1,a2) ;
    }

    // merge two sorted lists, removing duplicates (used by binsortpartu())
    public static Point2D[] binmergeu(Point2D a1[], Point2D a2[]) {
        Point2D result[]= new Point2D[a1.length+a2.length] ;
        Point2D last ;
        int sofar= 0 ;
        int i1=0, i2=0 ;
        while (i1<a1.length || i2<a2.length) {
            if (i1==a1.length)              last= result[sofar++]= a2[i2++] ;
            else if (i2==a2.length)         last= result[sofar++]= a1[i1++] ;
            else if (a1[i1].cmp(a2[i2])<0)  last= result[sofar++]= a1[i1++] ;
            else                            last= result[sofar++]= a2[i2++] ;
            while (i1<a1.length && a1[i1].equals(last)) i1++ ;
            while (i2<a2.length && a2[i2].equals(last)) i2++ ;
        }
        Point2D uresult[]= new Point2D[sofar] ;
        System.arraycopy(result, 0, uresult, 0, sofar) ;
        return uresult ;
    }

//////////////////////////////////////////////////////////////////////

}



// Extra utility routines
class Util {

    public static boolean within(double x, double y, double range) {
        return Math.abs(x-y)<range ;
    }

    // binary sort an array; requires cmp() routine
    public static Sortable[] binsort(Sortable o[]) {
        return binsortpart(o, 0, o.length) ;
    }

    // binary sort part of an array (used by binsort())
    public static Sortable[] binsortpart(Sortable o[], int start, int end) {
        // guard against bad input
        if (start>end) return null ;

        // first, if start=end, return that element
        if (start==end) {
            Sortable result[]= { o[start] } ;
            return result ;
        }

        // otherwise:  sort two halves, and merge them
        int mid= (start+end)/2 ;
        Sortable[] a1= binsortpart(o, start, mid) ;
        Sortable[] a2= binsortpart(o, mid+1, end) ;
        return binmerge(a1,a2) ;
    }

    // merge two sorted lists (used by binsortpart())
    public static Sortable[] binmerge(Sortable a1[], Sortable a2[]) {
        Sortable result[]= new Sortable[a1.length+a2.length] ;
        int sofar= 0 ;
        int i1=0, i2=0 ;
        while (sofar<result.length) {
            if (i1==a1.length)              result[sofar++]= a2[i2++] ;
            else if (i2==a2.length)         result[sofar++]= a1[i1++] ;
            else if (a1[i1].cmp(a2[i2])<0)  result[sofar++]= a1[i1++] ;
            else                            result[sofar++]= a2[i2++] ;
        }
        return result ;
    }

    // merge two sorted lists, removing duplicates (used by binsortpartu())
    public static Sortable[] binmergeu(Sortable a1[], Sortable a2[]) {
        Sortable result[]= new Sortable[a1.length+a2.length] ;
        Object last ;
        int sofar= 0 ;
        int i1=0, i2=0 ;
        while (i1<a1.length || i2<a2.length) {
            if (i1==a1.length)              last= result[sofar++]= a2[i2++] ;
            else if (i2==a2.length)         last= result[sofar++]= a1[i1++] ;
            else if (a1[i1].cmp(a2[i2])<0)  last= result[sofar++]= a1[i1++] ;
            else                            last= result[sofar++]= a2[i2++] ;
            while (i1<a1.length && a1[i1].equals(last)) i1++ ;
            while (i2<a2.length && a2[i2].equals(last)) i2++ ;
        }
        Sortable uresult[]= new Sortable[sofar] ;
        System.arraycopy(result, 0, uresult, 0, sofar) ;
        return uresult ;
    }

}


// denotes a class that can be sorted
interface Sortable {
    public double cmp(Object a) ;   // returns <0, 0, or >0 value
}