#include <chrono>
#include <iostream>

long getNanos() {
    return 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>
T* countingSort(const T* in, int size, int max, int (*key)(const T&)) {
    max++;
    int* counter = new int[max];
    for(int i = 0; i < max; i++) {
        counter[i] = 0;
    }
    for(int i = 0; i < size; i++) {
        counter[key(in[i])]++;
    }
    for(int i = 1; i < max; i++) {
        counter[i] += counter[i - 1];
    }
    T* out = new T[size];
    for(int i = size - 1; i >= 0; i--) {
        out[counter[key(in[i])]-- - 1] = in[i];
    }
    delete[] counter;
    return out;
}

void cacheTest() {
    for(int size = 512; size < 100'000'000; 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();
        int* b = countingSort(a, size, max - 1, intKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
               (static_cast<double>(time) / size));
        delete[] a;
        delete[] b;
    }
}

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

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

void structTest() {
    for(int size = 512; size < 100'000'000; 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();
        A* b = countingSort(a, size, max - 1, aKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
               (static_cast<double>(time) / size));
        delete[] a;
        delete[] b;
    }
}

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

void pointerTest() {
    for(int size = 512; size < 100'000'000; 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();
        int** b = countingSort<int*>(a, size, max - 1, 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;
        delete[] b;
    }
}

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