/*
 * Description: A small example application that illustrates a simple
 * way of experimenting with the runtime of algorithms in JAVA. 
 * (See CS2Bh LN1 for the background.)
 * 
 * Author: Martin Grohe (Thanks to Fancisco Vargas for removing the dependency on cformat.)
 * Date: 28 Januar 2002
 */

import java.util.*;
//import java.io.FilterOutputStream.*;
import java.io.PrintStream;
//import cformat.*;
// Package cformat is a package for formatted printing in C-Style.
// It is used here to print a table.

public class Search{
    private static final PrintStream fout = new PrintStream(System.out);
    // Intialises the output stream for formatted output.

    private static final Random rand = new Random(System.currentTimeMillis());
    // Initialises the random number generator.

    public static int linSearch(int[] A,int k) {
	for(int i = 0; i < A.length; i++) 
	    if ( A[i] == k )
		return i;
	return -1;
    }

    public static int binarySearch(int[] A,int k,int i1,int i2) {
	if ( i1 > i2 )
	    return -1;
	int j = (i1+i2)/2;
	if ( A[j] == k )
	    return j;
	else if ( A[j] < k )
	    return binarySearch(A,k,i1,j-1);
	else
	    return binarySearch(A,k,j+1,i2);
    }

    /*
     * This is the main test routine.
     * 'size' is the size of the input arrays for the test.
     * 'repetitions' is the number of repetitions.
     */ 
    private static void runTest(int size,int repetitions) {
	int[] A = new int[size];
	int i,j,t,k;
	long start,end;
	int maxLin = 0;
	int totalLin = 0;
	int maxBin = 0;
	int totalBin = 0;

	for ( i = 0; i < repetitions; i++ ) {
	    // Generate random integer array of size 'size' with
	    // entries in the range 0,...,size-1.
	    for( j =0; j < size; j++)
		A[j] = rand.nextInt(size);
	    // The integer 'k' to be searched in the array is a random
	    // number in the same range.
	    k = rand.nextInt(size);
	    // Binary search requires the array to be sorted.
	    Arrays.sort(A);
	    
	    // Run linSearch and measure how long it takes.
	    start = System.currentTimeMillis();
	    linSearch(A,k);
	    end = System.currentTimeMillis();
	    t = (int) (end - start);

	    // Now update the maximum time required by linSearch in
	    // the test run so far and the total time.
	    maxLin = t < maxLin ? maxLin : t;
	    totalLin += t;
	    
	    // Do the same for binarySearch.
	    start = System.currentTimeMillis();
	    binarySearch(A,k,0,A.length-1);
	    end = System.currentTimeMillis();
	    t = (int) (end - start);
	    maxBin = t < maxBin ? maxBin : t;
	    totalBin += t;
	}
	// Print the results as a line of the table.
	printLine(size,maxLin,((float)totalLin)/repetitions,
		  maxBin,((float)totalBin)/repetitions);
    }
    
    /*
     * Print the head of the table.
     */
    private static void printHead() {
	System.out.println(" input size |     linSearch     |  binarySearch");
	System.out.println("            |    wc   |   avc   |    wc   |   avc");
	System.out.println("------------+---------+---------+---------+-------- ");
    }

    /*
     * Print one line of the table.
     */
    private static void printLine(int size,int maxLin,float avLin,
				  int maxBin,float avBin) {
	    
        // The next command prints a blank and then the integer 'size'
        // using 10 digits, padded with blanks, to the stream 'fout'.
        //
        // In general, the 'printf(String,int)' method of the class
        // 'PrintfStream' works as follows: Suppose we call
        //
        //                 stream.printf( s, i ),
        //
        // where 'stream' is a 'PrintfStream', 's' is a string, and
        // 'i' an integer. The string 's' is supposed to be a
        // substring of the form '%<length>d', where <length> is a
        // positive integer. Then 's' is printed to 'stream' with
        // '%<length>d' replaced by 'i' padded with blanks to
        // precisely <length> digits.
        //
        // For example, 'fout.printf("---%5d---\n",17)' prints
        //
        // ---   17---
        //
        // to 'fout'.  ('\n' is the newline character.)
	fout.printf(" %10d",size);
	if ( maxLin <= 1 )
	    System.out.print(" | <= 1 ms ");
	else
	    fout.printf(" |%5d ms ",maxLin);
	if ( avLin <= 1.0 )
	    System.out.print("| <= 1 ms ");
	else
            // The method 'printf(String,double)' of 'PrintfStream'
            // works similarly as 'printf(String,int)', except that
            // the string contains a substring '%<length>.<dec>f' which
            // is replace by the double argument with <length>-1
            // digits and the decimal point rounded to <dec> digits behind
            // the decimal point.
	    //
	    // For example, 'fout.printf("---%5.1f---\n",17.798)' prints
	    //
	    // --- 17.8---
	    //
	    // to 'fout'.
	    fout.printf("|%5.1f ms ",avLin);
	if ( maxBin <= 1 )
	    System.out.print("| <= 1 ms ");
	else
	    fout.printf("|%5d ms ",maxBin);
	if ( avBin <= 1.0 )
	    System.out.println("| <= 1 ms ");
	else
	    fout.printf("|%5.1f ms\n",avBin);
    }
    
    /*
     * Print additional information below the table.
     */ 
    private static void printFoot(int r) {
	fout.printf("\n(%d repetitions for each size)\n",r);
    }
	

    public static void main(String[] args) {
	int[] sizes = {10,100,1000,10000,100000,200000,400000,
		       600000,800000,
		       1000000,2000000,3000000, 4000000, 5000000, 
		       6000000, 8000000};
	int repetitions = 100;
	printHead();
	for( int i = 0; i < sizes.length; i++ )
	    runTest(sizes[i],repetitions);
	printFoot(repetitions);
    }
}