// Program to display posets, Peter Jipsen, Version 0.2 6/11/99, 
// Graphics part adapted from JDK demo GraphLayout 

import java.util.*;
import java.awt.*;
import java.applet.Applet;

class Node {
    double x;
    double y;
    double dx;
    double dy;
    String name;
    String label;
    Color color;
    boolean fixed;
}

class Edge {
    int from;
    int to;
    Color color;
    double len;
    byte arrow;
}

class GraphPanel extends Panel implements Runnable {
    Poset graph;

    int nnodes;
    Node nodes[] = new Node[10]; // initial max size; doubles as needed
    int nedges;
    Edge edges[] = new Edge[20]; // initial max size; doubles as needed
    boolean noGrid;
    boolean noVerticalMove;
    boolean fixed;
    boolean showLabels;
    int repel;
    int attract;
    int gridX;
    int gridY;
    int bottom=38;
    double edgeLength;

    Thread relaxer;

    GraphPanel(Poset graph) {
        this.graph = graph;
    }

    int addNode(double x, double y, Color color, String name, String label) {
        Node n = new Node();
        n.x = x;
        n.y = y;
        n.color = color;
        n.name = name;
        n.label = label;
        if (nodes.length==nnodes) {
            Node newnodes[] = new Node[2*nnodes];
            for (int i=0; i<nnodes; i++) newnodes[i]=nodes[i];
            nodes=newnodes;
        }
        nodes[nnodes] = n;
        return nnodes++;
    }

    void updateNode(int i, double x, double y, Color color, String label) {
        Node n = nodes[i];
        n.x = x;
        n.y = y;
        n.color = color;
        n.label = label;
    }

    int findNode(String name) {
	for (int i = nnodes-1 ; i >=0 ; i--) {
	    if (nodes[i].name.equals(name)) {
		return i;
	    }
	}
	return addNode(0,0,Color.black,name,"");
    }

    void addEdge(String fromName, String toName, Color color, 
                 double len, byte arrow) {
        Edge e = new Edge();
        e.from = findNode(fromName);
        e.to = findNode(toName);
        e.color = color;
        e.len = len;
        e.arrow = arrow;
        if (edges.length==nedges) {
            Edge newedges[] = new Edge[2*nedges];
            for (int i=0; i<nedges; i++) newedges[i]=edges[i];
            edges=newedges;
        }
        edges[nedges++] = e;
    }

