// version of CList class that contains sorting procedures.

/*
This slight enhancement of the original sorting program
uses the java.util.Comparator interface in addition to the Comparable
interface.  This makes it easier to change the comparison method.  For
example, we want our sorting algorithms to sort increasing or descending
order by just changing the comparator.

interface Comparator<T>
{
   int compare(T x, T y);  
}

Given a Comparator<T> object cmt and two T objects a and b, cmt.compare(a,b)
can replace a.compareTo(b).  This allows us to separate the comparison method
from the data structure (String, student, gasStation, etc).

The program below still requires that interface T extends Comparable<T>,
but uses a Comparator object instead.  It sets the default Comparator
object to use the native .compareTo method of type T.  However, this
can be changed with the setComparator function.

This code also made some of the sorting methods more subtle: the 
sorting methods (or any method) that constructed new lists must make
sure that the new lists are using the correct comparator by copying it over.
*/

import java.util.Comparator;

public class CList<T extends Comparable<T>> extends LinkedList<T>
{

    class defaultcmt implements Comparator<T>
    {
	public int compare(T x, T y)
	{ if (x!=null) return x.compareTo(y);
	    else return -1 * y.compareTo(x);
	}
    }// inner default comparator

    protected Comparator<T> cmt;
    public CList() 
	{ 
	    super();  // call superclass constructor
	    cmt= (x,y)->x.compareTo(y);  // sets default comparator
	    //	    cmt = new defaultcmt();  more verbose form
	}
    // convenient way to call cmt.compare(x,y):
    protected int cmp(T x, T y) { return cmt.compare(x,y); }

    public void setComparator(Comparator<T> c)  // change comparator
    { if (c!=null) cmt=c; }
    public void invertComparator()
    {
	Comparator<T> c = cmt; // current comparator
	cmt = (x,y)->(c.compare(x,y) * -1);
    }

    // inherit pop and peek, which returns smallest value
    // inherit get and delete, which keep list sorted.
    public void insertAt(int i, T x)
    { throw new RuntimeException("illegal op on sorted list"); }

    public void orderInsert(T x) // override to add in sorted order
    {
	size++;
	if (size==1) {first=last = new node(x); return; }
	if (cmp(x,first.item)<=0) // push in front
	    { first = new node(x,first); return; }
	node current = first;
	// find node before insertion point:
	while (current!=last && cmp(x, current.next.item)>=0) 
	    current=current.next;
	current.next = new node(x,current.next);
	if (current==last) last = current.next;
    }//orderInsert

    public CList<T> isort()  // insertion sort, constructive
    {
	CList<T> S = new CList<T>(); // sorted list
	S.cmt = this.cmt; // use same comparator
	for(T x:this) S.orderInsert(x);
	return S;
    }
    
    public boolean sorted() // determines if list is sorted
    {
	if (size()<2) return true;
	for(node i=first;i!=last;i=i.next)
	    if (cmp(i.item, i.next.item)>0) return false;
	return true;
    }

    /////////////////////// MERGESORT ////////////////////////
    public CList<T> convert(LinkedList<T> L)  // typecast to CList
    {
	if (L==null) return null;
	CList<T> M = new CList<T>();
	M.size = L.size;  M.first=L.first;  M.last=L.last;
	return M;
    }

    // internal procedure operates directly on node lists
    protected CList<T> msort() // (constructive, AND destructive)
    {
	if (size<2) return this; // nothing to sort
	CList<T> right = convert(this.split(size/2));  // split into two
	right.cmt = this.cmt;  // important!
	CList<T> left = this;
	left = left.msort();          // recursively sort left partition
	right = right.msort();        // recursively sort right partition
	// stitch them together (merge)
	left.last.next = right.last.next = null;
	CList<T> S = new CList<T>();  // new list to be created
	node i = left.first, j = right.first;  // pointer into each list
	while (i!=null && j!=null)
	    {
		if (cmp(i.item, j.item)<=0)
		      { S.add(i.item);  i=i.next; }
		else  { S.add(j.item);  j=j.next; }
	    }
	// add remainder to S also:
	for(;i!=null;i=i.next) S.add(i.item);
	for(;j!=null;j=j.next) S.add(j.item);
	return S;
    }
    // destructive public interface
    public void mergesort()
    {
	CList<T> S = this.msort();
	first = S.first;  last = S.last;
	size = S.size;
    }
    

    /////////////////////////////////////////////////////////////
    ///// In-place (destructive) Quicksort using O(1) extra space.

    // find pivot node, null if list already sorted, returns first
    // node out of order: if not-null, list can be partitioned into
    // two non-empty portions.
    protected node findpivot(node start, node end)
    {
	if (start==null || end==null || start==end) return null;
	node current = start;
	while (current != end)
	    {
		if (cmp(current.next.item, current.item)<0)
		return current.next;
	      current = current.next;
	    }
	return null;
    }//findpivot

    // partition into two parts, <= and >, returns last node of first partition
    protected node partition(T pivot,node start, node end)
    {
	node i = start; // go through each element
	// create dummy node to simplify code
	node k = new node(null,start); // end of 1st partition, k.next=next slot
	while (i != end.next)
	    {
		if (cmp(i.item,pivot)<=0) // swap to left partition
		    {
			k = k.next; // advance k before swap (choice)
			T tmp = k.item;
			k.item = i.item;
			i.item = tmp;
		    }
		i = i.next;
	    }//while
	return k;
    }//partition
    // this partition function function only works with above findpivot

    // because depth of recursion is worst case O(n), quicksort must 
    // use its own stack data structure to simulate recursion...
    public void quicksort()
    {
	if (size()<2) return;  // already sorted
	// manual recursion stack
	LinkedList<node> Stack = new LinkedList<node>();
	// push last and first node of sorting partition onto stack
	Stack.push(last);   Stack.push(first);
	while (Stack.size()>1)
	    {
		node start = Stack.pop();
		node end = Stack.pop();
		node pivnode = findpivot(start,end);
		if (pivnode!=null)
		  {
		    node endfirst = partition(pivnode.item,start,end);
		    // push new partitions on top of stack, end, start,
		    // simulates recursive calls
		    Stack.push(end);   Stack.push(endfirst.next);
		    Stack.push(endfirst);  Stack.push(start);
		  }
	    }//recursion loop
    }//quicksort
    
    public static void main(String[] av)
    {
	int n = 1000;
	if (av.length>0) n = Integer.parseInt(av[0]);
	CList<Double> M = new CList<Double>();  // list of floats to sort
	for(int i=0;i<n;i++) M.add(Math.random()*n);

	M.invertComparator(); // sort in decreasing order

	System.out.println("sorting "+n+" values...");
	long t1 = System.currentTimeMillis();
	//	M = M.isort();
	      M.mergesort();
        //	M.quicksort();
	long t2 = System.currentTimeMillis();	
	//	System.out.println(M);
	System.out.println(M.sorted());
	System.out.println("approx time to sort: "+ (t2-t1)+"ms");
    }
}//CList - comparable or sorted list