/*****************************************************************************/
/*                                                                           */
/*                 Minimum Spanning Tree: Graphical Version                  */
/*                                                                           */
/*                     March 1998, Toshimi Minoura                           */
/*                    November 1999, Jacob Lundberg                          */
/*                                                                           */
/*****************************************************************************/

import java.awt.*;
import java.io.*;
import java.util.*;   // for classes StringTokenizer and Hashtable
import java.net.*;    // for class URL

// Nodes are stored in nodes[] in class MinSTG.
class Node {
  public String name;
  int xLoc;
  int yLoc;
  public Object value;         // value of this node
  Color color;

  static Color NodeColor = new Color(0, 100, 0);
  static Color FocusColor = new Color(150, 255, 0);
  static Color NewNodeColor = new Color(225, 225, 0);

  Node(String name, int x, int y) {  // constructor
    this.name = name;      // copy argument name
    xLoc = x;              // copy x location of noce
    yLoc = y;              // copy y location of noce
    value = null;          // copy argument value
    color = NodeColor;     // set initial color
  }

  public String toString() {   // create String representation for node
    return "Node: name = " + name + ", xLoc = " + xLoc + ", yLoc = " + yLoc;
  } 
}

// Edges are stored in edges[] in class MinSTG.
class Edge {
  int nodeIdx1;
  int nodeIdx2;
  public int weight;         // value associated with this edge
  Color color;

  static Color PendingColor   = Color.green;
  static Color HighlightColor = new Color(255, 160, 0);
  static Color SelectColor    = Color.blue;
  static Color NonSelectColor = new Color(200, 220, 220);

  Edge(int nodeIdx1, int nodeIdx2, int weight) {           // constructor
    this.nodeIdx1 = nodeIdx1;  // copy argument
    this.nodeIdx2 = nodeIdx2;  // copy argument
    this.weight = weight;      // copy argument
    color = Color.black;       // set default color
  }

  public String toString() {   // create String representation for node
    return "Edge between nodes " + nodeIdx1 + " and " + nodeIdx2 +
           ": weight = " + weight;
  } 
}
 
class MinSTG extends StepTestCanvas {
  static final int NodeTableSize = 100;   // size of nodes[]
  static final int EdgeTableSize = 100;   // size of edges[]
  private Node nodes[];                   // storage for Node data
  private Edge edges[];                   // storage for Edge data
  private int totalCost = 0;              // total weight of active edges
  int lastNode = -1;
  int lastEdge = -1;

  CanvasFrame canvasFrame;                // Frame for showing node sets
  public boolean isApplet = false;        // running as an applet

  static String dataFileName;
  Hashtable hashTable;
  SetsG nodeSets;                         // node sets of connected nodes

  public MinSTG() {                       // constructor
    nodes = new Node[NodeTableSize];
    edges = new Edge[EdgeTableSize];
    nodeSets = new SetsG();  
    canvasFrame = new CanvasFrame("Node Sets", nodeSets, 900, 300);
    canvasFrame.show();
  }

  // add nodes
  public int addNode(String name, int x, int y) {
    nodes[++lastNode] = new Node(name, x, y);
//    repaintStep("New node added with lastNode = " + lastNode + ": "
//                 + nodes[lastNode]);
    return lastNode;        // return array index of the node inserted
  }

