/*! @file big-o.cpp
 *  Big O complexity of std::sort vs. radix sort
 */

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <list>
#include <random>
#include <vector>

typedef std::vector<uint64_t> TestCase;

// typedef std::list<uint64_t> Bucket;
typedef std::vector<uint64_t> Bucket;
// typedef std::deque<uint64_t> Bucket;


uint64_t gen_random()
{
    static std::random_device rd;
    static std::mt19937 gen(rd());
    static std::uniform_int_distribution<uint64_t> dis;
    return dis(gen);
}

TestCase gen_test(size_t n)
{
    TestCase output;
    output.reserve(n);
    for (size_t i = 0; i < n; i++) {
        output.push_back(gen_random());
    }
    return output;
}

void compare_sort(TestCase& input)
{
    std::sort(input.begin(), input.end());
}

template<size_t K = 8> void radix_bucket_sort(TestCase& input)
{
    constexpr size_t slots = 1 << K;
    constexpr TestCase::value_type mask = slots - 1;
    constexpr size_t bits = sizeof(TestCase::value_type) * 8;
    for (int r = 0; r < bits; r += K) {
        Bucket radixes[slots];
        for (auto n : input) {
            radixes[(n >> r) & mask].push_back(n);
        }
        input.clear();
        for (auto& bucket : radixes) {
            input.insert(input.end(), bucket.begin(), bucket.end());
        }
    }
}

template<size_t K = 8> void radix_count_sort(TestCase& input)
{
    constexpr size_t slots = 1 << K;
    constexpr TestCase::value_type mask = slots - 1;
    constexpr size_t bits = sizeof(TestCase::value_type) * 8;

    TestCase output(input.size());

    for (int r = 0; r < bits; r += K) {
        size_t counts[slots] = {0};
        for (auto n : input) {
            ++counts[(n >> r) & mask];
        }
        size_t accum = 0;
        for (auto& n : counts) {
            n += accum;
            accum = n;
        }

        for (auto iter = input.rbegin(); iter != input.rend(); ++iter) {
            output[--counts[(*iter >> r) & mask]] = *iter;
        }

        std::swap(input, output);
    }
}

bool is_sorted(const TestCase& input)
{
    auto last = input[0];
    for (auto n : input) {
        if (n < last) {
            return false;
        }
        last = n;
    }
    return true;
}

std::chrono::nanoseconds run_test(const std::function<void(TestCase&)>& func, size_t n)
{
    TestCase input = gen_test(n);
    auto start = std::chrono::high_resolution_clock::now();
    func(input);
    auto stop = std::chrono::high_resolution_clock::now();

    assert(input.size() == n);
    assert(is_sorted(input));

    return stop - start;
}

int main(void)
{
    std::cout << "# n std::sort radix_bucket<4> radix_bucket<8> radix_count<4> radix_count<8>" << std::endl;
    for (size_t n = 100; n <= 1000000; n += 100) {
        uint64_t ttl_cmp(0), ttl_radix_4(0), ttl_radix_8(0);
        uint64_t ttl_count_4(0), ttl_count_8(0);

        for (int i = 0; i < 1; i++) {
            ttl_cmp += run_test(compare_sort, n).count();
            ttl_radix_4 += run_test(radix_bucket_sort<4>, n).count();
            ttl_radix_8 += run_test(radix_bucket_sort<8>, n).count();
            ttl_count_4 += run_test(radix_count_sort<4>, n).count();
            ttl_count_8 += run_test(radix_count_sort<8>, n).count();
        }

        std::cout << n
                  << " " << ttl_cmp * 1e-6
                  << " " << ttl_radix_4 * 1e-6
                  << " " << ttl_radix_8 * 1e-6
                  << " " << ttl_count_4 * 1e-6
                  << " " << ttl_count_8 * 1e-6
                  << std::endl;
    }

    return 0;
}