/******************************************************************************
    Selection Sort 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;

/** An observable sort of an array of objects using selection sort.  Observers
can monitor the progress of the sort in particular for describing the sort
algorithm through animation.  It is assumed the observers get a copy of the
array and only need to be informed about which array entries are being compared.
and which are being swapped.

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

public class SelectionObs extends SortObservable implements ArraySort {

  public SelectionObs(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 selection sort method.

<P><B>Loop invariant:</B><PRE>
&nbsp;   for i : 0..array.length :: ( sorted(array[0..i-1])
&nbsp;     and for j = i .. arrayLength-1 :: array[i-1] bp array[j] )
</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) {
       Object selected;
       int indexOfSelected;
       
       for (int i = 0 ; i < array.length-1 ; i++) {
           indexOfSelected = i; selected = array[indexOfSelected];
           
           // Loop invariant: for k = i+1 .. j-1 :: selected bp array[k]
       
           for (int j = i + 1 ; j < array.length ; j++) {

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

               if (bp.execute(array[j], selected)) {
                   indexOfSelected = j; selected = array[indexOfSelected];
               }
           }

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

           array[indexOfSelected] = array[i];
           array[i] = selected;
           
           sod.tag[i] = Color.black;
       }
   }
}