  // add edges via an insertion sort
  public int addEdge(int nodeIdx1, int nodeIdx2, int weight) {
    ++lastEdge;
    edges[lastEdge] = new Edge( nodeIdx1, nodeIdx2, weight );
    for( int currentEdge = 0 ; currentEdge < lastEdge ; currentEdge++ )
      if( weight < edges[currentEdge].weight ) {
        nodeIdx1 = edges[currentEdge].nodeIdx1;
        nodeIdx2 = edges[currentEdge].nodeIdx2;
        weight = edges[currentEdge].weight;
        edges[currentEdge].nodeIdx1 = edges[lastEdge].nodeIdx1;
        edges[currentEdge].nodeIdx2 = edges[lastEdge].nodeIdx2;
        edges[currentEdge].weight = edges[lastEdge].weight;
        edges[lastEdge].nodeIdx1 = nodeIdx1;
        edges[lastEdge].nodeIdx2 = nodeIdx2;
        edges[lastEdge].weight = weight;
      }

//    edges[++lastEdge] = new Edge(nodeIdx1, nodeIdx2, weight);
//    repaintStep("New edge added with lastEdge = " + lastEdge + ": "
//                 + edges[lastEdge]);
    return lastEdge;        // return array index of the edge inserted
  }

  // do not do dumb things like call this twice in a row
  public int includeEdge( int edgeIdx )
    {
      totalCost += edges[edgeIdx].weight;
      return totalCost;
    }

  // do not do dumb things like call this twice in a row
  public int excludeEdge( int edgeIdx )
    {
      totalCost -= edges[edgeIdx].weight;
      return totalCost;
    }

  static final int NodeWidth  = 50;  // width of node drawn
  static final int NodeHeight = 30;  // height of node drawn

  public void paint(Graphics g) {

    // draw all edges
    for (int edgeIdx = 0; edgeIdx <= lastEdge; edgeIdx++) {
      g.setColor(edges[edgeIdx].color);   
      int x1 = nodes[edges[edgeIdx].nodeIdx1].xLoc;
      int y1 = nodes[edges[edgeIdx].nodeIdx1].yLoc;
      int x2 = nodes[edges[edgeIdx].nodeIdx2].xLoc;
      int y2 = nodes[edges[edgeIdx].nodeIdx2].yLoc;
          
      if (Math.abs(x1 - x2) < Math.abs(y1 - y2)) {  
        g.drawLine(x1 -1, y1, x2 -1, y2);   // drwa a think line with three 
        g.drawLine(x1, y1, x2, y2);         // lines
        g.drawLine(x1 +1, y1, x2 + 1, y2);
        g.drawString("" + edges[edgeIdx].weight, 
                     (x1 + x2) / 2 + 6, (y1 + y2) / 2 - 1);
      } else {
        g.drawLine(x1, y1 -1, x2, y2 -1);
        g.drawLine(x1, y1, x2, y2);
        g.drawLine(x1, y1 +1, x2, y2 +1);
        g.drawString("" + edges[edgeIdx].weight, 
                     (x1 + x2) / 2 - 8, (y1 + y2) / 2 - 5);
      }
    }

    // draw all nodes
    for (int nodeIdx = 0; nodeIdx <= lastNode; nodeIdx++) {
      g.setColor(Node.NodeColor);        // set color for Node
      g.fillOval(nodes[nodeIdx].xLoc - NodeWidth / 2, 
                 nodes[nodeIdx].yLoc - NodeHeight / 2, NodeWidth, NodeHeight);
      if (nodes[nodeIdx].color == Node.FocusColor) {
        g.setColor(Color.blue);          // set color for node label
      } else {
        g.setColor(Color.white);         // for other node
      }
      g.drawString(nodes[nodeIdx].name, 
        nodes[nodeIdx].xLoc - NodeWidth / 2 + 4,
        nodes[nodeIdx].yLoc + 5); 
    }
  }

//  String url = "../oregon.data";   // MalformedURLException: no protocol
  String url = "http://www.cs.orst.edu/~minoura/cs261/javaProgs/oregon.data";
  public boolean readGraphData() {
    try {
      Reader dataReader;;
      if (isApplet) {
        System.out.println("Running as an applet.");
        URL dataURL = new URL(url);
        dataReader = new InputStreamReader(dataURL.openStream());
      } else {
        dataReader = new FileReader(dataFileName);  // run as an application
      };
      BufferedReader reader = new BufferedReader(dataReader);
      String inputLine;

      while ( (inputLine = reader.readLine()) != null ) {
//      System.out.println("Line read : " + inputLine);

        StringTokenizer tokenizer = new StringTokenizer(inputLine);
        String token;
        try {
          token = tokenizer.nextToken();
        } catch (NoSuchElementException e) {
          continue;
        }
        if (token.equals("node")) {
          String cityName = tokenizer.nextToken();
          int nodeIdx = addNode(cityName,
            (Integer.parseInt(tokenizer.nextToken()) + 100) * 2,
            ( - Integer.parseInt(tokenizer.nextToken()) + 110) * 2);
          hashTable.put(cityName, new Integer(nodeIdx));
        } else if (token.equals("edge")) {
          String cityName1 = tokenizer.nextToken();  // get 1st city name
          Integer cityIdx1 = (Integer) hashTable.get(cityName1);
          addEdge(cityIdx1.intValue(),
                  ((Integer) hashTable.get(tokenizer.nextToken())).intValue(),
                  Integer.parseInt(tokenizer.nextToken())); // get weight
        }
      }
      reader.close();
      return true;                        // graph data successfully read
    } catch (FileNotFoundException e) {
      System.out.println("Error: File Not Found Exception:" + e);
      return false;
    } catch (IOException e) {
      System.out.println("IOException : " + e );
      return false;
    }
  }

