import java.util.*;

public class SelectionSort{


  // find the location of the smallest element 
  // in the upper part of this list 
  // using the given Comparator
  int findMinLoc(ArrayList alist, int low, Comparator comp){
  	int minloc = low;
  	while (low < alist.size()){
  		if (comp.compare(alist.get(low), alist.get(minloc)) <= 0){
  			minloc = low;
  		}
  	    low = low + 1;
  	}
    return minloc;
  }

  // swap the elements at the two given locations in this list
  void swap(ArrayList alist, int loc1, int loc2){ 
    Object temp = alist.get(loc1);
    alist.set(loc1, alist.set(loc2, temp));
  } 

  // sort the list 
  void sort(ArrayList alist, Comparator comp){
    int index = 0;

    while (index < alist.size() - 1){
      System.out.println("iteration " + index);
      swap(alist, index, findMinLoc(alist, index + 1, comp));
      index = index + 1;
    }
  }
  
  class StringComp implements Comparator{
  	public int compare(Object obj1, Object obj2){
  		return ((String)obj1).compareTo((String)obj2);
  	}
  }

  public void testSort(){
  	
  	ArrayList alist = new ArrayList();
  	alist.add("Hello");
 	alist.add("Goodbye");
 	alist.add("Ciao");
 	alist.add("Servus");
 
 	ArrayList slist = new ArrayList();
 	slist.add("Ciao");
 	slist.add("Hello");
 	slist.add("Goodbye");
 	slist.add("Servus");
 	
 	swap(slist, 0, 2);
 	System.out.println("swap test: " + 
 			(("Goodbye".equals(slist.get(0)))
 		  && ("Ciao".equals(slist.get(2)))));
 			
 	System.out.println("findMinLoc test: " +
 			(2 == findMinLoc(alist, 0, new StringComp())));
 
 	// verifying the sorting
 	sort(alist, new StringComp());
 	Iterator it2 = alist.iterator();
 	
 	while (it2.hasNext()){
 		System.out.println(it2.next());
 	}	
  }
  
  public static void main(String[] argv){
  	SelectionSort ss = new SelectionSort();
  	ss.testSort();
  }

}