// Start with review: with rational class, and array of rationals.

/* generic linked lists */

// First explain: Concept of parametric (generic type) and the idea of
// POLYMORPHISM:

class cell<T extends Comparable<T>>
{
    T head;
    cell<T> tail;
    cell(T h, cell<T> t) {head=h; tail=t;}

    // function to add new cell N to end of list
    void addToEnd(T x)
    {
	cell<T> current = this; // front of list
	while (current.tail!=null) current = current.tail;
	current.tail = new cell<T>(x,null);
    } //addToEnd

    int length()
    { if (tail==null) return 1; else return 1+tail.length(); }

    // but what about sum? sorted?
    public boolean sorted()
    {
	boolean answer = true;
	cell<T> current = this;
	while (current.tail!=null && answer)
	    {
		if (current.head.compareTo(current.tail.head)>0) answer =false;
		current = current.tail;
	    }
	return answer;
    }//sorted

    //insert element x in sorted order. This function needs to return a 
    //value because it could change the first cell.
    cell<T> insert(T x)
    {
	if (x.compareTo(this.head)<=0) // insert in front
	    return new cell<T>(x,this);
	// insert x in front of first element it's less or equal to than.
	cell<T> current = this;
	while (current.tail!=null && x.compareTo(current.tail.head)>0)
	    current = current.tail;
	current.tail = new cell<T>(x,current.tail);
	return this; // this is still the first element of the list

	// note: this won't work if I changed current instead of current.tail
    }//insert

}// class cell<T>

// built-in classes Integer, String all implement Comparable

class rational implements Comparable<rational>
{
    int n;
    int d; 
    rational(int a, int b) {n=a; d=b;}
    public int compareTo(rational R)
    {
	return n*R.d - d*R.n;
	    
    }
}//rational


public class genlist08
{
    public static void main(String[] args)
    {
	cell<String> S = new cell<String>("abc",new cell<String>("xyz",null));
	cell<Integer> I = new cell<Integer>(2,new cell<Integer>(6,null));
	S.addToEnd("hello");
	System.out.println(S.length());
	System.out.println(I.length());

	cell<rational> R = new cell<rational>(new rational(1,2),null);
	R.addToEnd(new rational(2,3));

	System.out.println(I.length());
	System.out.println(I.sorted());
	System.out.println(S.sorted());
	System.out.println(R.sorted());
	
    }// main
}

// much more general technique than "operator overloading"