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

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author davereed
 */
public class DiGraphMatrix<E> implements Graph<E>{
    private E[] vertices;
    private Map<E, Integer> lookup;
    private boolean[][] adjMatrix;
    
    /**
     * Constructs an empty directed graph.
     *   @param vertices a list of all possible vertices in the graph
     */
    public DiGraphMatrix(List<Pair<E, E>> edges) {
        Set<E> vertexSet = new HashSet<E>();
        for (Pair<E, E> edgePair : edges) {
            vertexSet.add(edgePair.getKey());
            vertexSet.add(edgePair.getValue());
        }
        
        this.vertices = (E[])(new Object[vertexSet.size()]);
        this.lookup = new HashMap<E, Integer>();
        
        int index = 0;
        for (E nextVertex : vertexSet) {
            this.vertices[index] = nextVertex;
            lookup.put(nextVertex, index);
            index++;
        }
        
        this.adjMatrix = new boolean[index][index];
        
        for (Pair<E, E> edgePair : edges) {
            this.addEdge(edgePair.getKey(), edgePair.getValue());           
        }
    }

    /**
     * Helper method that adds an edge to the graph.
     * @param v1 the starting vertex of the edge
     * @param v2 the ending vertex of the edge
     */
    protected void addEdge(E v1, E v2) {
        Integer index1 = this.lookup.get(v1);
        Integer index2 = this.lookup.get(v2);
        if (index1 != null && index2 != null) {
            this.adjMatrix[index1][index2] = true;
        }          
    }
    
    /**
     * 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 isAdjacentTo(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];
    }

    /**
     * Gets all adjacent vertices.
     *   @param v a vertex in the graph
     *   @return a set of all vertices adjacent to v
     */
    public Set<E> getAllAdjacent(E v) {
        Integer row = this.lookup.get(v);
        
        Set<E> neighbors = new HashSet<E>();
        if (row != null) {
            for (int c = 0; c < this.adjMatrix.length; c++) {
                if (this.adjMatrix[row][c]) {
                    neighbors.add(this.vertices[c]);
                }
            }
        }
        return neighbors;
    }

   ////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        List<Pair<String, String>> edges = new ArrayList<Pair<String, String>>();
        edges.add(new Pair<String, String>("foo", "bar"));
        edges.add(new Pair<String, String>("foo", "biz"));
        edges.add(new Pair<String, String>("bar", "boo"));
        edges.add(new Pair<String, String>("boo", "foo"));
        
        Graph<String> words = new DiGraphMatrix<String>(edges);
        
        System.out.println(words.getAllAdjacent("foo"));
        System.out.println(words.getAllAdjacent("bar"));
        System.out.println(words.getAllAdjacent("biz"));
        System.out.println(words.getAllAdjacent("boo"));
        
        System.out.println(words.isAdjacentTo("foo", "biz") + " " +
                           words.isAdjacentTo("foo", "boo"));
    }

}