/******************************************************************************
Quicksort 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 quicksort.

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

public class QuicksortObs extends SortObservable implements ArraySort {

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

/**
@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 quicksort 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) {
     quicksort(array, 0, array.length-1, bp);
   }
   
   private void quicksort(final Object[] array,
                          final int lowerIndex, final int upperIndex,
                          final BinaryPredicate bp) {     
       if (lowerIndex >= upperIndex) {
           if (lowerIndex == upperIndex) sod.tag[lowerIndex] = Color.black;
           return;
       }
       
       Object pivotValue = array[lowerIndex], tmp;
       int splitIndex = lowerIndex;
       sod.tag[lowerIndex] = Color.magenta;
       
       for (int i = lowerIndex+1 ; i <= upperIndex ; i++) {

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

           if (bp.execute(array[i], pivotValue)) {
               splitIndex++;

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

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


       tmp = array[splitIndex]; array[splitIndex] = pivotValue;
       array[lowerIndex] = tmp;

       if (splitIndex - lowerIndex > upperIndex - splitIndex) {
           quicksort(array, splitIndex+1, upperIndex, bp);
           quicksort(array, lowerIndex, splitIndex-1, bp);
       }
       
      else {
           quicksort(array, lowerIndex, splitIndex-1, bp);
           quicksort(array, splitIndex+1, upperIndex, bp);
      }
   }
}