/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
/**
 *  Sort an array of <CODE>Object</CODE>s using Quicksort.  This is an
 *  O(n.log(n)) sort except when the data is almost sorted in which
 *  case it O(n^2).
 *
 *  @version 1.1 1999.11.27
 *  @author Russel Winder
 */
public class Quicksort4 {
  /**
   *  The sort operation.
   *
   *  @param a the array to be sorted.
   *  @param cr the <CODE>Comparator</CODE> used to compare the
   *  <CODE>Object</CODE>s during the sort process.
   *  @param ce the <CODE>Comparator</CODE> defining value equality.
   */ 
  public static void sort(final Object[] a,
                          final Comparator cr,
                          final Comparator ce) {
    quicksort(a, 0, a.length-1, cr, ce) ;
  }
  /**
   *  Given the array and two indices, swap the two items in the
   *  array.
   */
  private static void swap(final Object[] a,
                           final int x,
                           final int y) {
    Object temp = a[x] ;
    a[x] = a[y] ;
    a[y] = temp ;
  }
  /**
   *  Partition an array in two using the pivot value that is at the
   *  centre of the array being partitioned.
   *
   *  <P> This partition implementation based on the algorithm in G
   *  Brassard & P Bratley (1988) "Algortihmics: Theory and
   *  Practice", Prentice Hall, p.117.
   *
   *  @param a the array out of which to take a slice.
   *  @param lower the lower bound of this slice.
   *  @param upper the upper bound of this slice.
   *  @param cr the <CODE>Comparator</CODE> to be used to define the
   *  order.
   *  @param ce the <CODE>Comparator</CODE> defining value equality.
   */
  private static int partition(final Object[] a,
                               final int lower,
                               final int upper,
                               final Comparator cr,
                               final Comparator ce) {
    int b = lower ;
    int t = upper+1 ;
    Object pivotValue = a[lower] ;
    do {
      b++ ;
    } while ((cr.relation(a[b], pivotValue) ||
              ce.relation(a[b], pivotValue)) &&
             (b < upper)) ;
    do {
      t-- ;
    } while (cr.relation(pivotValue, a[t])) ;
    while (b < t) {
      swap(a, b, t) ;
      do {
        b++ ;
      } while (cr.relation(a[b], pivotValue) ||
               ce.relation(a[b], pivotValue)) ;
      do {
        t-- ;
      } while (cr.relation(pivotValue, a[t])) ;
    }
    swap(a, lower, t) ;
    return t ;
  }
  /**
   *  The recursive Quicksort function.
   *
   *  @param v the array out of which to take a slice.
   *  @param lower the lower bound of this slice.
   *  @param upper the upper bound of this slice.
   *  @param cr the <CODE>Comparator</CODE> to be used to define the
   *  order.
   *  @param ce the <CODE>Comparator</CODE> defining value equality.
   */
  private static void quicksort(final Object[] a,
                                final int lower,
                                final int upper,
                                final Comparator cr,
                                final Comparator ce) {
    int sliceLength = upper-lower+1 ;
    if (sliceLength > 1) {
      if (sliceLength == 2) {
        if (cr.relation(a[upper], a[lower])) {
          swap (a, lower, upper) ;
        }
      } else {
        int pivotIndex = partition(a, lower, upper, cr, ce) ;
        quicksort(a, lower, pivotIndex-1, cr, ce) ;
        quicksort(a, pivotIndex+1, upper, cr, ce) ;
      }
    }
  }
}