     public void run() {
        while (true) {
            if (!fixed) relax();
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                break;
            }
        }
    }
    
    synchronized void relax() {
      if (edgeLength!=0)
        for (int i = 0 ; i < nedges ; i++) {//tension along edges
            Edge e = edges[i];
            double vx = nodes[e.to].x - nodes[e.from].x;
            double vy = nodes[e.to].y - nodes[e.from].y;
            double len = Math.sqrt(vx * vx + vy * vy);    //true length
            double dx = 0;
            double dy = 0;
	    if (len == 0) {
	      dx += Math.random();  // don't superimpose nodes
	      dy += Math.random();  // allows nodes to pass eachother
	    } else {
	      double f = (edges[i].len - len) / (len * 3) ;
	      dx = f * vx;  // change in direction of desired length
	      dy = f * vy;
	    }
            nodes[e.to].dx += dx;
            nodes[e.to].dy += dy;
            nodes[e.from].dx += -dx;
            nodes[e.from].dy += -dy;
        }

        for (int i = 0 ; i < nnodes ; i++) {  // repulsion between nodes
            Node n1 = nodes[i];
            double dx = 0;
            double dy = 0;

            for (int j = 0 ; j < nnodes ; j++) {
                if (i == j) {
                    continue;
                }
                Node n2 = nodes[j];
                double vx = n1.x - n2.x;
                double vy = n1.y - n2.y;
                if (vy==0){
                  double len = vx * vx + vy * vy;
                  if (len == 0) {
                    dx += Math.random();  // don't superimpose nodes
                    dy += Math.random();  // allows nodes to pass eachother
                  } else if (len < 100*100) {
                    dx += vx / len;             // increment by scaled x-dist.
                    dy += vy / len;   // elements further away have less impact
                  }                   // because len is the squared distance
                }
            }
            double dlen = dx * dx + dy * dy;
            if (dlen > 0) {
                dlen = Math.sqrt(dlen);
                n1.dx += (dx / dlen)*repel;
                n1.dy += (dy / dlen)*repel;
            }
	    // provide tension towards grid points
            double rx = n1.x-gridX*Math.floor((n1.x-Poset.border)/gridX)-Poset.border;
            rx = ( rx < gridX/2 ? -rx : gridX-rx );
            n1.dx += (rx/gridX)*attract;
        }

        Dimension d = size();
        for (int i = 0 ; i < nnodes ; i++) {
            Node n = nodes[i];
            if (!n.fixed && !fixed) {
	      n.x += Math.max(-5, Math.min(5, n.dx));// change n.x by at most 5
                if (n.x < Poset.border) {
                    n.x = Poset.border;
                } else if (n.x > d.width-Poset.border) {
                    n.x = d.width-Poset.border;
                }
/*                if (n.y < 0) {
                    n.y = 0;
                } else if (n.y > d.height) {
                    n.y = d.height;
                }
*/            }
            n.dx /= 2;
            n.dy /= 2;
        }
        repaint();
    }

    Node pick;
    boolean pickfixed;
    Image offscreen;
    Dimension offscreensize;
    Graphics offgraphics;
    
    final Color selectColor = Color.pink;
    final Color nodeColor = new Color(250, 220, 100);

    public void paintNode(Graphics g, Node n, int i, FontMetrics fm) {
        int x = (int)n.x;
        int y = (int)n.y;
        if (n==pick || showLabels){
            g.setColor((n==pick?selectColor:n.color));
            int w = fm.stringWidth(n.label) + 6;
            int h = fm.getHeight();
            w=2*(w/2); 
            h=2*(h/2);
            g.fillOval(x - w/2, y - h / 2, w, h);
	    //            g.drawOval(x - w/2, y - h / 2, w, h);
	    if (n.fixed) {
              g.setColor(Color.red);
	      g.drawOval(x - w/2-1, y - h/2-1, w+2, h+2);
	    }
            g.setColor(Color.black);
            g.drawString(n.label, x - (w-6)/2, (y - (h-5)/2-2) + fm.getAscent());
        }else{
            g.setColor(n.color);
            int w = fm.stringWidth(n.name) + 6;
            int h = fm.getHeight();
            w=2*(w/2); h=2*(h/2);
            g.fillOval(x - w/2, y - h / 2, w, h);
            g.setColor((n.fixed?Color.red:Color.black));
            g.drawOval(x - w/2, y - h / 2, w, h);
	    if (n.fixed) {
	      g.drawOval(x - w/2-1, y - h/2-1, w+2, h+2);
	    }
            g.setColor(Color.black);
            g.drawString(n.name, x - (w-6)/2, 
                                           (y - (h-5)/2-2) + fm.getAscent());
        }
    }

    public void drawArrow(Graphics g, int x1, int y1, int x2, int y2) {
      int c = 10; //distance from arrow head to node center
      int a = 10; //length of arrow head
      double dd = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
      int ax = (int)(x2 - (c/dd)*(x2-x1));
      int ay = (int)(y2 - (c/dd)*(y2-y1));
      double bx = x2 - ((c+a)/dd)*(x2-x1);
      double by = y2 - ((c+a)/dd)*(y2-y1);
      double ox = a/(1.73*dd)*(y2-y1);
      double oy = a/(1.73*dd)*(x2-x1);
      g.drawLine((int)(bx-ox),(int)(by+oy),ax,ay);
      g.drawLine((int)(bx+ox),(int)(by-oy),ax,ay);
    }

    public synchronized void update(Graphics g) {
        Dimension d = size();
        if ((offscreen == null) || (d.width != offscreensize.width) 
                                || (d.height != offscreensize.height)) {
            offscreen = createImage(d.width, d.height);
            offscreensize = d;
            offgraphics = offscreen.getGraphics();
            offgraphics.setFont(getFont());
        }

        offgraphics.setColor(getBackground());
        offgraphics.fillRect(0, 0, d.width, d.height);
        for (int i = 0 ; i < nedges ; i++) {
            Edge e = edges[i];
            int x1 = (int)nodes[e.from].x;
            int y1 = (int)nodes[e.from].y;
            int x2 = (int)nodes[e.to].x;
            int y2 = (int)nodes[e.to].y;
            offgraphics.setColor(e.color);
            offgraphics.drawLine(x1, y1, x2, y2);
            if (e.arrow==1 || e.arrow==3)
	      drawArrow(offgraphics, x1, y1, x2, y2);
            if (e.arrow==2 || e.arrow==3)
	      drawArrow(offgraphics, x2, y2, x1, y1);
        }

        FontMetrics fm = offgraphics.getFontMetrics();
        for (int i = 0 ; i < nnodes ; i++) {
            paintNode(offgraphics, nodes[i], i+1, fm);
        }
        offgraphics.setColor(Color.black);
        if (!noGrid) 
          for (int px=Poset.border; px<=d.width-Poset.border; px+=gridX)
            for (int py=Poset.border; py<=d.height-Poset.border+2; py+=gridY)
                offgraphics.drawLine(px,py,px,py);

        g.drawImage(offscreen, 0, 0, null);
    }

  public synchronized void paint(Graphics g) {// seemingly needed for printing
        update(g);
    }

    public synchronized boolean mouseDown(Event evt, int x, int y) {
        double bestdist = Double.MAX_VALUE;
        for (int i = 0 ; i < nnodes ; i++) {
            Node n = nodes[i];
            double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
            if (dist < bestdist) {
                pick = n;
                bestdist = dist;
            }
        }
        pickfixed = pick.fixed;
        pick.fixed = true;
        pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;
	if (pick.x < Poset.border) pick.x = Poset.border;
        else if (pick.x > size().width-Poset.border) 
	  pick.x = size().width-Poset.border;
        if (!noVerticalMove) {
            pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;
	    if (pick.y < Poset.border) pick.y = Poset.border;
            else if (pick.y > size().height-Poset.border) 
	      pick.y = size().height-Poset.border;
        }
        repaint();
        return true;
    }

    public synchronized boolean mouseDrag(Event evt, int x, int y) {
        pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;
	if (pick.x < Poset.border) pick.x = Poset.border;
        else if (pick.x > size().width-Poset.border) 
	  pick.x = size().width-Poset.border;
        if (!noVerticalMove) {
            pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;
	    if (pick.y < Poset.border) pick.y = Poset.border;
            else if (pick.y > size().height-Poset.border) 
	      pick.y = size().height-Poset.border;
        }
        pickfixed = false;
        repaint();
        return true;
    }

    public synchronized boolean mouseUp(Event evt, int x, int y) {
        pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;
	if (pick.x < Poset.border) pick.x = Poset.border;
        else if (pick.x > size().width-Poset.border) 
	  pick.x = size().width-Poset.border;
        if (!noVerticalMove) {
            pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;
	    if (pick.y < Poset.border) pick.y = Poset.border;
            else if (pick.y > size().height-Poset.border) 
	      pick.y = size().height-Poset.border;
        }
        pick.fixed = !pickfixed;
        pick = null;
        repaint();
        return true;
    }

    public void start() {
        relaxer = new Thread(this);
        relaxer.start();
    }
    public void stop() {
        relaxer.stop();
    }

}

