public class MoreArraysSamples {

// Sieve of Eratosthenes
// Searching:
//    Linear Search + Binary Search
// Sorting:
//    Selection, Insertion, Bubble sorts

    public static java.util.Scanner scanner = new java.util.Scanner(System.in);
    public static java.util.Random random = new java.util.Random();

    public static void example00_sieve_of_eratosthenes() {
        System.out.print("Find all primes up to what value: ");
        int max = scanner.nextInt();
        int[] primes = findPrimes(max);
        printArray(primes);
    }
    
    // uses the "Sieve of Eratosthenes" to compute all
    // primes between 2 and max, inclusive
    public static int[] findPrimes(int max) {
        boolean[] isComposite = new boolean[max+1]; // ignore 0 and 1
        int primeCount = 0;
        for (int prime=2; prime<=max; prime++) {
            if (!isComposite[prime]) {
                primeCount++;
                // remove multiples of this prime from the sieve
                for (int multiple=2*prime; multiple<=max; multiple += prime)
                    isComposite[multiple] = true;
            }
        }
        int[] primes = new int[primeCount];
        int i = 0;
        for (int prime=2; prime<= max; prime++)
            if (!isComposite[prime]) primes[i++] = prime;
        return primes;
    }

    public static void example01_linear_search() {
        System.out.print("Check for primes primes up to what value: ");
        int max = scanner.nextInt();
        int[] primes = findPrimes(max);
        int n;
        while (true) {
            System.out.print("Enter a number [<=0 to exit]: ");
            n = scanner.nextInt();
            if (n <= 0)
                break;
            else if (n > max)
                System.out.println("Too big -- only checking up to " + max);
            else {
                int index = linearSearch(primes,n);
                if (index < 0)
                    System.out.println(n + " is not prime");
                else
                    System.out.println(n + " is the " + (index+1) + "th prime");    
            }
        }
    }
    
    // returns the index where n occurs in a[], or -1 if it does not
    public static int linearSearch(int[] a, int n) {
        for (int i=0; i<a.length; i++)
            if (a[i] == n)
                return i;
        return -1;
    }

    public static void example02_binary_search() {
        System.out.print("Check for primes primes up to what value: ");
        int max = scanner.nextInt();
        int[] primes = findPrimes(max);
        int n;
        while (true) {
            System.out.print("\nEnter a number [<=0 to exit]: ");
            n = scanner.nextInt();
            if (n <= 0)
                break;
            else if (n > max)
                System.out.println("Too big -- only checking up to " + max);
            else {
                int index = binarySearch(primes,n);
                if (index < 0)
                    System.out.println(n + " is not prime");
                else
                    System.out.println(n + " is the " + (index+1) + "th prime");    
            }
        }
    }
    
    // returns the index where n occurs in a[], or -1 if it does not
    public static int binarySearch(int[] a, int n) {
        int guesses = 0; // just for accounting
        System.out.println("Binary search in array of size " + a.length);
        System.out.print("Guesses:  ");
        int lo, mid, hi;
        lo = 0;
        hi = a.length-1;
        while (lo <= hi) {
            mid = (lo + hi)/2;
            guesses++;
            if (guesses > 1) System.out.print(", ");
            System.out.print("a[" + mid + "]=" + a[mid]);
            if (a[mid] == n) {
                System.out.println("\nFound it in " + guesses + " guesses.");
                return mid;
            }
            else if (n > a[mid])
                lo = mid+1;
            else
                hi = mid-1;
        }
        System.out.println("\nDid not find it in " + guesses + " guesses.");
        return -1;
    }

    public static void example03_one_pass_of_bubblesort() {
        int[] a = makeArray(4);
        boolean changed;
        printArray(a);
        changed = bubblesortPass(a);
        if (changed) {
            System.out.print("New array: ");
            printArray(a);
        }
        else
            System.out.println("No change -- it is sorted!");
    }
    
