package graph;
import container.InvalidPositionException;
import java.util.Iterator;
import java.util.Map;
import java.util.HashMap;

/** An implementation of KeyedDigraph that wraps another Digraph
 * (no matter what its implementation) and adds a hash table. 
 */

public class HashKeyedDigraph implements KeyedDigraph {  

  /** The underlying graph. */
  Digraph g;

  /** Maps keys to vertices. */
  protected Map m;

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

  /** If g is an empty Digraph, this constructs a new empty
   * KeyedDigraph.  This KeyedDigraph is really just a keyed "view" of
   * g, not a separate graph.  That's because if the KeyedDigraph is
   * modified in any way, the Digraph g will change too, and
   * vice-versa.<p>
   *
   * Any vertices already in g will not be accessible via keys, but new 
   * vertices added through findOrInsertKeyedVertex may have keys.
   */
  public HashKeyedDigraph(Digraph g) {
    this.g = g;
    m = new HashMap();
  }

  // ---------- PUBLIC METHODS OF KeyedDigraph ----------

  public Vertex findKeyedVertex(Object k) {
    FILL THIS IN.  AVOID DUPLICATING CODE.
  }

  public Vertex findOrInsertKeyedVertex(Object k) {
    FILL THIS IN.  AVOID DUPLICATING CODE.
  }


  public DirectedEdge keyedInsertDirectedEdge(Object keyFrom, 
					      Object keyTo, 
					      Object element) {
    FILL THIS IN.  AVOID DUPLICATING CODE.
  }

  // ---------- PUBLIC METHODS OF Digraph ----------
  //
  // These are just passed down to the underlying graph.

  public int numVertices() { return g.numVertices(); }
  public int numEdges() { return g.numEdges(); }
  public Iterator outIncidentEdges(Vertex v) { return g.outIncidentEdges(v); }
  public Vertex insertVertex(Object element) { return g.insertVertex(element); }
  public DirectedEdge insertDirectedEdge(Vertex from, Vertex to, Object element) throws InvalidPositionException {
    return g.insertDirectedEdge(from,to,element);
  }
  public void insertReverseOf(DirectedEdge e) { g.insertReverseOf(e); }


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

  /** Returns the directed graph from figure 12.2 of the textbook. */

  public static KeyedDigraph fig12_2() {
    KeyedDigraph kg = new HashKeyedDigraph(new AdjListDigraph());

    kg.keyedInsertDirectedEdge("bos", "jfk", "NW 35");
    kg.keyedInsertDirectedEdge("bos", "mia", "DL 247");
    kg.keyedInsertDirectedEdge("jfk", "mia", "AA 903");
    kg.keyedInsertDirectedEdge("jfk", "dfw", "AA 1387");
    kg.keyedInsertDirectedEdge("jfk", "sfo", "TW 45");
    kg.keyedInsertDirectedEdge("mia", "dfw", "AA 523");
    kg.keyedInsertDirectedEdge("mia", "lax", "AA 411");
    kg.keyedInsertDirectedEdge("dfw", "ord", "DL 335");
    kg.keyedInsertDirectedEdge("dfw", "lax", "AA 49");
    kg.keyedInsertDirectedEdge("ord", "dfw", "UA 877");
    kg.keyedInsertDirectedEdge("lax", "ord", "UA 120");

    return kg;
  }

  // Convenience method used below.  Inserts a pair of edges.
  private void insertDistance(String s1, String s2, int i) {
    insertReverseOf(keyedInsertDirectedEdge(s1, s2, new Integer(i)));
  }

  /** Returns the undirected, weighted graph from figure 12.15 of the textbook. 
   * Each undirected edge is represented as a pair of directed edges,
   * each of which store the same Integer.
   */

  public static KeyedDigraph fig12_15() {
    HashKeyedDigraph kg = new HashKeyedDigraph(new AdjListDigraph());

    kg.insertDistance("bos", "jfk", 187);
    kg.insertDistance("bos", "mia", 1258);
    kg.insertDistance("bos", "ord", 867);
    kg.insertDistance("bos", "sfo", 2704);
    kg.insertDistance("pvd", "jfk", 144);
    kg.insertDistance("pvd", "ord", 849);
    kg.insertDistance("jfk", "ord", 740);
    kg.insertDistance("jfk", "bwi", 184);
    kg.insertDistance("jfk", "mia", 1090);
    kg.insertDistance("jfk", "dfw", 1391);
    kg.insertDistance("bwi", "ord", 621);
    kg.insertDistance("bwi", "mia", 946);
    kg.insertDistance("mia", "dfw", 1121);
    kg.insertDistance("mia", "lax", 2342);
    kg.insertDistance("ord", "dfw", 802);
    kg.insertDistance("ord", "sfo", 1846);
    kg.insertDistance("dfw", "sfo", 1464);
    kg.insertDistance("dfw", "lax", 1235);
    kg.insertDistance("sfo", "lax", 337);

    return kg;
  }

  /** This test method does some work but doesn't actually print anything.
   * See the Dijkstra class for a test method that actually does something
   * with the graphs.
   */
  public static void main(String args[]) {

    // Make a couple of little graphs.

    fig12_2();
    fig12_15();

    // Make a big graph to check that it is fast even when the
    // edge lists get large.  Vertex 0 is connected to 100000 other 
    // vertices.

    KeyedDigraph kg = new HashKeyedDigraph(new AdjListDigraph());
    int i=0;
    while (i<100000) {
      // print progress dots as we go
      if (++i % 100 == 0) System.out.print(".");
      kg.insertReverseOf(kg.keyedInsertDirectedEdge("start", "vertex "+i, "edge between 0 and "+i));
    }
  }
}