import java.util.List;
import java.util.Random;
import java.util.Arrays;

public class JavaSortTiming {

    /*
    * Returns whether integers in given list are sorted
    * in non-decreasing order.
    */
    private static boolean isSorted(int[] v) {
        int i = 0;
        for (; i < v.length-1 && v[i] <= v[i+1]; i++);

        // Returns whether i stopped before reaching end of array. Ie. if
        // inversion was present. Empty array also considered sorted.
        return i == (v.length-1) || v.length == 0;
    }

    /*
    * Perform tests and output whether the implementation
    * correctly sorts different inputs.
    */
    public static void correctnessTest() {
        System.out.println("Tests whether implementation correctly sorts.");
        System.out.println("----------------");
        // Initialize arrays to sort.
        int[] nonDecreasing = new int[] {1,2,3,4,5,6,7,8,9};
        int[] nonIncreasing = new int[] {9,8,7,6,5,4,3,2,1};
        int[] similar = new int[] {42,42,42,42,42,42};
        int[] empty  = new int[] {};
        int[] taocpNumbers = new int[] {503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703};

        // Sorts arrays.
        Arrays.sort(nonDecreasing);
        Arrays.sort(nonIncreasing);
        Arrays.sort(similar);
        Arrays.sort(empty);
        Arrays.sort(taocpNumbers);

        // Prints whether arrays are sorted.
        System.out.println("Input (sorted non-decreasing): " + isSorted(nonDecreasing));
        System.out.println("Input (sorted non-increasing): " + isSorted(nonIncreasing));
        System.out.println("Input (similar): " + isSorted(similar));
        System.out.println("Input (empty): " + isSorted(empty));
        System.out.println("Input (TAOCP numbers): " + isSorted(taocpNumbers));

        System.out.println("----------------\n\n");
    }

    /*
    * Tests quick sort with random input of size n.
    */
    private static void randomCase(int n) {
        // Creates array with three identical input arrays. (generated randomly)
        int[][] v = new int[3][n];
        Random rnd = new Random();
        for (int i = 0; i < n; i++)
            v[0][i] = rnd.nextInt(n);
        v[1] = Arrays.copyOf(v[0], n);
        v[2] = Arrays.copyOf(v[0], n);

        // Perform sorting three times and stores running time.
        long[] runningTimes = new long[3];
        for (int i = 0; i < 3; i++) {
            long t1 = System.currentTimeMillis();
            Arrays.sort(v[i]);
            long t2 = System.currentTimeMillis();
            runningTimes[i] = t2-t1;
        }

        // Output statistics.
        System.out.println("Input size n: " + n);
        long avg = Arrays.stream(runningTimes).sum()/3;
        System.out.println("Average running time (avg): " + avg);
        // Should be constants (see slides).
        System.out.println("Computes (avg/n*log2(n)): " + avg/((long) n*(Math.log10(n)/Math.log10(2)))); // cast to long; otherwise might overflow.
        System.out.println("----------------");
    }

    /*
    * Perform sorting and output time measurement.
    */
    public static void timeImplementation() {
        System.out.println("Random inputs: ");
        System.out.println("----------------");
        randomCase(4_000_000);
        randomCase(8_000_000);
        randomCase(16_000_000);
        randomCase(32_000_000);
        randomCase(64_000_000);
        System.out.println();


    }

    // Main method
    public static void main(String[] args) {
        correctnessTest();
        timeImplementation();
    }

}