//
// This is a Pure List. It does not use a container. It is simple and powerful
// Downside is that we have to preceed calls with List. in a similar way to
// the Math. package.
//
// This should be compared to the IntList material in Ex1
//

public class List {
    int head;
    List tail;

    public List(int i,List tail){head = i; this.tail = tail;}

    public static int head(List l){return l.head;}
    public static List tail(List l){return l.tail;}

    public static int length(List l){
	if (l == null) return 0;
	else return 1 + length(tail(l));
    }

    public static int sum(List l){
	if (l == null) return 0;
	else return head(l) + sum(tail(l));
    }

    public static boolean exists(int e,List l){
	return l != null && (head(l) == e || exists(e,tail(l)));
    }

    public static List reverse(List l){
	if (l == null) return null;
	else return reverse(l,null);
    }

    public static List reverse(List l1,List l2){
	if (l1 == null) return l2;
	else return reverse(tail(l1),new List(head(l1),l2));
    }				

    public static List delete(int e,List l){
	if (l == null) return null;
	else if (e == head(l)) return delete(e,tail(l));
	else return new List(head(l),delete(e,tail(l)));
    }

    //
    // IMPLEMENT ME
    //
    public static int count(int e,List l){return -999;}

    //
    // IMPLEMENT ME
    //
    public static boolean equal(List l1,List l2){return false;}

    //
    // IMPLEMENT ME
    //
    public static int nth(int n,List l){return -99999;}

    //
    // IMPLEMENT ME
    //
    public static List insert(int e,List l){return l;}

    //
    // IMPLEMENT ME
    //
    public static List sort(List l){return l;}

    //
    // IMPLEMENT ME
    //
    public static List append(List l1,List l2){return l1;}

    //
    // IMPLEMENT ME
    //
    public static int max(List l){return -999;}

    
    public String toString(){return "[" + toString(this) + "]";}

    private String toString(List l){
	if (l == null) return "";
	else if (tail(l) == null) return "" + head(l);
	else return head(l) +","+ toString(tail(l));
    }
}
//
// code the following
//
//  - insert(e,l)   delivers a new list with e inserted in order into l
//  - sort(l)       delivers a new list sorted in non-decreasing order (uses insert)
//  - count(e,l)    delivers the number of times e occurs in l
//  - nth(n,l)      delivers the nth element of the list l (null if empty)
//  - equal(l1,l2)  delivers true if lists l1 and l2 are equal
//  - append(l1,l2) delivers a new list with l2 appended to the end of l1
//  - max(l)        delivers the largest number in the list l (-999 if empty)
//