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

#include <boost/intrusive/detail/iterator.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/static_assert.hpp>

namespace boost{  namespace intrusive {  namespace test{

//////////////////////////////////////////////
//
// Some traits to avoid special cases with
// containers without bidirectional iterators
//
//////////////////////////////////////////////
template<class C>
struct has_member_reverse_iterator
{
   typedef char yes_type;
   struct no_type{   char _[2];  };

   template<typename D> static no_type test(...);
   template<typename D> static yes_type test(typename D::reverse_iterator const*);
   static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
};

template<class C>
struct has_member_const_reverse_iterator
{
   typedef char yes_type;
   struct no_type{   char _[2];  };

   template<typename D> static no_type test(...);
   template<typename D> static yes_type test(typename D::const_reverse_iterator const*);
   static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
};

template<class C, bool = has_member_reverse_iterator<C>::value>
struct get_reverse_iterator
{
   typedef typename C::reverse_iterator type;
   static type begin(C &c) {  return c.rbegin(); }
   static type   end(C &c) {  return c.rend(); }
};

template<class C>
struct get_reverse_iterator<C, false>
{
   typedef typename C::iterator type;
   static type begin(C &c) {  return c.begin(); }
   static type   end(C &c) {  return c.end(); }
};

template<class C, bool = has_member_const_reverse_iterator<C>::value>
struct get_const_reverse_iterator
{
   typedef typename C::const_reverse_iterator type;
   static type begin(C &c) {  return c.crbegin(); }
   static type   end(C &c) {  return c.crend(); }
};

template<class C>
struct get_const_reverse_iterator<C, false>
{
   typedef typename C::const_iterator type;
   static type begin(C &c) {  return c.cbegin(); }
   static type   end(C &c) {  return c.cend(); }
};

//////////////////////////////////////////////
//
//          Iterator tests
//
//////////////////////////////////////////////

template<class I>
void test_iterator_operations(I b, I e)
{
   //Test the range is not empty
   BOOST_TEST(b != e);
   BOOST_TEST(!(b == e));
   {
      I i;
      I i2(b); //CopyConstructible
      i = i2;  //Assignable
      //Destructible
      (void)i;
      (void)i2;
   }

   typedef typename iterator_traits<I>::reference reference;
   reference r = *b;
   (void)r;
   typedef typename iterator_traits<I>::pointer pointer;
   pointer p = (iterator_arrow_result)(b);
   (void)p;
   I &ri= ++b;
   (void)ri;
   const I &cri= b++;
   (void)cri;
}

template<class C>
void test_iterator_compatible(C &c)
{
   typedef typename C::iterator        iterator;
   typedef typename C::const_iterator  const_iterator;
   typedef typename get_reverse_iterator<C>::type        reverse_iterator;
   typedef typename get_const_reverse_iterator<C>::type  const_reverse_iterator;
   //Basic operations
   test_iterator_operations(c. begin(), c. end());
   test_iterator_operations(c.cbegin(), c.cend());
   test_iterator_operations(get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
   test_iterator_operations(get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
   //Make sure dangeous conversions are not possible
   BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_iterator, iterator>::value));
   BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_reverse_iterator, reverse_iterator>::value));
   //Test iterator conversions
   {  
      const_iterator ci;
      iterator i(c.begin());
      ci = i;
      (void)ci;
      BOOST_ASSERT(ci == i);
      BOOST_ASSERT(*ci == *i);
      const_iterator ci2(i);
      BOOST_ASSERT(ci2 == i);
      BOOST_ASSERT(*ci2 == *i);
      (void)ci2;
   }
   //Test reverse_iterator conversions
   {
      const_reverse_iterator cr;
      reverse_iterator r(get_reverse_iterator<C>::begin(c));
      cr = r;
      BOOST_ASSERT(cr == r);
      BOOST_ASSERT(*cr == *r);
      const_reverse_iterator cr2(r);
      BOOST_ASSERT(cr2 == r);
      BOOST_ASSERT(*cr2 == *r);
      (void)cr2;
   }
}

template<class C>
void test_iterator_input_and_compatible(C &c)
{
   typedef typename C::iterator                          iterator;
   typedef typename C::const_iterator                    const_iterator;
   typedef typename get_reverse_iterator<C>::type        reverse_iterator;
   typedef typename get_const_reverse_iterator<C>::type  const_reverse_iterator;
   typedef iterator_traits<iterator>            nit_traits;
   typedef iterator_traits<const_iterator>      cit_traits;
   typedef iterator_traits<reverse_iterator>         rnit_traits;
   typedef iterator_traits<const_reverse_iterator>   crit_traits;

   using boost::move_detail::is_same;
   //Trivial typedefs
   BOOST_STATIC_ASSERT((!is_same<iterator, const_iterator>::value));
   BOOST_STATIC_ASSERT((!is_same<reverse_iterator, const_reverse_iterator>::value));
   //difference_type
   typedef typename C::difference_type difference_type;
   BOOST_STATIC_ASSERT((is_same<difference_type, typename nit_traits::difference_type>::value));
   BOOST_STATIC_ASSERT((is_same<difference_type, typename cit_traits::difference_type>::value));
   BOOST_STATIC_ASSERT((is_same<difference_type, typename rnit_traits::difference_type>::value));
   BOOST_STATIC_ASSERT((is_same<difference_type, typename crit_traits::difference_type>::value));
   //value_type
   typedef typename C::value_type value_type;
   BOOST_STATIC_ASSERT((is_same<value_type, typename nit_traits::value_type>::value));
   BOOST_STATIC_ASSERT((is_same<value_type, typename cit_traits::value_type>::value));
   BOOST_STATIC_ASSERT((is_same<value_type, typename rnit_traits::value_type>::value));
   BOOST_STATIC_ASSERT((is_same<value_type, typename crit_traits::value_type>::value));
   //pointer
   typedef typename C::pointer pointer;
   typedef typename C::const_pointer const_pointer;
   BOOST_STATIC_ASSERT((is_same<pointer,        typename nit_traits::pointer>::value));
   BOOST_STATIC_ASSERT((is_same<const_pointer,  typename cit_traits::pointer>::value));
   BOOST_STATIC_ASSERT((is_same<pointer,        typename rnit_traits::pointer>::value));
   BOOST_STATIC_ASSERT((is_same<const_pointer,  typename crit_traits::pointer>::value));
   //reference
   typedef typename C::reference reference;
   typedef typename C::const_reference const_reference;
   BOOST_STATIC_ASSERT((is_same<reference,         typename nit_traits::reference>::value));
   BOOST_STATIC_ASSERT((is_same<const_reference,   typename cit_traits::reference>::value));
   BOOST_STATIC_ASSERT((is_same<reference,         typename rnit_traits::reference>::value));
   BOOST_STATIC_ASSERT((is_same<const_reference,   typename crit_traits::reference>::value));
   //Dynamic tests
   test_iterator_compatible(c);
}

template<class C, class I>
void test_iterator_forward_functions(C const &c, I const b, I const e)
{
   typedef typename C::size_type size_type;
   {
      size_type i = 0;
      I it = b;
      for(I it2 = b; i != c.size(); ++it, ++i){
         BOOST_TEST(it == it2++);
         I ittmp(it);
         I *iaddr = &ittmp;
         BOOST_TEST(&(++ittmp) == iaddr);
         BOOST_TEST(ittmp == it2);
      }
      BOOST_TEST(i == c.size());
      BOOST_TEST(it == e);
   }
}

template<class C>
void test_iterator_forward_and_compatible(C &c)
{
   test_iterator_input_and_compatible(c);
   test_iterator_forward_functions(c, c.begin(),   c.end());
   test_iterator_forward_functions(c, c.cbegin(),  c.cend());
   test_iterator_forward_functions(c, get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
   test_iterator_forward_functions(c, get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
}

template<class C, class I>
void test_iterator_bidirectional_functions(C const &c, I const b, I const e)
{
   typedef typename C::size_type size_type;
   {
      size_type i = 0;
      I it = e;
      for(I it2 = e; i != c.size(); --it, ++i){
         BOOST_TEST(it == it2--);
         I ittmp(it);
         I*iaddr = &ittmp;
         BOOST_TEST(&(--ittmp) == iaddr);
         BOOST_TEST(ittmp == it2);
         BOOST_TEST((++ittmp) == it);
      }
      BOOST_TEST(i == c.size());
      BOOST_TEST(it == b);
   }
}

template<class C>
void test_iterator_bidirectional_and_compatible(C &c)
{
   test_iterator_forward_and_compatible(c);
   test_iterator_bidirectional_functions(c, c.begin(),   c.end());
   test_iterator_bidirectional_functions(c, c.cbegin(),  c.cend());
   test_iterator_bidirectional_functions(c, c.rbegin(),  c.rend());
   test_iterator_bidirectional_functions(c, c.crbegin(), c.crend());
}

template<class C, class I>
void test_iterator_random_functions(C const &c, I const b, I const e)
{
   typedef typename C::size_type size_type;
   {
      I it = b;
      for(size_type i = 0, m = c.size(); i != m; ++i, ++it){
         BOOST_TEST(i == size_type(it - b));
         BOOST_TEST(b[i] == *it);
         BOOST_TEST(&b[i] == &*it);
         BOOST_TEST((b + i) == it);
         BOOST_TEST((i + b) == it);
         BOOST_TEST(b == (it - i));
         I tmp(b);
         BOOST_TEST((tmp+=i) == it);
         tmp = it;
         BOOST_TEST(b == (tmp-=i));
      }
      BOOST_TEST(c.size() == size_type(e - b));
   }
   {
      I it(b), itb(b);
      if(b != e){
         for(++it; it != e; ++it){
            BOOST_TEST(itb < it);
            BOOST_TEST(itb <= it);
            BOOST_TEST(!(itb > it));
            BOOST_TEST(!(itb >= it));
            BOOST_TEST(it > itb);
            BOOST_TEST(it >= itb);
            BOOST_TEST(!(it < itb));
            BOOST_TEST(!(it <= itb));
            BOOST_TEST(it >= it);
            BOOST_TEST(it <= it);
            itb = it;
         }
      }
   }
}

template<class C>
void test_iterator_random_and_compatible(C &c)
{
   test_iterator_bidirectional_and_compatible(c);
   test_iterator_random_functions(c, c.begin(),   c.end());
   test_iterator_random_functions(c, c.cbegin(),  c.cend());
   test_iterator_random_functions(c, c.rbegin(),  c.rend());
   test_iterator_random_functions(c, c.crbegin(), c.crend());
}

////////////////////////

template<class C>
void test_iterator_forward(C &c)
{
   typedef typename C::iterator                 iterator;
   typedef typename C::const_iterator           const_iterator;
   typedef typename get_reverse_iterator<C>::type        reverse_iterator;
   typedef typename get_const_reverse_iterator<C>::type  const_reverse_iterator;
   typedef iterator_traits<iterator>         nit_traits;
   typedef iterator_traits<const_iterator>   cit_traits;
   typedef iterator_traits<reverse_iterator>         rnit_traits;
   typedef iterator_traits<const_reverse_iterator>   crit_traits;

   using boost::intrusive::detail::is_same;
   //iterator_category
   BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename nit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename cit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename rnit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename crit_traits::iterator_category>::value));
   //Test dynamic
   test_iterator_forward_and_compatible(c);
}

template<class C>
void test_iterator_bidirectional(C &c)
{
   typedef typename C::iterator        iterator;
   typedef typename C::const_iterator  const_iterator;
   typedef typename C::reverse_iterator        reverse_iterator;
   typedef typename C::const_reverse_iterator  const_reverse_iterator;
   typedef iterator_traits<iterator>         nit_traits;
   typedef iterator_traits<const_iterator>   cit_traits;
   typedef iterator_traits<reverse_iterator>         rnit_traits;
   typedef iterator_traits<const_reverse_iterator>   crit_traits;

   using boost::intrusive::detail::is_same;
   //iterator_category
   BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename nit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename cit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename rnit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename crit_traits::iterator_category>::value));
   //Test dynamic
   test_iterator_bidirectional_and_compatible(c);
}

template<class C>
void test_iterator_random(C &c)
{
   typedef typename C::iterator        iterator;
   typedef typename C::const_iterator  const_iterator;
   typedef typename C::reverse_iterator        reverse_iterator;
   typedef typename C::const_reverse_iterator  const_reverse_iterator;
   typedef iterator_traits<iterator>         nit_traits;
   typedef iterator_traits<const_iterator>   cit_traits;
   typedef iterator_traits<reverse_iterator>         rnit_traits;
   typedef iterator_traits<const_reverse_iterator>   crit_traits;

   using boost::intrusive::detail::is_same;
   //iterator_category
   BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename nit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename cit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename rnit_traits::iterator_category>::value));
   BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename crit_traits::iterator_category>::value));
   //Test dynamic
   test_iterator_random_and_compatible(c);
}

}}}   //boost::container::test