import java.io.*;
import java.awt.*;
import java.applet.*;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.Enumeration;

/** This program implement's the "Left Edge Algorithm" for channel
    routing.  It includes vertical constraints but cannot deal with cyclic
    vertical constraints.

*/

public class ChannelRouterApplet extends Applet {

  private TextField[] upperFields, lowerFields;    
  private Netlist n;
  ChannelRouterCanvas cv;
  
  public void init() {
    System.out.println("starting applet!!!");
    n = new Netlist();
    setLayout(new BorderLayout());
    Panel up = new Panel();
    Panel lp = new Panel();
    Panel gp = new Panel();
    Panel bp = new Panel();
    cv = new ChannelRouterCanvas(n);
    setLayout(new BorderLayout());
    up.setLayout(new GridLayout(1, Netlist.NUM_COLS));
    lp.setLayout(new GridLayout(1,Netlist.NUM_COLS));
    gp.setLayout(new BorderLayout());
    bp.setLayout(new FlowLayout());
    Button cb = new Button("Clear Nets");
    Button rb = new Button("Route Nets");

    upperFields = new TextField[Netlist.NUM_COLS];
    lowerFields = new TextField[Netlist.NUM_COLS];
    for (int i = 0; i < Netlist.NUM_COLS; i++) {
      TextField tf;
      upperFields[i] = tf = new TextField("", 2);
      up.add(tf);
      lowerFields[i] = tf = new TextField("", 2);
      lp.add("Center", tf);
    }
    gp.add("North", up);
    gp.add("South", lp);
    gp.add("Center", cv);
    bp.add(cb);
    bp.add(rb);
    add("South", bp);
    add("Center", gp);

  }
  
  /** Clear all net fields */
  private void clearNetFields() {
    for (int i = 0; i < Netlist.NUM_COLS; i++) {
      upperFields[i].setText("");
      lowerFields[i].setText("");
    }
  }
  
  /** Scan the terminal fields for each column and build up the netlist data structure */
  private void scanFieldsAndRoute() {
    n.clear();
    for (int i = 0; i < Netlist.NUM_COLS; i++) {
      String uname = upperFields[i].getText().trim();
      String lname = lowerFields[i].getText().trim();
      Terminal term;
      Net nt;
      // process upper terminal of column i
      if (!uname.equals("")) {
        nt = n.findNet(uname);
        if (nt == null) {
          nt = new Net(uname);
          n.addNet(nt);
          }
        term = n.getTerminal(i, Terminal.TOP);
        nt.addTerminal(term);
      }
      // now process lower terminal of column i
      if (!lname.equals("")) {
        nt = n.findNet(lname);
        if (nt == null) {
          nt = new Net(lname);
          n.addNet(nt);
        }
        term = n.getTerminal(i, Terminal.BOTTOM);
        nt.addTerminal(term);
      }
    }
    // n.write(System.out);
    n.leftEdgeAlgorithm();
    // n.write(System.out);
  }
  
  public boolean handleEvent(Event evt) {
    if (evt.id == Event.WINDOW_DESTROY) System.exit(0);
    return super.handleEvent(evt);
  }
  
  public boolean action(Event evt, Object arg) {
    if (arg.equals("Route Nets")) {
      scanFieldsAndRoute();
      cv.repaint();
    } else if (arg.equals("Clear Nets")) {
      clearNetFields();
      scanFieldsAndRoute();  // to clear the old nets away
      cv.repaint();
    } else return super.action(evt, arg);
    return true;
  }
  
}

class ChannelRouterCanvas extends Canvas {

  private Netlist nl;
  
  public ChannelRouterCanvas(Netlist n) { nl = n; }

  private static final int BORDER_Y_OFFSET = 10;
  private static final int HEIGHT_ADJUST = 10;
  private static final int WIDTH_ADJUST = 1;
  
  private int colWidth;
  private int trackHeight;
  
  private void setScale() {
    Dimension d = size();
    colWidth = (d.width) / Netlist.NUM_COLS;
    trackHeight = (d.height - HEIGHT_ADJUST - BORDER_Y_OFFSET) / (nl.getMaxTrack() + 1);
  }

