import java.util.Arrays;
import java.util.Scanner;

/**
 * Test the methods in the class Quick.
 *
 * @author Mark Young (A00000000)
 */
public class TestQuick {

    public static void main(String[] args) {
        int size = 20;
        int part = size / 4;
        int[] numbers = new int[size];
        for (int i = 0; i < size; ++i) {
            numbers[i] = (int) (1000 * Math.random());
        }

        testSmallest(part, Arrays.copyOf(numbers, size));
        pause();
        testLargest(part, Arrays.copyOf(numbers, size));
        pause();
        testMiddle(part, Arrays.copyOf(numbers, size));
        pause();
        testSort(Arrays.copyOf(numbers, size));
        pause();
    }

    /**
     * Test the method to find the smallest elements in an array.
     *
     * @param numbers the array to test with
     */
    private static void testSmallest(int part, int[] numbers) {
        System.out.println("Test Small");
        System.out.println("...before: " + toString(numbers));
        Quick.sortSmallest(part, numbers);
        System.out.println("...after: " + toString(numbers));
        sorted(numbers, 0, part);
    }

    /**
     * Test the method to sfind the largest elements in an array.
     *
     * @param numbers the array to test with
     */
    private static void testLargest(int part, int[] numbers) {
        System.out.println("Test Large");
        System.out.println("...before: " + toString(numbers));
        Quick.sortLargest(part, numbers);
        System.out.println("...after: " + toString(numbers));
        sorted(numbers, numbers.length - part, numbers.length);
    }

    /**
     * Test the method to find the mid-sized elements of the array.
     *
     * @param numbers the array to test with
     */
    private static void testMiddle(int part, int[] numbers) {
        System.out.println("Test Middle");
        System.out.println("...before: " + toString(numbers));
        Quick.sortMiddle(part, numbers);
        System.out.println("...after: " + toString(numbers));
        int numOutside = numbers.length - part;
        int numBelow = numOutside / 2;
        sorted(numbers, numBelow, numbers.length - numBelow);
    }

    /**
     * Test the method to sort the entire array.
     *
     * @param numbers the array to test with
     */
    private static void testSort(int[] numbers) {
        System.out.println("Test Sort");
        System.out.println("...before: " + toString(numbers));
        Quick.sort(numbers);
        System.out.println("...after: " + toString(numbers));
        sorted(numbers, 0, numbers.length);
    }

    /**
     * Check whether the array is such that:
     * <ul>
     * <li> Everything below {@code begin} is at least as small as anything in
     * the sorted range.
     * <li> Everything between {@code begin} (included) and {@code end}
     * (excluded) is sorted.
     * <li> Everything at/above {@code end} is at least as large as anything in
     * the sorted range.
     * </ul>
     *
     * @param numbers the array to test
     * @param begin the lowest index (inclusive) of the sorted range
     * @param end the highest index (exclusive) of the sorted range
     */
    private static void sorted(int[] numbers, int begin, int end) {
        // To start we'll assume the middle range is sorted, so that the
        // smallest element is in position begin, and the largest is in
        // position end - 1.
        //
        // We WILL test this assumption later!
        int low = numbers[begin];
        int high = numbers[end - 1];

        // everything before sorted range should be small
        boolean allSmaller = true;
        for (int i = 0; i < begin; ++i) {
            if (numbers[i] > low) {
                System.out.println("ERROR BELOW THE SORTED RANGE!");
                System.out.println("numbers[" + i + "] == " + numbers[i]
                        + " > " + low);
                System.out.println(toString(numbers));
                allSmaller = false;
            }
        }
        if (allSmaller) {
            System.out.printf("...everything below it is smaller than "
                    + "arr[%d] == %d%n",
                    begin, low);
        }

        // everything in sorted range should be sorted (duh!)
        boolean isSorted = true;
        for (int i = begin + 1; i < end; ++i) {
            if (numbers[i - 1] > numbers[i]) {
                System.out.println("ERROR IN THE SORTED RANGE!");
                System.out.println("numbers[" + (i - 1) + "] == "
                        + numbers[i - 1] + " > "
                        + "numbers[" + i + "] == " + numbers[i]);
                System.out.println(toString(numbers));
                isSorted = false;
            }
        }
        if (isSorted) {
            System.out.printf("...everything in the range arr[%d] = %d "
                    + "arr[%d] = %d is sorted%n",
                    begin, low, end - 1, high);
        }

        // everything above sorted range should be large
        boolean allBigger = true;
        for (int i = end; i < numbers.length; ++i) {
            if (numbers[i] < high) {
                System.out.println("ERROR ABOVE THE SORTED RANGE!");
                System.out.println("numbers[" + i + "] == " + numbers[i]
                        + " < " + high);
                System.out.println(toString(numbers));
                allBigger = false;
            }
        }
        if (allBigger) {
            System.out.printf("...everything above it is larger than "
                    + "arr[%d] == %d%n",
                    end - 1, high);
        }
    }

    private static final Scanner KBD = new Scanner(System.in);

    /**
     * Prompt the user and wait for them to press the enter key.
     */
    private static void pause() {
        System.out.print("\n...press enter...");
        KBD.nextLine();
        System.out.println();
    }

    /**
     * Generate a String for an array in some reasonable fashion.
     *
     * @param arr the array to print
     */
    private static String toString(int[] arr) {
        String result = "";
        int onLine = 0;
        for (int num : arr) {
            if (onLine % 10 == 0) {
                result += "\n\t";
            }
            result += String.format("%6d", num);
            ++onLine;
        }
        return result + "\n";
    }
}