// Stuart Reges
// 4/3/10
//
// This program tests stage 1 of the SortedIntList project.  The methods called
// in main each perform a series of checks and halt execution if any test
// fails.
//
// The basic approach of the testing code is to use an ArrayList<Integer> to
// compute the correct answer and to continually compare the SortedIntList to
// the ArrayList<Integer>.  The manipulations performed on the ArrayList are
// highly inefficient (sorting after each individual add).  We can live with
// this kind of inefficiency in a testing program, but it should not be taken
// as an example of good coding.

import java.util.*;

public class Test1 {
    // number of elements to use in the checkAdd and checkIndexOf tests
    // change this to a larger number to conduct a more thorough test
    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);
    }

    // This method adds a series of numbers to a list and makes sure that size,
    // toString, and get all return appropriate values by comparing the results
    // against a known correct answer built using an ArrayList.
    public static void checkAdd(int testSize) {
        System.out.println("Beginning basic add test of size " + testSize);
        SortedIntList list = new SortedIntList(testSize);
        List<Integer> result = new ArrayList<Integer>();
        String history = "";
        Random r = new Random();
        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;
            history += " " + next;
            result.add(next);
            Collections.sort(result);
            list.add(next);
            boolean sizeOK = result.size() == list.size();
            boolean toStringOK = result.toString().equals(list.toString());
            if (!sizeOK || !toStringOK) {
                System.out.println("wrong size or toString when adding these"
                                   + " values to list:" + history);
                System.out.println("size should       = " + result.size());
                System.out.println("toString should   = " + result.toString());
                System.out.println("actual size       = " + list.size());
                System.out.println("actual toString   = " + list.toString());
                if (result.size() > 1) {
                    System.out.println("size and ToString were working "
                                       + "properly prior to adding last "
                                       + "value of " + next);
                }
                System.exit(1);
            } else {
                for (int j = 0; j < result.size(); j++) {
                    if (list.get(j) != result.get(j)) {
                        System.out.println("wrong value for get(" + j + ")");
                        System.out.println("list = " + result.toString());
                        System.out.println("get should   = " + result.get(j));
                        System.out.println("get actually = " + list.get(j));
                        System.exit(1);
                    }
                }
            }
        }
        System.out.println("    Passed");
        System.out.println();
    }

    // This method adds a series of number to a list and makes sure that
    // indexOf returns appropriate values by comparing the results against a
    // known correct answer built using an ArrayList.
    public static void checkIndexOf(int testSize) {
        System.out.println("Beginning basic indexOf test of size " + testSize);
        SortedIntList list = new SortedIntList(testSize);
        List<Integer> result = new ArrayList<Integer>();
        Random r = new Random();
        checkIndexes(testSize, result, 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;
            result.add(next);
            Collections.sort(result);
            list.add(next);
            checkIndexes(testSize, result, list);
        }
        System.out.println("    Passed");
        System.out.println();
    }

    // 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 speed 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 / 75;
        SortedIntList list = new SortedIntList(testSize);
        System.out.println("construction--should take a fraction of a second");
        System.out.println("done after 75 dots:");
        for (int i = 0; i < testSize; i++) {
            list.add(2 * i);
            if (i % dot == 0)
                System.out.print(".");
        }
        System.out.println();
        double elapsed = (System.currentTimeMillis() - start)/1000.0;
        System.out.println("construction took " + elapsed + " seconds");
        System.out.println();

        // keep track of starting time before indexOf tests
        start = System.currentTimeMillis();
        System.out.println("searching list--should take a second or two");
        System.out.println("done after 75 dots:");
        for (int i = 0; i < testSize; i++) {
            if (i % dot == 0)
                System.out.print(".");
            for (int j = 0; j < 100; j++) {
                int index = list.indexOf(2 * i);
                if (index != i) {
                    System.out.println("wrong value for indexOf(" + 2*i + ")");
                    System.out.println("indexOf should = " + i);
                    System.out.println("actual indexOf = " + index);
                    System.exit(1);
                }
            }
        }
        System.out.println();
        elapsed = (System.currentTimeMillis() - start) / 1000.0;
        System.out.println("searching took " + elapsed + " seconds");
    }

    // Compares the given ArrayList and SortedIntList to make sure that indexOf
    // is returning appropriate values for the given testSize.
    public static boolean checkIndexes(int testSize, List<Integer> result,
                                       SortedIntList list) {
        for (int i = -testSize; i < testSize; i++) {
            int index = list.indexOf(i);
            boolean bad;
            if (result.indexOf(i) == -1) {
                bad = index != -1;
            } else {
                bad = index < 0 || result.get(index) != i;
            }
            if (bad) {
                System.out.println("wrong value for indexOf(" + i + ")");
                System.out.println("list = " + result.toString());
                if (result.indexOf(i) == -1) {
                    System.out.println("indexOf should = -1");
                    System.out.println("actual indexOf = " + index);
                } else {
                    System.out.println("indexOf is returning " + index);
                    System.out.println(i + " is not at that index");
                }
                System.exit(1);
            }
        }
        return true;
    }
}