//
// This is a Pure List, of integers. 
// 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.
//

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));
    }
    //
    // get the length of the list l
    //

    public static int sum(List l){
	if (l == null) return 0;
	else return head(l) + sum(tail(l));
    }
    //
    // give sum total of values in the list
    //

    public static boolean exists(int e,List l){
	return l != null && (head(l) == e || exists(e,tail(l)));
    }
    //
    // does integer e exist in the list?
    //

    public static List reverse(List l){
	if (l == null) return null;
	else return reverse(l,null);
    }
    //
    // deliver a new list, the reversal of l
    //

    private 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)));
    }
    //
    // deliver a new list, the list l with
    // all values e deleted
    //

    //
    // IMPLEMENT ME
    //
    public static int count(int e,List l){
	if (l == null) return 0;
	if (head(l) == e) return 1 + count(e,tail(l));
	return count(e,tail(l));
    }
    //
    // deliver an integer result, the number of times e occurs in l
    //

    //
    // IMPLEMENT ME
    //
    public static boolean equal(List l1,List l2){
	return (l1 == null && l2 == null) ||
	       (l1 != null && l2 != null && 
		head(l1) == head(l2) && 
		equal(tail(l1),tail(l2)));
    }
    //
    // are lists l1 and l2 equal? That is, do they contain
    // the same data in the same order?
    //

    //
    // IMPLEMENT ME
    //
    public static int nth(int n,List l) throws ListException {
	if (l == null) throw new ListException("empty list");
	if (n == 0) return head(l);
	return nth(n-1,tail(l));
    }
    //
    // return the nth element of the list, where first element is in
    // position 0. Throw an exception if list is empty or n is beyond length 
    // of the list
    //

    //
    // IMPLEMENT ME
    //
    public static List insert(int e,List l){
	if (l == null) return new List(e,null);
	if (e < head(l)) return new List(e,l);
	return new List(head(l),insert(e,tail(l)));
    }	    
    //
    // deliver a new list that has e inserted into l in 
    // non-decreasing order
    //

    //
    // IMPLEMENT ME
    //
    public static List insertionSort(List l){
	if (l == null) return null;
	return insert(head(l),insertionSort(tail(l)));
    }
    //
    // Using an insertion sort, deliver a new list
    // corresponding to l sorted in non-decreasing order
    // i.e. use insert above
    // 

    //
    // IMPLEMENT ME
    //
    public static List append(List l1,List l2){
	if (l1 == null) return l2;
	return new List(head(l1),append(tail(l1),l2));
    }
    //
    // deliver a new list that contains all the elements
    // of l1 with the current list l2 appended to the end
    // i.e. l2 is not copied, just pointed to
    //

    //
    // IMPLEMENT ME
    //
    public static int max(List l) throws ListException {
	if (l == null) throw new ListException("empty list");
	if (tail(l) == null) return head(l);
	return Math.max(head(l),max(tail(l)));
    }
    //
    // deliver the largest integer in the list
    // if the list is empty throw an exception
    //

    
    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));
    }

    private static List merge(List l1,List l2){
	if (l1 == null) return l2;
	if (l2 == null) return l1;
	if (head(l1) < head(l2)) return new List(head(l1),merge(tail(l1),l2));
	else return new List(head(l2),merge(l1,tail(l2)));
    }

    public static List mergeSort(List l){
	if (l == null || tail(l) == null) return l;
	List L = null;
	List R = null;
	while (l != null){
	    L = new List(head(l),L); 
	    l = tail(l);
	    if (l != null){
		R = new List(head(l),R);
		l = tail(l);
	    }
	}
	return merge(mergeSort(L),mergeSort(R));
    }

    public static List quickSort(List l){
	System.out.println("qsort("+ l +")");
	if (l == null || tail(l) == null) return l;
	List L = null;
	List E = null;
	List G = null;
	int e = head(l);
	while (l != null){
	    if (head(l) < e)  L = new List(head(l),L);
	    if (head(l) == e) E = new List(head(l),E);
	    if (head(l) > e)  G = new List(head(l),G);
	    l = tail(l);
	}
	System.out.println("pivot: "+ e +" L: "+ L +" E: "+ E +" G: "+ G);
	return append(quickSort(L),append(E,quickSort(G)));
    }
	
	
}