import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.HashSet;

/**
 * Generic class that searches for paths within the specified graph.
 *   @author Dave Reed
 *   @version 11/11/11
 */
public class PathFinder<E> {
    private AdjacencyGraph<E> graph;

    public PathFinder(AdjacencyGraph<E> graph) {
        this.graph = graph;
    }

    public List<E> findDepth1(E startItem, E endItem) {
        if (startItem.equals(endItem)) {
            List<E> startPath = new ArrayList<E>();
            startPath.add(startItem);
            return startPath;
        }
        else {
            for (E adjItem : this.graph.adjacencies(startItem)) {
                List<E> restPath = findDepth1(adjItem, endItem);
                if (restPath != null) {
                    restPath.add(0, startItem);
                    return restPath;
                }
	    }
            return null;
	}
    }

    public List<E> findDepth2(E startItem, E endItem) {
        List<E> path = new ArrayList<E>();
        path.add(startItem);
        if (this.findDepth2(path, endItem)) {
            return path;
        }
        else {
            return null;
        }
    }
    private boolean findDepth2(List<E> pathSoFar, E endItem) {
        E lastItemSoFar = pathSoFar.get(pathSoFar.size()-1);
        if (lastItemSoFar.equals(endItem)) {
            return true;
        }
        else {
            for (E adjItem : this.graph.adjacencies(lastItemSoFar)) {
		if (!pathSoFar.contains(adjItem)) {
                    pathSoFar.add(adjItem);
                    if (findDepth2(pathSoFar, endItem)) {
                        return true;
                    }
                    else {
                        pathSoFar.remove(pathSoFar.size()-1);
                    }
		}
	    }
            return false;
	}
    }


    public List<E> findBreadth(E startItem, E endItem) {
        Queue< List<E> > pathQ = new LinkedList< List<E> >();

        List<E> startPath = new ArrayList<E>();
        startPath.add(startItem);
        pathQ.add(startPath);

        HashSet<E> usedItems = new HashSet<E>();
        usedItems.add(startItem);

        while (!pathQ.isEmpty()) {
	    List<E> shortestPath = pathQ.remove();
            
            E lastItem = shortestPath.get(shortestPath.size()-1);
            if (lastItem.equals(endItem)) {
                return shortestPath;
            }
            else {
                for (E adjItem : this.graph.adjacencies(lastItem)) {
		    if (!usedItems.contains(adjItem)) {
			List<E> copy = new ArrayList<E>();
                        copy.addAll(shortestPath);
                        copy.add(adjItem);
			pathQ.add(copy);
                        
                        usedItems.add(adjItem);
		    }
		}
	    }
        }
        return null;
    }

    //////////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        AdjacencyGraph<String> words = new DictionaryGraph("dictionary.txt");
        PathFinder finder = new PathFinder(words);
        System.out.println(finder.findDepth2("white", "whale"));
        System.out.println(finder.findBreadth("white", "whale"));
    }
}