public class Poset extends Applet {
    GraphPanel panel;
    TextField edgeLen;
    TextField repel;
    TextField attract;    
    TextField gX;
    Button start;
    static int border=20;

    static int str2int(String s) {
        return Integer.valueOf(s.trim()).intValue();
    }

    static String str2name(String s) {
        int i = s.indexOf('"');
        if (i>=0) {
          int j = s.substring(i+1).indexOf('"');
          if (j>=0) 
	    return s.substring(i+1).substring(0,j);
	  System.out.println("Warning: \",\" in nameString or missing \" ");
	  return s.substring(i+1);
        }
        return s.trim();
    }

    static Color str2color(String s) {
        Color col;
        if (s.equals("black")) col = Color.black;
        else if (s.equals("blue")) col = Color.blue;
        else if (s.equals("cyan")) col = Color.cyan;
        else if (s.equals("darkGray")) col = Color.darkGray;
        else if (s.equals("gray")) col = Color.gray;
        else if (s.equals("green")) col = Color.green;
        else if (s.equals("lightGray")) col = Color.lightGray;
        else if (s.equals("magenta")) col = Color.magenta;
        else if (s.equals("orange")) col = Color.orange;
        else if (s.equals("pink")) col = Color.pink;
        else if (s.equals("red")) col = Color.red;
        else if (s.equals("white")) col = Color.white;
        else if (s.equals("yellow")) col = Color.yellow;
        else col = Color.decode(s);
        return col;
    }

