import java.util.ArrayList;

/**
 * For maintaining lists of T-elements enabling
 * a structure suited for backwards traversal
 * 
 * @author Pieter Koopman, Sjaak Smetsers
 * @author Camil Staps, s4498062
 * 
 * @param <T> The element this node is based on
 */
@SuppressWarnings("Convert2Diamond")    // We disable these warnings for Java <=1.7 compatibility.
public class Node<T extends Comparable> implements Comparable<Node<T>>
{
    // the data field
    private final T item;
    // a reference to the predecessor
    private final Node<T> previous;

    /* A constructor that initializes each node
     * with the specified values
     * @param from the node preceding the current node
     * @param item the initial data item
     */
    public Node (Node<T> from, T item) {
        this.previous    = from;
        this.item        = item;
    }

    /* a getter for the item
     * @return item
     */
    public T getItem() {
        return item;
    }

    /*
     * a getter for the predecessor
     * @return previous
     */
    public Node<T> getPrevious() {
        return previous;
    }

    /*
     * determines the length of the current list
     * @return the length as an integer
     */
    public int length () {
        int length = 1;
        Node<T> prev = previous;
        while ( prev != null ) {
            prev = prev.previous;
            length++;
        }
        return length;
    }
    
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        
        ArrayList<Node<T>> path;
        path = new ArrayList<Node<T>>();
        Node<T> prev = this;
        while ( prev != null ) {
            path.add(prev);
            prev = prev.previous;
        }
        
        for (int i = path.size() - 1; i >= 0; i--)
            result.append(path.size() - i - 1).append(":\n").append(path.get(i).getItem().toString());
        
        return result.toString();
    }
    
    /**
     * Just comparing the items isn't very clever. The Manhattan distance is a fairly small number.
     * With large queues, many nodes will then have the same priority. It's much better to select
     * on both Manhattan distance and path length. That way, we will find shorter paths.
     * Note though that since we're prioritizing on Manhattan distance primarily, this does not 
     * mean that we necessarily find the shortest path.
     * @param t
     * @return 
     */
    @Override
    public int compareTo(Node<T> t) {
        if (this.item.compareTo(t.item) == 0)
            return Integer.compare(length(), t.length());
        return this.item.compareTo(t.item);
    }
}