import java.util.*;


/**
 * A class that contains a group of search algorithms.
 * The input to the search algorithms is assumed to be
 * an array of integers.
 * 
 * @author Donald Chinn
 * @version January 11, 2004
 */
public class Search {

    // Constructor for objects of class Sort
    public Search () {
    }


    /**
     * Given an array of integers and a key, search the array for the
     * key using sequential search.  Return the index of the first occurrence
     * of the key in the array, or -1 if the key is not in the array.
     * @param data  an array of integers
     * @param key   key to search for
     * @return  index of key (or -1 if the key is not in the array)
     */
    public static int sequentialSearch (int[] data, int key) {
        return -1;
    }

    
    /**
     * Given a sorted array (in ascending order) of integers and a key, search
     * the array for the key using iterative binary search.  Return the index
     * of the first occurrence of the key in the array, or -1 if the key is not
     * in the array.
     * @param data  an array of integers
     * @param key   key to search for
     * @return  index of key (or -1 if the key is not in the array)
     */
    public static int binarySearchIterative (int[] data, int key) {
        return -1;
    }


    /**
     * Given a sorted array (in ascending order) of integers and a key, search
     * the array for the key using recursive binary search.  Return the index
     * of the first occurrence of the key in the array, or -1 if the key is not
     * in the array.
     * @param data  an array of integers
     * @param key   key to search for
     * @return  index of key (or -1 if the key is not in the array)
     */
    public static int binarySearchRecursive (int[] data, int key) {
        return binarySearchRecursiveWorkhorse (data, key, 0, data.length - 1);
    }

    /**
     * Given a sorted array (in ascending order) of integers and a key, search
     * the array for the key using recursive binary search.  Return the index
     * of the first occurrence of the key in the array, or -1 if the key is not
     * in the array.
     * @param data  an array of integers
     * @param key   key to search for
     * @param low   low index of the search range
     * @param high  high index of the search range
     * @return  index of key (or -1 if the key is not in the array)
     */
    public static int binarySearchRecursiveWorkhorse (int[] data,
                                                      int key,
                                                      int low,
                                                      int high) {

        return -1;
    }


    /**
     * Given an integer size, produce an array of integers initialized
     * so that the integer at index i is i.
     * @param size  the number of elements in the returned array
     * @return      an array of integers
     */
    public static int[] getArrayOfIntegers(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = i;
        }
        return data;
    }


    /**
     * Given an integer size, produce an array of size random integers.
     * The integers of the array are between 0 and size (inclusive) with
     * random uniform distribution.
     * @param size  the number of elements in the returned array
     * @return      an array of integers
     */
    public static int[] getRandomArrayOfIntegers(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = (int) ((size + 1) * Math.random());
        }
        return data;
    }
    

    /**
     * Given an integer size, produce an array of size random integers.
     * The integers of the output array are between 0 and size-1 with
     * exactly one of each in the array.  Each permutation is generated
     * with random uniform distribution.
     * @param size  the number of elements in the returned array
     * @return      an array of integers
     */
    public static int[] getRandomPermutationOfIntegers(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = i;
        }
        // shuffle the array
        for (int i = 0; i < size; i++) {
            int temp;
            int swap = i + (int) ((size - i) * Math.random());
            temp = data[i];
            data[i] = data[swap];
            data[swap] = temp;
        }
        return data;
    }


    /**
     * Perform checks to see if the algorithm has a bug.
     */
    private static void testCorrectness() {
        int[] data = getArrayOfIntegers(100);
        
        for (int i = 0; i < data.length; i++) {
            System.out.println("data[" + i + "] = " + data[i]);
        }
        
        // to test a different algorithm, change the method call
        // in the if statement
        for (int i = 0; i < 100; i++) {
            if (sequentialSearch(data, i) != i) {
                System.out.println ("Error!  data[" + i + "] = " + data[i] + ".");
            }
        }
    }
    
    
    /**
     * Perform timing experiments.
     */
    private static void testTiming () {
        // timer variables
        long totalTime = 0;
        long startTime = 0;
        long finishTime = 0;

        // start the timer
        Date startDate = new Date();
        startTime = startDate.getTime();

        int n = 5000;    // n = size of the array
        int[] data = getArrayOfIntegers(n);
        for (int key = 0; key < n; key++) {
            sequentialSearch(data, key);
        }

        // stop the timer
        Date finishDate = new Date();
        finishTime = finishDate.getTime();
        totalTime += (finishTime - startTime);
        
        System.out.println("** Results for sequential search:");
        System.out.println("    " + "n = " + n);
        System.out.println("    " + "Time: " + totalTime + " ms.");
    }
    
    
    /**
     * code to test the sorting algorithms
     */
    public static void main (String[] argv) {
        testCorrectness();
        testTiming();
    }
}