// Adapted from Carrano&Savitch, Data Structures and Abstractions With Java
// Providing ways to manually create a graph AND use adjacency list

import java.util.*;

public class Digraph {
    
    private Map verticies; // key-val pairs of (VertexName,Vertex)
                           // each Vertex points to its adjacency list
    private int edgeCount; // number of edges
    
    public Digraph( ) {
	verticies = new LinkedHashMap();  // helps to maintain order in which nodes are created
    }
    
    // Add vertex to map; key is its name; val is the vertex:
    public void addVertex(Object name) { 
	verticies.put(name, new Vertex(name));
    }
    
    // Adds edge assuming source and dest verticies exist:
    public void addEdge(Object source, Object dest, int weight) { 
	Vertex s = (Vertex)verticies.get(source); // get source index
	Vertex d = (Vertex)verticies.get(dest);   // get dest index
	s.addEdge(new Edge(s,d,weight));          // add edge to source's adjacency list
	edgeCount++;
    }
    public void addEdge(Object source, Object dest) {
	addEdge(source,dest,0);
    }

    // Empty graph?
    public boolean isEmpty() {	return verticies.isEmpty(); }

    // Return number of vertices:
    public int getVertexCount() { return verticies.size(); }

    // Return number of edges:
    public int getEdgeCount() { return edgeCount; }

    // Stringify by returning edges with their adjacency lists:
    public String toString() {
	String s = "";
	Iterator it=verticies.keySet().iterator();
	while(it.hasNext()) {
	    Object key = it.next();                    // current vertex label
	    Vertex val = (Vertex) verticies.get(key);  // current Vertex
	    s += "[" + val + "]" + "-->";
	    s += val.getEdges();
	    s += "\n";
	}
	return s;
    }
 
    // ***** NEW *****
    // Want vertex iterator to do things to each Vertex in hashtable:
    public Iterator getVertexIterator() {
	return verticies.values().iterator();
    }

    public void resetVerticies() {
	for (Iterator vi = getVertexIterator() ; vi.hasNext() ; ) {
	    Vertex v = (Vertex) vi.next();
	    v.unvisit();
	    v.setCost(0);
	    v.setPrev(null);
	}
    }

    public SeqStructure getBFS(Object origin) {
	
	resetVerticies();
	SeqStructure toDo = new QueueAsList();
	SeqStructure path = new QueueAsList();
	 
	Vertex originVertex = (Vertex)verticies.get(origin);
	originVertex.visit();
	toDo.put(originVertex);
	path.put(originVertex);

	while(!toDo.isEmpty()) {
	    Vertex currentVertex = (Vertex)toDo.get();

	    for (Iterator edges = currentVertex.getEdgeIterator(); edges.hasNext(); ) {
		Edge currentEdge = (Edge) edges.next();
		Vertex nextVertex = currentEdge.getDest();
		
		if(!nextVertex.isVisited()) {
		    nextVertex.visit();
		    toDo.put(nextVertex);
		    path.put(nextVertex);
		}
	    }

	}
	
	return path;

    }
   
    public SeqStructure getDFS(Object origin) {
	
	resetVerticies();
	SeqStructure toDo = new StackAsList();
	SeqStructure path = new QueueAsList();
	 
	Vertex originVertex = (Vertex)verticies.get(origin);
	originVertex.visit();
	toDo.put(originVertex);
	path.put(originVertex);

	while(!toDo.isEmpty()) {
	    // take top of stack, but might have to put it back if it terminates:
	    Vertex currentVertex = (Vertex)toDo.get();

	    // try to find unvisited neighbor:
	    Iterator edges = currentVertex.getEdgeIterator();
	    boolean found = false;
	    Vertex nextVertex = null;
	    while (!found && edges.hasNext()) {
		Edge currentEdge = (Edge) edges.next();
		Vertex trialVertex = currentEdge.getDest();
		if(!trialVertex.isVisited()) {
		    found = true;
		    nextVertex = trialVertex;
		}
	    }
	    
	    // unvisited vertex found! visit vertex and record doing so:
	    // otherwise, we leave currentVertex removed from stack because it had no unvisited neighbors
	    if (nextVertex != null) {
		toDo.put(currentVertex); // put currentVertex back because path didn't terminate here
		nextVertex.visit();
		toDo.put(nextVertex); // next node to process
		path.put(nextVertex); // save path
	    }
	}

	return path;

    }

    public boolean search(Object o) {
	if (verticies.get(o)==null)
	    return false;
	return true;
    }
	
    public SeqStructure unweightedShortestPath(Object origin,Object end) {
	
	resetVerticies();
	boolean done = false;
	SeqStructure toDo = new QueueAsList();
	SeqStructure path = new StackAsList();
	
	Vertex originVertex = (Vertex)verticies.get(origin);
	Vertex endVertex = (Vertex)verticies.get(end);
	originVertex.visit();
	toDo.put(originVertex);

	while(!done && !toDo.isEmpty()) {
	    Vertex currentVertex = (Vertex)toDo.get();

	    for (Iterator edges = currentVertex.getEdgeIterator(); !done && edges.hasNext(); ) {
		Edge currentEdge = (Edge) edges.next();
		Vertex nextVertex = currentEdge.getDest();
		
		if(!nextVertex.isVisited()) {
		    nextVertex.visit();
		    nextVertex.setCost(1+currentVertex.getCost());
		    nextVertex.setPrev(currentVertex);
		    toDo.put(nextVertex);
		}

		if (nextVertex.equals(endVertex))
		    done = true;
		
	    } // end for
	    
	} // end while

	path.put(endVertex);
	while(endVertex.hasPrev()) {	
	    endVertex = endVertex.getPrev();
	    path.put(endVertex);
	}
	
	return path;

    }



}