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

/**
 * Adjacency List implementation of a directed graph.
 *   @param <E> 
 *   @author Dave Reed
 *   @version 8/1/24
 */
public class DiGraphList<E> implements Graph<E>{
    private Map<E, Set<E>> adjLists;
    
    /**
     * Constructs a directed graph with the specified edges.
     *   @param edges the list of edges (vertex pairs)
     */
    public DiGraphList(List<Pair<E, E>> edges) {
        this.adjLists = new HashMap<E, Set<E>>();
        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) {
        if (!this.adjLists.containsKey(v1)) {     
            this.adjLists.put(v1, new HashSet<E>());
        }
        this.adjLists.get(v1).add(v2);         
    }
    
    /**
     * Determines whether the two vertices are adjacent.
     *   @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) {
        return this.adjLists.containsKey(v1) && this.getAllAdjacent(v1).contains(v2);
    }
    
    /**
     * 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) {
        if (!this.adjLists.containsKey(v)) {  
            return new HashSet<E>();
        }
        return this.adjLists.get(v);
    }

    ////////////////////////////////////////////////////////////////////////////
    
    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 DiGraphList<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"));
    }
}