// Stuart Reges
// 9/29/06
//
// This program tests stage 1 of the SortedIntList project.  The methods
// called in main each

import java.util.*;

public class Test1 {
    public static void main(String[] args) {
        checkAdd(10);        // start small (10), eventually big (500)
        checkIndexOf(10);    // start small (10), eventually big (500)
        checkSpeed(100000);  // should be very large
    }

    // 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) {
        SortedIntList list = new SortedIntList(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;
            list.add(next);
            // check list size and make sure list is sorted
            int expectedSize = i + 1;
            if (list.size() != expectedSize) {
                throw new RuntimeException("after adding " + expectedSize
                                           + " items, size = " + i);
            } else if (!isSorted(list)) {
                throw new RuntimeException("adding " + next + " failed, before"
                                           + " add = " + old + ", after add = "
                                           + list);
            }
        }
        System.out.println("Passed basic add test");
    }

    // 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) {
        SortedIntList list = new SortedIntList(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 basic indexOf test");
    }

    // 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) {
        // 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("building list, please wait, 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");

        // keep track of starting time before indexOf tests
        start = System.currentTimeMillis();
        for (int i = 0; i < testSize; i++) {
            for (int j = 0; j < 100; j++) {
                if (list.indexOf(2 * i) != i) {
                    throw new RuntimeException("indexOf " + 2 * i + " should"
                                               + " be " + i + ", is returning "
                                               + list.indexOf(2 * i));
                }
            }
        }
        elapsed = (System.currentTimeMillis() - start)/1000.0;
        System.out.println("indexOf test passed in " + elapsed + " seconds");
    }

    // 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 != -1) {
                bad = true;
            }
            if (bad) {
                String result = original + " should not have index " + index
                    + " when list = " + list + " 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;
    }
}