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

    This program demonstrates heapsort for an array of any
    data type that implements Comparable and includes a
    couple of classes that create objects that can be sorted.
*/

class Person implements Comparable<Person> {
    private String firstName, lastName;
    
    public Person(String fn, String ln) {
        firstName = fn;
        lastName = ln;
    }
    
    // This is just a convenience method for the display routine
    // used by the main program.
    @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 DemoHeapSortG2 {
    // Notes:
    //    left child index = parent index * 2 + 1
    //    right child index = parent index * 2 + 2
    
    private static <T extends Comparable<? super T>> void heapsort(T[] ar) {
        // Max-heapify array
        int len = ar.length;
        int lastHeapElement = len - 1;
        int lastElementWithAChild = (lastHeapElement - 1) / 2; 
        for (int i=lastElementWithAChild; i>=0; i--) siftDown(ar, i, lastHeapElement);
        // Sort the array
        do {
            // Swap the largest item (root) with last item in heap
            swap(ar, 0, lastHeapElement);
            // Reduce the size of the heap by one
            lastHeapElement--;
            // Re-max-heapify what remains of the heap
            siftDown(ar, 0, lastHeapElement);
        } while (lastHeapElement > 0);
    }
    
    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 siftDown(T[] ar, int parentNdx, int endOfHeap) {
        if (parentNdx == endOfHeap) return;
        // The max heap rule is that a parent must not be smaller
        // in value than either of its children.
        while (parentNdx <= (endOfHeap-1)/2) {
            // The parent has at least one child if we got here
            int leftChildNdx = parentNdx * 2 + 1;
            int rightChildNdx = parentNdx * 2 + 2;
            // Assume the left child is the largest child
            int largestChildNdx = leftChildNdx;
            // If there is a right child and it is larger, change largestChildNdx
            if (rightChildNdx <= endOfHeap && ar[rightChildNdx].compareTo(ar[leftChildNdx]) > 0) {
                largestChildNdx = rightChildNdx;
            }
            // Now see if parent is larger than largest child
            if (ar[largestChildNdx].compareTo(ar[parentNdx]) > 0) {
                // Child was larger, so swap and continue sifting
                swap(ar, parentNdx, largestChildNdx);
                parentNdx = largestChildNdx;
            } else {
                // Parent was the largest value, so sifting is done
                break;
            }
        }
    }

    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 random integers
        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");
        heapsort(a);
        
        // Display the sorted array
        display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
    }
}