/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2007-2013
//
// 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.
//
/////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP
#define BOOST_INTRUSIVE_TEST_CONTAINER_HPP

#include <boost/detail/lightweight_test.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/simple_disposers.hpp>
#include <boost/intrusive/detail/iterator.hpp>
#include <boost/move/utility_core.hpp>
#include <boost/move/adl_move_swap.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/static_assert.hpp>
#include "iterator_test.hpp"
#include <cstdlib>

namespace boost {
namespace intrusive {
namespace test {

BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(is_unordered, hasher)

template<class Container>
struct test_container_typedefs
{
   typedef typename Container::value_type       value_type;
   typedef typename Container::iterator         iterator;
   typedef typename Container::const_iterator   const_iterator;
   typedef typename Container::reference        reference;
   typedef typename Container::const_reference  const_reference;
   typedef typename Container::pointer          pointer;
   typedef typename Container::const_pointer    const_pointer;
   typedef typename Container::difference_type  difference_type;
   typedef typename Container::size_type        size_type;
   typedef typename Container::value_traits     value_traits;
};

template< class Container >
void test_container( Container & c )
{
   typedef typename Container::const_iterator   const_iterator;
   typedef typename Container::iterator         iterator;
   typedef typename Container::size_type        size_type;

   {test_container_typedefs<Container> dummy;  (void)dummy;}
   const size_type num_elem = c.size();
   BOOST_TEST( c.empty() == (num_elem == 0) );
   {
      iterator it(c.begin()), itend(c.end());
      size_type i;
      for(i = 0; i < num_elem; ++i){
         ++it;
      }
      BOOST_TEST( it == itend );
      BOOST_TEST( c.size() == i );
   }

   //Check iterator conversion
   BOOST_TEST(const_iterator(c.begin()) == c.cbegin() );
   {
      const_iterator it(c.cbegin()), itend(c.cend());
      size_type i;
      for(i = 0; i < num_elem; ++i){
         ++it;
      }
      BOOST_TEST( it == itend );
      BOOST_TEST( c.size() == i );
   }
   static_cast<const Container&>(c).check();
   //Very basic test for comparisons
   {
      BOOST_TEST(c == c);
      BOOST_TEST(!(c != c));
      BOOST_TEST(!(c < c));
      BOOST_TEST(c <= c);
      BOOST_TEST(!(c > c));
      BOOST_TEST(c >= c);
   }
}


template< class Container, class Data >
void test_sequence_container(Container & c, Data & d)
{
   assert( d.size() > 2 );
   {
      c.clear();

      BOOST_TEST( c.size() == 0 );
      BOOST_TEST( c.empty() );


      {
      typename Data::iterator i = d.begin();
      c.insert( c.begin(), *i );
      BOOST_TEST( &*c.iterator_to(*c.begin())  == &*i );
      BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &*i );
      BOOST_TEST( &*Container::s_iterator_to(*c.begin())  == &*i );
      BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &*i );
      c.insert( c.end(), *(++i) );
      }
      BOOST_TEST( c.size() == 2 );
      BOOST_TEST( !c.empty() );

      typename Container::iterator i;
      i = c.erase( c.begin() );

      BOOST_TEST( c.size() == 1 );
      BOOST_TEST( !c.empty() );

      i = c.erase( c.begin() );

      BOOST_TEST( c.size() == 0 );
      BOOST_TEST( c.empty() );

      c.insert( c.begin(), *d.begin() );

      BOOST_TEST( c.size() == 1 );
      BOOST_TEST( !c.empty() );

      {
      typename Data::iterator di = d.begin();
      ++++di;
      c.insert( c.begin(), *(di) );
      }

      i = c.erase( c.begin(), c.end() );
      BOOST_TEST( i == c.end() );

      BOOST_TEST( c.empty() );

      c.insert( c.begin(), *d.begin() );

      BOOST_TEST( c.size() == 1 );