  /** @return the Y coordinate for track number. */
  public int trackY(int track) {
    return BORDER_Y_OFFSET + trackHeight * track;
  }
  /** X coordinate of column */
  public int colX(int col) {
    return colWidth/2 + colWidth * col;
  }
  
  public int channelWidth() {
    return (colWidth * Netlist.NUM_COLS - 1);
  }
  
  public int channelHeight() {
    return (trackY(nl.getMaxTrack() +1) - trackY(0) + 1);
  }
  

  private Font f;
  private FontMetrics fm;
  private boolean fontsSet = false;
  
  private void setFonts(Graphics g) {
    if (fontsSet) return;
    f = new Font("Helvetica", Font.PLAIN, 12);
    fm = g.getFontMetrics(f);
    g.setFont(f);
    fontsSet = true;
  }

  public void paint(Graphics g) {
    setFonts(g);
    setScale();  
    g.drawRect(0, BORDER_Y_OFFSET, channelWidth(), channelHeight());  
    if (nl.getCyclesPresent()) {
      g.drawString("This circuit contains unresolved vertical constraint cycles", 
        20, trackY(1) - 5);
    }
    for (Enumeration e = nl.getNets() ; e.hasMoreElements() ;) { 
      Net n = (Net)e.nextElement(); 
      if (n.getTrack() != Net.TRACK_UNASSIGNED) {
        g.setColor(Color.blue);
        g.fillRect(colX(n.getLeftEdge()), trackY(n.getTrack())-2,
          colX(n.getRightEdge()) - colX(n.getLeftEdge())+2, 5);
        // int xnoff = fm.stringWidth(n.getName()) / 2;
        for (Enumeration eterms = n.getTerminals(); eterms.hasMoreElements() ; ) {
          Terminal t = (Terminal)eterms.nextElement();
          g.setColor(Color.red);
          if (t.getTopOrBottom()) {
            g.fillRect(colX(t.getColumn())-2, trackY(0),
              5, trackY(n.getTrack()) - trackY(0) + 3);               
            //g.drawString(n.getName(), colX(t.getColumn()) - xnoff, trackY(0) - 2);
          } else {
            g.fillRect(colX(t.getColumn()) - 2, trackY(n.getTrack())-2,
              5, trackY(nl.getMaxTrack()+1) - trackY(n.getTrack())+4);
            //g.drawString(n.getName(), colX(t.getColumn()) - xnoff, trackY(nl.getMaxTrack()+1) + fm.getAscent());
          }
          g.setColor(Color.black);
          g.fillRect(colX(t.getColumn())-3, trackY(n.getTrack())-3, 7, 7);
        }
      }
    }
  }

}
  
class Netlist
{
  private Terminal[] upperTerms;
  private Terminal[] lowerTerms;
  private Vector nlist;
  private int maxTrack = Net.TRACK_UNASSIGNED;
  private boolean cyclesPresent = false;
    
  public static final int NUM_COLS = 10;
  
  public Netlist() {
    nlist = new Vector();
    upperTerms = new Terminal[NUM_COLS];
    lowerTerms = new Terminal[NUM_COLS];
    for (int i = 0; i < NUM_COLS; i++) {
      upperTerms[i] = new Terminal(i, Terminal.TOP);
      lowerTerms[i] = new Terminal(i, Terminal.BOTTOM);
    }
  }  
  
  public boolean getCyclesPresent() { return cyclesPresent; }
  
  /** return terminal object for the given position */
  public Terminal getTerminal(int pos, boolean topOrBottom) {
    if (topOrBottom == Terminal.TOP) return upperTerms[pos];
    else return lowerTerms[pos];
  }

  /** insert net into netList sorted by left edge */  
  public void addNet(Net n) {
    int i;
    for (i = 0; i < nlist.size(); i++) {
      if (((Net)nlist.elementAt(i)).getLeftEdge() > n.getLeftEdge()) {
        nlist.insertElementAt(n, i);
        return;
      }
    }
    nlist.addElement(n);
  }
  
