123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375 |
- //////////////////////////////////////////////////////////////////////////////
- //
- // (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
|