// This program demonstrates how to time fast operations, by measuring
// how long a simple but non-primitive algorithm for Science of Computing
// lists takes. The algorithm in question computes the length of a list.

// History:
//   November 2004 -- Created by Doug Baldwin.




import geneseo.cs.sc.List;




class ShortTimeList extends List {




	// The makeNewList method.
	
	public List makeNewList() {
		return new ShortTimeList();
	}




	// The length method. This is based on the recursive insight
	// that the length of an empty list is 0, while the length of
	// a non-empty list is one more than the length of its tail.
	
	public int length() {
		if ( this.isEmpty() ) {
			return 0;
		}
		else {
			return 1 + ((ShortTimeList)this.getRest()).length();
		}
	}




	// Main creates a list of a set length, and then measures how
	// long it takes to send that list a "length" message.

	public static void main(String args[]) {
	
	
		// Create and populate the list. This should also take care
		// of any class initialization overhead on Java's part.
		
		final int size = 50;			// The size of the list
			
		ShortTimeList testList = new ShortTimeList();
		
		for ( int i = 0; i < size; i++ ) {
			testList.addItem( "hello" );
		}
		
		
		// Time the "length" message:
		
		final int repeats = 20000;
		
		long start = System.currentTimeMillis();
		for ( int i = 0; i < repeats; i++ ) {
			testList.length();
		}
		long end = System.currentTimeMillis();
		long time = end - start;
		
		long ostart = System.currentTimeMillis();
		for ( int i = 0; i < repeats; i++ ) {
			
		}
		long oend = System.currentTimeMillis();
		long otime = oend - ostart;
		
		double timePerMsg = ((double)(time-otime)) / repeats;

		System.out.println( "'length' takes " + timePerMsg + " mS." );
		System.out.println( "Raw time = " + time );
		System.out.println( "Overhead = " + otime );
	}
	
}