#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <boost/sort/sort.hpp>

using namespace std;

#define LEN   4
#define COUNT 1000000
#define USE_BOOST_SORT

// simple structure that i think to be identical to std::string
struct test
{
    inline bool operator<(const test& a) const  noexcept
    {
        size_t minsize = len < a.len ? len : a.len;
        int res = ::memcmp(ptr, a.ptr, minsize);
        return res < 0 || (res == 0 && len < a.len);
    }
    inline size_t size() const noexcept
    {return len;}
    inline const char* data() const noexcept
    {return ptr;}
    inline const char& operator[](size_t index) const noexcept
    {return ptr[index];}

    const char* ptr = nullptr;
    size_t len = 0;
};


int main(int,char**)
{
    // stage 1.a - initialize string sorting data with randoms
    vector<string> strings;
    strings.resize(COUNT);
    int counter = 0;
    for (string& s : strings)
    {
        s.resize(LEN);
        for (char& c : s)
            c = (counter++) % 256;
    }
    // stage 1.b - make the copy of data to get deterministic results and initialize tests array
    vector<string> strings_copy = strings;
    vector<test> tests;
    tests.resize(strings_copy.size());
    for (size_t i = 0; i < tests.size(); ++i)
    {
        tests[i].ptr = strings_copy[i].data();
        tests[i].len = strings_copy[i].size();
    }

    //  stage 2. sorting
    for (size_t i = 0; i < 10; ++i)
    {
        // make the copy of data to keep order unchanged
        vector<string> to_be_sorted = strings;
        chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
#ifdef USE_BOOST_SORT
        boost::sort::spreadsort::string_sort(to_be_sorted.begin(), to_be_sorted.end());
#else
        sort(to_be_sorted.begin(), to_be_sorted.end());
#endif
        chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
        to_be_sorted.clear();
        // make the copy of tests for sorting
        vector<test> tests_for_sort = tests;
        chrono::high_resolution_clock::time_point t3 = chrono::high_resolution_clock::now();
#ifdef USE_BOOST_SORT
        boost::sort::spreadsort::string_sort(tests_for_sort.begin(), tests_for_sort.end());
#else
        sort(tests_for_sort.begin(), tests_for_sort.end());
#endif
        chrono::high_resolution_clock::time_point t4 = chrono::high_resolution_clock::now();

        cout << "String sort time: " << chrono::duration_cast<chrono::milliseconds>(t2-t1).count()
             << " msec" << endl;
        cout << "Test sort time: " << chrono::duration_cast<chrono::milliseconds>(t4-t3).count()
             << " msec" << endl;
    }
}