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.0 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).
     */
    public int partition(int lb, int ub, Comparator compare)
        throws IncomparableException
    {
        
        //  Use the first element of the subsequence as the pivot value. 
        int pivot = lb;

        int first = lb; // Elements [lb..first] are all <= pivotval
        int last = ub; // Elements [last+1..ub] are all > pivotval

        // Keep going until we run out of elements to put in the correct place.

        while (first < last) {
            
            // At this point, we know that 
            //   (1) first < last
            //   (2) Elements [lb..first] are all <= pivot
            //   (3) Elements [last+1..ub] are all > pivot


            // Skip over any large elements in the right half

            while ( (compare.lessThan(this.get(pivot),this.get(last))) 
                    && (first < last))
                --last;

            // At this point, we know that
            //    (1) first <= last (we stop moving r left when we hit first 
            //        or run out of large elements)
            //    (2) elements [lb..first] are all <= pivot (we haven't moved first)
            //    (3) elements [last+1..ub] are all > pivot (by the for loop)
            //    (4) element last is <= pivot (we either stopped moving when
            //        we hit such an element or (a) last = first and (b) first
            //       indexes such an element)

            // Skip over any small elements in the left half.

            while ( ((compare.lessThan(this.get(first),this.get(pivot))) ||
                    (compare.equals(this.get(first),this.get(pivot)))) 
                    && (first < last))
                ++first;

            // At this point, we know that
            //    (1) first <= last (we stop moving last left when we hit first or 
            //        possibly sooner; we stop moving first right when we hit
            //        last or possibly sooner)
            //    (2) elements [lb..first-1] are all <= pivot (by the for loop)
            //    (3) elements [last+1..ub] are all > pivot (we haven't moved last)
            //    (4) element last is <= pivot (we either stopped moving when
            //        we hit such an element or last = first (and first indexes 
            //        such an element)
            //    (5) if first < last then element first is > pivot 
            //        (by the for loop)
            //    (6) if first = last then element first is <= pivot
          
            // Do we have a large element in the left and a small element
            // on the right?

            if (compare.lessThan(this.get(last),this.get(first)))
                this.swap(first,last);

        }//while

        // At this point, we know that
        //    (1) elements [lb..first] are all <= pivot 
        //    (2) elements [first+1..ub] are all > pivot
        
        // Put the pivot in the middle.  Note that at this point, element first is

        this.swap(lb,first);

        // Done!
        return first;

    }// 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