/*****************************************************************************/
/*                                                                           */
/*       Calculating Shortest Paths in a Graph: Graphical Version            */
/*                                                                           */
/*               February 1998,  Bryan Burns and Toshimi Minoura             */
/*                                                                           */
/*****************************************************************************/

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.io.*;
import java.net.*;

class Node {
  String name;       // Name of this Node
  Vector edges;      // Vector of edges adjacent to his Node
  int distance;      // shortest distance from the source Node
  Node previous;     // previous Node in the shortest-path to this Node
  int xLoc;          // the x location of the center of this Node
  int yLoc;          // the y location of the center of this Node
  int nodeWidth;     // the width of the graphical representation of this Node
  boolean focused;   // true if this Node is currently "focused"
  boolean processed; // true if this Node has been proccessed, false otherwise
  boolean inQueue;   // true if this Node is in the queue, false otherwise.
  
  public Node(String _name) {     // constructor
    name = _name;                 // copy argument
    edges = new Vector();         // create an empty Vector for adjacent edges
    focused = processed = inQueue = false;    // reset flags
    distance = -1;   // distance not computed yet
    nodeWidth = 60;  // changed according to length of String in Node
  }

  public Node(String _name, int x, int y) {   // constructor
    this(_name);                              // call constructor Node(String)
    xLoc = x;                                 // copy argument, x location
    yLoc = y;                                 // copy argument, y location
  }

  /**
   * Adds an edge to the node.
   *
   * @param edge An edge to be added to the Vector of adjacent edges.
   */
  public void addEdge(Edge edge) {
    edges.addElement(edge);         // add edge to adjacency list of this Node
  }
  
  /**
   * Deletes an edge from the node.
   * 
   * @param edge the edge to be deleted from the Vector of adjacent edges.
   */
  public boolean delEdge(Edge edge) {   // delete edge from adjacency list
    return edges.removeElement(edge);  
  }

  /**
   * returns an array of edges the node contains.
   */
  public Edge[] getEdges() {
    Edge[] temp = new Edge[edges.size()];   // create an array for edges
    edges.copyInto(temp);                   // convert from Vector to array
    return temp;                            // return edge array
  }

  /**
   * returns a Vector of edges representing the shortest path from the source
   * Node to this Node.
   */
  public Vector getTrail() {
    Node currentNode = this;                // highlight destination Node
    Vector trail = new Vector();            // initially trail is empty 
    while (currentNode.previous != null) {         // source node reached?
      Edge[] edges = currentNode.getEdges();       // get edges of current node
      for (int i = 0; i < edges.length; i++) {     // find edge connecting
        if (edges[i].fromNode == currentNode.previous ||   // current node and
           edges[i].toNode == currentNode.previous) {      // preceding node
          trail.addElement(edges[i]);              // add edge found to trail
          break;
        }
      }
      currentNode = currentNode.previous;          // get to preceding node
    }
    return trail;                                
  }

  public String toString() {
    return name;
  }
  
}

class Edge {
  Node fromNode;   // The node the edge leaves from
  Node toNode;     // The node the edge leads to  
  int weight;      // weight (or cost) of the edge 
  boolean focused; // true if the line is "focused"

  public Edge(Node source, Node dest, int weight) {
    fromNode = source;
    toNode = dest;
    this.weight = weight;
    focused = false;
  }
}

class ShortPathG extends StepTestCanvas implements MouseListener {

  public CanvasFrame heapFrame;       // The frame the heap resides in.
  static String dataFileName;         // name of file containing the data.
  public boolean isApplet = false;    // running as an applet

  /* miscelanious global variables */
  Hashtable nodes;  // Collection of all the nodes in the graph.
  int numNodes;     // How many nodes our graph contains.
  Node focusedNode; // A reference to the currently focused node.
  Node startNode;   // The node to start with for the shortest-path.
  Node goalNode;    // The node to end with for the shortest-path.
  HeapIG priQueue;  // The heap used for the shortest-path algorithm.
  boolean finished; // true if the shortest paths have been calculated.
  
