public class RunTime
{
    static int[] randInts;
    static int noOfInts;

    public static void main(String[] args)
    {
	long start, stop;
	if (args.length == 2) {
	    if (args[0].equals("lin")) {
		loadRandInts(args[1]);
		start = System.currentTimeMillis();
		System.out.println(linearSearch(-1));
		stop = System.currentTimeMillis();
	    }
	    else if (args[0].equals("bin")) {
		loadRandInts(args[1]);
		start = System.currentTimeMillis();
		System.out.println(binarySearch(0, noOfInts, -1));
		stop = System.currentTimeMillis();
	    }
	    else if (args[0].equals("sel")) {
		loadRandInts(args[1]);
		start = System.currentTimeMillis();
		selectionSort();
		stop = System.currentTimeMillis();
		saveRandInts("sorted");
	    }
	    else if (args[0].equals("merge")) {
		loadRandInts(args[1]);
		start = System.currentTimeMillis();
		mergeSort(0, noOfInts);
		stop = System.currentTimeMillis();
		saveRandInts("sorted");
	    }
	    else if (args[0].equals("fib")) {
		int n = Integer.parseInt(args[1]);
		start = System.currentTimeMillis();
		System.out.println("fib(" + n + ") = " + fibo(n));
		stop = System.currentTimeMillis();
	    }
	    else {
		System.out.println("Unknown algorithm");
		return;
	    }
	    System.out.println("Running time: " + (stop-start) + " msecs");
	}
	else {
	    System.out.println("Usage: RunTime (lin | bin | sel | merge) <filename>");
	    System.out.println("    or RunTime fib <int>");
	}
    }

    // read integers from text file
    public static void loadRandInts(String filename)
    {
	try {
	    CS211In file = new CS211In(filename);
	    randInts = new int[1];
	    for(noOfInts=0; file.peekAtKind() != file.EOF;) {
		if (noOfInts == randInts.length) {  // expand array
		    int[] temp = new int[randInts.length * 2];
		    for(int j=0; j<noOfInts; j++) temp[j] = randInts[j];
		    randInts = temp;
		}
		randInts[noOfInts++] = file.getInt();
	    }
	} catch (Exception e) {
	    System.out.println("Error reading file " + filename);
	    System.exit(1);
	}
    }

    public static void saveRandInts(String filename)
    {
	try {
	    CS211Out file = new CS211Out(filename);
	    for(int i=0; i<noOfInts; i++) file.println(randInts[i]);
	    file.close();
	    System.out.println("File `" + filename + "' saved");
	} catch (Exception e) {
	    System.out.println("Error writing file " + filename);
	    System.exit(1);
	}
    }

    // print integers on screen (for debugging purposes)
    private static void printInts()
    {
	for(int i=0; i<noOfInts; i++) System.out.print(randInts[i] + " ");
	System.out.println("");
    }

    // Selection Sort
    public static void selectionSort()
    {
	int minSoFar, posOfMin;
	for(int i=0; i<noOfInts-1; i++) {
	    minSoFar = randInts[i];
	    posOfMin = i;
	    for(int j=i; j<noOfInts; j++)
		if (randInts[j] < minSoFar) {
		    minSoFar = randInts[j];
		    posOfMin = j;
		}
	    randInts[posOfMin] = randInts[i];
	    randInts[i] = minSoFar;
	}
    }

    // Merge Sort
    public static void mergeSort(int left, int right)
    {
	if (left+1 < right) {
	    int middle = (left + right) / 2;
	    mergeSort(left, middle);
	    mergeSort(middle, right);

	    // merge sorted subarrays
	    int[] tmp = new int[right-left];
	    int i1 = left, i2 = middle;
	    for (int j=0; j<right-left; j++) {
		if (i1 >= middle)
		    tmp[j] = randInts[i2++];  // copy rest
		else if (i2 >= right)
		    tmp[j] = randInts[i1++];  // copy rest
		else
		    tmp[j] = randInts[i1] < randInts[i2] ? randInts[i1++] : randInts[i2++];  // copy smaller
	    }
	    for (int j=left; j<right; j++) randInts[j] = tmp[j-left];
	}
    }

    // Linear Search
    public static boolean linearSearch(int key)
    {
	boolean found = false;
	for(int i=0; i<noOfInts && !found; i++)
	    if (randInts[i] == key) found = true;
	return found;
    }

    // Binary Search (array must be sorted!)
    public static boolean binarySearch(int key, int left, int right)
    {
	if (left < right) {
	    int middle = (left + right + 1) / 2;
	    if (randInts[middle] == key)
		return true;
	    else if (key < randInts[middle])
		return binarySearch(key, left, middle);
	    else
		return binarySearch(key, middle, right);
	}
	return false;
    }

    // Fibonacci Numbers
    // NB. This is a brain-dead way to compute Fibonacci numbers.
    // There is a much better algorithm (optional exercise!) that runs
    // in linear time.
    public static int fibo(int n)
    {
	return n==0 ? 0 : n==1 ? 1 : fibo(n-1) + fibo(n-2);
    }
}