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

/**
 * Adjacency Matrix implementation of a directed graph.
 *   @param <E> 
 *   @author Dave Reed
 *   @version 11/25/16
 */
public class DiGraphMatrixMap<E> implements Graph<E>{
    private HashMap<E, HashMap<E, Boolean>> adjMatrix;
    
    /**
     * Constructs an empty directed graph.
     */
    public DiGraphMatrixMap() {
        this.adjMatrix = new HashMap<E, HashMap<E, Boolean>>();
    }

    /**
     * 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 (!adjMatrix.containsKey(v1)) {
            adjMatrix.put(v1, new HashMap<E, Boolean>());
        }
        
        adjMatrix.get(v1).put(v2, true);
    }

    /**
     * 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 (!adjMatrix.containsKey(v)) {
            return new HashSet<E>();
        }
        else {
            return this.adjMatrix.get(v).keySet();
        }
    }

    /**
     * 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.adjMatrix.containsKey(v1) &&
                this.adjMatrix.get(v1).containsKey(v2));
    }
    
   ////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        Graph<String> words = new DiGraphMatrixMap<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"));
    }

}