      BOOST_TEST( c.begin() != c.end() );

      i = c.erase_and_dispose( c.begin(), detail::null_disposer() );
      BOOST_TEST( i == c.begin() );

      c.assign(d.begin(), d.end());

      BOOST_TEST( c.size() == d.size() );

      c.clear();

      BOOST_TEST( c.size() == 0 );
      BOOST_TEST( c.empty() );
   }
   {
      c.clear();
      c.insert( c.begin(), d.begin(), d.end() );
      Container move_c(::boost::move(c));
      BOOST_TEST( move_c.size() == d.size() );
      BOOST_TEST( c.empty());

      c = ::boost::move(move_c);
      BOOST_TEST( c.size() == d.size() );
      BOOST_TEST( move_c.empty());
   }
}

template< class Container, class Data >
void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::true_ unordered)
{
   (void)unordered;
   typedef typename Container::size_type        size_type;
   typedef typename Container::key_of_value     key_of_value;
   typedef typename Container::iterator         iterator;
   typedef typename Container::const_iterator   const_iterator;

   assert( d.size() > 2 );

   c.clear();
   c.insert(d.begin(), d.end());

   {
      Container const &cc = c;
      for( typename Data::const_iterator di = d.begin(), de = d.end();
         di != de; ++di )
      {
         BOOST_TEST( cc.find(key_of_value()(*di), c.hash_function(), c.key_eq()) != cc.end() );
         std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.hash_function(), c.key_eq());
         BOOST_TEST(rdi.first != rdi.second);
         BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.hash_function(), c.key_eq()));
      }

      for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
      {
         BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
         std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.hash_function(), c.key_eq());
         BOOST_TEST(rci.first != rci.second);
         size_type const sc = c.count(key_of_value()(*ci), c.hash_function(), c.key_eq());
         BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
         BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.hash_function(), c.key_eq()));
         ci = rci.second;
      }
      BOOST_TEST(c.empty());
   }

   c.clear();
   c.insert(d.begin(), d.end());

   typename Data::const_iterator db = d.begin();
   typename Data::const_iterator da = db++;

   size_type old_size = c.size();

   c.erase(key_of_value()(*da), c.hash_function(), c.key_eq());
   BOOST_TEST( c.size() == old_size-1 );
   //This should not eras anyone
   size_type second_erase = c.erase_and_dispose
      ( key_of_value()(*da), c.hash_function(), c.key_eq(), detail::null_disposer() );
   BOOST_TEST( second_erase == 0 );

   BOOST_TEST( c.count(key_of_value()(*da), c.hash_function(), c.key_eq()) == 0 );
   BOOST_TEST( c.count(key_of_value()(*db), c.hash_function(), c.key_eq()) != 0 );

   BOOST_TEST( c.find(key_of_value()(*da), c.hash_function(), c.key_eq()) == c.end() );
   BOOST_TEST( c.find(key_of_value()(*db), c.hash_function(), c.key_eq()) != c.end() );

   BOOST_TEST( c.equal_range(key_of_value()(*db), c.hash_function(), c.key_eq()).first != c.end() );

   c.clear();

   BOOST_TEST( c.equal_range(key_of_value()(*da), c.hash_function(), c.key_eq()).first == c.end() );

   //
   //suggested_upper_bucket_count
   //
   //Maximum fallbacks to the highest possible value
   typename Container::size_type sz = Container::suggested_upper_bucket_count(size_type(-1));
   BOOST_TEST( sz > size_type(-1)/2 );
   //In the rest of cases the upper bound is returned
   sz = Container::suggested_upper_bucket_count(size_type(-1)/2);
   BOOST_TEST( sz >= size_type(-1)/2 );
   sz = Container::suggested_upper_bucket_count(size_type(-1)/4);
   BOOST_TEST( sz >= size_type(-1)/4 );
   sz = Container::suggested_upper_bucket_count(0);
   BOOST_TEST( sz > 0 );
   //
   //suggested_lower_bucket_count
   //
   sz = Container::suggested_lower_bucket_count(size_type(-1));
   BOOST_TEST( sz <= size_type(-1) );
   //In the rest of cases the lower bound is returned
   sz = Container::suggested_lower_bucket_count(size_type(-1)/2);
   BOOST_TEST( sz <= size_type(-1)/2 );
   sz = Container::suggested_lower_bucket_count(size_type(-1)/4);
   BOOST_TEST( sz <= size_type(-1)/4 );
   //Minimum fallbacks to the lowest possible value
   sz = Container::suggested_upper_bucket_count(0);
   BOOST_TEST( sz > 0 );
}

