// CSE 143, Winter 2009, Marty Stepp
//
// This program tests stage 1 of the SortedIntList project.
// You can change the constant values to conduct larger
// tests to better verify your SortedIntList class.
//
// last updated Tue 1/13/09  (revised to improve test case output/verbosity)
// adapted from 9/29/06 version by Stuart Reges

import java.util.*;

public class Test1 {
    // number of elements to use in the checkAdd and checkIndexOf tests
    public static final int BASIC_TEST_SIZE = 10;
    
    // number of elements to use in the checkSpeed test (should be very large)
    public static final int SPEED_TEST_SIZE = 100000;
    
    public static void main(String[] args) {
        checkAdd(BASIC_TEST_SIZE);
        checkIndexOf(BASIC_TEST_SIZE);
        checkSpeed(SPEED_TEST_SIZE);
        System.out.println("All tests passed!");
    }

    // This method adds a series of numbers to the list and makes sure that
    // the size increases and that it produces a sorted list.
    public static void checkAdd(int testSize) {
        System.out.println("Beginning checkAdd basic add test of size " + testSize);
        SortedIntList list = new SortedIntList(false, testSize);
        Random r = new Random();
        for (int i = 0; i < testSize; i++) {
            // remember old list contents in case of a problem
            String old = list.toString();
            // pick a number between -testSize and +testSize, add to list
            int next = r.nextInt(2 * testSize + 1) - testSize;
            
            int expectedSize = i + 1;
            String addMessage;

            if (r.nextBoolean()) {
                // add to end of list
                list.add(next);
                addMessage = " to end of list";
            } else {
                // randomly add the element at some index to the list
                // (it should stay sorted)
                int randomIndex = r.nextInt(expectedSize + 1);
                list.add(randomIndex, next);
                addMessage = " at index " + randomIndex;
            }
            
            // check list size and make sure list is sorted
            if (list.size() != expectedSize) {
                throw new RuntimeException("\n\nafter adding " + expectedSize
                                           + " items, size = " + i + " (should be " + expectedSize + ")\n");
            } else if (!isSorted(list)) {
                throw new RuntimeException(
                        "\n\nadding " + next + addMessage + " failed; list is not sorted.\n" +
                        "List before add = " + old + ";\nlist after  add = " + list + "\n");
            }
        }
        System.out.println("    Passed!\n");
    }

    // This method adds values to the list and uses a boolean array to keep
    // track of what values have been added.  It then checks often to make
    // sure that indexOf returns values that make sense given the set of
    // values that have been added to the list.
    public static void checkIndexOf(int testSize) {
        System.out.println("Beginning checkIndexOf basic indexOf test of size " + testSize);
        SortedIntList list = new SortedIntList(false, testSize);
        Random r = new Random();
        // numbers will be between -testSize and +testSize
        boolean[] chosen = new boolean[2 * testSize + 1];
        checkIndexes(testSize, chosen, list);
        for (int i = 0; i < testSize; i++) {
            // pick a number between -testSize and +testSize, add to list
            int next = r.nextInt(2 * testSize + 1) - testSize;
            list.add(next);
            chosen[next + testSize] = true;
            checkIndexes(testSize, chosen, list);
        }
        System.out.println("    Passed!\n");
    }

    // This method constructs a very large list of even numbers and calls
    // indexOf many times to make sure that the code is fast.
    public static void checkSpeed(int testSize) {
        System.out.println("Beginning checkSpeed indexOf test of size " + testSize);

        // keep track of starting time before constructing
        long start = System.currentTimeMillis();

        // fill up the list with even numbers
        int dot = testSize / 10;
        SortedIntList list = new SortedIntList(false, testSize);
        System.out.print("    Building list of the first " + testSize + " multiples of 2: ");
        boolean addTooSlow = false;
        for (int i = 0; i < testSize; i++) {
            list.add(2 * i);
            if (i % dot == 0) {
                System.out.print(".");
            }
            if (!addTooSlow && System.currentTimeMillis() >= start + testSize / 20) {
                System.out.print(" (add is too slow) ");
                addTooSlow = true;
            }
        }
        System.out.println();
        double elapsed = (System.currentTimeMillis() - start)/1000.0;
        // System.out.println("    construction took " + elapsed + " seconds");

        // keep track of starting time before indexOf tests
        System.out.print("    Checking indexOf each element: ");
        start = System.currentTimeMillis();
        dot = testSize / 10;
        for (int i = 0; i < testSize; i++) {
            for (int j = 0; j < 100; j++) {
                int actualIndex = list.indexOf(2 * i);
                if (actualIndex != i) {
                    System.out.println();
                    throw new RuntimeException(
                            "\n\nindexOf " + 2 * i + " should have returned: " +
                            i + ",\n  but your method actually returned: " +
                            actualIndex + "\n");
                }
            }
            if (System.currentTimeMillis() >= start + testSize / 5) {
                System.out.println();
                throw new RuntimeException(
                        "\n\nindexOf appears to be running too slowly.\n");
            }
            if (i % dot == 0) {
                System.out.print(".");
            }
        }
        double elapsed2 = (System.currentTimeMillis() - start)/1000.0;
        if (addTooSlow) {
            System.out.println();
            throw new RuntimeException(
                    "\n\nYour add method appears to have run too slowly.  (runtime: " + elapsed + " seconds)\n");
        }
        System.out.println("\n    Passed!  (runtime: " + elapsed2 + " seconds)\n");
    }

    // returns true if list is sorted, false otherwise
    public static boolean isSorted(SortedIntList list) {
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    // Compares the boolean array to the SortedIntList to make sure that
    // they match.  If a number has not been chosen, then its index should be
    // reported as -1.  If it has been chosen, then it should have a 
    // non-negative index and the number should actually be at that index.
    public static boolean checkIndexes(int testSize, boolean[] chosen, SortedIntList list) {
        for (int i = 0; i < chosen.length; i++) {
            int original = i - testSize;
            int index = list.indexOf(original);
            
            // start by assuming it's not bad
            boolean bad = false;
            
            // then check for bad cases
            if (chosen[i] && (index < 0 || index >= list.size()
                              || list.get(index) != original)) {
                bad = true;
            } else if (!chosen[i] && index >= 0) {
                bad = true;
            }
            if (bad) {
                String result = "\n\n" + original + " should not have index " + index
                    + "\nlist = " + list + "\n";
                /*
                // commenting out this output because it seems unhelpful
                    + " and chosen values =";
                boolean any = false;
                for (int j = 0; j < chosen.length; j++)
                    if (chosen[j]) {
                        result += " " + (j - testSize);
                        any = true;
                    }
                if (!any) {
                    result += " nothing";
                }
                */
                throw new RuntimeException(result);
            }
        }
        return true;
    }
}