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)
 * @author Mable Mathemagician
 * @author Myron Mathemagician
 * @version 1.1 of October 1999
 */
public class Quicksortable
  extends Array
  implements Sortable
{
  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+
  
  /**
   * Build a new sortable array of a particular size.
   */
  public Quicksortable(int n) {
    super(n);
  } // Quicksortable(int)
  
  /**
   * Build a new sortable array with a particular set of elements. 
   */
  public Quicksortable(Object[] elements) {
    super(elements);
  } // Quicksortable(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
  {
    // STUB.  Can you figure it out?
    return lb;
  } // 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(int,int)
} // Quicksortable