template< class Container, class Data >
void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::false_ unordered)
{
   (void)unordered;
   typedef typename Container::size_type        size_type;
   typedef typename Container::key_of_value     key_of_value;
   typedef typename Container::iterator         iterator;
   typedef typename Container::const_iterator   const_iterator;

   assert( d.size() > 2 );

   c.clear();
   typename Container::reference r = *d.begin();
   c.insert(d.begin(), ++d.begin());
   BOOST_TEST( &*Container::s_iterator_to(*c.begin())  == &r );
   BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &r );

   c.clear();
   c.insert(d.begin(), d.end());
   {
      Container const &cc = c;
      for( typename Data::const_iterator di = d.begin(), de = d.end();
         di != de; ++di )
      {
         BOOST_TEST( cc.find(key_of_value()(*di), c.key_comp()) != cc.end() );
         std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.key_comp());
         BOOST_TEST(rdi.first != rdi.second);
         BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.key_comp()));
      }

      for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
      {
         BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
         std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.key_comp());
         BOOST_TEST(rci.first != rci.second);
         size_type const sc = c.count(key_of_value()(*ci), c.key_comp());
         BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
         BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.key_comp()));
         ci = rci.second;
      }
      BOOST_TEST(c.empty());
   }

   c.clear();
   c.insert(d.begin(), d.end());

   typename Data::const_iterator db = d.begin();
   typename Data::const_iterator da = db++;

   size_type old_size = c.size();

   c.erase(key_of_value()(*da), c.key_comp());
   BOOST_TEST( c.size() == old_size-1 );
   //This should not erase any
   size_type second_erase = c.erase_and_dispose( key_of_value()(*da), c.key_comp(), detail::null_disposer() );
   BOOST_TEST( second_erase == 0 );

   BOOST_TEST( c.count(key_of_value()(*da), c.key_comp()) == 0 );
   BOOST_TEST( c.count(key_of_value()(*db), c.key_comp()) != 0 );
   BOOST_TEST( c.find(key_of_value()(*da), c.key_comp()) == c.end() );
   BOOST_TEST( c.find(key_of_value()(*db), c.key_comp()) != c.end() );
   BOOST_TEST( c.equal_range(key_of_value()(*db), c.key_comp()).first != c.end() );
   c.clear();
   BOOST_TEST( c.equal_range(key_of_value()(*da), c.key_comp()).first == c.end() );
}