  /* various color definitions */
  Color LineColor = new Color(0, 0, 0);
  Color FocusedLineColor = new Color(255, 0, 0);
  Color TrailColor = new Color(0, 100, 255);
  Color NodeColor = new Color(0, 100, 0);
  Color VisitedNodeColor = new Color(150, 255, 0);
  Color FocusedNodeColor = new Color(225, 225, 0);
  Color QueuedNodeColor = new Color(100, 150, 255);
  
  /* size definitions */
  int NodeWidth  = 60;
  int NodeHeight = 30;

  public ShortPathG() {
    nodes = new Hashtable();     // create an empty Hashtable to store Nodes
    numNodes = 0;                // initially, no Nodes
    startNode = null;
    goalNode = null;
    addMouseListener(this);
    priQueue = new HeapIG();     // queue for pending Nodes
    heapFrame =  new CanvasFrame("Priority Queue", priQueue, 800, 350);
    heapFrame.show();
  }
  
  /**
   * Adds a node to the graph.
   *
   * @param name The name of the node to be added.
   */
  public int addNode(String name) {
    return addNode(new Node(name));
  }
  
  /**
   * Adds a node to the graph.
   *
   * @param name The name of the node.
   * @param x The x location of the node.
   * @param y the y location of the node.
   */
  public int addNode(String name, int x, int y) {
    return addNode(new Node(name, x, y));
  }

  /**
   * Adds a node to the graph.
   * 
   * @param n The node to be added
   */
  public int addNode(Node newNode) {
    nodes.put(newNode.name, newNode);   // Add the node to our graph
    System.out.println("Node with name "+newNode.name+" has been added to "+
                       "the graph.");
    return ++numNodes;
  }

  /**
   * Returns the Node located at location x, y.  Note: this is not the actual
   * x, y position of the node as input into the program, but any x, y inside
   * the oval representing the node.  This is used by the mouseClicked()
   * event listener.
   *
   * @param x the x location of the mouse
   * @param y the y location of the mouse
   */
  public Node getNode(int x, int y) {
    Enumeration enum = nodes.elements();   // get elements of Hashtable
    Node node;
    while (enum.hasMoreElements()) {
      node = (Node) enum.nextElement();
      int width = node.nodeWidth;
      int nx = node.xLoc;
      int ny = node.yLoc;
      if ((x > (nx - width / 2) && x < (nx + width / 2)) &&
         (y > (ny - NodeHeight / 2) && y < (ny + NodeHeight / 2)))
        return node;
    }
    return null;
  }

  /**
   * Unfocuses all nodes and edges
   */
  public void unfocusAll() {
    focusedNode = null;
    Enumeration enum = nodes.keys();
    while (enum.hasMoreElements()) {
      Node n = (Node) nodes.get(enum.nextElement());
      n.focused = false;
      Edge[] e = n.getEdges();
      for(int i = 0; i < e.length; i++)
        e[i].focused = false;
    }
  }

  /**
   * Resets all the nodes to their original state.  In other words, it sets
   * distance to 0, and focused, processed and inQueue to false.
   */
  public void reset() {
    unfocusAll();
    Enumeration enum = nodes.elements();
    while (enum.hasMoreElements()) {
      Node n = (Node) enum.nextElement();
      n.distance = -1;
      n.processed = false;
      n.focused = false;
      n.inQueue = false;
    }
  }

  /**
   * Deletes a node from the graph.  
   *
   * @param name The name of the node to be deleted.
   *
   * @return True if the node existed, false if no such node could be found.
   */
  public boolean delNode(String name) {
    if (nodes.remove(name) != null) {
      System.out.println("Node with name "+name+" has been deleted");
      return true;
    }
    else{
      System.err.println("An error occured trying to delete node "+name);
      return false;
    }
  }

  /**
   * Adds an edge between two nodes.
   *
   * @param source The source node.
   * @param dest The destination node.
   * @param weight The <b>weight</b> of the edge
   */
  public boolean addEdge(String source, String dest, int weight) {
    Node sourceNode, destNode;
    sourceNode = (Node) nodes.get(source);
    destNode = (Node) nodes.get(dest);

    if (sourceNode == null) {
      System.out.println("Non-existing node name " + source +
        " in edge data: " + source + " " + dest + " " + weight); 
      return false;
    }
    if (destNode == null) {
      System.out.println("Non-existing node name " + dest +
        " in edge data: " + source + " " + dest + " " + weight); 
      return false;
    }

    Edge newEdge = new Edge(sourceNode, destNode, weight);
    sourceNode.addEdge(newEdge);
    destNode.addEdge(newEdge);
    return true;
  }

