/****************************************************************************** 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.
@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(); } }