/******************************************************************************
Heapsort Observable
----------------------------------------------------
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.awt.Color;

/** Sort an array of objects using heapsort.

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

public class HeapsortObs extends SortObservable implements ArraySort {

  public HeapsortObs(final Object[] array, final BinaryPredicate bp) {
      super(array, bp);
  }

/** Comparison to use in restoreHeapDown. */

  private BinaryPredicate bp;

/** Swap location to avoid either passing it or creating a new one on
every swap.  Speeds up the algorith. */

  private Object tmp;
  
/** Pointer to array for swap, or restoreHeapDown, if array elements passed to
swap. */

  private Object[] heap;
  
/**
@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 heapsort method.

<P><B>Loop invariant:</B><PRE> ???
</PRE>

@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public void execute(final Object[] array, final BinaryPredicate bp) {
     int length = array.length;
     this.bp = bp;
     heap = array;
 
     heapify(length-1);
     for (int i = length-1 ; i > 0 ; i--) {
       swapIntoPosition(0, i);
       restoreHeapDown(0,i-1);
     }
  }

/**  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 void heapify(int last) {
    for (int i = last/2 ; i >= 0 ; i-- ) {
      restoreHeapDown(i,last);
    }
  }

/** 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 void restoreHeapDown(int root, int last) {
    int left = 2*root+1;
    if (left > last) return;
    int right = left + 1;
    if (right > last) { // Only a left child exists
        if (compare(left,root)) return;
        else { swap(root,left); return; }
    }
    
    // Both children exist.
    
    if (compare(left, root)) {
        if (compare(right, root)) return;
        else { swap(root, right);
               restoreHeapDown(right, last);
        }
    }
    else {
        if (compare(right, root)) {
            swap(root, left);
            restoreHeapDown(left, last);
        }
        else {
            if (compare(right, left)) {
                swap(root, left);
                restoreHeapDown(left, last);
            }
            else {
                swap(root, right);
                restoreHeapDown(right, last);
            }
        } 
    }
  }

/** Do a comparison. */

  private boolean compare(int a, int b) {

    // Comparison -- Added to make the sort observable. >>>>
    setChanged(); sod.swap = false;
    sod.tag[a] = Color.magenta; sod.tag[b] = Color.magenta;
    notifyObservers(sod);
    try { synchronized(this) { wait(); }
    } catch (InterruptedException e) {}
    sod.tag[a] = Color.gray; sod.tag[b] = Color.gray;
    // <<<<

    return bp.execute(heap[a], heap[b]);
  }
  
/** Exchange elements heap[a] and heap[b]. */

  private void swap(int a, int b) {

           // Swap -- Added to make the sort observable. >>>>
           setChanged(); sod.swap = true;
           sod.tag[a] = Color.cyan; sod.tag[b] = Color.cyan;
           notifyObservers(sod);
           try { synchronized(this) { wait(); }
           } catch (InterruptedException e) {}
           sod.tag[a] = Color.gray; sod.tag[b] = Color.gray;
           // <<<<

    tmp = heap[a];  heap[a] = heap[b];  heap[b] = tmp;
  }

  private void swapIntoPosition(int a, int b) {

           // Swap -- Added to make the sort observable. >>>>
           setChanged(); sod.swap = true;
           sod.tag[a] = Color.cyan; sod.tag[b] = Color.cyan;
           notifyObservers(sod);
           try { synchronized(this) { wait(); }
           } catch (InterruptedException e) {}
           sod.tag[a] = Color.gray; sod.tag[b] = Color.black;
           // <<<<

    tmp = heap[a];  heap[a] = heap[b];  heap[b] = tmp;
  }
 
}