//ListsCompared.java
//compare times to do searches, iterations and random accesses in ArrayList and LinkedList

//generate random ints, add to an arraylist and to a linkedlist, 
//do iterations, do random accesses, do random searches,
//then sort and do random binary searches, comparing times.

import java.util.*;   
import javax.swing.*;

class ListsCompared {
    public static void main(String[] args) {
	String input;
	int size;
	int range;
	int randInt;
	int numberAccesses, randIndex;
	int numberSearches, hits, misses;
	long timeStart, timeEnd;
	double elapsedSeconds;
	
	ArrayList myArrayList = new ArrayList();  
	LinkedList myLinkedList = new LinkedList();  
	
	input = JOptionPane.showInputDialog( "Enter number of random ints to generate" );
	size = Integer.parseInt( input );

	input = JOptionPane.showInputDialog( "Enter upper range of the random ints" );
	range = Integer.parseInt( input );

	for (int i=1; i<=size; i++) {   
	    randInt = (int)(Math.random()*range);  
	    myArrayList.add(new Integer(randInt));  
	    myLinkedList.add(new Integer(randInt)); 
	}

	//****************************************************
	//** iteration tests
	Iterator it = myArrayList.iterator();
	timeStart = System.currentTimeMillis();   
	while (it.hasNext())
	    it.next();    //don't actually do anything with each item
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("ArrayList iteration ("+size+" items)");
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per item: " + (elapsedSeconds/size) + "s");


	it = myLinkedList.iterator();
	timeStart = System.currentTimeMillis();   
	while (it.hasNext())
	    it.next();  
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("LinkedList iteration ("+size+" items)");
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per item: " + (elapsedSeconds/size) + "s");
	System.out.println();


	//****************************************************
	//** random access tests
	input = JOptionPane.showInputDialog( "Enter number of random accesses to do in the list" );
	numberAccesses = Integer.parseInt( input );
	
	//*** ArrayList
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberAccesses; i++) {  
	    randIndex = (int)(Math.random()*size);    //random index
	    myArrayList.get(randIndex);
	}
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("ArrayList ("+size+" items) random "+numberAccesses+ " gets");
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberAccesses) + "s");

	//*** LinkedList
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberAccesses; i++) {  
	    randIndex = (int)(Math.random()*size);    //random index
	    myLinkedList.get(randIndex);
	}
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("LinkedList ("+size+" items) random "+numberAccesses+ " gets");
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberAccesses) + "s");
	System.out.println();


	//****************************************************
	//** unsorted sequential search tests
	input = JOptionPane.showInputDialog( "Enter number of random sequential searches to do in the unsorted list" );
	numberSearches = Integer.parseInt( input );
	
	//***sequential search ArrayList
	hits = misses = 0;
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  
	    if (myArrayList.contains(new Integer(randInt)))
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("ArrayList ("+size+" items)  unsorted sequential search:  hits: "+hits+"  misses: "+misses);
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberSearches) + "s");


	//***sequential search LinkedList
	hits = misses = 0;
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  
	    if (myArrayList.contains(new Integer(randInt)))
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();  
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("LinkedList ("+size+" items) unsorted sequential search  hits: "+hits+"  misses: "+misses);
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberSearches) + "s");
	System.out.println();


	//****************************************************
	//** sorted sequential search tests

	//sort the data	
        Collections.sort(myArrayList); 
        Collections.sort(myLinkedList); 

	//***sequential search ArrayList
	hits = misses = 0;
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  
	    if (myArrayList.contains(new Integer(randInt)))
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("ArrayList ("+size+" items)  sorted sequential search:  hits: "+hits+"  misses: "+misses);
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberSearches) + "s");


	//***sequential search LinkedList
	hits = misses = 0;
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  
	    if (myArrayList.contains(new Integer(randInt)))
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();  
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("LinkedList ("+size+" items)  sorted sequential search  hits: "+hits+"  misses: "+misses);
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberSearches) + "s");
	System.out.println();

        
	//**************************************************
	//** binary search tests

	input = JOptionPane.showInputDialog( "Enter number of random binary searches to do in the sorted list" );
	numberSearches = Integer.parseInt( input );

	//***binary search ArrayList
	hits = misses = 0;
	timeStart = System.currentTimeMillis(); 
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  
	    if (Collections.binarySearch(myArrayList,(new Integer(randInt))) >= 0) //***
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;
	System.out.println("ArrayList ("+size+" items) binary search  hits: "+hits+"  misses: "+misses);
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberSearches) + "s");
        
	//***binary search LinkedList
	hits = misses = 0;
	timeStart = System.currentTimeMillis(); 
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range); 
	    if (Collections.binarySearch(myArrayList,(new Integer(randInt))) >= 0) //***
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();   
	elapsedSeconds = (timeEnd-timeStart)/1000.0;
	System.out.println("LinkedList ("+size+" items) binary search   hits: "+hits+"  misses: "+misses);
	System.out.println("  Elapsed time: " + elapsedSeconds + "s" +
			   "  Time per search: " + (elapsedSeconds/numberSearches) + "s");
        
	System.out.println();
	

    }
}

/*

range same as size
For each of ArrayList and LinkedList:

iteration:  
    #items    total time    time per item
----------    ----------    -------------
    10,000
   100,000
 1,000,000

random access:
    #items    #accesses   total time    time per item
----------    ---------   ----------    -------------
    10,000         1000
    10,000        10000
   100,000        10000
   100,000       100000


for both unsorted and sorted sequential search
    #items    #searches   total time    time per search
----------    ---------   ----------    ---------------
    10,000         1000
    10,000        10000
   100,000         1000


binary search   
    #items    #searches   total time    time per search
----------    ---------   ----------    ---------------
    10,000         1000
    10,000        10000
   100,000        10000
   100,000       100000
 1,000,000      1000000
*/