import java.util.*;

/**
 * This abstract class represents a Node of the A* algorithm.
 */
public abstract class Node {

    /**
     * nodeCount is the counter for all instances of this class. It is used to
     * assign each instance a unique identifier used in the
     * {@link #distinguishCompare(Node)} method.
     */
    private static long nodeCount = 0;

    /**
     * nodeNum is the "serial number" of this instance, initialized in the
     * constructor using the {@link #nodeCount} value.
     */
    private long nodeNum;

    /**
     * Simple constructor that takes the parent node and the g-value as
     * parameters. It automatically initializes the "serial number" also.
     */
    protected Node(Node parent, double gValue) {
        this.parent = parent;
        this.gValue = gValue;
        nodeNum = nodeCount++;
    }

    /**
     * The parent node. It represents the search state from which we generated
     * the current state.
     */
    private Node parent;

    /**
     * The g-value.
     */
    private double gValue;

    /**
     * This is the cached g+h value, for better performance.
     * 
     * Whenever we need to find the g+h value of this search node, and
     * {@link #useCachedGPlusH} is set to <tt>true</tt>, we'll read the g+h
     * value from this field instead of calculating it.
     */
    private double cachedGPlusH = 0;

    /**
     * This boolean flag will be "true" if g+h has already been evaluated.
     */
    private boolean useCachedGPlusH = false;

    /**
     * Returns the parent node.
     */
    public Node getParent() {
        return parent;
    }

    /**
     * Returns the g-value.
     */
    public double getGValue() {
        return gValue;
    }

    /**
     * Evaluates and returns the g+h value for this node.
     */
    public double evaluateGPlusH() {
        if (useCachedGPlusH) {
            return cachedGPlusH;
        } else {
            cachedGPlusH = evaluateHeuristic() + getGValue();
            useCachedGPlusH = true;
            return cachedGPlusH;
        }
    }

    /**
     * Returns a comparator used to compare nodes when deciding on which to
     * expand next. If one of the nodes has smaller g+h value, it gets expanded
     * first. If both nodes have the same g+h value, the one with bigger g value
     * will get expanded first. If both nodes have the same g value and the same
     * h value, then we need to call {@link #distinguishCompare(Node)} so that
     * we never return 0 for different nodes.
     */
    public Comparator<Node> getComparator() {
        return new Comparator<Node>() {
            /**
             * Returns -1 if the first node should be expanded first, 1 if the
             * second node should be expanded first. 0 is returned if and only
             * if both nodes refer to the same search state, that is, the same
             * instance of {@link Node}.
             * 
             * @param n1
             * @param n2
             * @return
             */
            public int compare(Node n1, Node n2) {
                // TODO: your code here.
                /*
                 * Implementation notes:
                 * See the getComparator method comment.
                 * Useful functions:
                 * 
                 * node.evaluateGPlusH() returns the g+h value of the node
                 * 
                 * node.getGValue() returns the g value of the node.
                 * 
                 * IMPORTANT: if both nodes have the same g and h values, call
                 *     return n1.distinguishCompare(n2) 
                 */
            }

            /**
             * Returns "true" if both pointers refer to the same instance.
             * 
             * @param n1
             * @param n2
             * @return
             */
            public boolean equals(Node n1, Node n2) {
                return n1 == n2;
            }
        };
    }

    /**
     * This abstract method generates the successor states.
     * 
     * @return
     */
    public abstract List<? extends Node> generateChildren();

    /**
     * This abstract method decided whether this search state is the goal state.
     * 
     * @return
     */
    public abstract boolean isGoal();

    /**
     * Evaluates the h-value for this search state.
     * 
     * @return
     */
    public abstract double evaluateHeuristic();

    /**
     * Used to compare nodes with the same g and h values. Should not return 0
     * if the provided node refers to a different search state.
     */
    public int distinguishCompare(Node n) {
        if (nodeNum > n.nodeNum)
            return 1;
        if (nodeNum < n.nodeNum)
            return -1;
        return 0;
    }

    /**
     * Prints out the solution, assuming that this node is the goal node. This
     * default implementation prints all the states from the root one to the
     * goal one and returns the number of states.
     */
    public int printSolution() {
        List<Node> nodes = new ArrayList<Node>();
        Node p = this;
        while (p != null) {
            nodes.add(p);
            p = p.getParent();
        }
        for (int i = nodes.size() - 1; i >= 0; i--) {
            System.out.println(nodes.size() - i - 1 + ":");
            System.out.println(nodes.get(i).toString());
        }
        return nodes.size();
    }
}