package graph;
import container.*;
import pqueue.*;
import java.util.Iterator;

/** A class to find shortest paths from a single start point to any
 * end point.  The user interface is nicely set up so that it is
 * efficient regardless of whether the user wants the distance to lots
 * of end points, or just to a single end point near the start point.
 */

public class Dijkstra {

  // ---------- INSTANCE VARIABLES ----------

  /** The graph we are searching. */
  protected Digraph g;

  /** An object that can compute the weight function on edges. */
  protected Weighter weighter;

  /** The start vertex. */
  protected Vertex vStart;   

  /** A priority queue of vertices that still have to be relaxed,
   * keyed by their attrDist.  Smallest attrDist is at the front of
   * the queue.  A vertex's attrDist attribute may change during the
   * course of the algorithm (which is why we need an AdaptablePriorityQueue),
   * but it is guaranteed to be correct by the time the vertex reaches
   * the front of the queue.
   */
  protected AdaptablePriorityQueue pq;
  
  // ---------- ATTRIBUTES FOR DECORATED VERTICES ----------
  // (see textbook section 12.3 for discussion of the "decorator pattern")

  /** Distance attribute.  A vertex's attrDist is the total length of
   * the shortest known path from vStart to that vertex.  If a vertex
   * does not have this attribute yet, it has not yet been discovered,
   * and its attrDist should be considered to be infinite.<p>
   *
   * This attribute is public, enabling the user to find its value at
   * any vertex.
   */
  public Attribute attrDist;

  /** Backpointer attribute.  A vertex's attrBestEdgeIn is the last edge leading
   * to the vertex on a shortest-known path from vStart.  If a vertex does not 
   * have this attribute, no path to it from vStart has been discovered yet.
   * vStart has an attrBestEdgeIn of null.<p>
   *
   * This attribute is public, enabling the user to find its value at
   * any vertex.
   */
  public Attribute attrBestEdgeIn;

  /** Entry attribute.  A vertex's attrEntry is its entry on the
   * adaptable priority queue.  Knowing this lets us change the
   * vertex's priority.  If a vertex does not have this attribute, it
   * is not currently on the priority queue -- either it has not yet
   * been inserted, or it has already been removed.
   */
  protected Attribute attrEntry;

  // ---------- CONSTRUCTORS  ----------

  /** Constructor that sets up a shortest-path problem.  Dijkstra's algorithm
   * is not actually run yet.  But we are ready to find the shortest paths
   * in graph g from vertex vStart, where edges are weighted by weighter.
   */
  public Dijkstra(Digraph g, Weighter weighter, Vertex vStart) {   

    // Set up the problem.

    this.g = g;
    this.weighter = weighter;
    this.vStart = vStart;

    // The attributes are specific to this instance of Dijkstra --
    // they are not static to the Dijkstra class as in the book.  This
    // is because the user might have several instances of Dijkstra
    // running simultaneously on the same graph.

    attrDist = new Attribute("distance from start vertex "+vStart);
    attrBestEdgeIn = new Attribute("best edge in");
    attrEntry = new Attribute("entry on the Dijkstra repriority queue");

    // Create the priority queue and put vStart on it.
    // The priority queue uses the default comparator that uses
    // the keys' own built-in compareTo method.  That's appropriate
    // since our keys are numbers (Doubles representing distances)
    // and we want the smallest number at the front of the queue.

    this.pq = new HeapAdaptablePriorityQueue();  
    recordNewPathTo(vStart, 0, null);
  }


  /** Convenience version of the constructor where the graph is keyed 
   * and the start vertex is specified by a key.
   *
   * @throws ClassCastException if the graph is not an instance of KeyedDigraph.
   * @throws NoSuchVertexException if there is no vertex keyed by keyStart.
   */
  public Dijkstra(Digraph g, Weighter weighter, Object keyStart) {

    FILL THIS IN

  }

  // ---------- MAJOR METHODS ----------

  /** Run Dijkstra's algorithm until we know the shortest path from
   * vertex vStart to vertex vEnd.  Then stop and return that path.  
   * Or return null if there is no directed path from vStart to vEnd.<p>
   * 
   * The user may call us again later with another vertex vEnd, in which
   * case we will pick up where we left off and continue running Dijkstra's
   * algorithm, if necessary, until we know the shortest path to THAT vertex!<p>
   *
   * To find the length of the path, the user can look at
   * v.get(d.attrDist), where d is this Dijkstra instance.  Alternatively,
   * the user can just sum the weights of the returned path's edges.<p>
   *
   * @throws NegativeWeightException if negative edge weights are 
   *   discovered in the graph.
   */
  public Path getPathTo(Vertex vEnd) throws NegativeWeightException {
    computePathTo(vEnd);
    return pathTo(vEnd);
  }

