/******************************************************************************
Heapsort
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.searchAndSort;
import FlexOr.container.*;
import java.lang.reflect.*;

/** Sort an array of objects using heapsort.

<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public class Heapsort implements ArraySort {
  
/**
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public void sort(final Object[] array, final BinaryPredicate bp) {
       execute(array, bp);
   }

/** The heap sort method.

@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public static void execute(final Object[] array, final BinaryPredicate bp) {
     int length = Array.getLength(array);
 
     heapify(array, length-1, bp);


  // Loop invariant: array[i+1 .. length-1] is sorted.
  //             and array[0..i] is a heap
  //             and array[0] is the "biggest" with respect to to bp

     for (int i = length-1 ; i > 0 ; i--) {
       swap(array, 0, i);
       restoreHeapDown(array, 0, i-1, bp);
     }  
  }

/**  Rearrange, if necessary, heap elements to restore the heap property
with respect to <CODE>comparison</CODE>.

<P><PRE><B>Requires:</B> True
<B>Ensure:</B> heap has the heap property.
*/

  private static void heapify(final Object[] heap, final int last,
                              final BinaryPredicate bp) {
    for (int i = last/2 ; i >= 0 ; i-- ) {
      restoreHeapDown(heap, i, last, bp);
    }
  }

/** Percolate down the obj at the root of the current subtree, if it violates
the heap property.

<P><PRE><B>Requires:</B> Subtrees at 2*root and 2*root+1 have the heap
property
<B>Ensures:</B> Heap property holds in the subtree beginning at root.
*/

  private static void restoreHeapDown(final Object[] heap, final int root,
                                      final int last,
                                      final BinaryPredicate bp) {
    int left = 2*root+1;
    if (left > last) return;
    int right = left + 1;
    if (right > last) { // Only a left child exists
        if (bp.execute(heap[left], heap[root])) return;
        else { swap(heap, root, left); return; }
    }
    
    // Both children exist.
    
    if (bp.execute(heap[left], heap[root])) {
        if (bp.execute(heap[right], heap[root])) return;
        else { swap(heap, root, right);
               restoreHeapDown(heap, right, last, bp);
        }
    }
    else {
        if (bp.execute(heap[right], heap[root])) {
            swap(heap, root, left);
            restoreHeapDown(heap, left, last, bp);
        }
        else {
            if (bp.execute(heap[right], heap[left])) {
                swap(heap, root, left);
                restoreHeapDown(heap, left, last, bp);
            }
            else {
                swap(heap, root, right);
                restoreHeapDown(heap, right, last, bp);
            }
        } 
    }
  }

/** Exchange elements heap[a] and heap[b]. */

  private static void swap(Object[] heap, int a, int b) {
    Object tmp;
    tmp = heap[a];  heap[a] = heap[b];  heap[b] = tmp;
  }
 
}   
