/* Various sorting algorithms (and further examples of recursion).

   This program implements mergesort and quicksort.  Another procedure
   called swapsort, is also given for comparison.  The most important point
   to note is that mergesort can and is implemented recursively, because
   the depth of recursion is bounded by log(n).  However, although quicksort
   is described as a recursive algorithm, it is not implemented using
   recursion because the worst-case depth of recursion is O(n), which means
   that it can overflow the runtime stack. 

           Worst Time     Average Time     Worst Stack   Extra Memory

Swapsort    O(n*n)         O(n*n)           O(1)          O(1)
Quicksort   O(n*n)         O(n*log n)       O(n)          O(1)
Mergesort   O(n*log n)     O(n*log n)       O(log n)      O(n)

An interface (type) T that extends Comparable<T> means given a value n
of type T, we can call n.compareTo(T m), which returns an int.  The
returned integer is 0 if n and m are considered "equal".  The integer
is negative if n is considered "less than" m, and the integer is
positive if n is considered "greater than" m.  T in the following
class is called a "generic" type variable.  It's similar to template
variables in C++, but C++ does not allow you to constrain T like in
Java (at least not at compile time).  Many built-in java clasess, such
as String, already implement this interface.  For each numeric type
int, long, double, etc, there's also a corresponding reference (object)
type Integer, Long, Double, etc.  These types also implement Comparable.

-------------

I've added another twist since this program was originally written:
the Comparable interface allows objects to be compared, but it's not
so easy to change the comparison algorithm dynamically (at runtime) 
using this interface.  For example, if you write something like

class student implements Comparable<student>
{
    String name;
    int id;
    public int compareTo(student x) { return this.id - x.id; }
    // boring stuff skipped...
}

You are locked into comparing student objects by their id, and in
increasing order (x<y if x.compareTo(y)<0), unless you override
compareTo in a subclass.  But what if you want more flexibility to
change at any time the comparison method so you can use the name or
some other criteria to determine the ordering, and in increasing or
decreasing order?  The java.util.Comparator interface is designed for
that purpose. This interface is defined as

  public interface Comparator<T>
  {
   int compare(T x, T y);    // should observe requirements of compareTo
  }

On the surface it doesn't look too different from Comparable, but
it allows you to create comparator objects independently of the
data objects (student) that are being compared. Given student objects 
x and y, in order to compare them you need to create a class that implements
the Comparator<student> interface, and an instance of it, then call the
compare(x,y) on this instance:

class idcmp implements Comparator<student>
{
   public int compare(student x, student y)
   {  return x.id - y.id; }
}
class namecmp implements Comparator<student>
{
   public int compare(student x, student y)
   {  return x.name.compareTo(y.name); //use .compareTo for Strings
   } 
}
Now you can declare an instance variable that can either be an idcmp object,
or a namecmp object:

Comparator<student> cmp = new idcmp(); // creates idcmp object
...
cmp = new namecmp(); // change comparator to compare names instead.

To compare two (student) objects x and y, instead of calling x.compareTo(y)
you would call cmp.compare(x,y).  The compare function should return an
integer that observes the same requirements as x.compareTo(y).  

/////////// LAMBDA EXPRESSIONS

To simply the creation of a class and an instance of it, Java allows a
limited form of *lambda expressions*.  These expressions are inlined functions
that exist in most modern languages, and Java's support for them is rather
new and *limited to interfaces that contain a single function specification*.
That is, with interfaces such as Comparator, which contains a single 
specification for  int compare(T x, Ty), you can create a class that
implements the interface as well as an instance of it "on the fly":

Comparator<student> cmp = (x,y) -> x.id - y.id;  // compare ids
cmp = (x,y) -> x.name.compareTo(y.name);  // change to comparing names
cmp = (x,y) -> y.id - x.id;  // switch to decreasing order on ids

The java compiler will figure out from the syntax of a lambda expression
how a new class and instantance of Comparator is to be created.

I've changed the rsorts class to allow this flexibility.  The class still
requires a type that is consistent with Comparable so we can create a
default Comparator class.

The use of lambda expressions is demonstrated in main.
*/

import java.util.Comparator;

public class rsorts<T extends Comparable<? super T>>
{
    protected T[] A; //    array to be sorted
    protected Comparator<T> cmp; // comparator

    class defaultcomparator implements Comparator<T>
    {
	public int compare(T x, T y)
        { return x.compareTo(y);} //default is consistent with Comparable
    }