    public static boolean bubblesortPass(int[] a) {
        boolean changed = false;
        for (int i=1; i<a.length; i++)
            if (a[i] < a[i-1]) {
                swap(a,i,i-1);
                changed = true;
            }
        return changed;
    }
    
    public static void example04_bubblesort() {
        int[] a = makeArray(8);
        boolean changed;
        do {
            printArray(a);
            changed = bubblesortPass(a);
        } while (changed);
    }

    public static void example05_traditional_bubblesort() {
        int[] a = makeArray(8);
        printArray(a);
        bubblesort(a);
        printArray(a);
    }
    
    public static void bubblesort(int[] a) {
        boolean changed;
        do {
            changed = false;
            for (int i=1; i<a.length; i++)
                if (a[i] < a[i-1]) {
                    swap(a,i,i-1);
                    changed = true;
                }
        } while (changed);
    }

    public static void example06_insertionsort() {
        int[] a = makeArray(8);
        printArray(a);
        insertionsort(a);
        printArray(a);
    }
    
    public static void insertionsort(int[] a) {
        for (int i=1; i<a.length; i++) {
            // insert a[i] into the sorted list a[0],a[1],...,a[i-1]
            for (int j=i; ((j > 0) && (a[j] < a[j-1])); j--)
                swap(a,j,j-1);
        }
    }

    public static void example07_selectionsort() {
        int[] a = makeArray(8);
        printArray(a);
        selectionsort(a);
        printArray(a);
    }
    
    public static void selectionsort(int[] a) {
        for (int i=0; i<a.length-1; i++) {
            int minIndex = getIndexOfMin(a,i);
            swap(a,i,minIndex);
        }
    }

    public static int getIndexOfMin(int[] a, int fromIndex) {
        if ((a == null) || (a.length == 0))
            return -1;
        int i, minIndex = fromIndex;
        for (i=fromIndex+1; i<a.length; i++)
            if (a[i] < a[minIndex])
                minIndex = i;
        return minIndex;
    }

    ///////////////////
    // from last time (ArraysSamples.java)
    ///////////////////
    
    public static void printArray(int[] a) {
        System.out.print("a[] = {");
        int i;
        for (i=0; i<a.length; i++) {
            if (i > 0) System.out.print(", ");
            System.out.print(a[i]);
        }
        System.out.println("}");
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static int[] makeArray(int size) {
        int[] result = new int[size];
        loadArray(result);
        return result;
    }

    public static void loadArray(int[] a) {
        // load the array
        int i;
        for (i=0; i<a.length; i++)  // a.length equals 10 here
            a[i] = random.nextInt(100);
    }

    ////////////////////////////////
    // Helper code
    ////////////////////////////////
        
    public static void main(String[] args) {
        java.util.ArrayList<String> examples = new java.util.ArrayList<String>();
        try {
            Class c = Class.forName("MoreArraysSamples");
            java.lang.reflect.Method[] methods = c.getMethods();
            for (java.lang.reflect.Method method : methods) {
                if (method.getName().startsWith("example"))
                    examples.add(method.getName());
            }
            java.util.Collections.sort(examples);
        }
        catch (Exception e) {
            e.printStackTrace();
        }
        while (true) {
            System.out.println("\n--------------------------");
            System.out.println("Choose from these examples:");
            for (int i=0;i<examples.size();i++)
                System.out.println("    " + examples.get(i));
            System.out.print("\nWhich example: [<0 to exit] ");
            int choice = scanner.nextInt();
            System.out.println("\n--------------------------");
            if (choice < 0) break;
            else if (choice >= examples.size())
                System.out.println("No such example");
            else try {
                Class c = Class.forName("MoreArraysSamples");
                java.lang.reflect.Method m = c.getMethod(examples.get(choice));
                m.invoke(null);
            }
            catch (Exception e) {
                e.printStackTrace();
            }
        }
    }    
}