#include <chrono>
#include <iostream>

#define MAX_SIZE 200000

long getNanos() {
    return std::chrono::high_resolution_clock::now().time_since_epoch().count();
}

long getMillis() {
    return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}

int intKey(const int& i) {
    return i;
}

static unsigned long seed = 0;

int randomInt() {
    seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFF;
    return static_cast<int>(seed >> 17);
}

template<typename T>
void bubbleSort(T* in, int size, int (*key)(const T&)) {
    bool madeSwap; // flag to know if we are done
    // make the bubble sort
    do {
        madeSwap = false;
        for (int i = 0; i < size - 1; i++) {
            // if this element is bigger that the next one swap places
            if (key(in[i]) > key(in[i + 1])) {
                madeSwap = true;
                T val = in[i + 1];
                in[i + 1] = in[i];
                in[i] = val;
            }
        }
    } while (madeSwap);
}

void cacheTest() {
    for (int size = 512; size < MAX_SIZE; size *= 2) {
        printf("Cache Test with size = %9d | ", size);
        constexpr int max = 500;
        int* a = new int[size];
        seed = 0;
        for (int i = 0; i < size; i++) {
            a[i] = randomInt() % max;
        }
        long time = -getNanos();
        bubbleSort(a, size, intKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
            (static_cast<double>(time) / size));
        delete[] a;
    }
}

struct A {
    int key;
    char filler[32];
};

int aKey(const A& a) {
    return a.key;
}

void structTest() {
    for (int size = 512; size < MAX_SIZE; size *= 2) {
        printf("Struct Test with size = %9d | ", size);
        constexpr int max = 500;
        A* a = new A[size];
        seed = 0;
        for (int i = 0; i < size; i++) {
            a[i].key = randomInt() % max;
        }
        long time = -getNanos();
        bubbleSort(a, size, aKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
            (static_cast<double>(time) / size));
        delete[] a;
    }
}

int pointerKey(int* const& a) {
    return *a;
}

void pointerTest() {
    for (int size = 512; size < MAX_SIZE; size *= 2) {
        printf("Pointer Test with size = %9d | ", size);
        constexpr int max = 500;
        int** a = new int* [size];
        seed = 0;
        for (int i = 0; i < size; i++) {
            a[i] = new int(randomInt() % max);
        }
        long time = -getNanos();
        bubbleSort<int*>(a, size, pointerKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
            (static_cast<double>(time) / size));
        for (int i = 0; i < size; i++) {
            delete a[i];
        }
        delete[] a;
    }
}

int main() {
    cacheTest();
    structTest();
    pointerTest();
    return 0;
}