376 lines
14 KiB
C++
376 lines
14 KiB
C++
//////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// (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
|