  void unmarkNets() {
    for (Enumeration e = getNets() ; e.hasMoreElements() ; )  
      ((Net)e.nextElement()).setMark(false);
  }
  
  /** make vertical constraints and check for cycles - if they occur, just remove one constraint
       even though it's wrong. */ 
  public void makeConstraints() {
    for (int i = 0; i < NUM_COLS; i++) {
      Net unet = upperTerms[i].getNet();
      Net lnet = lowerTerms[i].getNet();
      if (unet != null && lnet != null && unet != lnet) {
        //System.out.println("Adding constraint " + unet.getName() 
        //  + " above " + lnet.getName());
        lnet.addConstraint(unet);
     }
   }
   // Search for cycles in constraints - just delete a constraint when one is found (for now)
   cyclesPresent = false;
   for (int i = 0; i < NUM_COLS; i++) {
     unmarkNets();
     Net lnet = lowerTerms[i].getNet();
     if (lnet != null && !lnet.checkConstraint()) cyclesPresent = true;
    }
  }

        
  
  public void clear() { 
    nlist.removeAllElements();
    for (int i = 0; i < NUM_COLS; i++) {
      upperTerms[i].setNet(null);
      lowerTerms[i].setNet(null);
    }
  }
  
  public Enumeration getNets() { return nlist.elements(); }

  public Net findNet(String findName) {
    for (int i = 0; i < nlist.size(); i++) {
      Net nt = (Net)nlist.elementAt(i);
      if (nt.getName().equals(findName)) return nt;
    }
    return null;
  }
  
  public void write(PrintStream os) {
    os.println("Writing netlist");
    for (Enumeration e = nlist.elements() ; e.hasMoreElements() ;) {  
      ((Net)e.nextElement()).writeNet(os);
   } 
  }
  
  /** determine whether we can assign net testNet to track trk by scanning nets */
  private boolean canRoute(Net testNet, int trk) {
    for (Enumeration ne = nlist.elements(); ne.hasMoreElements() ; ) {
      Net n = (Net)ne.nextElement();
      if (n.getTrack() == trk && testNet.overlap(n)) return false;
    }
    return true;
  }

  /** assign nets to tracks in channel using the Left Edge Algorithm */  
  public void leftEdgeAlgorithm() {
    makeConstraints();
    int track = 0;
    boolean done = false;
    while (!done) {
      track++;
      done = true;
      // place unrouted nets in current track if they fit
      for (Enumeration e = nlist.elements(); e.hasMoreElements() ; ) {
        Net n = (Net)e.nextElement();
        if (n.isRouted()) continue;  // skip nets already done
        if (n.testConstraints() && canRoute(n, track)) {
          //System.out.println("Assigning net " + n.getName() + 
          //    "(" + n.getLeftEdge() + ":" + n.getRightEdge() + 
          //    ") to track" + track);
          n.setTrack(track);
        }
        else done = false;  // at least one net (this one) remains unrouted!         
      }
    }
    maxTrack = track;
  }

  public int getMaxTrack() { return maxTrack; }

}

class Net {

  /** Symbolic constant for unrouted net */
  public static final int TRACK_UNASSIGNED = 0;

  private String name;
  private Vector terms = new Vector(5);
  private Vector constraints = new Vector(2);  // contains vertical constraints (if any)  
  private int leftEdge = Integer.MAX_VALUE;
  private int rightEdge = 0;
  private int track = TRACK_UNASSIGNED;
  private boolean mark = false;
  
  /** Create a new net from a string containing the net name
     */
  public Net(String n) { ;
      name = n;
  }
  
  /** @return true if net assigned to a track */
  public boolean isRouted() {
    return (getTrack() != Net.TRACK_UNASSIGNED);
  }
  
  /** Get the assigned track of this net
     * @return 	the assigned track of this net
     */
  public int getTrack() { return track; }

