import java.util.Vector;		// These are extended vectors
import rebelsky.util.Comparable;	// We need to compare elements
import rebelsky.util.IncomparableException;
					// Some things can't be compared
import rebelsky.util.StringUtils;	// For the "animated" version
import rebelsky.io.SimpleOutput;	// For the "animated" version

/**
 * An extension of java.util.Vector that supports an
 * additional quicksort method that sorts the current
 * vector.  Written as part of a laboratory for CS152.
 * Copyright (c) 1998 Samuel A. Rebelsky and YOUR NAME HERE.  
 * All rights reserved.
 *
 * @author Samuel A. Rebelsky
 * @author YOUR NAME HERE
 * @version 1.0 of March 1998
 */
public class QuicksortableVector
  extends Vector
{

  // +-----------+---------------------------------------------------------
  // | Variables |
  // +-----------+

  /**
   * The number of steps in the last call to quicksort.
   */
  protected int steps;

  /**
   * Where does output go?  If this is not set to null, produces
   * an "animation" of sorting to the output channel.  Otherwise, 
   * does not produce any output when sorting.
   */
  SimpleOutput out;

  /**
   * The width of the widest entry in the vector.  Used only when
   * printing the animation.
   */
  int width;


  // +--------------+------------------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new empty vector.
   */
  public QuicksortableVector()
  {
    super();
    out = null;
    width = -1;
  } // QuicksortableVector()

  /**
   * Construct an empty vector with the specified initial capacity.
   */
  public QuicksortableVector(int initial_capacity)
  {
    super(initial_capacity);
    out = null;
    width = -1;
  } // QuicksortableVector(int)

  /**
   * Construct a new vector with specified initial capacity and
   * capacity increment.  
   */
  public QuicksortableVector(int initial_capacity, int increment)
  {
    super(initial_capacity, increment);
    out = null;
    width = -1;
  } // QuicksortableVector


  // +------------------+--------------------------------------------------
  // | Exported Methods |
  // +------------------+

  /**
   * Sort the current vector.
   * pre: All the elements of the current vector are Comparable
   *          and can be compared to each other.
   * post: The elements are in order.
   *
   * @exception IncomparableException
   *   when two elements can't be compared.
   */
  public void quickSort()
    throws IncomparableException
  {
    // Indicate that we've spent 0 steps on this process.
    steps = 0;
    // No "animation"
    this.out = null;
    // Quicksort all the elements of the vector
    quickSort(0, size()-1);
  } // quickSort()

  /**
   * Sort the current vector.  Describe the steps as we go to the
   * given output.  See the other version for pre and postconditions.
   */
  public void quickSort(SimpleOutput out)
    throws IncomparableException
  {
    // Indicate that we've spent 0 steps on this process.
    steps = 0;
    // Set up output
    this.out = out;
    // Determine the maximum width of any cell
    for (int i = 0; i < size(); ++i) {
      int new_width = elementAt(i).toString().length();
      if (width < new_width) {
        width = new_width;
      }
    } // for
    width = width + 2;
    // Quicksort all the elements of the vector
    quickSort(0, size()-1);
    // Print the sorted vector
    printSubvector(0, size()-1);
    out.println();
    // And restore the animation stuff
    out = null;
    width = -1;
  } // QuicksortableVector


  // +---------------+-----------------------------------------------------
  // | Local Methods |
  // +---------------+

  /**
   * Partition a subvector vector based on a pivot (which must be 
   * in the subvector.  While determining that the pivot is at
   * position P, this method ensures that all the elements smaller
   * than or equal to the pivot precede the pivot, and all elements
   * larger than the pivot follow the pivot.
   * pre: 0 <= lb <= ub < size()
   * post: for all i, lb <= i <= P, for all j, P < j <= ub,
   *    elementAt(i) <= elementAt(j) 
   * @exception IncomparableException
   *   When two elements can't be compared.
   */
  protected int partition(Comparable pivot, int lb, int ub)
    throws IncomparableException
  {
    /*
     * We'll use two indices into the subvector, one to the
     * "larger" half, one to the "smaller" half.  Both begin
     * at the far end of their presumed section.  We advance
     * each toward the center over correctly placed elements
     * until they cross or hit incorrectly placed elements.
     * When both are over incorrectly placed elements, we swap.
     */
    // The index of the pivot
    int pivot_loc = -1;
    // The index into the larger elements.
    int larger = ub;
    // The index into the smaller elements.
    int smaller = lb;
    // Keep going until we cross.  Throw an exception if we ever hit
    // an invalid type.
    try {
      while (smaller < larger) {
        // Move the larger index towards the middle as much as is possible.
        // The casting of the element to Comparable is caught outside the
        // while loop.
        while ( (larger >= lb) &&
                (pivot.lessThan(((Comparable) elementAt(larger)))) ) {
          larger = larger - 1;
        } // while ( pivot < elementAt(larger) )
        // Move the smaller index towards the middle as much as possible.
        while ( (smaller <= ub) &&
                (!pivot.lessThan(((Comparable) elementAt(smaller)))) ) {
          if (pivot.equals(elementAt(smaller))) {
            pivot_loc = smaller;
          }
          smaller = smaller + 1;
        } // while ( pivot >= elementAt(smaller) )
        // Swap if necessary
        if (smaller < larger) {
          swap(smaller,larger);
        } // if
      } // while (smaller < larger)
    } // try
    catch (ClassCastException e) {
      throw new IncomparableException();
    } // catch

    // At this point, we know that smaller points to the beginning of
    // the large element and larger points to the end of the small
    // elements.  We want to put the pivot at that position and then
    // return that position.
    swap(pivot_loc, larger);
    return larger;
  } // partition(Comparable, int, int)
  
  /**
   * Pick a pivot.  Analyses I've seen suggest that the second
   * element works better than the first.  The use of a separate
   * method lets us experiment.
   * pre: 0 <= lb < ub < size()
   * post: some element in the range [lb .. ub] is returned
   *
   * @exception IncomparableException
   *   when the selected pivots is not Comparable
   */
  protected Comparable pickPivot(int lb, int ub)
    throws IncomparableException
  {
    try {
      return (Comparable) elementAt(lb+1);
    }
    catch (Exception e) {
      throw new IncomparableException();
    }
  } // pickPivot(int, int)

  /**
   * Print a subvector.  Does not indent by the appropriate amount.
   */
  protected void printSubvector(int lb, int ub) {
    // If there are no cells, stop
    if (ub < lb) return;
    // Print an intitial separator
    out.print("|");
    // Print all the cells followed by a separator
    for (int i = lb; i <= ub; ++i) {
      out.print(StringUtils.center(elementAt(i).toString(), width) + "|");
    }
  } // printSubvector

  /**
   * Sort a subrange of the current vector (all elements between
   * lb and ub inclusive).
   * pre: All the elements in the subrange are Comparable
   *          and can be compared to each other.
   * pre: 0 <= lb, ub < size()
   * post: The elements in the range [lb .. ub] are in order.
   *
   * @exception IncomparableException
   *   when two elements can't be compared.
   */
  protected void quickSort(int lb, int ub)
    throws IncomparableException
  {
    // Observe that we've spent an additional step
    steps = steps + 1;
    // If we're animating, print the vector
    if ((out != null) && (lb <= ub)) {
      out.print(StringUtils.spaces((width+1)*lb));
      printSubvector(lb, ub);
      out.println();
    }
    // Base case: subrange of length 0 or 1.
    if (ub <= lb) return;
    // Identify a pivot.  This pivot must be in the vector.
    Comparable pivot = pickPivot(lb,ub);
    // Partition the subvector based on that pivot.  This pivot must
    // be in the vector.  The function returns the position of the
    // pivot.
    int pivot_loc = partition(pivot, lb, ub);
    // If we're animating, print the partitioned vector
    if (out != null) {
      out.print(StringUtils.spaces((width+1)*pivot_loc+1));
      out.print("*");
      out.print(StringUtils.center(elementAt(pivot_loc).toString(), width-2));
      out.print("*");
      out.println();
    } // if we're animating
    // Sort the two subvectors.  It's important that we be able to
    // shrink at least one of the subvectors by at least one element,
    // otherwise we may never stop (e.g., when all the elements are
    // the same).
    quickSort(lb, pivot_loc-1);
    quickSort(pivot_loc+1,ub);
    // No need to merge, as we've been doing everything in place
  } // quickSort(int,int)

  /**
   * Swap two elements of the vector.
   * pre: 0 <= alpha, beta < size()
   * post: the element at alpha and the element at beta have
   *     swapped positions.
   */
  protected void swap(int alpha, int beta)
  {
    Object tmp = elementAt(alpha);
    setElementAt(elementAt(beta), alpha);
    setElementAt(tmp, beta);
  } // swap(int, int)

} // QuicksortableVector