import java.util.*;

public abstract class Pathfinding {
    public static List<Node> BigFreakingSearch(Node start, Node goal){
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> discovered = new HashSet<>();
        HashMap<Node, Node> parents = new HashMap<>();

        queue.add(start);
        discovered.add(start);

        while(!queue.isEmpty()){
            Node v = queue.poll();
            if(v.equals(goal)){
                return returnPath(v, parents);
            }
            for(Node w : v.getNeighbors()){
                if(!discovered.contains(w)){
                    discovered.add(w);
                    parents.put(w, v);
                    queue.add(w);
                }
            }
        }

        return null;
    }

    public static List<Node> DigFreakingSearch(Node start, Node goal){
        Stack<Node> stack = new Stack<>();
        HashSet<Node> discovered = new HashSet<>();
        HashMap<Node, Node> parents = new HashMap<>();

        stack.add(start);
        discovered.add(start);

        while(!stack.isEmpty()){
            Node v = stack.pop();
            discovered.add(v);
            if(v.equals(goal)){
                return returnPath(v, parents);
            }
            for(Node w : v.getNeighbors()){
                if(!discovered.contains(w)){
                    parents.put(w, v);
                    stack.add(w);
                }
            }
        }

        return null;
    }

    private static List<Node> returnPath(Node n, HashMap<Node, Node> parents){
        Stack<Node> stack = new Stack<>();
        Node curr = n;
        while(curr!=null){
            stack.push(curr);
            curr = parents.get(curr);
        }
        return Arrays.asList(stack.toArray(new Node[stack.size()]));
    }
}