  public void mouseClicked(MouseEvent event) {
    Node node = getNode(event.getX(), event.getY());
    if (node == null || !finished) {
      return;                           // calculation not finished yet
    }
    unfocusAll();
    node.focused = true;
    focusedNode = node;
    repaint();
    System.out.println(node.name + " clicked.");
  }

  // unused mouseListener methods
  public void mouseEntered(MouseEvent e) {}
  public void mouseExited(MouseEvent e) {}
  public void mousePressed(MouseEvent e) {}
  public void mouseReleased(MouseEvent e) {}

  /**
   * resets everything to it's initial state.  Just calls reset()
   * @see reset
   */
  public void initialize() {
    priQueue.clear();
    reset();
    nodes.clear();
    repaint();
    numNodes = 0;
    finished = false;
  }

  public void paint(Graphics g) {
//  System.out.println("ShortPathG.paint() entered");
    if (numNodes < 1) {  // no user node, initial condition
      g.drawString("Graph is Empty", 400, 300);
      return;
    }

    Vector trail = null;
    String label = null;
    FontMetrics fm = getFontMetrics(getFont());
    if (focusedNode != null)
      trail = focusedNode.getTrail();
    Enumeration enum=nodes.keys();
    while (enum.hasMoreElements()) {
      Node thisNode = (Node) nodes.get(enum.nextElement());
      Node otherNode;
      Edge[] edges = thisNode.getEdges();
      if (edges != null) {
        for(int j = 0; j < edges.length ; j++) {
          if (edges[j].focused)
            g.setColor(FocusedLineColor);
          else if (trail != null && trail.contains(edges[j]))
            g.setColor(TrailColor);
          else
            g.setColor(LineColor);
          if (edges[j].fromNode == thisNode)
            otherNode = edges[j].toNode;
          else
            otherNode = edges[j].fromNode;

          int x1, x2, y1, y2; // Some shortcuts
          x1 = thisNode.xLoc;
          x2 = otherNode.xLoc;
          y1 = thisNode.yLoc;
          y2 = otherNode.yLoc;
          
          if (Math.abs(x1 - x2) < Math.abs(y1 - y2)) {  // rather vertical?
            g.drawLine(x1 -1, y1, x2 -1, y2);
            g.drawLine(x1, y1, x2, y2);
            g.drawLine(x1 +1, y1, x2 + 1, y2);
            g.drawString("" + edges[j].weight, 
                     (x1 + x2) / 2 + 6, (y1 + y2) / 2 - 1);
          }
          else {                                        // ratherhorizontal?
            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[j].weight, 
                     (x1 + x2) / 2 - 8, (y1 + y2) / 2 - 5);
          }
        }
      }
    }
    enum = nodes.keys();
    while (enum.hasMoreElements()) {
      Node thisNode = (Node) nodes.get(enum.nextElement());

      if (thisNode.focused)
        g.setColor(FocusedNodeColor);
      else if (thisNode.processed)
        g.setColor(VisitedNodeColor);
      else if (thisNode.inQueue)
        g.setColor(QueuedNodeColor);
      else
        g.setColor(NodeColor);

      /* Create the label for this node.  We need this to calculate
       * how big the oval should be. */
      if (thisNode.distance == -1)
        label = thisNode.name + ",-";
      else
        label = thisNode.name + "," + thisNode.distance;
      
      NodeWidth = fm.stringWidth(label) +10;
      thisNode.nodeWidth = NodeWidth;
      
      g.fillOval(thisNode.xLoc - NodeWidth / 2,    // x of top-left corner
                 thisNode.yLoc - NodeHeight / 2,   // y of top-left corner
                 NodeWidth, NodeHeight);
      if (thisNode.focused || thisNode.processed)
        g.setColor(Color.black);
      else
        g.setColor(Color.white);
      g.drawString(label,
                   thisNode.xLoc - NodeWidth / 2 + 5, thisNode.yLoc + 5); 
    }
  }

