import java.util.*;

/**
 * This class contains a skeleton implementation of the A* algorithm. Its single
 * static method {@link #run} accepts the root node and runs the A* algorithm
 * using that node's methods to generate children, evaluate heuristics, etc.
 * This way, plugging in root nodes of different types, we can run this A* to
 * solve different problems.
 */
public class AStar {

    /**
     * Runs the A* algorithm given the root node. The class of the root node
     * defines the problem that's being solved. The algorithm either prints out
     * the solution (again, the format depends on the class of the root node) or
     * says that there's no solution.
     */
    public static void run(Node rootNode) {
        // TODO: add your code here
        
        /*
         * Implementation notes:
         * 
         * We need our fringe to be some container capable of storing objects
         * of class Node. Furthermore, the container should be ordered and should have
         * an operation of extracting the Node with the smallest g+h value. 
         * There's a class in Java library that suits our needs - TreeSet. So we 
         * create a TreeSet and provide it with the node's comparator like this:
         * 
         * TreeSet<Node> fringe = new TreeSet<Node>(rootNode.getComparator());
         * 
         * Useful operations with the fringe:
         * 
         * fringe.isEmpty() returns true if there're no nodes in the fringe
         * 
         * fringe.add(Node node) will add the node to the fringe
         * 
         * fringe.add(List<Node> nodes) will add all the nodes from the list to the fringe
         * 
         * fringe.first() will return the node with the smallest g+h value currently 
         * in the fringe, without removing the node from the fringe
         * 
         * fringe.remove() will remove the specified node from the fringe
         * 
         * General algorithm:
         * 1. Create an empty fringe, as above
         * 2. Put the root search node to the fringe
         * 3. While fringe is not empty:
         * 4.     Get the first search node from the fringe
         * 5.     Remove that node from the fringe
         * 6.     If that's a goal node, print the solution using node.printSolution()
         * 7.     Otherwise, generate the successor nodes using node.generateChildren
         * 8.     Add all the generated nodes to the fringe
         * 9. If no solution was found, print "No solution found." 
         */
    }
};