/* Performance comparison of plain vs. segmented for_each loops
 * over double_ended::batch_deque.
 *
 * Copyright 2017 Joaquin M Lopez Munoz.
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 */
  
#include "stdafx.h"
#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <numeric> 

std::chrono::high_resolution_clock::time_point measure_start,measure_pause;
    
template<typename F>
double measure(F f)
{
  using namespace std::chrono;
    
  static const int              num_trials=10;
  static const milliseconds     min_time_per_trial(200);
  std::array<double,num_trials> trials;
  volatile decltype(f())        res; /* to avoid optimizing f() away */
    
  for(int i=0;i<num_trials;++i){
    int                               runs=0;
    high_resolution_clock::time_point t2;
    
    measure_start=high_resolution_clock::now();
    do{
      res=f();
      ++runs;
      t2=high_resolution_clock::now();
    }while(t2-measure_start<min_time_per_trial);
    trials[i]=duration_cast<duration<double>>(t2-measure_start).count()/runs;
  }
  (void)res; /* var not used warn */
    
  std::sort(trials.begin(),trials.end());
  return std::accumulate(
    trials.begin()+2,trials.end()-2,0.0)/(trials.size()-4);
}

template<typename F>
double measure(unsigned int n,F f)
{
  double t=measure(f);
  return (t/n)*10E9;
}    

void pause_timing()
{
  measure_pause=std::chrono::high_resolution_clock::now();
}
    
void resume_timing()
{
  measure_start+=std::chrono::high_resolution_clock::now()-measure_pause;
}

#include <algorithm>
#include <boost/container/vector.hpp>
#include <boost/container/deque.hpp>
#include <boost/double_ended/devector.hpp>
#include <boost/double_ended/batch_deque.hpp>
#include <boost/preprocessor/stringize.hpp>
#include <boost/type_index.hpp>
#include <boost/range/counting_range.hpp>
#include <cmath>
#include <random>
#include <iostream>



template<typename Container1, typename Container2>
void measure_insert_contiguous()
{
  std::cout<<"n\t" << boost::typeindex::type_id<Container1>().pretty_name() << "\t" << boost::typeindex::type_id<Container2>().pretty_name() << "\t\n";
  for(std::size_t n=1000;n<=10000000;n*=10)
  {
    // set container size and allow for free capacity
    const std::size_t containerSize = n / 100;
    const std::size_t m = containerSize * 95 / 100;

    // set up positions
    auto insertRange = boost::counting_range<std::size_t>( 0, m );
    std::vector<std::size_t> insertPositions( insertRange.begin(), insertRange.end() );
    std::random_device rd;
    std::mt19937 generator( rd() );
    std::shuffle( insertPositions.begin(), insertPositions.end(), generator );


    auto f1=[&]()
    {
        Container1 container1;
        container1.reserve( containerSize );
        
        for( auto i = 0; i < m; ++i )
        {
            std::size_t position = container1.empty() ? 0 : insertPositions[i] % container1.size();
            //std::cout << position << ' ' << std::endl;
            container1.insert( container1.begin() + position, i );
        }

        return container1.size();
    };

    auto f2 = [&]()
    {
        Container2 container2( containerSize / 2, containerSize / 2, boost::double_ended::reserve_only_tag{} );

        for( auto i = 0; i < m; ++i )
        {
            std::size_t position = container2.empty() ? 0 : insertPositions[i] % container2.size();
            container2.insert( container2.begin() + position, i );
        }

        return container2.size();
    };

  
    std::cout<<"10E"<<int(std::log10(n))<<"\t"
                <<measure(n,f1)<<"\t"<<measure(n,f2)<<"\n";
  }
}


template<typename Container1, typename Container2>
void measure_erase_contiguous()
{
    std::cout << "n\t" << boost::typeindex::type_id<Container1>().pretty_name() << "\t" << boost::typeindex::type_id<Container2>().pretty_name() << "\t\n";
    for( std::size_t n = 1000; n <= 10000000; n *= 10 )
    {
        // set container size a
        const std::size_t containerSize = n / 100;

        // set up positions
        auto insertRange = boost::counting_range<std::size_t>( 0, containerSize );
        std::vector<std::size_t> insertPositions( insertRange.begin(), insertRange.end() );
        std::random_device rd;
        std::mt19937 generator( rd() );
        std::shuffle( insertPositions.begin(), insertPositions.end(), generator );

        auto f1 = [&]()
        {
            Container1 container1( containerSize, 42 );

            for( auto i = 0; i < containerSize; ++i )
            {
                std::size_t position = insertPositions[i] % container1.size();
                container1.erase( container1.begin() + position );
            }

            return container1.size();
        };

        auto f2 = [&]()
        {
            Container2 container2( containerSize, 42 );

            for( auto i = 0; i < containerSize; ++i )
            {
                std::size_t position = insertPositions[i] % container2.size();
                container2.erase( container2.begin() + position );
            }

            return container2.size();
        };


        std::cout << "10E" << int( std::log10( n ) ) << "\t"
            << measure( n, f1 ) << "\t" << measure( n, f2 ) << "\n";
    }
}


int main()
{

 
    measure_insert_contiguous<boost::container::vector<int>, boost::double_ended::devector<int>>();
    measure_erase_contiguous<boost::container::vector<int>, boost::double_ended::devector<int>>();

    std::cout << "\n";
}