/*
 * Med1.java
 * 
 * Version:
 *     $Id: Med1.java,v 1.3 2008/11/01 17:42:41 jtw1366 Exp $
 *
 * Revisions:
 *     $Log: Med1.java,v $
 *     Revision 1.3  2008/11/01 17:42:41  jtw1366
 *     Added comments to files
 *
 *     Revision 1.2  2008/10/30 00:57:42  jtw1366
 *     Activity 2 of Lab 9 done
 *
 *     Revision 1.1  2008/10/28 17:44:52  jtw1366
 *     Activity 1 of Lab 9 done
 *
 */

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
  * This program finds the median of a set of numbers using a partition-based
  * general selection algorithm.
  *
  * @author John T. Wodder II
  **/

public class Med1 {

 /**
   * The main() method reads in a file of numbers and finds their median.
   *
   * @param args	the command-line arguments (the name of a file to read)
   **/

 public static void main(String args[]) {
  try {
   Scanner scanner = new Scanner (new File(args[0]));
   List<Integer> list = new ArrayList<Integer>(); 
   while (scanner.hasNext()) {
    list.add(scanner.nextInt());
   }
   long start = System.currentTimeMillis();
   int k = list.size()/2, left = 0, right = list.size()-1;
   for (;;) {
    int pivotIndex = (int) Math.floor(Math.random() * (right-left+1)) + left;
    int pivotNewIndex = partition(list, left, right, pivotIndex);
    if (k == pivotNewIndex) break;
    else if (k < pivotNewIndex) right = pivotNewIndex - 1;
    else left = pivotNewIndex+1;
   }
   System.out.println("Elapsed time: " + (System.currentTimeMillis()-start));
   System.out.println(list.get(k));
  } catch (FileNotFoundException e) {
   System.err.println("File not found: " + args[0]);
  }
 }

 /**
   * The partition() method determines how many numbers within a certain range
   * of a List are less than a certain element.
   *
   * @param list	the List of Integers to operate on
   * @param left	the index at which to start comparing numbers
   * @param right	the index at which to stop comparing numbers (inclusive)
   * @param pivotIndex	the index of the Integer to compare against the other
   * 			numbers
   *
   * @return		the amount of numbers in `list' with indices from
   * 			`left' to `right' that are less than the Integer at
   * 			index `pivotIndex'
   **/

 private static int partition(List<Integer> list, int left, int right,
  int pivotIndex) {
  Integer pivotValue = list.get(pivotIndex);
  list.set(pivotIndex, list.get(right));
  list.set(right, pivotValue);
  int storeIndex = left;
  for (int i=left; i<right; i++) {
   if (list.get(i).compareTo(pivotValue) < 0) {
    if (i != storeIndex) {
     Integer tmp = list.get(i);
     list.set(i, list.get(storeIndex));
     list.set(storeIndex, tmp);
    }
    storeIndex++;
   }
  }
  list.set(right, list.get(storeIndex));
  list.set(storeIndex, pivotValue);
  return storeIndex;
 }
}