/**
 * Title: ListCompare
 * Description: Creates some different types of Lists and 
 *   times sequences of operations
 *
 * Issues: java has no way of getting at CPU time,
 * so the accuracy of this code relies on
 *    1. short measurements (minimize the chance the process
 *          is interrupted).
 *    2. don't take any single run as gospel, run many times
 *      and look for the most common timings.
 *    3. Elapsed time is an upper bound for CPU time, 
 *       it can report times that are too big (longer than
 *       the code actually takes in CPU time), but it can't
 *       report times too small.
 *
 * @author hollingd@cs.rpi.edu
 */
import java.util.*;

class ListCompare {

  static final int LIST_SIZE=10000;
  static final int MAX_RANDNUM=100000;

  public static void main(String [] args) {

	// runs the tests
	long starttime,diff;  // used for timing

	// buildListAdd test creates a list by adding elements to the
	// end of the list (using add()).

	// try with an ArrayList
	starttime = (new Date()).getTime();
	buildListAdd(new ArrayList());
	diff = (new Date()).getTime() - starttime;
	System.out.println("buildListAdd(ArrayList) Elapsed time was " + diff + " ms.");

	// try with a LinkedList
	starttime = (new Date()).getTime();
	buildListAdd(new LinkedList());
	diff = (new Date()).getTime() - starttime;
	System.out.println("buildListAdd(LinkedList) Elapsed time was " + diff + " ms.");

	// use add to insert new elements randomly (not all at the end).

	// try with an ArrayList
	starttime = (new Date()).getTime();
	buildListInsert(new ArrayList());
	diff = (new Date()).getTime() - starttime;
	System.out.println("buildListInsert(ArrayList) Elapsed time was " + diff + " ms.");

	// try with a LinkedList
	starttime = (new Date()).getTime();
	buildListAdd(new LinkedList());
	diff = (new Date()).getTime() - starttime;
	System.out.println("buildListInsert(LinkedList) Elapsed time was " + diff + " ms.");

	// random access - need a list to start with
	List l1 = new ArrayList();
	buildListAdd(l1);

	// try with an ArrayList
	starttime = (new Date()).getTime();
	randomAccess(l1);
	diff = (new Date()).getTime() - starttime;
	System.out.println("randomAccess(ArrayList) Elapsed time was " + diff + " ms.");


	List l2 = new LinkedList();
	buildListAdd(l2);

	// try with a LinkedList
	starttime = (new Date()).getTime();
	randomAccess(l2);
	diff = (new Date()).getTime() - starttime;
	System.out.println("randomAccess(LinkedList) Elapsed time was " + diff + " ms.");

  }


  // buildList creates a list by calling add 

  public static void buildListAdd(List l) {
	
	// Populate with LIST_SIZE random Integer objects
	Random r = new Random();
	
	for (int i=0;i<LIST_SIZE;i++) {
	  l.add( new Integer(r.nextInt(MAX_RANDNUM)));
	}
  }

  // buildListInsert creates a list by inserting elements into the 
  // list at random locations

  public static void buildListInsert(List l) {
	
	// Populate with LIST_SIZE random Integer objects
	Random r = new Random();
	
	l.add( new Integer(r.nextInt(MAX_RANDNUM)));
	for (int i=1;i<LIST_SIZE;i++) {
	  l.add( r.nextInt(l.size()),new Integer(r.nextInt(MAX_RANDNUM)));
	}
  }


  // randomAccess accesses list elements randomly
  public static void randomAccess(List l) {
	
	Random r = new Random();

	for (int i=0;i<LIST_SIZE;i++) {
	   l.get(r.nextInt(LIST_SIZE));
	}
  }

}