/* Sorter.java
** An instance of a child of this abstract class inherits methods from 
** this class by which to sort an array (or a segment thereof) of any
** reference type into ascending order using the classic Selection Sort 
** algorithm.  The ordering of elements (which is determined by the 
** criteria used in comparing them) is defined by the isLessThan() method, 
** which here is abstract (and hence is left to be implemented by each 
** child class).
**
** Author: R. McCloskey
*/

public abstract class Sorter<T> {

   /* Rearranges the elements in a[] so that they are in ascending 
   ** lexicographic order.
   */
   public void sort(T[] a) { sort(a, 0, a.length); }

   
   /* Rearranges the elements in a[low..high) so that they are in
   ** ascending order.
   ** pre: 0 <= low <= high <= a.length 
   */
   public void sort(T[] a, int low, int high) { 
      for (int i = low; i != high; i=i+1) {
         // loop invariant: a[low..i) is in ascending order and no element
         //    within it is larger than any element in a[i..high).
         int locOfMin = locationOfMin(a, i, high);
         swap(a,i,locOfMin);
      }
   }

   /* Returns k (low <= k < high) such that b[k] is the minimum value
   ** in b[low..high).
   ** pre: 0 <= low < high <= b.length
   */
   private int locationOfMin(T[] b, int low, int high) {
      int locOfMinSoFar = low;
      for (int j = low+1;  j != high;  j = j+1) {
         // loop invariant: low <= locOfMinSoFar < j  && 
         //    b[locOfMinSoFar] is the minimum value in b[low..j)
         if (isLessThan(b[j], b[locOfMinSoFar])) {
            locOfMinSoFar = j;
         }
      }
      return locOfMinSoFar;
   }


   /* Returns true iff x < y.  It is left to descendant classes to implement.
   */
   protected abstract boolean isLessThan(T x, T y);


   /* pre: 0 <= i,j < b.length
    * post: references in b[i] and b[j] have been swapped
   */
   private void swap(T[] b, int i, int j) {
      T temp = b[i];
      b[i] = b[j];
      b[j] = temp;
   }

}