    public void init() {
        setLayout(new BorderLayout());
        panel = new GraphPanel(this);
        setBackground(Color.white);
        add("Center", panel);

        Dimension d = size();
        int maxX = str2int(getParameter("maxX"));
        int maxY = str2int(getParameter("maxY"));
        panel.gridX = (int)Math.floor((d.width-2*border)/maxX);
        panel.gridY = (int)Math.floor((d.height-2*border-panel.bottom)/maxY);
        edgeLen = new TextField(String.valueOf(panel.gridY-5),3);
        panel.edgeLength = (double)str2int(edgeLen.getText());

        String param = getParameter("noGrid");
        if (param!=null) panel.noGrid=param.equals("true");
        else panel.noGrid=true;

        param = getParameter("noVerticalMove");
        if (param!=null) panel.noVerticalMove=param.equals("true");
        else panel.noVerticalMove=true;

        param = getParameter("showLabels");
        if (param!=null) panel.showLabels=param.equals("true");
        else panel.showLabels=false;

      param = getParameter("showControls");
      if (param == null || param.equals("true")) {

        Panel p = new Panel();
        add("South", p);
        param = getParameter("fix");
        if (param!=null) panel.fixed=param.equals("true");
        else panel.fixed=true;
        if (panel.fixed) start = new Button("Start");
        else start = new Button("Stop");
        p.add(start);

        p.add(new Label("Repel:"));
        param = getParameter("repel");
        if (param==null) param="0";
        repel = new TextField(param,3);
        p.add(repel);
        panel.repel = str2int(repel.getText());

        p.add(new Label("Attract:"));
        param = getParameter("attract");
        if (param==null) param="0";
        attract = new TextField(param,3);
        p.add(attract);
        panel.attract = str2int(attract.getText());

        p.add(new Label("Grid X:"));
        gX = new TextField(String.valueOf(panel.gridX),3);
        p.add(gX);

        p.add(new Label("Edge L:"));
        p.add(edgeLen);
        p.add(new Button("Adjust"));
        p.add(new Button("Output"));
        p.add(new Checkbox("Labels"));
      } else {
            panel.bottom = 0;
            panel.fixed = true;
            panel.gridY = (int)Math.floor((d.height-2*border-panel.bottom)/maxY);
      }
        Color color;
        String poset = getParameter("poset");
        for (StringTokenizer t = new StringTokenizer(poset, ",") ; 
                                                   t.hasMoreTokens() ; ) {
            String str = t.nextToken();
            int i = str.indexOf('[');
            if (i >= 0) str=str.substring(i+1);
            i = str.indexOf('[');
            if (i >= 0) str=str.substring(i+1);
            String nname = str2name(str);
            int nx = str2int(t.nextToken());
            int ny = str2int(t.nextToken());
            str = t.nextToken();
            i = str.indexOf('"');
            String nl="";
            boolean ok=true;
	    color = Color.yellow;
            if (i >= 0) {                    //read the label
                str = str.substring(i+1);
                i = str.indexOf('"');
                if (i >= 0) nl = str.substring(0,i);
                else {
                    nl = str;
		    for (; t.hasMoreTokens() && ok ; ) {
                        str = t.nextToken();
                        i = str.indexOf('"');
                        if (i >= 0) {
                            ok = false;
                            nl = nl.concat(str.substring(0,i));
                        } else nl = nl.concat(str);
                    }
                }
                i = nl.indexOf('#');       //look for color
                if (i >= 0) {
                    color = str2color(nl.substring(i+1));
                    nl = nl.substring(0,i);
                }
            } else nl = str.trim();
            panel.updateNode(panel.findNode(nname), 
                nx*panel.gridX+border,(maxY-ny)*panel.gridY+border,color,nl);

            ok=true;
            color = Color.black;
	    byte arrow = 0;
            for (; t.hasMoreTokens() && ok ; ) {
                str = t.nextToken();
                i = str.indexOf(']');
                if (i >= 0) {
                    ok = false;
                    str = str.substring(0, i);
                }
                i = str.indexOf('[');
                if (i >= 0) str=str.substring(i+1);
                if (!str.trim().equals("")) {
                    i = str.indexOf('#');
                    if (i >= 0) {
                        str = str.substring(i+1);
                        i = str.indexOf('"');
                        if (i >= 0) str = str.substring(0,i);
                        i = str.indexOf('>');
                        if (i >= 0) {
                            arrow = 1;
                            str = str.substring(0,i);
                        }
                        i = str.indexOf('<');
                        if (i >= 0) {
                            arrow = (byte)(arrow + 2);
                            str = str.substring(0,i);
                        }
                        color = str2color(str);
                    } else {
                        String mname = str2name(str);
                        panel.addEdge(nname, mname, color, 
				      panel.edgeLength, arrow);
                        color = Color.black;
			arrow = 0;
                    }
                }
            }
        }
        int c = 0;
        String newEmbedding = getParameter("newEmbedding");
        if (newEmbedding!=null)
        for (StringTokenizer t = new StringTokenizer(newEmbedding, ",") ; 
                                                   t.hasMoreTokens() ; ) {
            String str = t.nextToken();
            int i = str.indexOf('[');
	    if (i >= 0) {                
                str=str.substring(i+1);
                i = str.indexOf('[');
                if (i >= 0) str=str.substring(i+1);
                c = panel.findNode(str2name(str));
                str = t.nextToken();
                panel.nodes[c].x=str2int(str)*panel.gridX+border;
                str = t.nextToken();
                i = str.indexOf(']');
                if (i>=0) str=str.substring(0,i);
                panel.nodes[c].y=(maxY-str2int(str))*panel.gridY+border;
	    }
	}
        panel.repaint();
    }

