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

// We are now sorting 100,000 elements at compile time!
const std::size_t SIZE = 100000;

// =====================================================================
// 1. C++14 Constexpr Array 
// =====================================================================
template <typename T, std::size_t N>
struct CXArray {
    T data[N];
    constexpr T& operator[](std::size_t i) { return data[i]; }
    constexpr const T& operator[](std::size_t i) const { return data[i]; }
    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. The 100k Strategy: Constexpr Radix Sort O(N)
// Reduces 20,000,000 compiler steps to just 1,600,000 steps
// =====================================================================
template <typename T, std::size_t N>
constexpr CXArray<T, N> generate_radix_sort(CXArray<T, N> arr) {
    // We allocate a buffer entirely inside compiler memory
    CXArray<T, N> buffer{}; 
    
    // 4 passes for 32-bit integers (8 bits / base-256 per pass)
    for (int byte = 0; byte < 4; ++byte) {
        int counts[256] = {0};
        int shift = byte * 8;
        
        // Step A: Count frequencies (O(N))
        for (std::size_t i = 0; i < N; ++i) {
            unsigned int val = static_cast<unsigned int>(arr[i]);
            counts[(val >> shift) & 0xFF]++;
        }
        
        // Step B: Prefix sums (O(256))
        int pos[256] = {0};
        for (int i = 1; i < 256; ++i) {
            pos[i] = pos[i - 1] + counts[i - 1];
        }
        
        // Step C: Scatter to buffer (O(N))
        for (std::size_t i = 0; i < N; ++i) {
            unsigned int val = static_cast<unsigned int>(arr[i]);
            int bucket = (val >> shift) & 0xFF;
            buffer[pos[bucket]++] = arr[i];
        }
        
        // Step D: Copy back to array (O(N))
        for (std::size_t i = 0; i < N; ++i) {
            arr[i] = buffer[i];
        }
    }
    
    return arr;
}

// =====================================================================
// 3. Constexpr Data Generation
// =====================================================================
constexpr CXArray<int, SIZE> generate_random_data() {
    CXArray<int, SIZE> arr{};
    unsigned int seed = 987654321;
    for (std::size_t i = 0; i < SIZE; ++i) {
        seed = (1103515245 * seed + 12345) % 2147483648; 
        arr[i] = seed % 10000000; // Generate numbers up to 10 million
    }
    return arr;
}

// 💥 COMPILER EXECUTES 100,000 ELEMENT RADIX SORT HERE 💥
constexpr auto unsorted_data = generate_random_data();
constexpr auto sorted_data = generate_radix_sort(unsorted_data);

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

    // 1. Runtime Standard Sort Benchmark
    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;

    // 2. Compile-Time Sort Benchmark (0ms)
    auto start2 = std::chrono::high_resolution_clock::now();
    volatile int dummy = sorted_data[0]; 
    auto end2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time_cx = end2 - start2;

    std::cout << "\n--- Benchmark Results ---\n";
    std::cout << "Runtime std::sort:          " << time_std.count() << " ms\n";
    std::cout << "Compile-Time Radix 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;
}