  /** Assign this net to a track
      * @param t	The track this net will be assigned to.
      */
  public void setTrack(int t) { track = t; }
  
  /** get the left edge of this net
     * @return the leftmost column of this net
     */
  public int getLeftEdge() { return leftEdge; }
  
 /** get the right edge of this net
     * @return the rightmost column of this net
     */
  public int getRightEdge() { return rightEdge; }
  
  public boolean overlap(Net n2) {
    int l1 = getLeftEdge();
    int r1 = getRightEdge();
    int l2 = n2.getLeftEdge();
    int r2 = n2.getRightEdge();
    return (l2 <= r1 && r2 >= l1) || (l1 <= r2 && r1 >= l2);
  }
  
  /** write out the net */
  public void writeNet(PrintStream os) {
    os.print(name + " ");
    if (getTrack() != TRACK_UNASSIGNED) os.print(track + " ");
    for (Enumeration e = terms.elements(); e.hasMoreElements() ; )
      ((Terminal)e.nextElement()).writeTerminal(os);
    os.println();
  }
  
  /** @return the name of this net
     */
  public String getName() { return name; }
  
  /** Add a terminal to this net
      * @param trm	The terminal to be added to this net.
      */
  public void addTerminal(Terminal trm){
    terms.addElement(trm);
    trm.setNet(this);
    if (trm.getColumn() < leftEdge) leftEdge = trm.getColumn();
    if (trm.getColumn() > rightEdge) rightEdge = trm.getColumn();
  }
  
  /** @return an enumeration containing the terminals of this net */
  public Enumeration getTerminals() {
    return terms.elements();
  }
  
  public void addConstraint(Net nt) {
    if (!constraints.contains(nt))
      constraints.addElement(nt);
  }
    
  public boolean checkConstraint() {
    if (constraints == null) return true;
    boolean result = true;
    setMark(true);
    for ( int i = 0; i < constraints.size(); i++ ) {
      Net ctgt = (Net)constraints.elementAt(i);
      if (ctgt.getMark()) {
        //System.out.println("Constraint cycle found from Net " + getName() + //debug
        //    " to " + ctgt.getName() + " ... removing");
        constraints.removeElementAt(i);
        result = false;
      } else {
        if (!ctgt.checkConstraint()) result = false;
      }
    }
    setMark(false);
    return result;
  }
  
  public Enumeration getConstraints() {
    return constraints.elements();
  }
  
  /** Test vertical constraints on this net;  @return true if all nets in constraint are already routed */
  public boolean testConstraints() {
    for (Enumeration e = getConstraints(); e.hasMoreElements(); ) {
      Net testnet = (Net)e.nextElement();
      if (!testnet.isRouted()) return false;
    }
    return true;
  }
  
  public void setMark(boolean m) { mark = m; }
  
  public boolean getMark() { return mark; }

}


class Terminal {

  private int column;
  private boolean topOrBottom;
  private Net owner;
  
  /** Symbolic constant for terminals at top of channel */
  public static final boolean TOP = true;
  /** Symbolic constants for terminals at bottom of channel */
  public static final boolean BOTTOM = false;

  public Terminal(int col, boolean tOrB) {
    column = col;
    topOrBottom = tOrB;
  }
  
  public Terminal(String spec) throws IOException {
    switch (spec.charAt(spec.length() - 1)) {
      case 'u':
      case 'U': topOrBottom = Terminal.TOP;
                 break;
      case 'l':
      case 'L': topOrBottom = Terminal.BOTTOM;
                 break;
      default:  throw new IOException();
    }
    String s = spec.substring(0, spec.length()-1);
    column = Integer.parseInt(spec.substring(0, spec.length() - 1));
  }
  
  public int getColumn() { return column; }
  
  public boolean getTopOrBottom() { return topOrBottom; }
  
  public Net getNet() { return owner; }
  
  public void setNet(Net n) { owner = n; }
  
  public void writeTerminal(PrintStream os) {
    os.print(column);
    if (topOrBottom == Terminal.TOP) os.print("U ");
    else os.print("L ");
  }


};