/** Helper methods.

    @author Anna Rafferty
    @author Jed Yang
*/
public class Helper
{
   /** Swaps the array entries array[i] and array[j]. */
   private static void swap(int[] array, int i, int j)
   {
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
   }
   
   /** Orders two given array entries into ascending order so that
       a[i] <= a[j].
       @param a an array of ints
       @param i an integer >= 0 and < array.length
       @param j an integer >= 0 and < array.length
   */
   private static void order(int[] a, int i, int j)
   {
      if (a[i] > a[j])
      {
         swap(a, i, j);
      }
   }
   
   /** Sorts the first, middle, and last entries of an array into ascending
       order.
       @param a an array of ints
       @param first the integer index of the first array entry;
       first >= 0 and < a.length
       @param mid the integer index of the middle array entry
       @param last the integer index of the last array entry;
       last - first >= 2, last < a.length 
   */
   private static void sortFirstMiddleLast(int[] a, int first, int mid, int last)
   {
      order(a, first, mid); // make a[first] <= a[mid]
      order(a, mid, last); // make a[mid] <= a[last]
      order(a, first, mid); // make a[first] <= a[mid]
   }
   
   /** Partitions the array a so that the entries in [first, last] are
       rearranged into a "smaller" part and a larger part.

       All the entries located to the left of that
       index are less than the value at the pivot index, and all the entries to
       the right of that index are greater than the pivot.
       @return index of the pivot
       FIXME:
   */
   public static int partition(int[] a, int first, int last)
   {
      int mid = (first + last) / 2;
      sortFirstMiddleLast(a, first, mid, last);
      // Assertion: The pivot is a[mid]; a[first] <= pivot and
      // a[last] >= pivot, so do not compare these two array entries
      // with pivot.
      // move pivot to next-to-last position in array
      swap(a, mid, last - 1);
      int pivotIndex = last - 1;
      int pivot = a[pivotIndex];
      // determine subarrays Smaller = a[first..endSmaller]
      // and Larger = a[endSmaller+1..last-1]
      // such that entries in Smaller are <= pivot and
      // entries in Larger are >= pivot; initially, these subarrays are empty
      int indexFromLeft = first + 1;
      int indexFromRight = last - 2;
      boolean done = false;
      while (!done)
      {
         // starting at beginning of array, leave entries that are < pivot;
         // locate first entry that is >= pivot; you will find one,
         // since last entry is >= pivot
         while (a[indexFromLeft] < pivot)
         {
            indexFromLeft++;
         }
         // starting at end of array, leave entries that are > pivot;
         // locate first entry that is <= pivot; you will find one,
         // since first entry is <= pivot
         while (a[indexFromRight] > pivot)
         {
            indexFromRight--;
         }
         // Assertion: a[indexFromLeft] >= pivot
         //            a[indexFromRight] <= pivot
         if (indexFromLeft < indexFromRight)
         {
            swap(a, indexFromLeft, indexFromRight);
            indexFromLeft++;
            indexFromRight--;
         }
         else
         {
            done = true;
         }
      } 

      // place pivot between Smaller and Larger subarrays
      swap(a, pivotIndex, indexFromLeft);
      pivotIndex = indexFromLeft;
      return pivotIndex;
   }
   
   /** Helper method for insertion sort to enable insertion sorting only part
       of an array.
   */
   public static void insertionSort(int[] array, int first, int last)
   {
      for (int i = first + 1; i <= last; i++)
      {
         //i is the index in the array we're going to find the right place for
         int j = i;
         while (j > first && array[j-1] > array[j])
         {
            swap(array, j-1, j);
            j--;
         }
      }
   }
   
   /** Generates a pseudo-random permutation of the integers from 0 to
       a.length - 1.
       See p. 139 of "Seminumerical Algorithms, 2nd edition," by Donald Knuth.
   */
   public static void fillAndShuffle(int[] a)
   {
      // Fill the array with the integers from 0 to a.length - 1.
      int k;
      for (k = 0; k < a.length; k++)
      {
         a[k] = k;
      }

      // Shuffle.
      for (k = a.length - 1; k > 0; k--)
      {
         int swapIndex = (int)Math.floor(Math.random() * (k + 1));
         swap(a, k, swapIndex);
      }
   }
}