import java.io.IOException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Random;
 
/**
 * 
 */
 
/**
 * @author Roger
 *
 */
public class MyQuickSort {
 
    /**
     * @param args
     */
    public static void main(String[] args) throws IOException {
        String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt", 
                "twain3.txt", "twain.txt", "eliot.txt", "tolstoy.txt" };
        //String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt"};
 
        MyQuickSort sort = new MyQuickSort();
 
        SimpleDateFormat format =
            new SimpleDateFormat("EEE MMM dd HH:mm:ss-SSS zzz yyyy");
        String[] sortTest = null;
        String[] suckySortTest = null;
 
        System.out.println("---------TEST QUICK SORT ------------");
        for (int x = 0; x < files.length; x++) {
            String[] testCase = MergeTest.readFile(files[x]);
 
            long start = System.currentTimeMillis();
            Date now = new Date(start);
            System.out.println("File: " + files[x]);
            System.out.println("Total words: " + testCase.length);
            System.out.println("begin test: " + format.format(now));    
 
            sortTest = sort.quickSort(testCase, 0, testCase.length-1);
 
            long end = System.currentTimeMillis();
            now = new Date(end);
            System.out.println("end test: " + format.format(now));
            System.out.println("total time: " + (end - start));
            System.out.println("--------------------------\n\n");
 
            // Make it suck...
            String[] reverseTest = new String[sortTest.length];
            for (int i = sortTest.length - 1, j = 0; i >= 0; i--, j++) {
                reverseTest[j] = sortTest[i];
            }
 
            start = System.currentTimeMillis();
            now = new Date(start);
            System.out.println("-------SUCKY VERSION----------");
            System.out.println("File: " + files[x]);
            System.out.println("Total words: " + testCase.length);
            System.out.println("begin test: " + format.format(now));
 
            suckySortTest = sort.quickSort(testCase, 0, testCase.length-1);
 
            end = System.currentTimeMillis();
            now = new Date(end);
            System.out.println("end test: " + format.format(now));
            System.out.println("total time: " + (end - start));
            System.out.println("--------------------------\n\n");
        }
 
 
        //for (int i = 0; i < sortTest.length; i++) {
        //    System.out.println(sortTest[i]);
        //}
 
    }
 
    private String[] quickSort(String[] list, int low, int high) {
        if (high <= low) return list;
        //int pivot =  partition(list, low, high);
        int pivot =  nonSuckyPartition(list, low, high);
        quickSort(list, low, pivot-1);
        quickSort(list, pivot+1, high);
 
        return list;
    }
 
    /**
     * Sucky version of partition -- it uses the first element as the partition.
     * @param list
     * @param low
     * @param high
     * @return
     */
    private int partition(String[] list, int low, int high) {
        int i = low - 1;
        int j = high;
        while (i < high) {
            while (list[++i].compareTo(list[high]) < 0) ; // do nothing
            while (list[high].compareTo(list[--j]) < 0) {
                if (j == low) break;
            }
            if (i >= j) break;
            swap(list, i, j);
        }
        swap(list, i, high);
        return i;
    }
 
    private int nonSuckyPartition(String[] list, int low, int high) {
        int i = low - 1;
        int j = high;
        int partition = randomizeInRange(low, high);
        while (i < high) {
            while (list[++i].compareTo(list[partition]) < 0) ; // do nothing
            while (list[partition].compareTo(list[--j]) < 0) {
                if (j == low) break;
            }
            if (i >= j) break;
            swap(list, i, j);
        }
        swap(list, i, high);
        return i;
    }
 
    private void swap(String[] list, int i, int j) {
        String swap = list[i];
        list[i] = list[j];
        list[j] = swap;
    }
 
    private int randomizeInRange(int low, int high) {
        assert (low < high);
        int retval = 0;
        Random rand = new Random();
        // get the range value
        long range = (long)high - (long)low + 1;
        long fraction = (long)(range * rand.nextDouble());
        retval = (int)(fraction + low);
 
        return retval;
    }
 
 
}