  /** Convenience version of getPathTo() where the end
   * vertex is specified by a key.
   *
   * @throws ClassCastException if the graph is not an instance of KeyedDigraph.
   * @throws NoSuchVertexException if there is no vertex keyed by keyEnd.
   * @throws NegativeWeightException if negative edge weights are 
   *   discovered in the graph.
   */
  public Path getPathTo(Object keyEnd) throws NegativeWeightException {
    return getPathTo(((KeyedDigraph)g).findKeyedVertex(keyEnd));
  }

  // ---------- IMPLEMENTATION ----------

  /** Run Dijkstra's algorithm until we know the shortest path from
   * vertex vStart to vertex vEnd, or have explored the whole graph
   * without finding such a path.<p>
   *
   * pathTo() can then be used to find the shortest path to vEnd,
   * or the shortest KNOWN path (so far) to another vertex.
   *
   * @throws NegativeWeightException if negative edge weights are 
   *   discovered in the graph.
   */
  protected void computePathTo(Vertex vEnd) throws NegativeWeightException {
    int vertexWork = 0, relaxWork = 0, edgeWork = 0;   // how much work have we done?

    FILL THIS IN - THIS IS THE MAIN CODE FOR DIJKSTRA'S ALGORITHM
    // Hint: At what point do you KNOW the SHORTEST path to vEnd? 

    System.out.println("  Explored "+edgeWork+" edges from "
		       +vertexWork+" vertices; "
		       +relaxWork+" relaxations");
  }

  /** Get the best currently known path from vStart to v, by following
   * the backpointers (attrBestEdgeIn) from v back to vStart.
   * Returns null if there is no known path from vStart to v.
   *
   * Note: computePathTo() does the real work, and then pathTo() can
   * be called to extract the paths.  Those two methods are separate 
   * and do not call one another.
   */
  protected Path pathTo(Vertex v) {

    FILL THIS IN  
    // Hint: what does the Path class extend?
    // Hint: use recursion

  }

  // ---------- UTILITY METHODS  ----------

  /** Remove and return the Vertex at the front of the priority queue. */
  private Vertex removeMinVertex() {
    Vertex v = (Vertex) pq.removeMin().value();
    v.remove(attrEntry);   // no longer on the queue

    // --- You might want to temporarily uncomment this 
    // --- line to trace the algorithm's progress. 
    // System.out.println("Popped "+v.element()+"\tdist "+v.get(attrDist)
    //		       +"\tbest path "+pathTo(v));

    return v;
  }

  /** Value of v's attrDist attribute, as a double. */
  private double getDist(Vertex v) {   
    return ((Double) v.get(attrDist)).doubleValue();
  }

  /** We'll call this method when we find a new, shorter
   * path to v.  The total weight of the new path is d
   * and its last edge is e.<p>
   *
   * In addition to recording the new path in v's attributes, we
   * ensure that v is on the priority queue, so that the change in its
   * attrDist will be propagated to its neighbors.  This may mean
   * inserting or reprioritizing v.  
   *
   * Note: This method doesn't have to care whether v has previously been
   * popped off the queue.  However, it is interesting to remember
   * that in Dijkstra's algorithm, a vertex's distance will never
   * improve further once it has been popped, so it never goes back on
   * on the priority queue.  (This is also true for the A* algorithm
   * if we use a "monotonic" heuristic function, which is usually the
   * case and is the case in this assignment.)
   */
  private void recordNewPathTo(Vertex v, double d, DirectedEdge e) {

    FILL THIS IN

  }

  // ---------- EXOTIC FINALIZER! ----------
    
  /** The finalizer for this Dijkstra instance.  It clears the
   * attributes that it may have placed on the vertices.  Otherwise,
   * the vertices of a graph can get cluttered with attributes from
   * many runs of Dijkstra's algorithm.  The Dijkstra
   * objects may finish their work and get garbage-collected, but
   * the attributes are still accessible from the graph, and 
   * Java doesn't know that it's okay to garbage-collect THEM.
   * We have to tell it.<p>
   *
   * A finalizer is the opposite of a constructor.  When and if a
   * Dijkstra instance is eventually garbage-collected (long after
   * we're done with it), Java will automatically call the
   * special finalize() method if it exists.  Since this particular
   * finalize() method is public, the user is also welcome to call
   * it sooner when done with the Dijkstra instance, instead of waiting 
   * for the garbage collector to show up.
   *
   * In C++, it is necessary to have destructors for most objects
   * because there is no garbage collection in C++; memory
   * must be released explicitly.  But in Java, 
   * it is quite rare to need a finalizer.
   */
  public void finalize() {
    clearAttributes(vStart);
  }