    public rsorts(T[] init) //constructor
    {   A=init; // A points to external array
	cmp = new defaultcomparator();
    }

    public void setcmp(Comparator<T> c) // change the comparator
    { if (c!=null) cmp = c; }

    // swap sort - O(n*n)  - only given here for comparison
    public void swapsort()
    { 
	for (int i=0;i<A.length-1;i++)
	    {
		// find smallest value starting from i, swap to ith position
		int min = i;
		for(int k=i+1;k<A.length;k++)
		    if (cmp.compare(A[min],A[k])>0) min =k; // A[min]>A[k]
		    //if (A[min].compareTo(A[k])>0) min =k; // previous version
		T tmp = A[min]; A[min]= A[i];  A[i] = tmp;
	    }
    }//swapsort

    public boolean sorted() // check if array is sorted
    {
	for(int i=0;i<A.length-1;i++)
	    if (cmp.compare(A[i],A[i+1])>0) return false;
	return true;
    }//sorted

    ////////////////////////// Mergesort

    protected T[] B;   // extra workspace buffer needed for merging
    protected void msort(int start, int end) // sort to A[start] to A[end-1]
    {
	if (end-start<2) return;
	int mid = (start+end)/2;
	msort(start,mid);
	msort(mid,end);
	merge(start,mid,end);
    }
    protected void merge(int start,int mid,int end)
    {
	int i = start, j=mid; // i indexes left, j indexes right
	int k = start; // indexes workspace
	while (i<mid && j<end)
	    {
		if (cmp.compare(A[i],A[j])<0) B[k++] = A[i++];
		else B[k++] = A[j++];
	    }
	// copy over remainder of left partition
	while (i<mid) B[k++] = A[i++];
	// remainder of right parition can stay in place
	while (k>start) A[--j] = B[--k]; // copy from workspace back to A
    }
    public void mergesort()
    {
	if (B==null) B = (T[]) A.clone();  // create buffer - same size as A
	msort(0,A.length);
    }

    ///////////////////// Quicksort
 
    class qstack   // linked list class for quicksort recursion stack
    {
	int start;
	int end;
	qstack next;
	public qstack(int s, int e, qstack n)
	{start =s; end=e; next = n;}
    }
    // qstack S = null; // empty stack
    // S = new qstack(a,b,S); // push
    // S = S.next;            // pop

    // the pivot is the first value out of order, no pivot means sorted
    protected int findpivot(int start, int end)
    {
	for(int i=start;i<end-1;i++)
	    if (cmp.compare(A[i],A[i+1])>0) return i+1;
	return -1; // no pivot
    }
    protected int partition(T pivot, int start, int end)
    {
	int i = start; // indexes entire partition
	int k = start; // indexes left parition
	while (i<end)
	    {
		if (cmp.compare(A[i],pivot)<=0)
		    {  // swap to left partition
			T tmp = A[k];
			A[k] = A[i];  A[i] = tmp;
			k++;
		    }
		i++;
	    }
	return k; // start of second parition
    }//partition
    
    public void quicksort() // manual "recursion"
    {
	qstack Stack = new qstack(0,A.length,null);
	while (Stack!=null)
	    {
		int start = Stack.start, end = Stack.end;
		Stack = Stack.next;  //pops stack
	        int pi = findpivot(start,end);
		if (pi!=-1) // pivot exists
		    {
			int mid = partition(A[pi],start,end);
			Stack = new qstack(start,mid,Stack); // sort left
			Stack = new qstack(mid,end,Stack);   // sort right
		    }// if pivot exists
	    }// main recursion loop
    }

    public static void main(String[] av)
    {
	int n = 1024;
	if (av.length>0) n = Integer.parseInt(av[0]);
	// Templates (generic) variables can only be instantiated with
	// a reference (object) type: so we use Double instead of double:
	Double[] A = new Double[n];
	for (int i=0;i<n;i++) A[i] =  Math.random(); //(double)n*2-i;
	rsorts<Double> Sorter = new rsorts<Double>(A);
        // Sample useof inlined lambda expression:
        Sorter.setcmp( (x,y) -> y.compareTo(x) ); //sorts in decreasing order
	long t1 = System.currentTimeMillis();
	  //Sorter.swapsort();
	  Sorter.quicksort();
	  //Sorter.mergesort();
	long t2 = System.currentTimeMillis();
	if (!Sorter.sorted()) System.out.println("oops!");
	System.out.println("time to sort = "+(t2-t1)+"ms");
    }//main
}//sorter