/*
 * File qsort.pizza
 */

package net.sf.pizzacompiler.examples;


/**
 * The main class for quicksorting arrays.
 *
 * The class is parameterized with the element type of the arrays to
 * be sorted.
 *
 * @author Martin Odersky 96/10/07
 * @author John Maraist 96/11/07
 */
public class QuickSorter<A> {

/**
 * The comparison function
 */
    private (A,A)->boolean less;

/**
 * Creates a new sorter
 * @param less		the comparison function     
 */
    public QuickSorter((A,A)->boolean less) {
	this.less = less;
    }

/**
 * Sorts all elements in array between bounds
 * @param xs		the array to be sorted
 * @param lo		the lower bound
 * @param hi		the upper bound
 */
    private void sort(A[] xs, int lo, int hi) {
        int i = lo;
        int j = hi;
        A pivot = xs[(i+j)/2];
        do {
            while (less(xs[i], pivot)) i++;
            while (less(pivot, xs[j])) j--;
            if (i <= j) {
                A temp = xs[i];
                xs[i] = xs[j];
                xs[j] = temp;
                i++;
                j--;
            }
        } while (i <= j);
        if (lo < j) sort(xs, lo, j);
        if (i < hi) sort(xs, i, hi);
    }

/** sorts array
 * @param xs		the array to be sorted
 */
    public void sort(A[] xs) {
	if (xs.length > 1) sort(xs, 0, xs.length-1);
    }

/** static method to sort an array with a given comparison functon
 * @param xs		the array to be sorted
 * @param less		the comparison function
 *
 * This method is executed in two steps.  We first create an object
 * of the class for the particular sorting function, and then call 
 * the sort method for a particular array.
 * 
 */
    public static <B> void sort(B[] xs, (B,B)->boolean less) {
	new QuickSorter(less).sort(xs);
    }
}

class QuickSortTest {

    static boolean less(String x, String y) {
	return x.compareTo(y) < 0;
    }

    static boolean greater(String x, String y) {
	return x.compareTo(y) > 0;
    }

    static void showArray(String[] a) {
        for (int i=0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }   

    public static void main(String[] argv) {
	System.out.print("The original array:    ");
	showArray(argv);

	QuickSorter<String> q = new QuickSorter(less);
	q.sort(argv);
	System.out.print("Sorted small first:    ");
        showArray(argv);

	QuickSorter.sort(argv, greater);
	System.out.print("Sorted big first:      ");
        showArray(argv);

	q.sort(argv);
	System.out.print("Resorted small first:  ");
        showArray(argv);
    }
}