/* 
 * A program with some loops
 * @author	Biagioni, Edoardo
 * @assignment	lecture 4
 * @date	January 28, 2008
 * @bugs	none
 * @inspiration	William Albritton's BigO.java
 */

import java.util.*;

public class Loops {
    /* record start and finish times for each call */
    private static long startTime;
    private static boolean started;

    /* main method is invoked when the program is started
     * @param arguments  command-line arguments
     */
    public static void main(String[] arguments) {
	long count = 0;
	int n;			// how many loops to do

	started = false;	// initialize the field "started"

	/* example 1 */
	n = 100000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	stopTimerAndPrint("example 1", n);
	n = 10000000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	stopTimerAndPrint("example 1", n);
	n = 100000000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	stopTimerAndPrint("example 1", n);

	/* example 2 */
	n = 1000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		count++;
	    }
	}
	stopTimerAndPrint("example 2", n);
	n = 10000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		count++;
	    }
	}
	stopTimerAndPrint("example 2", n);

	/* example 3 */
	n = 100;
	startTimer();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		for (int k = 0; k < n; k++) {
		    count++;
		}
	    }
	}
	stopTimerAndPrint("example 3", n);
	n = 1000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		for (int k = 0; k < n; k++) {
		    count++;
		}
	    }
	}
	stopTimerAndPrint("example 3", n);

	/* example 4 */
	n = 100;
	startTimer();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < 100; j++) {
		for (int k = 0; k < 100; k++) {
		    count++;
		}
	    }
	}
	stopTimerAndPrint("example 4", n);
	n = 1000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < 100; j++) {
		for (int k = 0; k < 100; k++) {
		    count++;
		}
	    }
	}
	stopTimerAndPrint("example 4", n);

	/* example 5 */
	n = 100000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	for (int j = 0; j < n; j++) {
	    count++;
	}
	for (int k = 0; k < n; k++) {
	    count++;
	}
	stopTimerAndPrint("example 5", n);
	n = 1000000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	for (int j = 0; j < n; j++) {
	    count++;
	}
	for (int k = 0; k < n; k++) {
	    count++;
	}
	stopTimerAndPrint("example 5", n);

	/* example 6 */
	n = 1000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	for (int j = 0; j < n; j++) {
	    for (int k = 0; k < n; k++) {
		count++;
	    }
	}
	stopTimerAndPrint("example 6", n);
	n = 10000;
	startTimer();
	for (int i = 0; i < n; i++) {
	    count++;
	}
	for (int j = 0; j < n; j++) {
	    for (int k = 0; k < n; k++) {
		count++;
	    }
	}
	stopTimerAndPrint("example 6", n);

	/* example 7 */
	n = 1000000;
	startTimer();
	for (int i = 1; i < n; i = i + i) {
	    count++;
	}
	stopTimerAndPrint("example 7", n);
	n = 1000000000;
	startTimer();
	for (int i = 1; i < n; i = i + i) {
	    count++;
	}
	stopTimerAndPrint("example 7", n);

	/* example 8 */
	n = 1000000;
	startTimer();
	recurse(n);
	stopTimerAndPrint("example 8", n);
	n = 1000000000;
	startTimer();
	recurse(n);
	stopTimerAndPrint("example 8", n);

	/* example 9 */
	n = 100000;
	startTimer();
	for (int i = 1; i < n; i = i + i) {
	    for (int j = 0; j < n; j++) {
		count++;
	    }
	}
	stopTimerAndPrint("example 9", n);
	n = 1000000;
	startTimer();
	for (int i = 1; i < n; i = i + i) {
	    for (int j = 0; j < n; j++) {
		count++;
	    }
	}
	stopTimerAndPrint("example 9", n);
    }

    private static void recurse(int n) {
	if (n > 0) {
	    recurse(n / 2);
	}
    }

    /* start the timer
     * @param	none
     * @return	none
     */
    private static void startTimer() {
	if (started) {
	    System.out.println("error: timer already started");
	    System.exit(1);
	}
	/* all is well */
	started = true;
	startTime = System.currentTimeMillis();
    }

    /* stop the timer and return the time since started
     * @param	none
     * @return	the milliseconds since started
     */
    private static long stopTimer() {
	if (! started) {
	    System.out.println("error: timer not started");
	    System.exit(1);
	}
	/* all is well, stop the timer, compute and return the time */
	started = false;
	return (System.currentTimeMillis() - startTime);
    }

    /* stop the timer and print the time since started
     * @param	a description of what was run
     * @return	none
     */
    private static void stopTimerAndPrint(String whatWasRun, int iterations) {
	/* before printing anything, get the time.  This makes the
	 * measurement more accurate, since printing can be slow.
	 */
	long time = stopTimer();
	System.out.print(whatWasRun + " time " + time + " milliseconds, ");
	if (iterations == 100) {
	    System.out.print("n is one hundred");
	} else if (iterations == 1000) {
	    System.out.print("n is one thousand");
	} else if (iterations == 10000) {
	    System.out.print("n is ten thousand");
	} else if (iterations == 100000) {
	    System.out.print("n is one hundred thousand");
	} else if (iterations == 1000000) {
	    System.out.print("n is one million");
	} else if (iterations == 10000000) {
	    System.out.print("n is ten million");
	} else if (iterations == 100000000) {
	    System.out.print("n is one hundred million");
	} else if (iterations == 1000000000) {
	    System.out.print("n is one billion");
	} else {
	    System.out.print("n == " + iterations);
	}
	System.out.println("");
    }

}