/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2007-2009
//
// 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)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////

//Includes for tests
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/config.hpp>
#include <list>
#include <functional>
#include <iostream>
#include <boost/intrusive/list.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>

using namespace boost::posix_time;

//[perf_list_value_type
//Iteration and element count defines
const int NumIter = 100;
const int NumElements   = 50000;

using namespace boost::intrusive;

template<bool BigSize>  struct filler        {  int dummy[10];   };
template <>             struct filler<false> {};

template<bool BigSize> //The object for non-intrusive containers
struct test_class :  private filler<BigSize>
{
   int i_;
   test_class()               {}
   test_class(int i) :  i_(i) {}
   friend bool operator <(const test_class &l, const test_class &r)  {  return l.i_ < r.i_;  }
   friend bool operator >(const test_class &l, const test_class &r)  {  return l.i_ > r.i_;  }
};

template <bool BigSize, link_mode_type LinkMode>
struct itest_class   //The object for intrusive containers
   :  public list_base_hook<link_mode<LinkMode> >,  public test_class<BigSize>
{
   itest_class()                                {}
   itest_class(int i) : test_class<BigSize>(i)  {}
};

template<class FuncObj> //Adapts functors taking values to functors taking pointers
struct func_ptr_adaptor  :  public FuncObj
{
   typedef typename FuncObj::first_argument_type*  first_argument_type;
   typedef typename FuncObj::second_argument_type* second_argument_type;
   typedef typename FuncObj::result_type           result_type;
   result_type operator()(first_argument_type a,  second_argument_type b) const
      {  return FuncObj::operator()(*a, *b); }
};
//]

template <bool BigSize, link_mode_type LinkMode>
struct get_ilist  //Helps to define an intrusive list from a policy
{
   typedef list<itest_class<BigSize, LinkMode>, constant_time_size<false> > type;
};

template <bool BigSize> //Helps to define an std list
struct get_list      {  typedef std::list<test_class<BigSize> > type;   };

template <bool BigSize> //Helps to define an std pointer list
struct get_ptrlist   {  typedef std::list<test_class<BigSize>*> type;   };

////////////////////////////////////////////////////////////////////////
//
//                            PUSH_BACK
//
////////////////////////////////////////////////////////////////////////

