1 | /* Boost.MultiIndex test for iterators. |
2 | * |
3 | * Copyright 2003-2023 Joaquin M Lopez Munoz. |
4 | * Distributed under the Boost Software License, Version 1.0. |
5 | * (See accompanying file LICENSE_1_0.txt or copy at |
6 | * http://www.boost.org/LICENSE_1_0.txt) |
7 | * |
8 | * See http://www.boost.org/libs/multi_index for library home page. |
9 | */ |
10 | |
11 | #include "test_iterators.hpp" |
12 | |
13 | #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ |
14 | #include "pair_of_ints.hpp" |
15 | #include "pre_multi_index.hpp" |
16 | #include "employee.hpp" |
17 | #include <algorithm> |
18 | #include <boost/detail/lightweight_test.hpp> |
19 | #include <boost/next_prior.hpp> |
20 | #include <boost/foreach.hpp> |
21 | #include <vector> |
22 | |
23 | using namespace boost::multi_index; |
24 | |
25 | template<typename Index> |
26 | void test_non_const_iterators(Index& i,int target) |
27 | { |
28 | typedef typename Index::iterator iterator; |
29 | typedef typename Index::reverse_iterator reverse_iterator; |
30 | |
31 | int n=0; |
32 | for(iterator it=i.begin();it!=i.end();++it){ |
33 | BOOST_TEST(i.iterator_to(*it)==it); |
34 | n+=it->id; |
35 | } |
36 | int m=0; |
37 | for(reverse_iterator rit=i.rbegin();rit!=i.rend();++rit){ |
38 | m+=rit->id; |
39 | } |
40 | int p=0; |
41 | for(iterator it2=i.end();it2!=i.begin();){ |
42 | --it2; |
43 | p+=it2->id; |
44 | } |
45 | int q=0; |
46 | for(reverse_iterator rit2=i.rend();rit2!=i.rbegin();){ |
47 | --rit2; |
48 | q+=rit2->id; |
49 | } |
50 | |
51 | BOOST_TEST(n==target&&n==m&&n==p&&n==q); |
52 | } |
53 | |
54 | template<typename Index> |
55 | void test_const_iterators(const Index& i,int target) |
56 | { |
57 | typedef typename Index::const_iterator const_iterator; |
58 | typedef typename Index::const_reverse_iterator const_reverse_iterator; |
59 | |
60 | BOOST_TEST(i.cbegin()==i.begin()); |
61 | BOOST_TEST(i.cend()==i.end()); |
62 | BOOST_TEST(i.crbegin()==i.rbegin()); |
63 | BOOST_TEST(i.crend()==i.rend()); |
64 | |
65 | int n=0; |
66 | for(const_iterator it=i.begin();it!=i.end();++it){ |
67 | BOOST_TEST(i.iterator_to(*it)==it); |
68 | n+=it->id; |
69 | } |
70 | int m=0; |
71 | for(const_reverse_iterator rit=i.rbegin();rit!=i.rend();++rit){ |
72 | m+=rit->id; |
73 | } |
74 | int p=0; |
75 | for(const_iterator it2=i.end();it2!=i.begin();){ |
76 | --it2; |
77 | p+=it2->id; |
78 | } |
79 | int q=0; |
80 | for(const_reverse_iterator rit2=i.rend();rit2!=i.rbegin();){ |
81 | --rit2; |
82 | q+=rit2->id; |
83 | } |
84 | |
85 | BOOST_TEST(n==target&&n==m&&n==p&&n==q); |
86 | } |
87 | |
88 | template<typename Index> |
89 | void test_non_const_hashed_iterators(Index& i,int target) |
90 | { |
91 | typedef typename Index::iterator iterator; |
92 | typedef typename Index::local_iterator local_iterator; |
93 | typedef typename Index::size_type size_type; |
94 | |
95 | int n=0; |
96 | for(iterator it=i.begin();it!=i.end();++it){ |
97 | BOOST_TEST(i.iterator_to(*it)==it); |
98 | n+=it->id; |
99 | } |
100 | int m=0; |
101 | for(size_type buc=0;buc<i.bucket_count();++buc){ |
102 | for(local_iterator it=i.begin(buc);it!=i.end(buc);++it){ |
103 | BOOST_TEST(i.local_iterator_to(*it)==it); |
104 | m+=it->id; |
105 | } |
106 | } |
107 | |
108 | BOOST_TEST(n==target&&n==m); |
109 | } |
110 | |
111 | template<typename Index> |
112 | void test_const_hashed_iterators(const Index& i,int target) |
113 | { |
114 | typedef typename Index::const_iterator const_iterator; |
115 | typedef typename Index::const_local_iterator const_local_iterator; |
116 | typedef typename Index::size_type size_type; |
117 | |
118 | BOOST_TEST(i.cbegin()==i.begin()); |
119 | BOOST_TEST(i.cend()==i.end()); |
120 | |
121 | int n=0; |
122 | for(const_iterator it=i.begin();it!=i.end();++it){ |
123 | BOOST_TEST(i.iterator_to(*it)==it); |
124 | n+=it->id; |
125 | } |
126 | int m=0; |
127 | for(size_type buc=0;buc<i.bucket_count();++buc){ |
128 | BOOST_TEST(i.cbegin(buc)==i.begin(buc)); |
129 | BOOST_TEST(i.cend(buc)==i.end(buc)); |
130 | for(const_local_iterator it=i.begin(buc);it!=i.end(buc);++it){ |
131 | BOOST_TEST(i.local_iterator_to(*it)==it); |
132 | m+=it->id; |
133 | } |
134 | } |
135 | |
136 | BOOST_TEST(n==target&&n==m); |
137 | } |
138 | |
139 | template<typename Index> |
140 | void test_non_const_rnd_iterators(Index& i,int target) |
141 | { |
142 | typedef typename Index::iterator iterator; |
143 | typedef typename Index::reverse_iterator reverse_iterator; |
144 | typedef typename Index::difference_type difference_type; |
145 | |
146 | iterator middle=i.begin()+(i.end()-i.begin())/2; |
147 | difference_type off=middle-i.begin(); |
148 | reverse_iterator rmiddle=i.rbegin()+off; |
149 | bool odd=((i.end()-i.begin())%2)!=0; |
150 | |
151 | int n=0; |
152 | for(iterator it=i.begin();it!=middle;++it){ |
153 | BOOST_TEST(i.iterator_to(*it)==it); |
154 | n+=it->id; |
155 | n+=it[off].id; |
156 | } |
157 | if(odd)n+=(boost::prior(i.end()))->id; |
158 | int m=0; |
159 | for(reverse_iterator rit=i.rbegin();rit!=rmiddle;++rit){ |
160 | m+=rit->id; |
161 | m+=(rit+off)->id; |
162 | } |
163 | if(odd)m+=(boost::prior(i.rend()))->id; |
164 | int p=0; |
165 | for(iterator it2=i.end();it2!=middle;){ |
166 | --it2; |
167 | p+=it2->id; |
168 | p+=(it2-off)->id; |
169 | } |
170 | if(odd)p-=middle->id; |
171 | int q=0; |
172 | for(reverse_iterator rit2=i.rend();rit2!=rmiddle;){ |
173 | --rit2; |
174 | q+=rit2->id; |
175 | q+=(rit2-off)->id; |
176 | } |
177 | if(odd)q-=rmiddle->id; |
178 | |
179 | BOOST_TEST(n==target&&n==m&&n==p&&n==q); |
180 | } |
181 | |
182 | template<typename Index> |
183 | void test_const_rnd_iterators(const Index& i,int target) |
184 | { |
185 | typedef typename Index::const_iterator const_iterator; |
186 | typedef typename Index::const_reverse_iterator const_reverse_iterator; |
187 | typedef typename Index::difference_type difference_type; |
188 | |
189 | BOOST_TEST(i.cbegin()==i.begin()); |
190 | BOOST_TEST(i.cend()==i.end()); |
191 | BOOST_TEST(i.crbegin()==i.rbegin()); |
192 | BOOST_TEST(i.crend()==i.rend()); |
193 | |
194 | const_iterator middle=i.begin()+(i.end()-i.begin())/2; |
195 | difference_type off=middle-i.begin(); |
196 | const_reverse_iterator rmiddle=i.rbegin()+off; |
197 | bool odd=((i.end()-i.begin())%2)!=0; |
198 | |
199 | int n=0; |
200 | for(const_iterator it=i.begin();it!=middle;++it){ |
201 | BOOST_TEST(i.iterator_to(*it)==it); |
202 | n+=it->id; |
203 | n+=it[off].id; |
204 | } |
205 | if(odd)n+=(boost::prior(i.end()))->id; |
206 | int m=0; |
207 | for(const_reverse_iterator rit=i.rbegin();rit!=rmiddle;++rit){ |
208 | m+=rit->id; |
209 | m+=(rit+off)->id; |
210 | } |
211 | if(odd)m+=(boost::prior(i.rend()))->id; |
212 | int p=0; |
213 | for(const_iterator it2=i.end();it2!=middle;){ |
214 | --it2; |
215 | p+=it2->id; |
216 | p+=(it2-off)->id; |
217 | } |
218 | if(odd)p-=middle->id; |
219 | int q=0; |
220 | for(const_reverse_iterator rit2=i.rend();rit2!=rmiddle;){ |
221 | --rit2; |
222 | q+=rit2->id; |
223 | q+=(rit2-off)->id; |
224 | } |
225 | if(odd)q-=rmiddle->id; |
226 | |
227 | BOOST_TEST(n==target&&n==m&&n==p&&n==q); |
228 | } |
229 | |
230 | template<typename Index> |
231 | void test_boost_for_each(const Index& i,int) |
232 | { |
233 | typedef typename Index::value_type value_type; |
234 | typedef typename Index::size_type size_type; |
235 | |
236 | size_type size=i.size(); |
237 | size_type count=0; |
238 | |
239 | BOOST_FOREACH(value_type const& x, i) |
240 | { |
241 | (void)x; |
242 | ++count; |
243 | } |
244 | |
245 | BOOST_TEST_EQ(count, size); |
246 | } |
247 | |
248 | void test_iterators() |
249 | { |
250 | employee_set es; |
251 | |
252 | es.insert(x: employee(0,"Joe" ,31,1123)); |
253 | es.insert(x: employee(1,"Robert" ,27,5601)); |
254 | es.insert(x: employee(2,"John" ,40,7889)); |
255 | es.insert(x: employee(3,"Albert" ,20,9012)); |
256 | es.insert(x: employee(4,"John" ,57,1002)); |
257 | |
258 | int target=0+1+2+3+4; |
259 | |
260 | test_non_const_iterators (i&: es,target); |
261 | test_const_iterators (i: es,target); |
262 | test_boost_for_each (i: es,target); |
263 | test_non_const_hashed_iterators(i&: get<1>(m&: es),target); |
264 | test_const_hashed_iterators (i: get<1>(m&: es),target); |
265 | test_boost_for_each (i: get<1>(m&: es),target); |
266 | test_non_const_iterators (i&: get<2>(m&: es),target); |
267 | test_const_iterators (i: get<2>(m&: es),target); |
268 | test_boost_for_each (i: get<2>(m&: es),target); |
269 | test_non_const_iterators (i&: get<3>(m&: es),target); |
270 | test_const_iterators (i: get<3>(m&: es),target); |
271 | test_boost_for_each (i: get<3>(m&: es),target); |
272 | test_non_const_hashed_iterators(i&: get<4>(m&: es),target); |
273 | test_const_hashed_iterators (i: get<4>(m&: es),target); |
274 | test_boost_for_each (i: get<4>(m&: es),target); |
275 | test_non_const_rnd_iterators (i&: get<5>(m&: es),target); |
276 | test_const_rnd_iterators (i: get<5>(m&: es),target); |
277 | test_boost_for_each (i: get<5>(m&: es),target); |
278 | |
279 | /* testcase for https://github.com/boostorg/multi_index/issues/68 */ |
280 | |
281 | { |
282 | typedef multi_index_container< |
283 | pair_of_ints, |
284 | indexed_by< |
285 | ordered_non_unique<member<pair_of_ints,int,&pair_of_ints::first> > |
286 | > |
287 | > container; |
288 | typedef container::iterator iterator; |
289 | |
290 | container c1,c2; |
291 | |
292 | std::vector<pair_of_ints> input; |
293 | input.push_back(x: pair_of_ints(1,0)); |
294 | input.push_back(x: pair_of_ints(1,1)); |
295 | input.push_back(x: pair_of_ints(1,2)); |
296 | input.push_back(x: pair_of_ints(0,0)); |
297 | input.push_back(x: pair_of_ints(1,3)); |
298 | |
299 | c1.insert(first: input.begin(),last: input.end()); |
300 | for(std::size_t i=0;i<input.size();++i)c2.insert(x: input[i]); |
301 | |
302 | std::pair<iterator,iterator> rng1=c1.equal_range(x: 1), |
303 | rng2=c2.equal_range(x: 1); |
304 | |
305 | BOOST_TEST( |
306 | std::distance(rng1.first,rng1.second)== |
307 | std::distance(rng2.first,rng2.second)); |
308 | BOOST_TEST(std::equal(rng1.first,rng1.second,rng2.first)); |
309 | } |
310 | } |
311 | |