package username.sorting;

import java.util.Comparator;
import java.util.Vector;

/**
 * Something that sorts with selection sort.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of May 2005
 */
public class SelectionSorter<T>
  implements OutOfPlaceVectorSorter<T>
{
  public Vector<T> sort(Vector<T> vec, Comparator<T> c)
  {
    int len = vec.size();
    // Selection sort is traditionally an in-place sort, so we 
    // make an exact copy of the vector and then sort it in
    // place.
    Vector<T> sorted = new Vector<T>(len);
    for (int i = 0; i < len; i++) {
      sorted.add(vec.get(i));
    } // for
    // Repeatedly find the smallest value in the remaining
    // portion of the vector and swap it into the current position.
    for (int i = 0; i < len; i++) {
      this.swap(sorted, i, this.indexOfSmallest(sorted, i, len-1, c));
    } // for
    return sorted;
  } // sort(Vector<T>, Comparator<T>)

  /**
   * Find the index of the smallest value in positions
   * lb to ub, inclusive.
   *
   * @return
   *   ios, the index of the smallest value
   * @pre
   *   0 <= lb <= ub < vec.size()
   * @pre
   *   c can be applied to any pair of values in vec.
   * @post
   *   c.compare(vec.get(ios),vec.get(i)) <= 0 for all i, lb <= i <= ub.
   */
  int indexOfSmallest(Vector<T> vec, int lb, int ub, Comparator<T> c)
  {
    // Initial guess: vec.get(lb) is the smallest value
    int iog = lb;	// That's "index of guess"
    T guess = vec.get(iog);
    // Step through each remaining element of interest, updating
    // our guess as appropriate.
    for (int i = lb+1; i <= ub; i++) {
      if (c.compare(vec.get(i), guess) <= 0) {
	iog = i;
        guess = vec.get(iog);
      } // if
    } //for
    // That's it, our guess is the answer
    return iog;
  } // indexOfSmallest

  /**
   * Swap two values in a vector.
   *
   * @pre
   *   0 <= a,b < vec.size()
   * @post
   *   vec.get(a) = "old value of" vec.get(b)
   * @post
   *   vec.get(b) = "old value of" vec.get(a)
   */
  void swap(Vector<T> vec, int a, int b)
  {
    T tmp = vec.get(a);
    vec.set(a, vec.get(b));
    vec.set(b, tmp);
  } // swap(Vector<T>, int, int)

} // class SelectionSorter