import Array;
import Comparator;
import IncomparableException;
import Sortable;

/**
 * Arrays that can be sorted using the amazing Quicksort routine.  Note
 * that we violate Java's method naming conventions because Quicksort is
 * a proper name.
 *
 * @author Samuel A. Rebelsky (general structure, partition method)
 * @author Mable Mathemagician
 * @author Myron Mathemagician
 * @version 1.1 of October 1999
 */
public class NewQuicksortable
  extends Array
  implements Sortable
{
  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+
  
  /**
   * Build a new sortable array of a particular size.
   */
  public NewQuicksortable(int n) {
    super(n);
  } // NewQuicksortable(int)
  
  /**
   * Build a new sortable array with a particular set of elements. 
   */
  public NewQuicksortable(Object[] elements) {
    super(elements);
  } // NewQuicksortable(Object[])
  
  // +-----------------------+-----------------------------------
  // | Methods from Sortable |
  // +-----------------------+
  
  /**
   * Sort an array using Quicksort.  
   * Pre: All elements in the array can be compared to each other.
   * Post: The array is sorted (using the standard meaning).
   */
  public void sort(Comparator compare) 
    throws IncomparableException
  {
    sort(compare, null);
  } // sort(Object[])

  /**
   * Sort an array using Quicksort.  If observer is non-null,
   * prints out pithy notes about the sorting.
   * Pre: All elements in the array can be compared to each other.
   * Post: The array is sorted (using the standard meaning).
   */
  public void sort(Comparator compare, SimpleOutput observer) 
    throws IncomparableException
  {
    Quicksort(0, size()-1, compare, observer);
  } // sort(Object[])

  // +----------------+------------------------------------------
  // | Helper Methods |
  // +----------------+
  
  /**
   * Sort part of an array using Quicksort.
   * Pre: All elements in the subarray can be compared to each other.
   * Pre: 0 <= lb <= ub < size()
   * Post: The array is sorted (using the standard meaning).
   */
  protected void Quicksort(int lb, int ub, 
                           Comparator compare,
                           SimpleOutput observer) 
    throws IncomparableException
  {
    if (observer != null) {
      observer.println("lb = " + lb + "; ub = " + ub);
    }
    // Variables
    Object pivot;	// The pivot we select.  Must be part of the subarray.
    int mid;		// The position of the pivot
    // Base case: size one arrays are sorted.
    if (lb == ub) return;
    // Pick a pivot and put it at the front of the array.
    swap(lb,pickPivot(lb,ub));
    // Determine the position of the pivot, while rearranging the array.
    mid = partition(lb,ub,compare);
    // Recurse on nonempty subarrays.
    if (lb<=mid-1) Quicksort(lb,mid-1, compare, observer);
    if (mid+1<=ub) Quicksort(mid+1,ub, compare, observer);
  } // Quicksort
  
  /**
   * Split the subarray given by [lb .. ub] into ``smaller'' and
   * ``larger'' elements, where smaller and larger are defined by
   * their relationship to a pivot.  Return the index of the pivot 
   * between those parts.  Uses the first element of the array 
   * as the pivot.
   * Pre: All the elements in the subarray can be compared.
   * Post: Returns n such that for all i between lb and n inclusive
   *   and j between n+1 and ub inclusive, get(i) <= pivot < get(j).
   */
  protected int partition(int lb, int ub, Comparator compare) 
    throws IncomparableException
  {
    // Strategy: split the array into three parts: the stuff known to
    // be less-than-or-equal to the pivot, the stuff known to
    // be greater than the pivot, and the stuff of unknown 
    // character.
  
    // Initially (and at every repetition of the main loop),
    //   Smaller or equal stuff is in get(lb) .. get(lower)
    //   Bigger stuff is in get(upper+1) .. get(ub)
    //   Unknown stuff is in get(lower+1) .. get(upper)
    int lower = lb;
    int upper = ub;

    // Get the pivot
    Object pivot = this.get(lb);

    // Keep going until we hit the middle element.
    while (lower < upper) {
      // Some error checking.  Pay no attention.
      // System.err.println("lower: " + lower + "; upper: " + upper);
      // System.err.println("  Pivot: '" + pivot.toString() + "'");
      // System.err.println("  Lower: '" + get(lower).toString() + "'");
      // System.err.println("  Upper: '" + get(upper).toString() + "'");
      // Try to expand the upper range.  Stop when you find a
      // small element or run out of things to look at
      while ( (compare.lessThan(pivot, this.get(upper))) 
              && (lower < upper) ) {
        upper--;
      } // expand the upper range

      // Try to expand the lower range.  Stop when you find a
      // large element or run out of elements.
      while ( ( (compare.lessThan(this.get(lower),pivot)) 
                || (compare.equals(pivot, this.get(lower))) )
              && (lower < upper) ) {
        lower++;
      } // expand the lower range.

      // If lower is not the same as upper, we've found a small
      // element in the upper range and a large element in the
      // smaller range, so swap 'em
      // of place.
      if (lower != upper)
        this.swap(lower,upper);
    } // while

    // We want to put the pivot in the middle.  lower gives
    // the position of the last "small" element.  Put the
    // pivot there.
    this.swap(lb,lower);

    // The pivot is now at position lower.
    return lower;
  } // partition(int, int, Comparator)
  
  /**
   * Pick a pivot in a subarray.
   * Pre: 0 <= lb <= ub < size()
   * Post: returns the index of the pivot (a value between lb and ub inclusive).
   */
  protected int pickPivot(int lb, int ub) {
    // Simple implementation: pick the last element.  Might be extended
    // to do something more interesting, such as pick a random element
    // in the subarray.
    return ub;
  } // pickPivot()
} // NewQuicksortable