  public static void main(String argv[]) {
    if (argv.length == 1) {
      dataFileName = argv[0];     // use 1st argument as graph data file name
    } else {                                
      System.out.println("Error: activate as java MinSTG ../oregon.data.");
      System.exit(-1);
    }

    new StepTestFrame("Minimum Spanning Tree", new MinSTG(),
                       900, 800).show();
  }
 
  public void runMain() {             // called from run() of StepTestCanvas
    System.out.println("MinSTG.runMain() entered");

    lastNode = -1;
    lastEdge = -1;
    hashTable = new Hashtable();
    nodeSets.reset();

    if (!readGraphData()) {
      repaintStep("Graph data file " + dataFileName + " cannot be read.");
      try {
        Thread.sleep(5000);
        System.exit(-1);
      } catch (InterruptedException e) { }
    }
    repaintStep();

    for (int nodeIdx = 0; nodeIdx <= lastNode; nodeIdx++) {
      nodeSets.setNode(nodeIdx, nodes[nodeIdx].name);
    }
    repaintStep("Singleton node sets created.");

    // sort of edges in edges[] according to weight performed during insertion

    for (int edgeIdx = 0; edgeIdx <= lastEdge; edgeIdx++) {
      edges[edgeIdx].color = Edge.HighlightColor;    // select one edge
      repaintStep("Edge between " + nodes[edges[edgeIdx].nodeIdx1].name +
             " and " + nodes[edges[edgeIdx].nodeIdx2].name + " visited.");

      int setIdx1 = nodeSets.findSet(edges[edgeIdx].nodeIdx1);
      int setIdx2 = nodeSets.findSet(edges[edgeIdx].nodeIdx2);
      if (setIdx1 == setIdx2) {  // nodes nodeIdx1 and nodeIdx2 in same set
        edges[edgeIdx].color = Edge.NonSelectColor;
        repaintStep("Edge between " + nodes[edges[edgeIdx].nodeIdx1].name +
             " and " + nodes[edges[edgeIdx].nodeIdx2].name +
             " already connected by other edges.");
        continue;
      } 
      includeEdge( edgeIdx );
      edges[edgeIdx].color = Edge.SelectColor;  // edge in spanning tree
      nodeSets.union(setIdx1, setIdx2);
      repaintStep("Edge between " + nodes[edges[edgeIdx].nodeIdx1].name +
             " and " + nodes[edges[edgeIdx].nodeIdx2].name +
             " added to a spanning tree.");
    }

   repaintStep("Minimum Spanning Tree Computed: Total Cost = " + totalCost + ".");
    System.out.println("runMain() completed");
  }  
}