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/18/13
 */
public class DiGraphMatrix<E> implements Graph<E>{
    private E[] vertices;
    private Map<E, Integer> lookup;
    private boolean[][] adjMatrix;
    
    /**
     * Constructs an empty directed graph.
     */
    public DiGraphMatrix(Collection<E> vertices) {
        this.vertices = (E[])(new Object[vertices.size()]);
        this.lookup = new HashMap<E, Integer>();
        
        int index = 0;
        for (E nextVertex : vertices) {
            this.vertices[index] = nextVertex;
            lookup.put(nextVertex, index);
            index++;
        }
        
        this.adjMatrix = new boolean[index][index];
    }

    /**
     * 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) {
        Integer index1 = this.lookup.get(v1);
        Integer index2 = this.lookup.get(v2);
        if (index1 == null || index2 == null) {
            throw new java.util.NoSuchElementException();
        }
        this.adjMatrix[index1][index2] = 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) {
        int row = this.lookup.get(v);
        
        Set<E> neighbors = new HashSet<E>();
        for (int c = 0; c < this.adjMatrix.length; c++) {
            if (this.adjMatrix[row][c]) {
                neighbors.add(this.vertices[c]);
            }
        }
        return neighbors;
    }

    /**
     * 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) {
        Integer index1 = this.lookup.get(v1);
        Integer index2 = this.lookup.get(v2);
        return index1 != null && index2 != null && 
               this.adjMatrix[index1][index2];
    }
    
   ////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        Set<String> v = new HashSet<String>();
        v.add("foo");
        v.add("bar");
        v.add("biz");
        v.add("boo");
        
        Graph<String> words = new DiGraphMatrix<String>(v);
        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"));
    }

}