template< class Container, class Data >
void test_common_unordered_and_associative_container(Container & c, Data & d)
{
   typedef typename Container::size_type        size_type;
   typedef typename Container::key_of_value     key_of_value;
   typedef typename Container::iterator         iterator;
   typedef typename Container::const_iterator   const_iterator;

   {
      assert( d.size() > 2 );

      c.clear();
      typename Container::reference r = *d.begin();
      c.insert(d.begin(), ++d.begin());
      BOOST_TEST( &*c.iterator_to(*c.begin())  == &r );
      BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &r );

      c.clear();
      c.insert(d.begin(), d.end());

      Container const &cc = c;
      for( typename Data::const_iterator di = d.begin(), de = d.end();
         di != de; ++di )
      {
         BOOST_TEST( cc.find(key_of_value()(*di)) != cc.end() );
         std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di));
         BOOST_TEST(rdi.first != rdi.second);
         BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di)));
      }

      for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
      {
         BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
         std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci));
         BOOST_TEST(rci.first != rci.second);
         size_type const sc = c.count(key_of_value()(*ci));
         BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
         BOOST_TEST(sc == c.erase(key_of_value()(*ci)));
         ci = rci.second;
      }
      BOOST_TEST(c.empty());
   }
   {
      c.clear();
      c.insert(d.begin(), d.end());

      typename Data::const_iterator db = d.begin();
      typename Data::const_iterator da = db++;

      size_type old_size = c.size();

      c.erase(key_of_value()(*da));
      BOOST_TEST( c.size() == old_size-1 );
      //This should erase nothing
      size_type second_erase = c.erase_and_dispose( key_of_value()(*da), detail::null_disposer() );
      BOOST_TEST( second_erase == 0 );

      BOOST_TEST( c.count(key_of_value()(*da)) == 0 );
      BOOST_TEST( c.count(key_of_value()(*db)) != 0 );

      BOOST_TEST( c.find(key_of_value()(*da)) == c.end() );
      BOOST_TEST( c.find(key_of_value()(*db)) != c.end() );

      BOOST_TEST( c.equal_range(key_of_value()(*db)).first != c.end() );
      BOOST_TEST( c.equal_range(key_of_value()(*da)).first == c.equal_range(key_of_value()(*da)).second );
   }
   {
      c.clear();
      c.insert( d.begin(), d.end() );
      size_type orig_size = c.size();
      Container move_c(::boost::move(c));
      BOOST_TEST(orig_size == move_c.size());
      BOOST_TEST( c.empty());
      for( typename Data::const_iterator di = d.begin(), de = d.end();
         di != de; ++di )
      {  BOOST_TEST( move_c.find(key_of_value()(*di)) != move_c.end() );   }

      c = ::boost::move(move_c);
      for( typename Data::const_iterator di = d.begin(), de = d.end();
         di != de; ++di )
      {  BOOST_TEST( c.find(key_of_value()(*di)) != c.end() );   }
      BOOST_TEST( move_c.empty());
   }
   typedef detail::bool_<is_unordered<Container>::value> enabler;
   test_common_unordered_and_associative_container(c, d, enabler());
}

template< class Container, class Data >
void test_associative_container_invariants(Container & c, Data & d)
{
   typedef typename Container::const_iterator   const_iterator;
   typedef typename Container::key_of_value     key_of_value;
   for( typename Data::const_iterator di = d.begin(), de = d.end();
      di != de; ++di)
   {
      const_iterator ci = c.find(key_of_value()(*di));
      BOOST_TEST( ci != c.end() );
      BOOST_TEST( ! c.value_comp()(*ci, *di) );
      BOOST_TEST( ! c.key_comp()(key_of_value()(*ci), key_of_value()(*di)) );
      const_iterator cil = c.lower_bound(key_of_value()(*di));
      const_iterator ciu = c.upper_bound(key_of_value()(*di));
      std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di));
      BOOST_TEST( cil == er.first );
      BOOST_TEST( ciu == er.second );
      if(ciu != c.end()){
         BOOST_TEST( c.value_comp()(*cil, *ciu) );
         BOOST_TEST( c.key_comp()(key_of_value()(*cil), key_of_value()(*ciu)) );
      }
      if(c.count(key_of_value()(*di)) > 1){
         const_iterator ci_next = cil; ++ci_next;
         for( ; ci_next != ciu; ++cil, ++ci_next){
            BOOST_TEST( !c.value_comp()(*ci_next, *cil) );
            BOOST_TEST( !c.key_comp()(key_of_value()(*ci_next), key_of_value()(*cil)) );
         }
      }
   }
}

template< class Container, class Data >
void test_associative_container(Container & c, Data & d)
{
   assert( d.size() > 2 );

   c.clear();
   c.insert(d.begin(),d.end());

   test_associative_container_invariants(c, d);

   const Container & cr = c;

   test_associative_container_invariants(cr, d);
}

