//SearchArrayListTest.java
//generate random ints, add to an arraylist, do random searches,
//then sort and do random binary searches, comparing times.

//try million ints in range million
//1000 unsorted searches
//million sorted searches (will be faster than the 1000 unsorted searches!) 

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

public class SearchArrayListTest {
    public static void main(String[] args) {
	String input, userstring;
	int size;
	int range;
	int randInt;
	int numberSearches, hits, misses;
	long timeStart, timeEnd;
	double elapsedSeconds;
	
	ArrayList myArrayList = new ArrayList();  
	
	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++) {   //i is not an index, just a loop counter
	    randInt = (int)(Math.random()*range);  //random int between 0 and range-1
	    //uncomment if this code confuses you:
	    //System.out.println("generated int: " + randInt);
	    myArrayList.add(new Integer(randInt));  //must wrap int into Integer
	}
	
	//*** here is the sequential searching
	input = JOptionPane.showInputDialog( "Enter number of random searches to do in the unsorted list" );
	numberSearches = Integer.parseInt( input );
	
	hits = misses = 0;
	//***time now (milliseconds since 1 Jan 1970)
	timeStart = System.currentTimeMillis();   
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  //random value to search for
	    //**contains does sequential search (there's nothing better it can do)
	    if (myArrayList.contains(new Integer(randInt)))  
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();   //***time now
	//***difference between the start and end times is the elapsed time in ms
	elapsedSeconds = (timeEnd-timeStart)/1000.0;    
	System.out.println("Elapsed time: " + elapsedSeconds + "s");
	System.out.println(" Time per search: " + (elapsedSeconds/numberSearches) + "s");
	System.out.println(" hits: "+hits+"  misses: "+misses);


	//sort the data	
        Collections.sort(myArrayList); 
        
	input = JOptionPane.showInputDialog( "Enter number of random searches to do in the sorted list" );
	numberSearches = Integer.parseInt( input );
        //***do searches using Collections.binarySearch(List,value) 
	//returns index if found, negative if not found
	hits = misses = 0;
	timeStart = System.currentTimeMillis();   //time now (milliseconds since 1 Jan 1970)
	for (int i=1; i<=numberSearches; i++) {  
	    randInt = (int)(Math.random()*range);  //random value to search for
	    if (Collections.binarySearch(myArrayList,(new Integer(randInt))) >= 0) //***
	        hits++;
	    else
	        misses++;
	}
	timeEnd = System.currentTimeMillis();   //time now
	elapsedSeconds = (timeEnd-timeStart)/1000.0;
	System.out.println("Elapsed time: " + elapsedSeconds + "s");
	System.out.println(" Time per search: " + (elapsedSeconds/numberSearches) + "s");
	System.out.println(" hits: "+hits+"  misses: "+misses);
    }
}