//  String url = "../oregon.data";   // MalformedURLException: no protocol
  String url = "http://www.cs.orst.edu/~minoura/cs261/javaProgs/oregon.data";
  public boolean readGraphData() {
    System.out.println("readGraphData(): isApplet = " + isApplet);
    try {
      Reader dataReader;;
      if (isApplet) {
        URL dataURL = new URL(url);
        dataReader = new InputStreamReader(dataURL.openStream());
        System.out.println("Running as an applet.");
      } 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 nodeName = tokenizer.nextToken();
          addNode(nodeName,
                  (Integer.parseInt(tokenizer.nextToken()) + 100) * 2,
                  ( - Integer.parseInt(tokenizer.nextToken()) + 110) * 2);
        } 
        else if (token.equals("edge")) {
          String nodeName1 = tokenizer.nextToken();  // get 1st city name
          String nodeName2 = tokenizer.nextToken();
          addEdge(nodeName1, nodeName2,
                  Integer.parseInt(tokenizer.nextToken())); // get weight
        }
        else if (token.equals("start")) {
          startNode = (Node) nodes.get(tokenizer.nextToken());
          System.out.println("start node : " + startNode);
        } else if (token.equals("goal")) {
          goalNode = (Node) nodes.get(tokenizer.nextToken());
          System.out.println("goal node : " + goalNode);
        }
      }
      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: data file name needed as an argument; " +
                         "Activate as java ShortPathG  ../oregon.data");
      System.exit(-1);
    }

    ShortPathG shortPathG = new ShortPathG();

    new StepTestFrame("Shortest Distance Calculation", shortPathG,
                       950, 800).show();
  }
 
  public void runMain() {            // called from run() of StepTestCanvas
    System.out.println("ShortPathG.runMain() entered");

    initialize();
    if (!readGraphData()) {          // read road distance information
      repaintStep("Graph data file " + dataFileName + " could not be read.");
      try {
        Thread.sleep(5000);
        System.exit(-1);
      } catch (InterruptedException e) { }
    }

    repaintStep("Press a button to calculate distance from "+
                startNode.name +" to all other nodes");

    if (startNode == null) {         // start Node not defined
      System.err.println("Formatting error in graph input: "+
                         "Need start node.");
      System.exit(1);
    }
                        
    startNode.distance = 0;
    priQueue.insert(0, startNode);
    
    Node currentNode, otherNode;

    while (!priQueue.isEmpty()) {  // process every entry in priority queue
      unfocusAll();
      HeapIG.Node heapNode = priQueue.removeMin();  // get node with min value
      currentNode = (Node) heapNode.value;          // get node
      currentNode.inQueue = false;       // current Node no longer in queue
      if (currentNode.distance != -1 && currentNode.distance < heapNode.key) {
        repaintStep("Node already processed with shorter distance");
        continue;             
      }
      currentNode.processed = true;      // shortest distance definite
      currentNode.focused = true;        // highlight current node
      focusedNode = currentNode;
      repaintStep("Distances from " + currentNode.name + 
                  " to neighboring cities will be computed.");

      Edge[] edges = currentNode.getEdges();      // get edges of current Node
      for (int i = 0; i < edges.length; i++) {    // process each edge
        if (edges[i].fromNode == currentNode)
          otherNode = edges[i].toNode;
        else
          otherNode = edges[i].fromNode;
        edges[i].focused = true;
        if (otherNode.distance > (currentNode.distance + edges[i].weight)
           || otherNode.distance == -1) {         // shorter path found?
          otherNode.distance = currentNode.distance + edges[i].weight;
          priQueue.insert(otherNode.distance, otherNode);  // add node to queue
          otherNode.inQueue = true;
          otherNode.previous = currentNode;
          repaintStep("Distance to " + otherNode.name + 
                " via " + currentNode.name + " calculated, pushed on queue.");
        } else {
          repaintStep("Shorter distance to " + otherNode.name +
                      " already known.");
        }
        edges[i].focused = false;
      }
      repaintStep("All edges from " + currentNode.name + " checked.");
      currentNode.focused = false;
    }
    unfocusAll();
    finished = true;
    repaintStep("All done.  Click on any node to see its shortest path. ");
    System.out.println("runMain() completed");
  }  
}