#include <algorithm>
#include <array>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <list>
#include <random>
#include <vector>

using namespace std;
using namespace std::chrono;

const int N_MAX = 120000;

std::mt19937 gen(127);
std::uniform_int_distribution<int> dist(0, N_MAX);

template <unsigned size> struct Foo {
    array<uint32_t, size> _data;

    explicit Foo(uint32_t val) {
        _data[0] = val;
    };

    bool operator<=(Foo rhs) {
        return _data[0] <= rhs._data[0];
    };

    bool operator<(Foo rhs) {
        return _data[0] < rhs._data[0];
    };
};

template <typename Container, typename ElementType>
void insert_sorted_stl(Container& cont, ElementType& ele) {
    auto it = lower_bound(cont.begin(), cont.end(), ele);
    cont.insert(it, ele);
}

template <typename Container, typename ElementType>
void insert_sorted_lin(Container& cont, ElementType& ele) {
    auto it = cont.begin();
    while (it != cont.end()) {
        if (ele <= *it) {
            cont.insert(it, ele);
            return;
        }
        ++it;
    }
    cont.push_back(ele);
}

template <typename Container, typename ElementType, typename Func>
uint32_t measure_container_algo(Container& cont, int count, Func insertFun) {
    time_point<high_resolution_clock> start;
    time_point<high_resolution_clock> stop;
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < count; i++) {
        ElementType ele(dist(gen));
        insertFun(cont, ele);
    }
    stop = std::chrono::high_resolution_clock::now();
    return duration_cast<microseconds>(stop - start).count();
}

void print_result(const char* container, const char* algo, unsigned long size,
    unsigned long dur) {
    cout << container << '\t' << algo << '\t' << std::setfill(' ')
         << std::setw(8) << size << '\t' << std::setfill(' ') << std::setw(8)
         << dur << endl;
}

template <typename ElementType> void runTest() {
    list<ElementType> l;
    vector<ElementType> v;
    long t;
    for (auto i : {10000, 40000, 80000, N_MAX}) {
        t = measure_container_algo<vector<ElementType>, ElementType>(
            v, i, insert_sorted_stl<vector<ElementType>, ElementType>);
        print_result("Vector", "STL", v.size(), t);
        v.clear();

        t = measure_container_algo<vector<ElementType>, ElementType>(
            v, i, insert_sorted_lin<vector<ElementType>, ElementType>);
        print_result("Vector", "Lin", v.size(), t);
        v.clear();

        t = measure_container_algo<list<ElementType>, ElementType>(
            l, i, insert_sorted_stl<list<ElementType>, ElementType>);
        print_result("List", "STL", l.size(), t);
        l.clear();

        t = measure_container_algo<list<ElementType>, ElementType>(
            l, i, insert_sorted_lin<list<ElementType>, ElementType>);
        print_result("List", "Lin", l.size(), t);
        l.clear();
    }
}


int main() {
    cout << "# Foo<8> size " << sizeof(Foo<8>) << endl;
    cout << "cont\talgo\telements\tduration[µs]" << endl;
    runTest<Foo<8>>();

    cout << "# Foo<128> size " << sizeof(Foo<128>) << endl;
    cout << "cont\talgo\telements\tduration[µs]" << endl;
    runTest<Foo<128>>();

    cout << "# Foo<1024> size " << sizeof(Foo<1024>) << endl;
    cout << "cont\talgo\telements\tduration[µs]" << endl;
    runTest<Foo<1024>>();
}