    public void start() {
        panel.start();
    }
    public void stop() {
        panel.stop();
    }

    public boolean action(Event evt, Object arg) {
        if (arg instanceof Boolean) {
            if (((Checkbox)evt.target).getLabel().equals("Labels")) {
                panel.showLabels = ((Boolean)arg).booleanValue();
                panel.repaint();
            }
            return true;
        } 
        if ("Start".equals(arg)) {
            panel.fixed=false;
            start.setLabel("Stop");
            return true;
        }
        if ("Stop".equals(arg)) {
            panel.fixed=true;
            start.setLabel("Start");
            return true;
        }
        if ("Adjust".equals(arg)) {
            for (int i = 0 ; i < panel.nedges ; i++) {
                Edge e = panel.edges[i];
                double vx = panel.nodes[e.from].x-panel.nodes[e.to].x;
                double vy = panel.nodes[e.from].y-panel.nodes[e.to].y;
                e.len = Math.sqrt(vx*vx + vy*vy);
            }
	    panel.repaint();
            return true;
        }
        if ("Output".equals(arg)) {
            System.out.print("<param name=newEmbedding value='[");
            for (int i = 0 ; i < panel.nnodes ; i++) {
                System.out.print("[\""+panel.nodes[i].name+"\","+
                     (int)Math.floor((panel.nodes[i].x-border)/panel.gridX+0.5)+","+
                     (int)Math.floor((size().height-border-panel.bottom-
                                            panel.nodes[i].y)/panel.gridY)+"]");
                if (i==panel.nnodes-1) System.out.println("];'>");
                else System.out.print(",");
            }
            return true;
        }
        if (evt.target == repel){
            panel.repel = str2int(repel.getText());
            return true;
        }
        if (evt.target == attract){
            panel.attract = str2int(attract.getText());
            return true;
        }
        if (evt.target == gX){
            int tgX = str2int(gX.getText());
            if (tgX == 0) panel.noGrid=true;
            else {
              panel.noGrid=false; 
              panel.gridX=tgX;
            }
	    panel.repaint();
            return true;
        }
        if (evt.target == edgeLen){
            panel.edgeLength = (double)str2int(edgeLen.getText());
            for(int i=0; i<panel.nedges; i++) {
                Edge f = panel.edges[i];
                f.len = panel.edgeLength*
                    Math.abs(panel.nodes[f.from].y-panel.nodes[f.to].y)/panel.gridY;
            }
            return true;
        }
        return false;
    }
}