#include <iostream>
#include <algorithm>
#include <chrono>

const std::size_t SIZE = 3000;

// =====================================================================
// 1. C++14 Fix: Custom Constexpr Array
// Bypasses the C++14 std::array limitation where operator[] isn't constexpr
// =====================================================================
template <typename T, std::size_t N>
struct CXArray {
    T data[N];
    
    // Explicitly marking both const and non-const operator[] as constexpr
    constexpr T& operator[](std::size_t i) { return data[i]; }
    constexpr const T& operator[](std::size_t i) const { return data[i]; }
    
    // Iterators so std::sort still works in our benchmark
    constexpr T* begin() { return data; }
    constexpr T* end() { return data + N; }
    constexpr const T* begin() const { return data; }
    constexpr const T* end() const { return data + N; }
};

// =====================================================================
// 2. C++14 Compile-Time Helpers
// =====================================================================
template <typename T>
constexpr void cx_swap(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}

// =====================================================================
// 3. C++14 Template Metaprogramming Quicksort (Compile-Time)
// =====================================================================
template <typename T, std::size_t N>
constexpr void compile_time_sort(CXArray<T, N>& arr, int left, int right) {
    if (left >= right) return;
    
    T pivot = arr[left + (right - left) / 2];
    int i = left;
    int j = right;
    
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        
        if (i <= j) {
            cx_swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    
    if (left < j) compile_time_sort(arr, left, j);
    if (i < right) compile_time_sort(arr, i, right);
}

// Wrapper to return the sorted array
template <typename T, std::size_t N>
constexpr CXArray<T, N> generate_sorted(CXArray<T, N> arr) {
    compile_time_sort(arr, 0, N - 1);
    return arr;
}

// =====================================================================
// 4. Constexpr Random Number Generator (LCG)
// =====================================================================
constexpr CXArray<int, SIZE> generate_random_data() {
    CXArray<int, SIZE> arr{};
    unsigned int seed = 12345;
    for (std::size_t i = 0; i < SIZE; ++i) {
        seed = (1103515245 * seed + 12345) % 2147483648; 
        arr[i] = seed % 100000;
    }
    return arr;
}

// The compiler generates, sorts, and embeds this in the binary
constexpr auto unsorted_data = generate_random_data();
constexpr auto sorted_data = generate_sorted(unsorted_data);

// =====================================================================
// Benchmark Engine
// =====================================================================
int main() {
    std::cout << "Data Size: " << SIZE << " elements\n";

    // Benchmark 1: std::sort (Runtime)
    CXArray<int, SIZE> runtime_data = unsorted_data; 
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::sort(runtime_data.begin(), runtime_data.end());
    auto end1 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time_std = end1 - start1;

    // Benchmark 2: Compile-Time Metaprogramming Sort
    auto start2 = std::chrono::high_resolution_clock::now();
    
    // Prevent compiler from optimizing the clock check away
    volatile int dummy = sorted_data[0]; 
    
    auto end2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time_cx = end2 - start2;

    // Results
    std::cout << "\n--- Benchmark Results ---\n";
    std::cout << "Runtime std::sort:   " << time_std.count() << " ms\n";
    std::cout << "Compile-Time sort:   " << time_cx.count() << " ms\n";

    bool correct = std::is_sorted(sorted_data.begin(), sorted_data.end());
    std::cout << "\nCompile-Time array is sorted correctly: " << (correct ? "True" : "False") << "\n";

    return 0;
}