1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
4// Software License, Version 1.0. (See accompanying file
5// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6//
7// See http://www.boost.org/libs/intrusive for documentation.
8//
9//////////////////////////////////////////////////////////////////////////////
10
11#include <boost/intrusive/detail/iterator.hpp>
12#include <boost/intrusive/detail/mpl.hpp>
13
14namespace boost{ namespace intrusive { namespace test{
15
16//////////////////////////////////////////////
17//
18// Some traits to avoid special cases with
19// containers without bidirectional iterators
20//
21//////////////////////////////////////////////
22template<class C>
23struct has_member_reverse_iterator
24{
25 typedef char yes_type;
26 struct no_type{ char _[2]; };
27
28 template<typename D> static no_type test(...);
29 template<typename D> static yes_type test(typename D::reverse_iterator const*);
30 static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
31};
32
33template<class C>
34struct has_member_const_reverse_iterator
35{
36 typedef char yes_type;
37 struct no_type{ char _[2]; };
38
39 template<typename D> static no_type test(...);
40 template<typename D> static yes_type test(typename D::const_reverse_iterator const*);
41 static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
42};
43
44template<class C, bool = has_member_reverse_iterator<C>::value>
45struct get_reverse_iterator
46{
47 typedef typename C::reverse_iterator type;
48 static type begin(C &c) { return c.rbegin(); }
49 static type end(C &c) { return c.rend(); }
50};
51
52template<class C>
53struct get_reverse_iterator<C, false>
54{
55 typedef typename C::iterator type;
56 static type begin(C &c) { return c.begin(); }
57 static type end(C &c) { return c.end(); }
58};
59
60template<class C, bool = has_member_const_reverse_iterator<C>::value>
61struct get_const_reverse_iterator
62{
63 typedef typename C::const_reverse_iterator type;
64 static type begin(C &c) { return c.crbegin(); }
65 static type end(C &c) { return c.crend(); }
66};
67
68template<class C>
69struct get_const_reverse_iterator<C, false>
70{
71 typedef typename C::const_iterator type;
72 static type begin(C &c) { return c.cbegin(); }
73 static type end(C &c) { return c.cend(); }
74};
75
76//////////////////////////////////////////////
77//
78// Iterator tests
79//
80//////////////////////////////////////////////
81
82template<class I>
83void test_iterator_operations(I b, I e)
84{
85 //Test the range is not empty
86 BOOST_TEST(b != e);
87 BOOST_TEST(!(b == e));
88 {
89 I i;
90 I i2(b); //CopyConstructible
91 i = i2; //Assignable
92 //Destructible
93 (void)i;
94 (void)i2;
95 }
96
97 typedef typename iterator_traits<I>::reference reference;
98 reference r = *b;
99 (void)r;
100 typedef typename iterator_traits<I>::pointer pointer;
101 pointer p = (iterator_arrow_result)(b);
102 (void)p;
103 I &ri= ++b;
104 (void)ri;
105 const I &cri= b++;
106 (void)cri;
107}
108
109template<class C>
110void test_iterator_compatible(C &c)
111{
112 typedef typename C::iterator iterator;
113 typedef typename C::const_iterator const_iterator;
114 typedef typename get_reverse_iterator<C>::type reverse_iterator;
115 typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator;
116 //Basic operations
117 test_iterator_operations(c. begin(), c. end());
118 test_iterator_operations(c.cbegin(), c.cend());
119 test_iterator_operations(get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
120 test_iterator_operations(get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
121 //Make sure dangeous conversions are not possible
122 BOOST_INTRUSIVE_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_iterator, iterator>::value));
123 BOOST_INTRUSIVE_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_reverse_iterator, reverse_iterator>::value));
124 //Test iterator conversions
125 {
126 const_iterator ci;
127 iterator i(c.begin());
128 ci = i;
129 (void)ci;
130 BOOST_ASSERT(ci == i);
131 BOOST_ASSERT(*ci == *i);
132 const_iterator ci2(i);
133 BOOST_ASSERT(ci2 == i);
134 BOOST_ASSERT(*ci2 == *i);
135 (void)ci2;
136 }
137 //Test reverse_iterator conversions
138 {
139 const_reverse_iterator cr;
140 reverse_iterator r(get_reverse_iterator<C>::begin(c));
141 cr = r;
142 BOOST_ASSERT(cr == r);
143 BOOST_ASSERT(*cr == *r);
144 const_reverse_iterator cr2(r);
145 BOOST_ASSERT(cr2 == r);
146 BOOST_ASSERT(*cr2 == *r);
147 (void)cr2;
148 }
149}
150
151template<class C>
152void test_iterator_input_and_compatible(C &c)
153{
154 typedef typename C::iterator iterator;
155 typedef typename C::const_iterator const_iterator;
156 typedef typename get_reverse_iterator<C>::type reverse_iterator;
157 typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator;
158 typedef iterator_traits<iterator> nit_traits;
159 typedef iterator_traits<const_iterator> cit_traits;
160 typedef iterator_traits<reverse_iterator> rnit_traits;
161 typedef iterator_traits<const_reverse_iterator> crit_traits;
162
163 using boost::move_detail::is_same;
164 //Trivial typedefs
165 BOOST_INTRUSIVE_STATIC_ASSERT((!is_same<iterator, const_iterator>::value));
166 BOOST_INTRUSIVE_STATIC_ASSERT((!is_same<reverse_iterator, const_reverse_iterator>::value));
167 //difference_type
168 typedef typename C::difference_type difference_type;
169 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<difference_type, typename nit_traits::difference_type>::value));
170 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<difference_type, typename cit_traits::difference_type>::value));
171 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<difference_type, typename rnit_traits::difference_type>::value));
172 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<difference_type, typename crit_traits::difference_type>::value));
173 //value_type
174 typedef typename C::value_type value_type;
175 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<value_type, typename nit_traits::value_type>::value));
176 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<value_type, typename cit_traits::value_type>::value));
177 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<value_type, typename rnit_traits::value_type>::value));
178 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<value_type, typename crit_traits::value_type>::value));
179 //pointer
180 typedef typename C::pointer pointer;
181 typedef typename C::const_pointer const_pointer;
182 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<pointer, typename nit_traits::pointer>::value));
183 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<const_pointer, typename cit_traits::pointer>::value));
184 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<pointer, typename rnit_traits::pointer>::value));
185 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<const_pointer, typename crit_traits::pointer>::value));
186 //reference
187 typedef typename C::reference reference;
188 typedef typename C::const_reference const_reference;
189 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<reference, typename nit_traits::reference>::value));
190 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<const_reference, typename cit_traits::reference>::value));
191 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<reference, typename rnit_traits::reference>::value));
192 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<const_reference, typename crit_traits::reference>::value));
193 //Dynamic tests
194 test_iterator_compatible(c);
195}
196
197template<class C, class I>
198void test_iterator_forward_functions(C const &c, I const b, I const e)
199{
200 typedef typename C::size_type size_type;
201 {
202 size_type i = 0;
203 I it = b;
204 for(I it2 = b; i != c.size(); ++it, ++i){
205 BOOST_TEST(it == it2++);
206 I ittmp(it);
207 I *iaddr = &ittmp;
208 BOOST_TEST(&(++ittmp) == iaddr);
209 BOOST_TEST(ittmp == it2);
210 }
211 BOOST_TEST(i == c.size());
212 BOOST_TEST(it == e);
213 }
214}
215
216template<class C>
217void test_iterator_forward_and_compatible(C &c)
218{
219 test_iterator_input_and_compatible(c);
220 test_iterator_forward_functions(c, c.begin(), c.end());
221 test_iterator_forward_functions(c, c.cbegin(), c.cend());
222 test_iterator_forward_functions(c, get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
223 test_iterator_forward_functions(c, get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
224}
225
226template<class C, class I>
227void test_iterator_bidirectional_functions(C const &c, I const b, I const e)
228{
229 typedef typename C::size_type size_type;
230 {
231 size_type i = 0;
232 I it = e;
233 for(I it2 = e; i != c.size(); --it, ++i){
234 BOOST_TEST(it == it2--);
235 I ittmp(it);
236 I*iaddr = &ittmp;
237 BOOST_TEST(&(--ittmp) == iaddr);
238 BOOST_TEST(ittmp == it2);
239 BOOST_TEST((++ittmp) == it);
240 }
241 BOOST_TEST(i == c.size());
242 BOOST_TEST(it == b);
243 }
244}
245
246template<class C>
247void test_iterator_bidirectional_and_compatible(C &c)
248{
249 test_iterator_forward_and_compatible(c);
250 test_iterator_bidirectional_functions(c, c.begin(), c.end());
251 test_iterator_bidirectional_functions(c, c.cbegin(), c.cend());
252 test_iterator_bidirectional_functions(c, c.rbegin(), c.rend());
253 test_iterator_bidirectional_functions(c, c.crbegin(), c.crend());
254}
255
256template<class C, class I>
257void test_iterator_random_functions(C const &c, I const b, I const e)
258{
259 typedef typename C::size_type size_type;
260 typedef typename C::difference_type difference_type;
261 {
262 I it = b;
263 for(difference_type i = 0, m = difference_type(c.size()); i != m; ++i, ++it){
264 BOOST_TEST(i == it - b);
265 BOOST_TEST(b[i] == *it);
266 BOOST_TEST(&b[i] == &*it);
267 BOOST_TEST((b + i) == it);
268 BOOST_TEST((i + b) == it);
269 BOOST_TEST(b == (it - i));
270 I tmp(b);
271 BOOST_TEST((tmp+=i) == it);
272 tmp = it;
273 BOOST_TEST(b == (tmp-=i));
274 }
275 BOOST_TEST(c.size() == size_type(e - b));
276 }
277 {
278 I it(b), itb(b);
279 if(b != e){
280 for(++it; it != e; ++it){
281 BOOST_TEST(itb < it);
282 BOOST_TEST(itb <= it);
283 BOOST_TEST(!(itb > it));
284 BOOST_TEST(!(itb >= it));
285 BOOST_TEST(it > itb);
286 BOOST_TEST(it >= itb);
287 BOOST_TEST(!(it < itb));
288 BOOST_TEST(!(it <= itb));
289 BOOST_TEST(it >= it);
290 BOOST_TEST(it <= it);
291 itb = it;
292 }
293 }
294 }
295}
296
297template<class C>
298void test_iterator_random_and_compatible(C &c)
299{
300 test_iterator_bidirectional_and_compatible(c);
301 test_iterator_random_functions(c, c.begin(), c.end());
302 test_iterator_random_functions(c, c.cbegin(), c.cend());
303 test_iterator_random_functions(c, c.rbegin(), c.rend());
304 test_iterator_random_functions(c, c.crbegin(), c.crend());
305}
306
307////////////////////////
308
309template<class C>
310void test_iterator_forward(C &c)
311{
312 typedef typename C::iterator iterator;
313 typedef typename C::const_iterator const_iterator;
314 typedef typename get_reverse_iterator<C>::type reverse_iterator;
315 typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator;
316 typedef iterator_traits<iterator> nit_traits;
317 typedef iterator_traits<const_iterator> cit_traits;
318 typedef iterator_traits<reverse_iterator> rnit_traits;
319 typedef iterator_traits<const_reverse_iterator> crit_traits;
320
321 using boost::intrusive::detail::is_same;
322 //iterator_category
323 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename nit_traits::iterator_category>::value));
324 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename cit_traits::iterator_category>::value));
325 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename rnit_traits::iterator_category>::value));
326 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename crit_traits::iterator_category>::value));
327 //Test dynamic
328 test_iterator_forward_and_compatible(c);
329}
330
331template<class C>
332void test_iterator_bidirectional(C &c)
333{
334 typedef typename C::iterator iterator;
335 typedef typename C::const_iterator const_iterator;
336 typedef typename C::reverse_iterator reverse_iterator;
337 typedef typename C::const_reverse_iterator const_reverse_iterator;
338 typedef iterator_traits<iterator> nit_traits;
339 typedef iterator_traits<const_iterator> cit_traits;
340 typedef iterator_traits<reverse_iterator> rnit_traits;
341 typedef iterator_traits<const_reverse_iterator> crit_traits;
342
343 using boost::intrusive::detail::is_same;
344 //iterator_category
345 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename nit_traits::iterator_category>::value));
346 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename cit_traits::iterator_category>::value));
347 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename rnit_traits::iterator_category>::value));
348 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename crit_traits::iterator_category>::value));
349 //Test dynamic
350 test_iterator_bidirectional_and_compatible(c);
351}
352
353template<class C>
354void test_iterator_random(C &c)
355{
356 typedef typename C::iterator iterator;
357 typedef typename C::const_iterator const_iterator;
358 typedef typename C::reverse_iterator reverse_iterator;
359 typedef typename C::const_reverse_iterator const_reverse_iterator;
360 typedef iterator_traits<iterator> nit_traits;
361 typedef iterator_traits<const_iterator> cit_traits;
362 typedef iterator_traits<reverse_iterator> rnit_traits;
363 typedef iterator_traits<const_reverse_iterator> crit_traits;
364
365 using boost::intrusive::detail::is_same;
366 //iterator_category
367 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename nit_traits::iterator_category>::value));
368 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename cit_traits::iterator_category>::value));
369 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename rnit_traits::iterator_category>::value));
370 BOOST_INTRUSIVE_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename crit_traits::iterator_category>::value));
371 //Test dynamic
372 test_iterator_random_and_compatible(c);
373}
374
375}}} //boost::container::test
376

source code of boost/libs/intrusive/test/iterator_test.hpp