/*
  from single to doubly linked lists
*/


interface list
{
   int length(int ax);  // tail recursive length function
   list insert(int x);  // insert in sorted order
   list enqueue(int x); // add to end of the list, regardless of order
}

class nil implements list
{
    public int length(int ax) { return ax; }
    public list insert(int x)
    { return new cell(x,this); }
    public list enqueue(int x)
    { return new cell(x,this); }
    public String toString() { return "\n"; }
}

class cell implements list
{
    private int head;   
    public list tail;  
    public cell(int h, list t) { head=h;  tail=t; }
    public int length(int ax)
    { return tail.length(ax+1); }
    public list insert(int x)
    { if (x<=head) return new cell(x,this); 
        else {
	       tail = tail.insert(x);
	       return this;
             }
    }
    public list enqueue(int x)  // adds to end of list in O(n) time
    {
	tail = tail.enqueue(x);
	return tail;
    } 
    public String toString()
    { return head+" "+tail.toString(); }
}// cell

///////////////// end of standard java ////// nothing above should change

///////////////// now make it doubly linked, with more efficient enqueue

interface dlist
{
    void previous(cell p); // set previous pointer
}

privileged aspect dlinked
{

    // locally modify inheritance relationship:
    declare parents : list extends dlist;
    
    /*  Why is it not dlist extends list?  Because then the code
        below must refer to dlist, not list, but the tail pointer
	of the structures are lists, not dlists.
    */

    // intertype declaration
    private cell nil.previous = null;
    private cell cell.previous = null;
    public void nil.previous(cell p) { previous = p; }
    public void cell.previous(cell p) { previous = p; }

    // declare a new constructor for nil subclass (not used in this example)
    public nil.new(cell p) { previous = p; }
    
    // modify constructor for cell subclass
    after(cell c, list t) : execution(cell.new(..)) && args(int,t) && target(c)
	{
	    t.previous(c);  // previous is private w/r to the ASPECT!
	}

    // modify enqueue operation into O(1) operation
    list around(list n, int x) : 
	call(* list+.enqueue(int)) && target(n) && args(x) 
	   && if (n instanceof nil)
	{ 
	    System.out.println("more efficient enqueue being executed");
	    cell p = ((nil)n).previous;
	    cell c = new cell(x,n);
	    c.previous = p;
	    if (p!=null) p.tail = c;
	    return c;  // return val is now actually superflous
	}

    // the insert function must also be modified:
    // when tail = tail.insert(x) is called, the calling object (this)
    // may need to be relinked with tail (target object)

    // first we add another method to the cell class:
    private void cell.linktail() { tail.previous(this); }

    // then we call the method with an advice
    after (cell a) : execution(* list.insert(int)) && this(a)
	{
	    a.linktail();
	}

    // print list in reverse by starting at end:
    public static void revprint(nil end)
	{
	    cell i = end.previous;
	    for(;i!=null;i=i.previous) System.out.print(i.head+" ");
	    System.out.print("\n");
	}

} // dlinked

public class linkedlist
{
   public static void main(String[] args)
    {
	list end = new nil();
	list front = new cell(2,new cell(3,new cell(7,new cell(11,end))));
	front = front.insert(5);
	System.out.print(front);
	end.enqueue(13);   // efficient insertion at end of list
	System.out.print(front);
	dlinked.revprint((nil)end);  // print in reverse (confirm links)
    }
}

// so we made a doubly linked list without having to change significantly
// the interface of the original, algebraic list adt.