/*
    DemoQuickSort.java
    CIS 260
    David Klick
    2016-03-24

    This program demonstrates a recursive Quicksort that can handle 
    any data type implementing Comparable. It includes a couple of
    classes used to demonstrate how such objects are sorted.
*/

class Person implements Comparable<Person> {
    private String firstName, lastName;
    public Person(String fn, String ln) {
        firstName = fn;
        lastName = ln;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (firstName.length() > 0) {
            sb.append(Character.toLowerCase(firstName.charAt(0)));
        }
        sb.append(lastName.toLowerCase());
        if (sb.length() > 7) sb.setLength(7);
        return sb.toString();
    }
    @Override
    public int compareTo(Person p) {
        int order = lastName.compareToIgnoreCase(p.lastName);
        if (order != 0) return order;
        return firstName.compareToIgnoreCase(p.firstName);
    }
}

class Teacher extends Person {
    private int id;
    public Teacher(String fn, String ln, int id) {
        super(fn, ln);
        this.id = id;
    }
}

public class DemoQuickSort {
    private static <T extends Comparable<? super T>> void quicksort(T[] ar) {
        qsort(ar, 0, ar.length-1);
    }
    
    private static <T extends Comparable<? super T>> void qsort(T[] ar, int left, int right) {
        int lptr = left;
        int rptr = right;
        
        int midpt = (left+right) / 2;
        swap(ar, left, midpt);
        
        T pivot = ar[lptr];
        
        while (lptr < rptr) {
            while ((ar[rptr].compareTo(pivot) >= 0) && (lptr < rptr)) rptr--;
            if (lptr != rptr) ar[lptr++] = ar[rptr];
            while ((ar[lptr].compareTo(pivot) <= 0) && (lptr < rptr)) lptr++;
            if (lptr != rptr) ar[rptr--] = ar[lptr];
        }
        ar[lptr] = pivot;
        if (left < lptr-1) qsort(ar, left, lptr-1);
        if (right > lptr+1) qsort(ar, lptr+1, right);
    }
    
    private static <T extends Comparable<? super T>> void swap(T[] ar, int pos1, int pos2) {
        // Swaps two array elements
        T temp = ar[pos1];
        ar[pos1] = ar[pos2];
        ar[pos2] = temp;
    }
    
    private static <T extends Comparable<? super T>> void display(T[] ar) {
        // Displays an int array with 8 columns per number
        for (T obj : ar) System.out.printf("%8s", obj.toString());
        System.out.println();
    }
    
    private static <T extends Comparable<? super T>> boolean isSorted(T[] ar) {
        // Returns true if array is in ascending order
        // Returns false if array is not in ascending order
        for (int pos=0; pos<ar.length-1; pos++) {
            if (ar[pos].compareTo(ar[pos+1]) > 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        // Create an array of objects
        Person[] a = {
            new Person("Yonny", "Garcia"),
            new Person("Monica", "Martinez"),
            new Person("Micah", "Huff"),
            new Person("Chris", "Trinh"),
            new Person("John", "Jack"),
            new Teacher("Dave", "Klick", 16),
            new Person("Jordon", "Hill") };
            
        // Display the unsorted array
        display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
        
        // Sort and then display sorted array
        System.out.println("\nSorting");
        quicksort(a);
        
        // Display the sorted array
        display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
    }
}