package graph;
import java.util.*;

/**
 * Represents a Graph G = (V,E), where V is a set of vertices and E is a set
 * of edges between the vertices.
 */

/*
 * TERMS OF USE: This Graph class for vertices of type T is essentially undocumented.
 * You are free to use and modify this for your CSE132 lab, but you must
 * add the required documentation for all methods.
 */

public class Graph<T> implements Iterable<T> {
	Map<T,HashSet<T>> out = new HashMap<T,HashSet<T>>();
	Map<T,HashSet<T>> in = new HashMap<T,HashSet<T>>();
	
	/*
	 * Representation Invariant:
	 * For all v1 and v2, out.get(v1).contains(v2) iff in.get(v2).contains(v1).
	 * 
	 * Abstraction Function for Graph g:
	 * AF(g) = (V,E), where
	 *    V = { v : g.out.containsKey(v) } and
	 *    E = { (v1,v2) : g.out.get(v1).contains(v2) }.
	 */
	
	public void addVertex(T v) {
		if (!containsVertex(v)) {
			out.put(v, new HashSet<T>());
			in.put(v, new HashSet<T>());
		}
	}
	
	public boolean containsVertex(T v) {
		return out.containsKey(v);
	}
	
	public void removeVertex(T v) throws NoSuchElementException {
		for (T neighbor : out.get(v))
			in.get(neighbor).remove(v);
		for (T neighbor : in.get(v))
			out.get(neighbor).remove(v);
		out.remove(v);
		in.remove(v);
	}
	
	public void addEdge(T from, T to) {
		addVertex(from);
		addVertex(to);
		out.get(from).add(to);
		in.get(to).add(from);
	}
	
	public boolean containsEdge(T from, T to) throws NoSuchElementException {
		return out.get(from).contains(to);
	}
	
	public void removeEdge(T from, T to) throws NoSuchElementException {
		out.get(from).remove(to);
		in.get(to).remove(from);
	}
	
	public void visitAll(Visitor<T> agent) {
		for (T x : this)
			agent.visit(x);
	}
	
	public void visitDepthFirst(Visitor<T> agent) throws CycleException {
		HashSet<T> visited = new HashSet<T>();
		LinkedList<T> path  = new LinkedList<T>();
		for (T vertex : this)
			visitDepthFirstHelper(vertex, agent, visited, path);
	}
	
	private void visitDepthFirstHelper(T vertex, Visitor<T> agent, Set<T> visited, LinkedList<T> path) throws CycleException {
		if (!visited.contains(vertex)) {
			if (path.contains(vertex))
				throw new CycleException(path);
			path.addLast(vertex);
			if (out.get(vertex) != null)
				for (T neighbor : out.get(vertex))
					visitDepthFirstHelper(neighbor, agent, visited, path);
			visited.add(vertex);
			agent.visit(vertex);
			path.removeLast();
		}
	}
	
	public NonMutatingIterator<T> edgesFrom(T vertex) throws NoSuchElementException {
		return new NonMutatingIterator<T>(out.get(vertex).iterator());
	}
	
	public NonMutatingIterator<T> edgesTo(T vertex) throws NoSuchElementException {
		return new NonMutatingIterator<T>(in.get(vertex).iterator());
	}
	
	public NonMutatingIterator<T> iterator() {
		return new NonMutatingIterator<T>(out.keySet().iterator());
	}
	
	static class CycleException extends java.lang.Exception {
		List cycle;
		public CycleException(List cycle) {
			super(cycle.toString());
		}
		public List getCycle() { return cycle; }
	}

}