#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 selectionSort(T* in, int size, int (*key)(const T&)) {
    int minValue;
    // move boundry of unsorted array one by one
    for (int i = 0; i < size - 1; i++) {
        // find the minimum element in the unsorted array
        minValue = i;
        for (int j = i + 1; j < size; j++) {
            if (key(in[j]) < key(in[minValue])) {
                minValue = j;
            }
        }

        // swap the minimum element with the current element
        T val = in[minValue];
        in[minValue] = in[i];
        in[i] = val;
    }
}

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();
        selectionSort(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();
        selectionSort(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();
        selectionSort<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;
}