#include <vector>
#include <random>
#include <algorithm>

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

#include <boost/range/counting_range.hpp>

#include <benchmark/benchmark.h>

namespace {

std::vector<std::size_t> getPositions(std::size_t n)
{
  auto range = boost::counting_range<std::size_t>(0, n);
  std::vector<std::size_t> positions(range.begin(), range.end());
  std::mt19937 generator(19937);
  std::shuffle(positions.begin(), positions.end(), generator);

  // normalize positions, no % on the hot path
  for (std::size_t i = 0; i < positions.size(); ++i)
  {
    positions[i] = positions[i] % (i + 1);
  }

  return positions;
}

void devector_insert(benchmark::State& state)
{
  const std::size_t n = state.range(0);
  const std::vector<std::size_t> positions(getPositions(n));
  boost::double_ended::devector<std::size_t> c;

  while (state.KeepRunning())
  {
    state.PauseTiming();
    c.clear();
    c.reserve_front(n/2);
    c.reserve_back(n/2);
    c.insert(c.begin(), 0);
    state.ResumeTiming();

    for (std::size_t p : positions)
    {
      c.insert(c.begin() + p, p);
    }
  }
}

BENCHMARK(devector_insert)->Range(256, 8<<13);

void cvector_insert(benchmark::State& state)
{
  const std::size_t n = state.range(0);
  const std::vector<std::size_t> positions(getPositions(n));
  boost::container::vector<std::size_t> c;

  while (state.KeepRunning())
  {
    state.PauseTiming();
    c.clear();
    c.reserve(n);
    c.insert(c.begin(), 0);
    state.ResumeTiming();

    for (std::size_t p : positions)
    {
      c.insert(c.begin() + p, p);
    }
  }
}

BENCHMARK(cvector_insert)->Range(256, 8<<13);

}

BENCHMARK_MAIN();