  /** Clears this instance's attributes from v and all the vertices
   * that can be reached from it by directed paths from v.  We do this 
   * by depth-first search from v.  
   */
  protected void clearAttributes(Vertex v) {
    if (v.has(attrDist)){   // we haven't been here and cleared this out yet.

      v.remove(attrDist);
      v.remove(attrBestEdgeIn);
      v.remove(attrEntry);

      Iterator iter = g.outIncidentEdges(v);
      while (iter.hasNext()) {
	DirectedEdge e = (DirectedEdge) iter.next();
	clearAttributes(e.destination());
      }
    }
  }

  // ---------- TEST METHODS ----------

  public static void main(String args[]) {

    /* Let's get some graphs to play with:
     * the graphs from textbook figures 12.2 and 12.15.
     */

    KeyedDigraph g1 = HashKeyedDigraph.fig12_2();  
    KeyedDigraph g2 = HashKeyedDigraph.fig12_15();  

    /* Let's make some weighters to play with.  Each one implements
     * the Weighter interface in a different way.<p>
     * 
     * Since these are mainly for testing purposes and we are not
     * expecting to use them elsewhere, it would be annoying to name
     * all these implementations and put each in its own .java file.
     * After all, each one is only going to have one instance.<p>
     * 
     * Fortunately, Java has an "anonymous class" feature that lets us
     * easily make a single instance of a new, unnamed class that extends
     * the Weighter interface.
     */

    // A weighter that takes every edge to have weight 1.

    Weighter weighterOne = new Weighter() { 
	public double weight(Object o) { return 1; }
      };
	
    // A weighter that gives negative weights.  This
    // should cause Dijkstra's algorithm to throw an
    // exception.

    Weighter weighterBad = new Weighter() { 
	public double weight(Object o) { return -1; }
      };

    // A new weighter that takes the weight of an edge (or other
    // position) to be the number stored as its element.  If someone
    // tries to find the weight of something that does not store a
    // numeric element, this weight() method will crash by throwing
    // a ClassCastException, which is what the Weighter interface
    // says it should do.

    Weighter weighterStored = new Weighter() { 
	public double weight(Object o) { 
	  Object element = ((Position) o).element();
	  return ((Number)element).doubleValue();
	}
      };


    /* The example from Fig. 12.15. 
     * To see this one run, you may want to uncomment the tracing
     * line in removeMinVertex().
     */
    Dijkstra d = new Dijkstra(g2, weighterStored, "bwi");
    System.out.println("********** Example of Fig. 12.15 **********");
    System.out.println("Finding best path from BWI to LAX (which is the farthest)");
    d.getPathTo("lax");   // go all the way to the worst one first
    System.out.println("Reporting paths from BWI to all airports (should take no extra work):");
    System.out.println(d.getPathTo("lax"));   
    System.out.println(d.getPathTo("sfo"));   
    System.out.println(d.getPathTo("dfw"));   
    System.out.println(d.getPathTo("mia"));   
    System.out.println(d.getPathTo("ord"));   
    System.out.println(d.getPathTo("bos"));   
    System.out.println(d.getPathTo("pvd"));   
    System.out.println(d.getPathTo("jfk"));   
    System.out.println(d.getPathTo("bwi"));   
    
    /* Set up some more Dijkstra objects. */

    Dijkstra d1 = new Dijkstra(g1, weighterOne, "jfk");
    Dijkstra d2 = new Dijkstra(g2, weighterOne, "jfk");
    Dijkstra d3 = new Dijkstra(g2, weighterStored, "jfk");
    Dijkstra d4 = new Dijkstra(g2, weighterStored, "bwi");

    /* Some airports to go to. */

    String[] destination = {"dfw", "lax", "mia", "jfk", "bos"};
    
    /* Do the work!  Note that we are using several 
     * Dijkstra objects at once, sometimes on the same
     * graph.  Because each uses its own attributes, they
     * don't interfere with one another.  This is especially
     * important in case we have many users all looking for
     * flight information at once on the same graph ...
     */
    for (int i=0; i < destination.length; i++) {
      String dest = destination[i];
      System.out.println("\n********** How far to "+dest+"? **********");
      if (i>0)
	System.out.println("(building on the work we've already done)\n");
      System.out.println("Fewest hops in directed graph of Fig. 12.2:     "
		       + d1.getPathTo(dest));
      System.out.println("Fewest hops in undirected graph of Fig. 12.15:  "
		       + d2.getPathTo(dest));
      System.out.println("Fewest miles in undirected graph of Fig. 12.15: "
		       + d3.getPathTo(dest));
      System.out.println("Same, if we flew from BWI instead of JFK:       "
		       + d4.getPathTo(dest));
    }
  }
}