/* Contains method main to try things on a linked list
*/

public class Main {

	public static void main(String args[]) {
		System.out.println( "Hello World!!!" );
		
	    // Store in b a linked list with values (5,4,3,2,1,0)
		    DoublyLinkedList b= new DoublyLinkedList();
		    
		    ListNode n= b.last(); // b is empty, so n is the head
		    for (int i= 0; i <= 5; i++)
		        {  b.insert(new Integer(i), n);  }
		System.out.println("" + b);
		
		insertionsort(b);
		System.out.println("" + b);
	}
	
    // Perform an insertion sort on b
	public static void insertionsort(DoublyLinkedList b) {
	    ListNode p= b.first();
	    // invariant: p is the name of a node in b (or is the tail).
	    //            The nodes before p are sorted.
	    while (b.isValid(p)) {
	        insert(b,p);
	        p= p.next;
	    }
	}
	
	// The nodes preceding node in list b are sorted. Push n
	// down to its sorted place in b. Precondition: b.isValid(p) 
	public static void insert(DoublyLinkedList b, ListNode n) {
	    ListNode m= n;
	    int p= ((Integer)m.element).intValue();
	    // invariant: value p belongs in node m.
	    //    The nodes following m up to node n are sorted and >= p
	    //    The nodes preceding m are sorted
	    while (b.hasPrec(m) ) {
	        ListNode mprev= b.prev(m);
	        int beforeP= ((Integer)mprev.element).intValue();
	        if (beforeP <= p) {
	            m.element= new Integer(p);
	            return;
	        }
	        m.element= new Integer(beforeP);
	        m= mprev;
	    }
	    m.element= new Integer(p);
	}
    
}