import SimpleInput;
import SimpleOutput;
import StringArrayInput;
import java.util.Random;
import StringSorter;

/**
 * Tools for sorting lists of strings using Quicksort.  Created 
 * for the answer key for assignment 7 in Grinnell's CSC152 99S.
 *
 * @author Samuel A. Rebelsky
 * @version 1.1 of March 1999
 */
public class QuicksortStrings 
  implements StringSorter
{

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** A random number generator, used to pick the pivot. */
  protected Random generator;

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

  /**
   * Build a new thing that can sort arrays of strings.
   */
  public QuicksortStrings() {
    generator = new Random();
  } // QuicksortStrings()


  // +----------------+------------------------------------------
  // | Public Methods |
  // +----------------+

  /**
   * Sort an array using Quicksort.  Included to support the
   * StringSorter interface.
   */
  public String[] sort(String[] strings) {
    // Make a copy.
    String[] stuff = new String[strings.length];
    for (int i = 0; i < strings.length; ++i) {
      stuff[i] = strings[i];
    }
    // Sort it.
    quickSort(stuff);
    // Return it.
    return stuff;
  } // sort(String[])
   
  /**
   * Sort an array in place using Quicksort.
   * Pre: All elements in the array can be compared to each other.
   * Post: The vector is sorted (using the standard meaning).
   */
  public void quickSort(String[] A) {
    quickSort(A, 0, A.length-1);
  } // quickSort(String[])
 
 
  // +----------------+------------------------------------------
  // | 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 < A.length
   * Post: The vector is sorted (using the standard meaning).
   */
  protected void quickSort(String[] A, int lb, int ub) {
    // Variables
    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.  
    putPivotAtFront(A,lb,ub);
    // Determine the position of the pivot, while rearranging the array.
    mid = partition(A, lb, ub);
    // Recurse.
    if (mid-1>=lb) quickSort(A, lb, mid-1);
    if (mid+1<=ub) quickSort(A, mid+1, ub);
  } // quickSort
  
  /**
   * Split the array 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 elements.  Uses the first element of the array 
   * as the pivot.
   */
  protected int partition(String[] A, int lb, int ub) {
    //  Use the first element of the subsequence as the pivot value.
    String pivotval = A[lb];
    int l=lb; // Elements [lb..l] are all <= pivotval
    int r=ub; // Elements [r+1..ub] are all > pivotval
    // Keep going until we run out of elements to put in the correct place.
    while (l < r) {
      // At this point, we know that 
      //   (1) l < r
      //   (2) Elements [lb..l] are all <= pivotval
      //   (3) Elements [r+1..ub] are all > pivotval
  
      // Skip over any large elements in the right half
      while ((pivotval.compareTo(A[r]) < 0) && (r > l)) {
        --r;
      }
  
      // At this point, we know that
      //    (1) l <= r (we stop moving r left when we hit l or run out
      //                of large elements)
      //    (2) elements [lb..l] are all <= pivotval (we haven't moved l)
      //    (3) elements [r+1..ub] are all > pivotval (by the for loop)
      //    (4) element r is <= pivotval (we either stopped moving when
      //        we hit such an element or (a) r = l and (b) l indexes such 
      //        an element)
  
      // Skip over any small elements in the left half.
      while ((A[l].compareTo(pivotval) <= 0) && (l < r)) {
        ++l;
      }
  
      // At this point, we know that
      //    (1) l <= r (we stop moving r left when we hit l or 
      //        possibly sooner; we stop moving l right when we hit
      //        r or possibly sooner)
      //    (2) elements [lb..l-1] are all <= pivotval (by the for loop)
      //    (3) elements [r+1..ub] are all > pivotval (we haven't moved r)
      //    (4) element r is <= pivotval (we either stopped moving when
      //        we hit such an element or r = l (and l indexes such an
      //        element)
      //    (5) if l < r then element l is > pivotval (by the for loop)
      //    (6) if l = r then element l is <= pivotval
    
      // Do we have a large element in the left and a small element
      // on the right?
      if (A[l].compareTo(A[r]) > 0) {
        swap(A,l,r);
      } 
    } // while
  
    // At this point, we know that
    //    (1) elements [lb..l] are all <= pivotval 
    //    (2) elements [l+1..ub] are all > pivotval
  
    // Put the pivot in the middle.  Note that at this point, element l is
    // <= pivotval, so this is a safe swap
    swap(A,lb,l);
  
    // And we're done
    return l;
  } // partition(String[], int, int)

  /**
   * Pick a pivot, and put it at the front of the subarray.
   * Pre: The subarray is nonempty.
   * Post: No elements are added.
   * Post: No elements are removed.
   * Post: Elements may have been rearranged.
   */
  protected void putPivotAtFront(String[] A, int lb, int ub) {
    // Determine the length of the subarray.
    int length = (ub - lb) + 1;
    // Pick a random number between 0 and length-1
    int r = Math.abs(generator.nextInt()) % length;
    // And swap
    swap(A,lb,lb+r);   
  } // putPivotAtFront(String[], int, int)

  /**
   * Swap two elements of an array.
   * Pre: Both indices are in the array.
   * Post: Afterwards, the two elements have been swapped.
   */
  protected void swap(String[] A, int x, int y) {
    String tmp = A[x];
    A[x] = A[y];
    A[y] = tmp;
  } // swap(String[], int, int)

} // class QuicksortStrings