template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_push_back()
{
   typedef typename get_ilist<BigSize, LinkMode>::type ilist;
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      //First create the elements and insert them in the intrusive list
      //[perf_list_push_back_intrusive
      std::vector<typename ilist::value_type> objects(NumElements);
      ilist l;
      for(int i = 0; i < NumElements; ++i)
         l.push_back(objects[i]);
      //Elements are unlinked in ilist's destructor
      //Elements are destroyed in vector's destructor
      //]
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_std_list_push_back()
{
   typedef typename get_list<BigSize>::type stdlist;
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      //Now create the std list and insert
      //[perf_list_push_back_stdlist
      stdlist l;
      for(int i = 0; i < NumElements; ++i)
         l.push_back(typename stdlist::value_type(i));
      //Elements unlinked and destroyed in stdlist's destructor
      //]
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_compact_std_ptrlist_push_back()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;
   //Now measure insertion time, including element creation
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      //Create elements and insert their pointer in the list
      //[perf_list_push_back_stdptrlist
      std::vector<typename stdlist::value_type> objects(NumElements);
      stdptrlist l;
      for(int i = 0; i < NumElements; ++i)
         l.push_back(&objects[i]);
      //Pointers to elements unlinked and destroyed in stdptrlist's destructor
      //Elements destroyed in vector's destructor
      //]
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "compact std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_disperse_std_ptrlist_push_back()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;
   //Now measure insertion time, including element creation
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      //Create elements and insert their pointer in the list
      //[perf_list_push_back_disperse_stdptrlist
      stdlist objects;  stdptrlist l;
      for(int i = 0; i < NumElements; ++i){
         objects.push_back(typename stdlist::value_type(i));
         l.push_back(&objects.back());
      }
      //Pointers to elements unlinked and destroyed in stdptrlist's destructor
      //Elements unlinked and destroyed in stdlist's destructor
      //]
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "disperse std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

////////////////////////////////////////////////////////////////////////
//
//                            REVERSE
//
////////////////////////////////////////////////////////////////////////

//[perf_list_reverse
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_reverse()
{
   typedef typename get_ilist<BigSize, LinkMode>::type ilist;
   //First create the elements
   std::vector<typename ilist::value_type> objects(NumElements);

   //Now create the intrusive list and insert data
   ilist l(objects.begin(), objects.end());

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      l.reverse();
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_std_list_reverse()
{
   typedef typename get_list<BigSize>::type stdlist;

   //Create the list and insert values
   stdlist l;
   for(int i = 0; i < NumElements; ++i)
      l.push_back(typename stdlist::value_type());

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      l.reverse();
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_compact_std_ptrlist_reverse()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;

   //First create the elements
   std::vector<typename stdlist::value_type> objects(NumElements);

   //Now create the std list and insert
   stdptrlist l;
   for(int i = 0; i < NumElements; ++i)
      l.push_back(&objects[i]);

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      l.reverse();
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "compact std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_disperse_std_ptrlist_reverse()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;

   //First create the elements
   std::list<typename stdlist::value_type> objects;
   //Now create the std list and insert
   stdptrlist l;
   for(int i = 0; i < NumElements; ++i){
      objects.push_back(typename stdlist::value_type());
      l.push_back(&objects.back());
   }

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      l.reverse();
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "disperse std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}
//]

////////////////////////////////////////////////////////////////////////
//
//                            SORT
//
////////////////////////////////////////////////////////////////////////

//[perf_list_sort
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_sort()
{
   typedef typename get_ilist<BigSize, LinkMode>::type ilist;

   //First create the elements
   std::vector<typename ilist::value_type> objects(NumElements);
   for(int i = 0; i < NumElements; ++i)
      objects[i].i_ = i;

   //Now create the intrusive list and insert data
   ilist l(objects.begin(), objects.end());

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      if(!(i % 2)){
         l.sort(std::greater<typename ilist::value_type>());
      }
      else{
         l.sort(std::less<typename ilist::value_type>());
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_std_list_sort()
{
   typedef typename get_list<BigSize>::type stdlist;

   //Create the list and insert values
   stdlist l;
   for(int i = 0; i < NumElements; ++i)
      l.push_back(typename stdlist::value_type(i));

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      if(!(i % 2)){
         l.sort(std::greater<typename stdlist::value_type>());
      }
      else{
         l.sort(std::less<typename stdlist::value_type>());
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_compact_std_ptrlist_sort()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;

   //First create the elements
   std::vector<typename stdlist::value_type> objects(NumElements);
   for(int i = 0; i < NumElements; ++i)
      objects[i].i_ = i;
   //Now create the std list and insert
   stdptrlist l;
   for(int i = 0; i < NumElements; ++i)
      l.push_back(&objects[i]);

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      if(!(i % 2)){
         l.sort(func_ptr_adaptor<std::greater<typename stdlist::value_type> >());
      }
      else{
         l.sort(func_ptr_adaptor<std::less<typename stdlist::value_type> >());
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "compact std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_disperse_std_ptrlist_sort()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;

   //First create the elements and the list
   std::list<typename stdlist::value_type> objects;
   stdptrlist l;
   for(int i = 0; i < NumElements; ++i){
      objects.push_back(typename stdlist::value_type(i));
      l.push_back(&objects.back());
   }

   //Now measure sorting time
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      if(!(i % 2)){
         l.sort(func_ptr_adaptor<std::greater<typename stdlist::value_type> >());
      }
      else{
         l.sort(func_ptr_adaptor<std::less<typename stdlist::value_type> >());
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "disperse std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}
//]

////////////////////////////////////////////////////////////////////////
//
//                            WRITE ACCESS
//
////////////////////////////////////////////////////////////////////////
//[perf_list_write_access
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_write_access()
{
   typedef typename get_ilist<BigSize, LinkMode>::type ilist;

   //First create the elements
   std::vector<typename ilist::value_type> objects(NumElements);
   for(int i = 0; i < NumElements; ++i){
      objects[i].i_ = i;
   }

   //Now create the intrusive list and insert data
   ilist l(objects.begin(), objects.end());

   //Now measure access time to the value type
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      typename ilist::iterator it(l.begin()), end(l.end());
      for(; it != end; ++it){
         ++(it->i_);
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_std_list_write_access()
{
   typedef typename get_list<BigSize>::type stdlist;

   //Create the list and insert values
   stdlist l;
   for(int i = 0; i < NumElements; ++i)
      l.push_back(typename stdlist::value_type(i));

   //Now measure access time to the value type
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      typename stdlist::iterator it(l.begin()), end(l.end());
      for(; it != end; ++it){
         ++(it->i_);
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_compact_std_ptrlist_write_access()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;

   //First create the elements
   std::vector<typename stdlist::value_type> objects(NumElements);
   for(int i = 0; i < NumElements; ++i){
      objects[i].i_ = i;
   }

   //Now create the std list and insert
   stdptrlist l;
   for(int i = 0; i < NumElements; ++i)
      l.push_back(&objects[i]);

   //Now measure access time to the value type
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      typename stdptrlist::iterator it(l.begin()), end(l.end());
      for(; it != end; ++it){
         ++((*it)->i_);
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "compact std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}

template <bool BigSize>
void test_disperse_std_ptrlist_write_access()
{
   typedef typename get_list<BigSize>::type stdlist;
   typedef typename get_ptrlist<BigSize>::type stdptrlist;

   //First create the elements
   std::list<typename stdlist::value_type> objects;
   //Now create the std list and insert
   stdptrlist l;
   for(int i = 0; i < NumElements; ++i){
      objects.push_back(typename stdlist::value_type(i));
      l.push_back(&objects.back());
   }

   //Now measure access time to the value type
   ptime tini = microsec_clock::universal_time();
   for(int i = 0; i < NumIter; ++i){
      typename stdptrlist::iterator it(l.begin()), end(l.end());
      for(; it != end; ++it){
         ++((*it)->i_);
      }
   }
   ptime tend = microsec_clock::universal_time();
   std::cout << "disperse std::list usecs/iteration: "
             << (tend-tini).total_microseconds()/NumIter << std::endl;
}
//]

////////////////////////////////////////////////////////////////////////
//
//                            ALL TESTS
//
////////////////////////////////////////////////////////////////////////
template<bool BigSize>
void do_all_tests()
{
   std::cout << "\n\nTesting push back() with BigSize:" << BigSize << std::endl;
   test_intrusive_list_push_back<BigSize, normal_link>();
   test_intrusive_list_push_back<BigSize, safe_link>();
   test_intrusive_list_push_back<BigSize, auto_unlink>();
   test_std_list_push_back<BigSize> ();
   test_compact_std_ptrlist_push_back<BigSize>();
   test_disperse_std_ptrlist_push_back<BigSize>();
   //reverse
   std::cout << "\n\nTesting reverse() with BigSize:" << BigSize << std::endl;
   test_intrusive_list_reverse<BigSize, normal_link>();
   test_intrusive_list_reverse<BigSize, safe_link>();
   test_intrusive_list_reverse<BigSize, auto_unlink>();
   test_std_list_reverse<BigSize>();
   test_compact_std_ptrlist_reverse<BigSize>();
   test_disperse_std_ptrlist_reverse<BigSize>();
   //sort
   std::cout << "\n\nTesting sort() with BigSize:" << BigSize << std::endl;
   test_intrusive_list_sort<BigSize, normal_link>();
   test_intrusive_list_sort<BigSize, safe_link>();
   test_intrusive_list_sort<BigSize, auto_unlink>();
   test_std_list_sort<BigSize>();
   test_compact_std_ptrlist_sort<BigSize>();
   test_disperse_std_ptrlist_sort<BigSize>();
   //write_access
   std::cout << "\n\nTesting write_access() with BigSize:" << BigSize << std::endl;
   test_intrusive_list_write_access<BigSize, normal_link>();
   test_intrusive_list_write_access<BigSize, safe_link>();
   test_intrusive_list_write_access<BigSize, auto_unlink>();
   test_std_list_write_access<BigSize>();
   test_compact_std_ptrlist_write_access<BigSize>();
   test_disperse_std_ptrlist_write_access<BigSize>();
}

int main()
{
   //First pass the tests with a small size class
   do_all_tests<false>();
   //Now pass the tests with a big size class
   do_all_tests<true>();
   return 0;
}

#include <boost/intrusive/detail/config_end.hpp>