#include <boost/container/vector.hpp>
#include <boost/double_ended/devector.hpp>
#include <boost/range/counting_range.hpp>

#include <benchmark/benchmark.h>

#include <algorithm>
#include <chrono>
#include <numeric> 
#include <random>
#include <vector>

namespace 
{

    using namespace std::chrono;


    void devector_insert( benchmark::State& state )
    {
        boost::double_ended::devector<std::size_t> c( state.range(0), 123lu );
        c.reserve_front(c.size() + 10);
        c.reserve_back(c.size() + 10);

        while (state.KeepRunning())
        {
            boost::container::vector<double> time;
            time.reserve( state.range( 0 ) );

            for (std::size_t p = 0; p < c.size(); ++p)
            {
                auto start = high_resolution_clock::now();
                c.insert(c.begin() + p, p);
                auto end = high_resolution_clock::now();
                auto elapsed_time = duration_cast<std::chrono::duration<double>>( end - start );
                time.push_back( elapsed_time.count() );
                c.erase(c.begin() + p);      
            }

            std::sort( time.begin(), time.end() );
            state.SetIterationTime( std::accumulate( time.begin(), time.end(), 0.0 ) );
        }
    }


    BENCHMARK( devector_insert )->RangeMultiplier( 2 )->Range( 2, 16 << 13 )->UseManualTime();


    void cvector_insert( benchmark::State& state )
    {
        boost::container::vector<std::size_t> c( state.range(0), 123lu );
        c.reserve(c.size() + 20);

        while (state.KeepRunning())
        {
            boost::container::vector<double> time;
            time.reserve( state.range( 0 ) );

            for( std::size_t p = 0; p < c.size(); ++p )
            {
                auto start = high_resolution_clock::now();
                c.insert( c.begin() + p, p );
                auto end = high_resolution_clock::now();
                auto elapsed_time = duration_cast<std::chrono::duration<double>>( end - start );
                time.push_back( elapsed_time.count() );
                c.erase( c.begin() + p );
            }

            std::sort( time.begin(), time.end() );
            state.SetIterationTime( std::accumulate( time.begin(), time.end(), 0.0 ) );
        }
    }


    BENCHMARK( cvector_insert )->RangeMultiplier( 2 )->Range( 2, 16 << 13 )->UseManualTime();

}

BENCHMARK_MAIN();