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

public class CountingSort {

    /*-------- Countingsort implementation START --------*/

    /*
    * Implementation of the Counting sort algorithm as presented by Cormen et al.
    */
    private static void countingSortInternal (int[] a, int[] b, int k){
        int[] c = new int[k+1];
        /* Note: Java performs 0-initialization so this is unnessary.
        for (int i = 0; i < c.length; i++)
            c[i] = 0;
        */

        for (int i = 0; i < a.length; i++)
            c[a[i]] += 1;

        for (int i = 1; i < c.length; i++) {
            c[i] = c[i] + c[i-1];
        }

        for (int i = a.length - 1; i >= 0; i--) {
            // Since the B-array in the pseudocode is 1-indexed, we have to
            // subtract 1 when indexing into 'b'.
            b[c[a[i]]-1] = a[i];
            c[a[i]]--;
        }
    }

    /*
    * Performs Counting sort on given array v.
    * Post condition: The given array v is a permutation of input array in
    * non-decreasing order (ie. it is sorted).
    * Note: To make the comparisons fair, we don't give counting sort the largest
    * integer in its input; it has to find that on its own. The reasoning is that
    * why would we give counting sort some extra information it uses in its sorting when
    *   1) it can find that information on its own, and
    *   2) the other sorting algorithms we have implemented are not given extra
    *   information that could be helpful to them.
    * Note: To find the largest element of array v, we convert v to an IntStream
    * and use its max method to find the maximum element. To non-CS students, this
    * is similar to doing a linear search over an array to find its maximum element.
    */
    private static void countingSort (int[] v) {
        if (v.length > 0) { // necessary to find max safely.
            // Note: By given a copy of v as the first actual parameter and v as
            // the second actual parameter, the second formal parameter in countingSortInternal(...)
            // will reference the same array in memory as the one originally given to
            // countingSort(...). Thereby, countingSort(...) works entirely by
            // side effects as seen from the user(s) of countingSort(...). Ie. it
            // is not necessary to return the reference to another array.
            countingSortInternal(Arrays.copyOf(v, v.length), v, Arrays.stream(v).max().getAsInt());
        }
    }

    /*-------- Countingsort implementation END --------*/

    /*-------- Quick sort implementation START --------*/

    /* Swaps elements at index i and j around in v. */
    private static void exchange(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /*
    * Implementation of the partition algoritm as presented by Cormen et al.
    */
    private static int partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p-1;

        for (int j = p; j < r; j++) {
            if (a[j] <= x) {
                i = i + 1;
        		int temp = a[i];
        		a[i] = a[j];
        		a[j] = temp;
            }
        }
        int temp = a[i+1];
        a[i+1] = a[r];
        a[r] = temp;
        return i+1;
    }

    /*
    * Implementation of the Quick sort algorithm as presented by Cormen et al.
    */
    private static void quickSortInternal(int[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);
            quickSortInternal(a, p, q-1);
            quickSortInternal(a, q+1, r);
        }
    }

    /*
    * Performs Quick sort on given array v.
    * Post condition: The given array v is a permutation of input array in
    * non-decreasing order (ie. it is sorted).
    */
    public static void quickSort(int[] v) {
        quickSortInternal(v, 0, v.length - 1);
    }

    /*-------- Quick sort implementation END --------*/

    /*-------- Testing methods implementation START --------*/

    /* Prints content of given array v. */
    private static void printArray(int[] v) {
        for (int i : v)
            System.out.print(i + "; ");
        System.out.println();
    }

    /*
    * Perform sorting of specified inputs in order to check it correctly sorts.
    */
    public static void correctnessTest() {
        // 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[] singleton  = new int[] {42};
        int[] taocpNumbers = new int[] {503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703};

        // Prints input arrays sorted.
        System.out.print("Input (sorted non-decreasing): ");
        printArray(nonDecreasing);
        System.out.print("Input (sorted non-increasing): ");
        printArray(nonIncreasing);
        System.out.print("Input (similar): " );
        printArray(similar);
        System.out.print("Input (empty): ");
        printArray(empty);
        System.out.print("Input (singleton): ");
        printArray(singleton);
        System.out.print("Input (TAOCP numbers): ");
        printArray(taocpNumbers);
        System.out.println();

        // Sorts arrays.
        countingSort(nonDecreasing);
        countingSort(nonIncreasing);
        countingSort(similar);
        countingSort(empty);
        countingSort(singleton);
        countingSort(taocpNumbers);

        // Prints output arrays which should be sorted.
        System.out.print("Output (input: sorted non-decreasing): ");
        printArray(nonDecreasing);
        System.out.print("Output (input: sorted non-increasing): ");
        printArray(nonIncreasing);
        System.out.print("Output (input: similar): ");
        printArray(similar);
        System.out.print("Output (input: empty): ");
        printArray(empty);
        System.out.print("Output (input: singleton): ");
        printArray(singleton);
        System.out.print("Output (input: TAOCP numbers): ");
        printArray(taocpNumbers);
    }

    /*
    * Tests running time of given sorting algoritm on random input of size n
    * where elements has values in range [0; k].
    */
    private static void randomInput(int n, int k) {
        // 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(k+1);
        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();
            countingSort(v[i]);
            long t2 = System.currentTimeMillis();
            runningTimes[i] = t2-t1;
        }

        // Output statistics.
        System.out.println("Input size n (k = " + k + "): " + 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+k)): " + avg/(n+k+0.0));
        System.out.println("----------------");
    }

    /*
    * Tests running time of quick sort and counting sort random input of size n
    * where elements has values in range [0; k].
    */
    private static void comparisonTest(int n, int k) {
        // Creates random array of size n with integers in range [0; k].
        int[] v = new int[n];
        Random rnd = new Random();
        for (int i = 0; i < n; i++)
            v[i] = rnd.nextInt(k+1);

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

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

        // Output statistics.
        System.out.println("Input size n = " + n + " and k = " + k);
        long avgCoutingSort = Arrays.stream(runningTimesCountingSort).sum()/3;
        long avgQuickSort = Arrays.stream(runningTimesQuickSort).sum()/3;
        System.out.println("Average running time (Counting sort): " + avgCoutingSort);
        System.out.println("Average running time (Quick sort): " + avgQuickSort);
        System.out.println("----------------");
    }
    /*-------- Testing methods implementation END --------*/

    /*
    * Main method.
    */
    public static void main (String[] args) {
        System.out.println("Tests whether implementation correctly sorts.");
        System.out.println("----------------");
        correctnessTest();
        System.out.println("----------------\n\n");

        System.out.println("Tests Counting sort running time on random inputs: ");
        System.out.println("----------------");
        randomInput(4_000_000, 4_000_000/50);
        randomInput(4_000_000, 4_000_000);
        randomInput(4_000_000, 4_000_000*50);
        System.out.println("----------------");
        randomInput(8_000_000, 8_000_000/50);
        randomInput(8_000_000, 8_000_000);
        randomInput(8_000_000, 8_000_000*50);
        System.out.println("----------------");
        randomInput(16_000_000, 16_000_000/50);
        randomInput(16_000_000, 16_000_000);
        randomInput(16_000_000, 16_000_000*50);
        System.out.println();

        System.out.println("Compares Quick sort and Counting sort running times: ");
        System.out.println("----------------");
        comparisonTest(8_000_000, 8_000_000/50);
        comparisonTest(8_000_000, 8_000_000);
        comparisonTest(8_000_000, 8_000_000*50);
        System.out.println("----------------");
    }
}