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

    This program demonstrates heapsort for an array of any
    data type that implements Comparable.
*/

public class DemoHeapSortG {
    // 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
        java.util.Random rnd = new java.util.Random();
        Integer[] a = new Integer[10000000];
        for (int i=0; i<a.length; i++) a[i] = rnd.nextInt(10000);
        
        // Display the unsorted array if not too large
        if (a.length <= 1000) display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
        
        // Sort the array
        System.out.println("\nSorting");
        heapsort(a);

        // Display the sorted array if not too large
        if (a.length <= 1000) display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
    }
}