import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;

/**
 * Adjacency List implementation of a directed graph.
 *   @param <E> 
 *   @author Dave Reed
 *   @version 11/18/13
 */
public class DiGraphList<E> implements Graph<E>{
    private Map<E, Set<E>> adjLists;
    
    /**
     * Constructs an empty directed graph.
     */
    public DiGraphList() {
        this.adjLists = new HashMap<E, Set<E>>();
    }
    
    /**
     * Adds an edge to the graph.
     *   @param v1 the vertex at the start of the edge
     *   @param v2 the vertex at the end of the edge
     */
    public void addEdge(E v1, E v2) {
        if (!this.adjLists.containsKey(v1)) {     
            this.adjLists.put(v1, new HashSet<E>());
        }
        this.adjLists.get(v1).add(v2);
    }

    /**
     * Gets all adjacent vertices.
     *   @param v a vertex in the graph
     *   @return a set of all vertices adjacent to v
     */
    public Set<E> getAdj(E v) {
        if (!this.adjLists.containsKey(v)) {  
            return new HashSet<E>();
        }
        return this.adjLists.get(v);
    }

    /**
     * Determines whether the graph contains an edge.
     *   @param v1 the vertex at the start of the edge
     *   @param v2 the vertex at the end of the edge
     *   @return true if v1->v2 edge is in the graph
     */
    public boolean containsEdge(E v1, E v2) {
        return this.adjLists.containsKey(v1) && this.getAdj(v1).contains(v2);
    }

   ////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        Graph<String> words = new DiGraphList<String>();
        words.addEdge("foo", "bar");
        words.addEdge("foo", "biz");
        words.addEdge("bar", "boo");
        words.addEdge("boo", "foo");
        
        System.out.println(words.getAdj("foo"));
        System.out.println(words.getAdj("bar"));
        System.out.println(words.getAdj("biz"));
        System.out.println(words.getAdj("boo"));
        
        System.out.println(words.containsEdge("foo", "biz") + " " +
                           words.containsEdge("foo", "boo"));
    }
}