]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | #include <boost/static_assert.hpp> | |
14 | ||
15 | namespace boost{ namespace intrusive { namespace test{ | |
16 | ||
17 | ////////////////////////////////////////////// | |
18 | // | |
19 | // Some traits to avoid special cases with | |
20 | // containers without bidirectional iterators | |
21 | // | |
22 | ////////////////////////////////////////////// | |
23 | template<class C> | |
24 | struct has_member_reverse_iterator | |
25 | { | |
26 | typedef char yes_type; | |
27 | struct no_type{ char _[2]; }; | |
28 | ||
29 | template<typename D> static no_type test(...); | |
30 | template<typename D> static yes_type test(typename D::reverse_iterator const*); | |
31 | static const bool value = sizeof(test<C>(0)) == sizeof(yes_type); | |
32 | }; | |
33 | ||
34 | template<class C> | |
35 | struct has_member_const_reverse_iterator | |
36 | { | |
37 | typedef char yes_type; | |
38 | struct no_type{ char _[2]; }; | |
39 | ||
40 | template<typename D> static no_type test(...); | |
41 | template<typename D> static yes_type test(typename D::const_reverse_iterator const*); | |
42 | static const bool value = sizeof(test<C>(0)) == sizeof(yes_type); | |
43 | }; | |
44 | ||
45 | template<class C, bool = has_member_reverse_iterator<C>::value> | |
46 | struct get_reverse_iterator | |
47 | { | |
48 | typedef typename C::reverse_iterator type; | |
49 | static type begin(C &c) { return c.rbegin(); } | |
50 | static type end(C &c) { return c.rend(); } | |
51 | }; | |
52 | ||
53 | template<class C> | |
54 | struct get_reverse_iterator<C, false> | |
55 | { | |
56 | typedef typename C::iterator type; | |
57 | static type begin(C &c) { return c.begin(); } | |
58 | static type end(C &c) { return c.end(); } | |
59 | }; | |
60 | ||
61 | template<class C, bool = has_member_const_reverse_iterator<C>::value> | |
62 | struct get_const_reverse_iterator | |
63 | { | |
64 | typedef typename C::const_reverse_iterator type; | |
65 | static type begin(C &c) { return c.crbegin(); } | |
66 | static type end(C &c) { return c.crend(); } | |
67 | }; | |
68 | ||
69 | template<class C> | |
70 | struct get_const_reverse_iterator<C, false> | |
71 | { | |
72 | typedef typename C::const_iterator type; | |
73 | static type begin(C &c) { return c.cbegin(); } | |
74 | static type end(C &c) { return c.cend(); } | |
75 | }; | |
76 | ||
77 | ////////////////////////////////////////////// | |
78 | // | |
79 | // Iterator tests | |
80 | // | |
81 | ////////////////////////////////////////////// | |
82 | ||
83 | template<class I> | |
84 | void test_iterator_operations(I b, I e) | |
85 | { | |
86 | //Test the range is not empty | |
87 | BOOST_TEST(b != e); | |
88 | BOOST_TEST(!(b == e)); | |
89 | { | |
90 | I i; | |
91 | I i2(b); //CopyConstructible | |
92 | i = i2; //Assignable | |
93 | //Destructible | |
94 | (void)i; | |
95 | (void)i2; | |
96 | } | |
97 | ||
98 | typedef typename iterator_traits<I>::reference reference; | |
99 | reference r = *b; | |
100 | (void)r; | |
101 | typedef typename iterator_traits<I>::pointer pointer; | |
102 | pointer p = (iterator_arrow_result)(b); | |
103 | (void)p; | |
104 | I &ri= ++b; | |
105 | (void)ri; | |
106 | const I &cri= b++; | |
107 | (void)cri; | |
108 | } | |
109 | ||
110 | template<class C> | |
111 | void test_iterator_compatible(C &c) | |
112 | { | |
113 | typedef typename C::iterator iterator; | |
114 | typedef typename C::const_iterator const_iterator; | |
115 | typedef typename get_reverse_iterator<C>::type reverse_iterator; | |
116 | typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator; | |
117 | //Basic operations | |
118 | test_iterator_operations(c. begin(), c. end()); | |
119 | test_iterator_operations(c.cbegin(), c.cend()); | |
120 | test_iterator_operations(get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c)); | |
121 | test_iterator_operations(get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c)); | |
122 | //Make sure dangeous conversions are not possible | |
11fdf7f2 TL |
123 | BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_iterator, iterator>::value)); |
124 | BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_reverse_iterator, reverse_iterator>::value)); | |
7c673cae FG |
125 | //Test iterator conversions |
126 | { | |
127 | const_iterator ci; | |
128 | iterator i(c.begin()); | |
129 | ci = i; | |
130 | (void)ci; | |
131 | BOOST_ASSERT(ci == i); | |
132 | BOOST_ASSERT(*ci == *i); | |
133 | const_iterator ci2(i); | |
134 | BOOST_ASSERT(ci2 == i); | |
135 | BOOST_ASSERT(*ci2 == *i); | |
136 | (void)ci2; | |
137 | } | |
138 | //Test reverse_iterator conversions | |
139 | { | |
140 | const_reverse_iterator cr; | |
141 | reverse_iterator r(get_reverse_iterator<C>::begin(c)); | |
142 | cr = r; | |
143 | BOOST_ASSERT(cr == r); | |
144 | BOOST_ASSERT(*cr == *r); | |
145 | const_reverse_iterator cr2(r); | |
146 | BOOST_ASSERT(cr2 == r); | |
147 | BOOST_ASSERT(*cr2 == *r); | |
148 | (void)cr2; | |
149 | } | |
150 | } | |
151 | ||
152 | template<class C> | |
153 | void test_iterator_input_and_compatible(C &c) | |
154 | { | |
155 | typedef typename C::iterator iterator; | |
156 | typedef typename C::const_iterator const_iterator; | |
157 | typedef typename get_reverse_iterator<C>::type reverse_iterator; | |
158 | typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator; | |
159 | typedef iterator_traits<iterator> nit_traits; | |
160 | typedef iterator_traits<const_iterator> cit_traits; | |
161 | typedef iterator_traits<reverse_iterator> rnit_traits; | |
162 | typedef iterator_traits<const_reverse_iterator> crit_traits; | |
163 | ||
164 | using boost::move_detail::is_same; | |
165 | //Trivial typedefs | |
166 | BOOST_STATIC_ASSERT((!is_same<iterator, const_iterator>::value)); | |
167 | BOOST_STATIC_ASSERT((!is_same<reverse_iterator, const_reverse_iterator>::value)); | |
168 | //difference_type | |
169 | typedef typename C::difference_type difference_type; | |
170 | BOOST_STATIC_ASSERT((is_same<difference_type, typename nit_traits::difference_type>::value)); | |
171 | BOOST_STATIC_ASSERT((is_same<difference_type, typename cit_traits::difference_type>::value)); | |
172 | BOOST_STATIC_ASSERT((is_same<difference_type, typename rnit_traits::difference_type>::value)); | |
173 | BOOST_STATIC_ASSERT((is_same<difference_type, typename crit_traits::difference_type>::value)); | |
174 | //value_type | |
175 | typedef typename C::value_type value_type; | |
176 | BOOST_STATIC_ASSERT((is_same<value_type, typename nit_traits::value_type>::value)); | |
177 | BOOST_STATIC_ASSERT((is_same<value_type, typename cit_traits::value_type>::value)); | |
178 | BOOST_STATIC_ASSERT((is_same<value_type, typename rnit_traits::value_type>::value)); | |
179 | BOOST_STATIC_ASSERT((is_same<value_type, typename crit_traits::value_type>::value)); | |
180 | //pointer | |
181 | typedef typename C::pointer pointer; | |
182 | typedef typename C::const_pointer const_pointer; | |
183 | BOOST_STATIC_ASSERT((is_same<pointer, typename nit_traits::pointer>::value)); | |
184 | BOOST_STATIC_ASSERT((is_same<const_pointer, typename cit_traits::pointer>::value)); | |
185 | BOOST_STATIC_ASSERT((is_same<pointer, typename rnit_traits::pointer>::value)); | |
186 | BOOST_STATIC_ASSERT((is_same<const_pointer, typename crit_traits::pointer>::value)); | |
187 | //reference | |
188 | typedef typename C::reference reference; | |
189 | typedef typename C::const_reference const_reference; | |
190 | BOOST_STATIC_ASSERT((is_same<reference, typename nit_traits::reference>::value)); | |
191 | BOOST_STATIC_ASSERT((is_same<const_reference, typename cit_traits::reference>::value)); | |
192 | BOOST_STATIC_ASSERT((is_same<reference, typename rnit_traits::reference>::value)); | |
193 | BOOST_STATIC_ASSERT((is_same<const_reference, typename crit_traits::reference>::value)); | |
194 | //Dynamic tests | |
195 | test_iterator_compatible(c); | |
196 | } | |
197 | ||
198 | template<class C, class I> | |
199 | void test_iterator_forward_functions(C const &c, I const b, I const e) | |
200 | { | |
201 | typedef typename C::size_type size_type; | |
202 | { | |
203 | size_type i = 0; | |
204 | I it = b; | |
205 | for(I it2 = b; i != c.size(); ++it, ++i){ | |
206 | BOOST_TEST(it == it2++); | |
207 | I ittmp(it); | |
208 | I *iaddr = &ittmp; | |
209 | BOOST_TEST(&(++ittmp) == iaddr); | |
210 | BOOST_TEST(ittmp == it2); | |
211 | } | |
212 | BOOST_TEST(i == c.size()); | |
213 | BOOST_TEST(it == e); | |
214 | } | |
215 | } | |
216 | ||
217 | template<class C> | |
218 | void test_iterator_forward_and_compatible(C &c) | |
219 | { | |
220 | test_iterator_input_and_compatible(c); | |
221 | test_iterator_forward_functions(c, c.begin(), c.end()); | |
222 | test_iterator_forward_functions(c, c.cbegin(), c.cend()); | |
223 | test_iterator_forward_functions(c, get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c)); | |
224 | test_iterator_forward_functions(c, get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c)); | |
225 | } | |
226 | ||
227 | template<class C, class I> | |
228 | void test_iterator_bidirectional_functions(C const &c, I const b, I const e) | |
229 | { | |
230 | typedef typename C::size_type size_type; | |
231 | { | |
232 | size_type i = 0; | |
233 | I it = e; | |
234 | for(I it2 = e; i != c.size(); --it, ++i){ | |
235 | BOOST_TEST(it == it2--); | |
236 | I ittmp(it); | |
237 | I*iaddr = &ittmp; | |
238 | BOOST_TEST(&(--ittmp) == iaddr); | |
239 | BOOST_TEST(ittmp == it2); | |
240 | BOOST_TEST((++ittmp) == it); | |
241 | } | |
242 | BOOST_TEST(i == c.size()); | |
243 | BOOST_TEST(it == b); | |
244 | } | |
245 | } | |
246 | ||
247 | template<class C> | |
248 | void test_iterator_bidirectional_and_compatible(C &c) | |
249 | { | |
250 | test_iterator_forward_and_compatible(c); | |
251 | test_iterator_bidirectional_functions(c, c.begin(), c.end()); | |
252 | test_iterator_bidirectional_functions(c, c.cbegin(), c.cend()); | |
253 | test_iterator_bidirectional_functions(c, c.rbegin(), c.rend()); | |
254 | test_iterator_bidirectional_functions(c, c.crbegin(), c.crend()); | |
255 | } | |
256 | ||
257 | template<class C, class I> | |
258 | void test_iterator_random_functions(C const &c, I const b, I const e) | |
259 | { | |
260 | typedef typename C::size_type size_type; | |
261 | { | |
262 | I it = b; | |
263 | for(size_type i = 0, m = c.size(); i != m; ++i, ++it){ | |
264 | BOOST_TEST(i == size_type(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 | ||
297 | template<class C> | |
298 | void 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 | ||
309 | template<class C> | |
310 | void 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 | ||
11fdf7f2 | 321 | using boost::intrusive::detail::is_same; |
7c673cae FG |
322 | //iterator_category |
323 | BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename nit_traits::iterator_category>::value)); | |
324 | BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename cit_traits::iterator_category>::value)); | |
325 | BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename rnit_traits::iterator_category>::value)); | |
326 | BOOST_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 | ||
331 | template<class C> | |
332 | void 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 | ||
11fdf7f2 | 343 | using boost::intrusive::detail::is_same; |
7c673cae FG |
344 | //iterator_category |
345 | BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename nit_traits::iterator_category>::value)); | |
346 | BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename cit_traits::iterator_category>::value)); | |
347 | BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename rnit_traits::iterator_category>::value)); | |
348 | BOOST_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 | ||
353 | template<class C> | |
354 | void 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 | ||
11fdf7f2 | 365 | using boost::intrusive::detail::is_same; |
7c673cae FG |
366 | //iterator_category |
367 | BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename nit_traits::iterator_category>::value)); | |
368 | BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename cit_traits::iterator_category>::value)); | |
369 | BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename rnit_traits::iterator_category>::value)); | |
370 | BOOST_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 |