text: //----------------------------------------------------------------------------
  /// @file benchmark_objects.cpp
  /// @brief Benchmark of several sort methods with different objects
  ///
  /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n
  ///         Distributed under the Boost Software License, Version 1.0.\n
  ///         ( See accompanying file LICENSE_1_0.txt or copy at
  ///           http://www.boost.org/LICENSE_1_0.txt )
  ///
  ///         This program use for comparison purposes, the Threading Building
  ///         Blocks which license is the GNU General Public License, version 2
  ///         as  published  by  the  Free Software Foundation.
  ///
  /// @version 0.1
  ///
  /// @remarks
  //-----------------------------------------------------------------------------
  #include <algorithm>
  
  #include <iostream>
  #include <iomanip>
  #include <random>
  #include <stdlib.h>
  #include <vector>
  
  #include <boost/sort/common/time_measure.hpp>
  #include <boost/sort/common/file_vector.hpp>
  #include "boost/sort/common/int_array.hpp"
  
  #include <boost/sort/sort.hpp>
  
  
  #define NELEM 100000000
  #define NMAXSTRING 10000000
  
  using namespace std;
  namespace bsort = boost::sort;
  namespace bsc = bsort::common;
  
  
  using bsc::time_point;
  using bsc::now;
  using bsc::subtract_time;
  using bsc::fill_vector_uint64;
  using bsc::write_file_uint64;
  using bsc::int_array;
  using bsc::H_comp;
  using bsc::L_comp;
  
  using bsort::flat_stable_sort;
  using bsort::spinsort;
  using bsort::spreadsort::spreadsort;
  using bsort::pdqsort;
  
  
  template <class IA>
  void Generator_random(uint64_t N);
  
  template <class IA>
  void Generator_sorted(uint64_t N);
  template <class IA>
  void Generator_sorted_end(uint64_t N, size_t n_last );
  
  template <class IA>
  void Generator_sorted_middle(uint64_t N, size_t n_last );
  
  template <class IA>
  void Generator_reverse_sorted(uint64_t N);
  
  template <class IA>
  void Generator_reverse_sorted_end(uint64_t N, size_t n_last );
  
  template <class IA>
  void Generator_reverse_sorted_middle(uint64_t N, size_t n_last );
  
  template < class IA >
  struct H_rightshift {
    inline uint64_t operator()(const IA& A1, unsigned offset) {
      return A1.counter() >> offset;
    }
  };
  
  template < class IA >
  struct L_rightshift {
    inline uint64_t operator()(const IA& A1, unsigned offset) {
      return A1.M[0] >> offset;
    }
  };
  
  template <class IA, class rightshift, class compare>
  int Test(std::vector<IA> &B, rightshift shift, compare comp, std::vector<double> & V );
  
  template <class IA>
  void Test_size ( uint64_t N);
  
  void Print_vectors ( std::vector<double> & V1, std::vector<double> & V2);
  
  int main(int argc, char *argv[])
  {
      cout << "\n\n";
      cout << "************************************************************\n";
      cout << "**                                                        **\n";
      cout << "**                  B O O S T    S O R T                  **\n";
      cout << "**                                                        **\n";
      cout << "**          O B J E C T S     B E N C H M A R K           **\n";
      cout << "**                                                        **\n";
      cout << "************************************************************\n";
      cout << std::endl;
  
      cout << "=============================================================\n";
      cout << "=            OBJECT COMPARISON                              =\n";
      cout << "=          ---------------------                            =\n";
      cout << "=                                                           =\n";
      cout << "= The objects are arrays of 64 bits numbers                 =\n";
      cout << "= They are compared in two ways :                           =\n";
      cout << "= (H) Heavy : The comparison is the sum of all the numbers  =\n";
      cout << "=             of the array                                  =\n";
      cout << "= (L) Light : The comparison is with the first element of   =\n";
      cout << "=             the array, as a key                           =\n";
      cout << "=                                                           =\n";
      cout << "============================================================\n";
      cout << "\n\n";
  
      //-----------------------------------------------------------------------
      //                  I N T _ A R R A Y < 1 >
      //-----------------------------------------------------------------------
      cout << "************************************************************\n";
      cout << "**                                                        **\n";
      cout << "              "<<NELEM<<" OBJECTS UINT64_T [1]\n";
      cout << "**                                                        **\n";
      cout << "************************************************************\n";
  
      Test_size<int_array<1> >(NELEM);
  
      //-----------------------------------------------------------------------
      //                  I N T _ A R R A Y < 4 >
      //-----------------------------------------------------------------------
      cout << "************************************************************\n";
      cout << "**                                                        **\n";
      cout << "              "<<(NELEM >>2)<<" OBJECTS UINT64_T [4]\n";
      cout << "**                                                        **\n";
      cout << "************************************************************\n";
      Test_size<int_array<4> >(NELEM >> 2);
  
      //-----------------------------------------------------------------------
      //                  I N T _ A R R A Y < 8 >
      //-----------------------------------------------------------------------
      cout << "************************************************************\n";
      cout << "**                                                        **\n";
      cout << "            "<<(NELEM >>3)<<" OBJECTS UINT64_T [8]\n";
      cout << "**                                                        **\n";
      cout << "************************************************************\n";
      Test_size<int_array<8> >(NELEM >> 3);
  
      //-----------------------------------------------------------------------
      //                  I N T _ A R R A Y < 1 6 >
      //-----------------------------------------------------------------------
      cout << "************************************************************\n";
      cout << "**                                                        **\n";
      cout << "            "<<(NELEM >>4)<<" OBJECTS UINT64_T [16]\n";
      cout << "**                                                        **\n";
      cout << "************************************************************\n";
      Test_size<int_array<16> >(NELEM >> 4);
  
      //-----------------------------------------------------------------------
      //                  I N T _ A R R A Y < 6 4 >
      //-----------------------------------------------------------------------
      cout << "************************************************************\n";
      cout << "**                                                        **\n";
      cout << "            "<< (NELEM >>6)<<" OBJECTS UINT64_T [64]\n";
      cout << "**                                                        **\n";
      cout << "************************************************************\n";
      Test_size<int_array<64> >(NELEM >> 6);
  
     return 0;
  }
  
  template <class IA>
  void Test_size ( uint64_t N)
  {
      cout<<"\n";
      cout<<"[ 1 ] std::sort   [ 2 ] pdqsort          [ 3 ] std::stable_sort \n";
      cout<<"[ 4 ] spinsort    [ 5 ] flat_stable_sort [ 6 ] spreadsort\n\n";
  
      cout << "                    |   [ 1 ]   |   [ 2 ]   |   [ 3 ]   |";
      cout << "   [ 4 ]   |   [ 5 ]   |   [ 6 ]   |\n";
  
  
  
      //cout << "                    |           |           |           |";
      //cout << "           |           |           |\n";
      cout << "                    |  H     L  |  H     L  |  H     L  |";
      cout << "  H     L  |  H     L  |  H     L  |\n";
      cout << "--------------------+-----------+-----------+-----------+";
      cout << "-----------+-----------+-----------+\n";
      std::string empty_line = "                    |           |           |"
                           "           |           |           |           |\n";
  
      cout<<"random              |";
      Generator_random<IA>(N);
  
      cout<<empty_line;
      cout<<"sorted              |";
      Generator_sorted<IA>(N);
  
      cout<<"sorted + 0.1% end   |";
      Generator_sorted_end<IA>(N, N / 1000);
  
      cout<<"sorted +   1% end   |";
      Generator_sorted_end<IA>(N, N / 100);
  
      cout<<"sorted +  10% end   |";
      Generator_sorted_end<IA>(N, N / 10);
  
      cout<<empty_line;
      cout<<"sorted + 0.1% mid   |";
      Generator_sorted_middle<IA>(N, N / 1000);
  
      cout<<"sorted +   1% mid   |";
      Generator_sorted_middle<IA>(N, N / 100);
  
      cout<<"sorted +  10% mid   |";
      Generator_sorted_middle<IA>(N, N / 10);
  
      cout<<empty_line;
      cout<<"reverse sorted      |";
      Generator_reverse_sorted<IA>(N);
  
      cout<<"rv sorted + 0.1% end|";
      Generator_reverse_sorted_end<IA>(N, N / 1000);
  
      cout<<"rv sorted +   1% end|";
      Generator_reverse_sorted_end<IA>(N, N / 100);
  
      cout<<"rv sorted +  10% end|";
      Generator_reverse_sorted_end<IA>(N, N / 10);
  
      cout<<empty_line;
      cout<<"rv sorted + 0.1% mid|";
      Generator_reverse_sorted_middle<IA>(N, N / 1000);
  
      cout<<"rv sorted +   1% mid|";
      Generator_reverse_sorted_middle<IA>(N, N / 100);
  
      cout<<"rv sorted +  10% mid|";
      Generator_reverse_sorted_middle<IA>(N, N / 10);
      cout<< "--------------------+-----------+-----------+-----------+";
      cout << "-----------+-----------+-----------+\n";
      cout<<endl<<endl<<endl;
  }
  void Print_vectors ( std::vector<double> & V1, std::vector<double> & V2)
  {
      assert ( V1.size() == V2.size());
      std::cout<<std::setprecision(2)<<std::fixed;
      for ( uint32_t i =0 ; i < V1.size() ; ++i)
      {   std::cout<<std::right<<std::setw(5)<<V1[i]<<" ";
          std::cout<<std::right<<std::setw(5)<<V2[i]<<"|";
      };
      std::cout<<std::endl;
  }
  
  template <class IA>
  void Generator_random(uint64_t N)
  {
      bsc::uint64_file_generator gen("input.bin");
      vector<IA> A;
      A.reserve(N);
      std::vector<double> V1, V2 ;
  
      gen.reset();
      A.clear();
      for (uint32_t i = 0; i < N; i++) A.emplace_back(IA::generate(gen));
  
      Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
  
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  template <class IA>
  void Generator_sorted(uint64_t N)
  {
      bsc::uint64_file_generator gen("input.bin");
      vector<IA> A;
      A.reserve(N);
      std::vector<double> V1, V2 ;
  
      gen.reset();
      A.clear();
      for (uint32_t i = 0; i < N; i++) A.emplace_back(IA::generate(gen));
  
      std::sort( A.begin() , A.end(),H_comp<IA>() );
      Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
  
      std::sort( A.begin() , A.end(),L_comp<IA>() );
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  
  template <class IA>
  void Generator_sorted_end(uint64_t N, size_t n_last )
  {
      bsc::uint64_file_generator gen("input.bin");
      vector<IA> A;
      A.reserve(N);
      std::vector<double> V1, V2 ;
  
      gen.reset();
      A.clear();
      for (uint32_t i = 0; i < (N + n_last); i++)
          A.emplace_back(IA::generate(gen));
      std::sort ( A.begin() , A.begin() + N ,H_comp<IA>());
  
      Test(A, H_rightshift<IA>(), H_comp<IA>(),V1);
      std::sort ( A.begin() , A.begin() + N ,L_comp<IA>());
  
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  template <class IA>
  void Generator_sorted_middle(uint64_t N, size_t n_last )
  {
      bsc::uint64_file_generator gen("input.bin");
      std::vector<double> V1, V2 ;
      vector<IA> A;
      A.reserve(N + n_last);
  
      {   A.clear() ;
          gen.reset();
          vector<IA> B, C;
          C.reserve(N + n_last);
          B.reserve ( n_last);
          for (uint32_t i = 0; i < (N + n_last); i++)
              C.emplace_back(IA::generate(gen));
  
          for ( size_t i = N ; i < C.size() ; ++i)
              B.push_back ( std::move ( C[i]));
  
          C.resize ( N);
  
          std::sort ( C.begin() , C.end() ,H_comp<IA>());
          size_t step = N /n_last  ;
          size_t pos = 0 ;
  
          for ( size_t i =0 ; i < B.size() ; ++i)
          {   A.push_back ( B[i]);
              for ( size_t k = 0 ; k < step ; ++k )
                  A.push_back ( C[pos++] );
          };
          while ( pos < C.size() )
              A.push_back ( C[pos++]);
      };
  
      Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
  
      {   A.clear() ;
          gen.reset();
          vector<IA> B,C;
          C.reserve(N + n_last);
          B.reserve ( n_last);
          for (uint32_t i = 0; i < (N + n_last); i++)
              C.emplace_back(IA::generate(gen));
  
          for ( size_t i = N ; i < C.size() ; ++i)
              B.push_back ( std::move ( C[i]));
  
          C.resize ( N);
  
          std::sort ( C.begin() , C.end() ,L_comp<IA>());
          size_t step = N /n_last  ;
          size_t pos = 0 ;
  
          for ( size_t i =0 ; i < B.size() ; ++i)
          {   A.push_back ( B[i]);
              for ( size_t k = 0 ; k < step ; ++k )
                  A.push_back ( C[pos++] );
          };
          while ( pos < C.size() )
              A.push_back ( C[pos++]);
      };
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  template <class IA>
  void Generator_reverse_sorted(uint64_t N)
  {
      bsc::uint64_file_generator gen("input.bin");
      vector<IA> A;
      A.reserve(N);
      std::vector<double> V1, V2 ;
  
      gen.reset();
      A.clear();
      for (uint32_t i = 0; i < N; i++) A.emplace_back(IA::generate(gen));
  
      std::sort( A.begin() , A.end(),H_comp<IA>() );
      for ( size_t i = 0; i < (A.size() >>1) ; ++i)
          std::swap ( A[i], A[A.size() - i -1 ]);
  
      Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
  
      std::sort( A.begin() , A.end(),L_comp<IA>() );
      for ( size_t i = 0; i < (A.size() >>1) ; ++i)
          std::swap ( A[i], A[A.size() - i -1 ]);
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  template <class IA>
  void Generator_reverse_sorted_end(uint64_t N, size_t n_last )
  {
      bsc::uint64_file_generator gen("input.bin");
      vector<IA> A;
      A.reserve(N);
      std::vector<double> V1, V2 ;
  
      gen.reset();
      A.clear();
      for (uint32_t i = 0; i < (N + n_last); i++)
          A.emplace_back(IA::generate(gen));
      std::sort ( A.begin() , A.begin() + N ,H_comp<IA>());
      for ( size_t i =0 ; i < (N>>1); ++i)
          std::swap ( A[i], A[N-1-i]);
  
      Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
      std::sort ( A.begin() , A.begin() + N ,L_comp<IA>());
      for ( size_t i =0 ; i < (N>>1); ++i)
          std::swap ( A[i], A[N-1-i]);
  
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  template <class IA>
  void Generator_reverse_sorted_middle(uint64_t N, size_t n_last )
  {
      bsc::uint64_file_generator gen("input.bin");
      std::vector<double> V1, V2 ;
      vector<IA> A;
      A.reserve(N + n_last);
  
      {   A.clear() ;
          gen.reset();
          vector<IA> B,C;
          C.reserve(N + n_last);
          B.reserve ( n_last);
          for (uint32_t i = 0; i < (N + n_last); i++)
              C.emplace_back(IA::generate(gen));
  
          for ( size_t i = N ; i < C.size() ; ++i)
              B.push_back ( std::move ( C[i]));
  
          C.resize ( N);
  
          std::sort ( C.begin() , C.end() ,H_comp<IA>());
  
          for ( size_t i =0 ; i < (N>>1); ++i)
              std::swap ( C[i], C[N-1-i]);
  
          size_t step = N /n_last  ;
          size_t pos = 0 ;
  
          for ( size_t i =0 ; i < B.size() ; ++i)
          {   A.push_back ( B[i]);
              for ( size_t k = 0 ; k < step ; ++k )
                  A.push_back ( C[pos++ ] );
          };
          while ( pos < C.size() )
              A.push_back ( C[pos++]);
      };
  
      Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
  
      {   A.clear() ;
          gen.reset();
          vector<IA> B,C;
          C.reserve(N + n_last);
          B.reserve ( n_last);
          for (uint32_t i = 0; i < (N + n_last); i++)
              C.emplace_back(IA::generate(gen));
  
          for ( size_t i = N ; i < C.size() ; ++i)
              B.push_back ( std::move ( C[i]));
  
          C.resize ( N);
  
          std::sort ( C.begin() , C.end() ,L_comp<IA>());
  
          for ( size_t i =0 ; i < (N>>1); ++i)
              std::swap ( C[i], C[N-1-i]);
          size_t step = N /n_last  ;
          size_t pos = 0 ;
  
          for ( size_t i =0 ; i < B.size() ; ++i)
          {   A.push_back ( B[i]);
              for ( size_t k = 0 ; k < step ; ++k )
                  A.push_back ( C[pos++ ] );
          };
          while ( pos < C.size() )
              A.push_back ( C[pos++]);
      };
  
      Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
      Print_vectors ( V1, V2 ) ;
  };
  
  template<class IA, class rightshift, class compare>
  int Test (std::vector<IA> &B, rightshift shift, compare comp,std::vector<double> &V)
  {   //---------------------------- begin --------------------------------
      double duration;
      time_point start, finish;
      std::vector<IA> A (B);
      V.clear() ;
  
      //--------------------------------------------------------------------
      A = B;
      start = now ();
      std::sort (A.begin (), A.end (), comp);
      finish = now ();
      duration = subtract_time (finish, start);
      V.push_back (duration);
  
      A = B;
      start = now ();
      pdqsort (A.begin (), A.end (), comp);
      finish = now ();
      duration = subtract_time (finish, start);
      V.push_back (duration);
  
      A = B;
      start = now ();
      std::stable_sort (A.begin (), A.end (), comp);
      finish = now ();
      duration = subtract_time (finish, start);
      V.push_back (duration);
  
      A = B;
      start = now ();
      spinsort (A.begin (), A.end (), comp);
      finish = now ();
      duration = subtract_time (finish, start);
      V.push_back (duration);
  
      A = B;
      start = now ();
      flat_stable_sort (A.begin (), A.end (), comp);
      finish = now ();
      duration = subtract_time (finish, start);
      V.push_back (duration);
  
      A = B;
      start = now ();
      boost::sort::spreadsort::integer_sort (A.begin (), A.end (), shift, comp);
      finish = now ();
      duration = subtract_time (finish, start);
      V.push_back (duration);
  
      return 0;
  };
  