import java.util.Arrays;

public class HeapTest {

    public static void main(String[] args) {
        // int length = 2;
        // while (length < 10000000) {
        //     System.out.print("Length " + length + " - ");
        //     testHeap(length);
        //     length *= 2;
        // }
        // O(n) - Every time length doubles, time complexity doubles with it
        // Length 2 - Loop went 1 times
        // Length 4 - Loop went 2 times
        // Length 8 - Loop went 3 times
        // Length 16 - Loop went 4 times
        // Length 32 - Loop went 5 times
        // Length 64 - Loop went 6 times
        // Length 128 - Loop went 7 times
        // Length 256 - Loop went 8 times
        // Length 512 - Loop went 9 times
        // Length 1024 - Loop went 10 times
        // Length 2048 - Loop went 11 times
        // Length 4096 - Loop went 12 times
        // Length 8192 - Loop went 13 times
        // Length 16384 - Loop went 14 times
        // Length 32768 - Loop went 15 times
        // Length 65536 - Loop went 16 times
        // Length 131072 - Loop went 17 times
        // Length 262144 - Loop went 18 times
        // Length 524288 - Loop went 19 times
        // Length 1048576 - Loop went 20 times
        // Length 2097152 - Loop went 21 times
        // Length 4194304 - Loop went 22 times
        // Length 8388608 - Loop went 23 times
        //
        //
        // BUBBLE SORT RESULTS
        // sortTest(20);
        // sortTest(50000);
        // //100% usage of 1 CPU core for this btw
        // sortTest(100000);
        // sortTest(200000);
        // Elapsed Time For Length 20: 0
        // Elapsed Time For Length 50000: 3052
        // Elapsed Time For Length 100000: 13250
        // Elapsed Time For Length 200000: 49951
        //
        //
        // HEAP SORT
        sortTest(20);

        sortTest(200000);

        sortTest(2000000);

        sortTest(20000000);

        sortTest(40000000);

        // Elapsed Time For Length 20: 0
        // Elapsed Time For Length 200000: 21
        // Elapsed Time For Length 2000000: 196
        // Elapsed Time For Length 20000000: 7919
        // Elapsed Time For Length 40000000: 24130
        //
        // Looks like heap sort is much faster than bubble sort in this instance
    }

    public static void testHeap(int length) {
        IntMinHeap x = new IntMinHeap();

        for (int random : generateRandom(length)) {
            x.add(random);
        }

        x.addCountedLoops(-1);
    }

    public static void sortTest(int length) {
        int[] array = generateRandom(length);

        if (length < 25) System.out.println(Arrays.toString(array));

        long timeOne = System.currentTimeMillis();

        heapSort(array);

        long timeTwo = System.currentTimeMillis();

        if (length < 25) System.out.println(Arrays.toString(array));

        System.out.println(
            "Elapsed Time For Length " + length + ": " + (timeTwo - timeOne)
        );
    }

    public static void heapSort(int[] array) {
        IntMinHeap heap = new IntMinHeap(array.length);

        for (int num : array) {
            heap.add(num);
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = heap.remove();
        }
    }

    public static int[] generateRandom(int length) {
        int[] a = new int[length];
        for (int i = 0; i < length; i++) a[i] = (int) (Math.random() *
            length *
            10);
        return a;
    }

    public static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 1; j < a.length - i; j++) {
                if (a[j - 1] > a[j]) IntMinHeap.swap(a, j - 1, j);
            }
        }
    }
}