/******************************************************************************
Mergesort 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 mergesort.

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

public class MergeObs extends SortObservable implements ArraySort {

  public MergeObs(final Object[] array, final Integer[] mergeSpace,
                  final BinaryPredicate bp) {
      super(array, bp);
      this.mergeSpace = mergeSpace;
      for (int i = 0 ; i < array.length ; i++) {
        mergeSpace[i] = new Integer(1);
      }
      mod = new MergeObsData(sortArray.length);
}

/** Scratch space for the sort. */

  public Integer[] mergeSpace;

/**
@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 mergesort method.  Merge sort requires scratch space the same size as
the array to sort which is used to merge subarrays.

@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) {
    if (array.length > 1) 
        mergesort(false, array, mergeSpace, 0, array.length-1, bp);
  }

  private  MergeObsData mod;
   
  private void mergesort(final boolean transfer,
                         final Object[] array,
                         final Object[] mergeSpace,
                         final int lowerIndex, final int upperIndex,
                         final BinaryPredicate bp) {
      if (lowerIndex == upperIndex) {
        if (transfer) {
          move(array, lowerIndex, mergeSpace, lowerIndex, transfer, Color.gray);
         }
      return;
      }
      int mid = (lowerIndex + upperIndex)/2;
      mergesort(!transfer, array, mergeSpace, lowerIndex, mid, bp);
      mergesort(!transfer, array, mergeSpace, mid+1, upperIndex, bp);
      if (transfer)
          merge(array, mergeSpace, lowerIndex, mid, mid+1, upperIndex, bp,
                transfer);
      else
          merge(mergeSpace, array, lowerIndex, mid, mid+1, upperIndex, bp,
                transfer);
  }

/******************************************************************************
Merge from[lowerIndex1 .. upperIndex1] with from[lowerIndex2 .. upperIndex2]
into to[lowerIndex .. upperIndex].
*/

  private void merge(final Object[] from,
                     final Object[] to,
                     final int lowerIndex1, final int upperIndex1,
                     final int lowerIndex2, final int upperIndex2,
                     final BinaryPredicate bp,
                     final boolean transfer) {

    int i = lowerIndex1; // works through from[lowerIndex1 .. upperIndex1]
    int j = lowerIndex2; // works through from[lowerIndex2 .. upperIndex2]
    int k = lowerIndex1; // works through to[lowerIndex1 .. upperIndex2]

    Color mergeColor =
        (upperIndex2 - lowerIndex1 + 1) == to.length ? Color.black : Color.gray;
    
    while (i <= upperIndex1 && j <= upperIndex2) {

      // Comparison -- Added to make the sort observable. >>>>
      setChanged(); mod.swap = false;
      if (transfer) { mod.tag[i] = mod.tag[j] = Color.magenta; }
      else { mod.msTag[i] = mod.msTag[j] = Color.magenta; }
      notifyObservers(mod);
      try { synchronized(this) { wait(); }
      } catch (InterruptedException e) {}
      if (transfer) { mod.tag[i] = mod.tag[j] = Color.gray; }
      else { mod.msTag[i] = mod.msTag[j] = Color.gray; }
      // <<<<
               
      if (bp.execute(from[i], from[j])) {
        move(from, i, to, k, transfer, mergeColor); i++; }
      else { move(from, j, to, k, transfer, mergeColor); j++; }
      k++;
    }
    while (i <= upperIndex1)
        { move(from, i, to, k, transfer, mergeColor); i++; k++; }
    while (j <= upperIndex2)
        { move(from, j, to, k, transfer, mergeColor); j++; k++; }
  }
  
  private void move(Object[] from, int i, Object[] to, int j,
                    boolean transfer, Color mergeColor) { 

      // Move -- Added to make the sort observable. >>>>
      setChanged(); mod.swap = true;
      if (transfer) { mod.tag[i] = Color.cyan; mod.msTag[j] = Color.green; }
      else { mod.msTag[i] = Color.cyan; mod.tag[j] = Color.green; }
      notifyObservers(mod);
      try { synchronized(this) { wait(); }
      } catch (InterruptedException e) {}
      if (transfer) { mod.tag[i] = Color.lightGray; mod.msTag[j] = Color.gray; }
      else { mod.msTag[i] = Color.lightGray; mod.tag[j] = mergeColor; }
      // <<<<
     to[j] = from[i];
  }

//*****************************************************************************

  public void start() {
       mod = new MergeObsData(mergeSpace.length);
       super.start();
  }
}