template< class Container, class Data >
void test_unordered_associative_container_invariants(Container & c, Data & d)
{
   typedef typename Container::size_type        size_type;
   typedef typename Container::const_iterator   const_iterator;
   typedef typename Container::key_of_value     key_of_value;

   for( typename Data::const_iterator di = d.begin(), de = d.end() ;
      di != de ; ++di ){
      const_iterator i = c.find(key_of_value()(*di));
      size_type nb = c.bucket(key_of_value()(*i));
      size_type bucket_elem = boost::intrusive::iterator_distance(c.begin(nb), c.end(nb));
      BOOST_TEST( bucket_elem ==  c.bucket_size(nb) );
      BOOST_TEST( &*c.local_iterator_to(*c.find(key_of_value()(*di))) == &*i );
      BOOST_TEST( &*c.local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i );
      BOOST_TEST( &*Container::s_local_iterator_to(*c.find(key_of_value()(*di))) == &*i );
      BOOST_TEST( &*Container::s_local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i );
      std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di));
      size_type cnt = boost::intrusive::iterator_distance(er.first, er.second);
      BOOST_TEST( cnt == c.count(key_of_value()(*di)));
      if(cnt > 1){
         const_iterator n = er.first;
         i = n++;
         const_iterator e = er.second;
         for(; n != e; ++i, ++n){
            BOOST_TEST( c.key_eq()(key_of_value()(*i), key_of_value()(*n)) );
            BOOST_TEST( (c.hash_function()(key_of_value()(*i))) == (c.hash_function()(key_of_value()(*n))) );
         }
      }
   }

   size_type blen = c.bucket_count();
   size_type total_objects = 0;
   for(size_type i = 0; i < blen; ++i){
      total_objects += c.bucket_size(i);
   }
   BOOST_TEST( total_objects ==  c.size() );
}

template< class Container, class Data >
void test_unordered_associative_container(Container & c, Data & d)
{
   c.clear();
   c.insert( d.begin(), d.end() );

   test_unordered_associative_container_invariants(c, d);

   const Container & cr = c;

   test_unordered_associative_container_invariants(cr, d);
}

template< class Container, class Data >
void test_unique_container(Container & c, Data & d)
{
   //typedef typename Container::value_type value_type;
   c.clear();
   c.insert(d.begin(),d.end());
   typename Container::size_type old_size = c.size();
   //value_type v(*d.begin());
   //c.insert(v);
   Data d2(1);
   (&d2.front())->value_ = (&d.front())->value_;
   c.insert(d2.front());
   BOOST_TEST( c.size() == old_size );
   c.clear();
}

template< class Container, class Data >
void test_non_unique_container(Container & c, Data & d)
{
   //typedef typename Container::value_type value_type;
   c.clear();
   c.insert(d.begin(),d.end());
   typename Container::size_type old_size = c.size();
   //value_type v(*d.begin());
   //c.insert(v);
   Data d2(1);
   (&d2.front())->value_ = (&d.front())->value_;
   c.insert(d2.front());
   BOOST_TEST( c.size() == (old_size+1) );
   c.clear();
}

template< class Container, class Data >
void test_maybe_unique_container(Container & c, Data & d, detail::false_)//is_unique
{  test_unique_container(c, d);  }

template< class Container, class Data >
void test_maybe_unique_container(Container & c, Data & d, detail::true_)//!is_unique
{  test_non_unique_container(c, d);  }

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last )
{
   typedef typename boost::intrusive::iterator_traits<RandomIt>::difference_type difference_type;
   difference_type n = last - first;
   for (difference_type i = n-1; i > 0; --i) {
      difference_type j = std::rand() % (i+1);
      if(j != i) {
         boost::adl_move_swap(first[i], first[j]);
      }
   }
}

}}}

#endif   //#ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP