Branch data Line data Source code
1 : : // $Id: IteratorTest.cc 128 2011-05-18 07:23:35Z tb $
2 : :
3 : : /*
4 : : * STX B+ Tree Template Classes v0.8.6
5 : : * Copyright (C) 2008-2011 Timo Bingmann
6 : : *
7 : : * This library is free software; you can redistribute it and/or modify it
8 : : * under the terms of the GNU Lesser General Public License as published by the
9 : : * Free Software Foundation; either version 2.1 of the License, or (at your
10 : : * option) any later version.
11 : : *
12 : : * This library is distributed in the hope that it will be useful, but WITHOUT
13 : : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
15 : : * for more details.
16 : : *
17 : : * You should have received a copy of the GNU Lesser General Public License
18 : : * along with this library; if not, write to the Free Software Foundation,
19 : : * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 : : */
21 : :
22 : : #include <cppunit/extensions/HelperMacros.h>
23 : :
24 : : #include <stdlib.h>
25 : :
26 : : #include <vector>
27 : :
28 : : #include <stx/btree_multiset.h>
29 : : #include <stx/btree_multimap.h>
30 : : #include <stx/btree_map.h>
31 : : #include <stx/btree_set.h>
32 : :
33 : : class IteratorTest : public CPPUNIT_NS::TestFixture
34 [ + - ][ # # ]: 12 : {
35 [ + - ][ + - ]: 2 : CPPUNIT_TEST_SUITE( IteratorTest );
[ # # ]
36 : 1 : CPPUNIT_TEST(test_iterator1);
37 : 1 : CPPUNIT_TEST(test_iterator2);
38 : 1 : CPPUNIT_TEST(test_iterator3);
39 : 1 : CPPUNIT_TEST(test_iterator4);
40 : 1 : CPPUNIT_TEST(test_iterator5);
41 : 1 : CPPUNIT_TEST(test_erase_iterator1);
42 : 2 : CPPUNIT_TEST_SUITE_END();
43 : :
44 : : protected:
45 : :
46 : : struct traits_nodebug
47 : : {
48 : : static const bool selfverify = true;
49 : : static const bool debug = false;
50 : :
51 : : static const int leafslots = 8;
52 : : static const int innerslots = 8;
53 : : };
54 : :
55 : 1 : void test_iterator1()
56 : : {
57 : : typedef stx::btree_multiset<unsigned int,
58 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
59 : :
60 : 1 : std::vector<unsigned int> vector;
61 : :
62 : 1 : srand(34234235);
63 [ + + ]: 3201 : for(unsigned int i = 0; i < 3200; i++)
64 : : {
65 : 3200 : vector.push_back( rand() % 1000 );
66 : : }
67 : :
68 : 1 : CPPUNIT_ASSERT( vector.size() == 3200 );
69 : :
70 : : // test construction and insert(iter, iter) function
71 : 1 : btree_type bt(vector.begin(), vector.end());
72 : :
73 : 1 : CPPUNIT_ASSERT( bt.size() == 3200 );
74 : :
75 : : // copy for later use
76 : 1 : btree_type bt2 = bt;
77 : :
78 : : // empty out the first bt
79 : 1 : srand(34234235);
80 [ + + ]: 3201 : for(unsigned int i = 0; i < 3200; i++)
81 : : {
82 : 3200 : CPPUNIT_ASSERT(bt.size() == 3200 - i);
83 : 3200 : CPPUNIT_ASSERT( bt.erase_one(rand() % 1000) );
84 : 3200 : CPPUNIT_ASSERT(bt.size() == 3200 - i - 1);
85 : : }
86 : :
87 : 1 : CPPUNIT_ASSERT( bt.empty() );
88 : :
89 : : // copy btree values back to a vector
90 : :
91 : 1 : std::vector<unsigned int> vector2;
92 : 1 : vector2.assign( bt2.begin(), bt2.end() );
93 : :
94 : : // afer sorting the vector, the two must be the same
95 : 1 : std::sort(vector.begin(), vector.end());
96 : :
97 : 1 : CPPUNIT_ASSERT( vector == vector2 );
98 : :
99 : : // test reverse iterator
100 : 1 : vector2.clear();
101 : 1 : vector2.assign( bt2.rbegin(), bt2.rend() );
102 : :
103 : 1 : std::reverse(vector.begin(), vector.end());
104 : :
105 : 1 : btree_type::reverse_iterator ri = bt2.rbegin();
106 [ + + ]: 3201 : for(unsigned int i = 0; i < vector2.size(); ++i)
107 : : {
108 : 3200 : CPPUNIT_ASSERT( vector[i] == vector2[i] );
109 : 3200 : CPPUNIT_ASSERT( vector[i] == *ri );
110 : :
111 : 3200 : ri++;
112 : : }
113 : :
114 : 1 : CPPUNIT_ASSERT( ri == bt2.rend() );
115 : 1 : }
116 : :
117 : 1 : void test_iterator2()
118 : : {
119 : : typedef stx::btree_multimap<unsigned int, unsigned int,
120 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
121 : :
122 : 1 : std::vector< btree_type::value_type > vector;
123 : :
124 : 1 : srand(34234235);
125 [ + + ]: 3201 : for(unsigned int i = 0; i < 3200; i++)
126 : : {
127 : 3200 : vector.push_back( btree_type::value_type(rand() % 1000, 0) );
128 : : }
129 : :
130 : 1 : CPPUNIT_ASSERT( vector.size() == 3200 );
131 : :
132 : : // test construction and insert(iter, iter) function
133 : 1 : btree_type bt(vector.begin(), vector.end());
134 : :
135 : 1 : CPPUNIT_ASSERT( bt.size() == 3200 );
136 : :
137 : : // copy for later use
138 : 1 : btree_type bt2 = bt;
139 : :
140 : : // empty out the first bt
141 : 1 : srand(34234235);
142 [ + + ]: 3201 : for(unsigned int i = 0; i < 3200; i++)
143 : : {
144 : 3200 : CPPUNIT_ASSERT(bt.size() == 3200 - i);
145 : 3200 : CPPUNIT_ASSERT( bt.erase_one(rand() % 1000) );
146 : 3200 : CPPUNIT_ASSERT(bt.size() == 3200 - i - 1);
147 : : }
148 : :
149 : 1 : CPPUNIT_ASSERT( bt.empty() );
150 : :
151 : : // copy btree values back to a vector
152 : :
153 : 1 : std::vector< btree_type::value_type > vector2;
154 : 1 : vector2.assign( bt2.begin(), bt2.end() );
155 : :
156 : : // afer sorting the vector, the two must be the same
157 : 1 : std::sort(vector.begin(), vector.end());
158 : :
159 : 1 : CPPUNIT_ASSERT( vector == vector2 );
160 : :
161 : : // test reverse iterator
162 : 1 : vector2.clear();
163 : 1 : vector2.assign( bt2.rbegin(), bt2.rend() );
164 : :
165 : 1 : std::reverse(vector.begin(), vector.end());
166 : :
167 : 1 : btree_type::reverse_iterator ri = bt2.rbegin();
168 [ + + ]: 3201 : for(unsigned int i = 0; i < vector2.size(); ++i, ++ri)
169 : : {
170 : 3200 : CPPUNIT_ASSERT( vector[i].first == vector2[i].first );
171 : 3200 : CPPUNIT_ASSERT( vector[i].first == ri->first );
172 : 3200 : CPPUNIT_ASSERT( vector[i].second == ri->second );
173 : : }
174 : :
175 : 1 : CPPUNIT_ASSERT( ri == bt2.rend() );
176 : 1 : }
177 : :
178 : 1 : void test_iterator3()
179 : : {
180 : : typedef stx::btree_map<unsigned int, unsigned int,
181 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
182 : :
183 : 1 : btree_type map;
184 : :
185 : 1 : unsigned int maxnum = 1000;
186 : :
187 [ + + ]: 1001 : for(unsigned int i = 0; i < maxnum; ++i)
188 : : {
189 : 1000 : map.insert( std::make_pair(i, i*3) );
190 : : }
191 : :
192 : : { // test iterator prefix++
193 : 1 : unsigned int nownum = 0;
194 : :
195 [ + + ]: 1001 : for(btree_type::iterator i = map.begin();
196 : : i != map.end(); ++i)
197 : : {
198 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
199 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
200 : :
201 : 1000 : nownum++;
202 : : }
203 : :
204 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
205 : : }
206 : :
207 : : { // test iterator prefix--
208 : 1 : unsigned int nownum = maxnum;
209 : :
210 : 1 : btree_type::iterator i;
211 [ - + ][ + + ]: 1000 : for(i = --map.end(); i != map.begin(); --i)
212 : : {
213 : 999 : nownum--;
214 : :
215 : 999 : CPPUNIT_ASSERT( nownum == i->first );
216 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
217 : : }
218 : :
219 : 1 : nownum--;
220 : :
221 : 1 : CPPUNIT_ASSERT( nownum == i->first );
222 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
223 : :
224 : 1 : CPPUNIT_ASSERT(nownum == 0);
225 : : }
226 : :
227 : : { // test const_iterator prefix++
228 : 1 : unsigned int nownum = 0;
229 : :
230 [ + + ]: 1001 : for(btree_type::const_iterator i = map.begin();
231 : : i != map.end(); ++i)
232 : : {
233 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
234 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
235 : :
236 : 1000 : nownum++;
237 : : }
238 : :
239 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
240 : : }
241 : :
242 : : { // test const_iterator prefix--
243 : 1 : unsigned int nownum = maxnum;
244 : :
245 : 1 : btree_type::const_iterator i;
246 [ - + ][ + + ]: 1000 : for(i = --map.end(); i != map.begin(); --i)
247 : : {
248 : 999 : nownum--;
249 : :
250 : 999 : CPPUNIT_ASSERT( nownum == i->first );
251 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
252 : : }
253 : :
254 : 1 : nownum--;
255 : :
256 : 1 : CPPUNIT_ASSERT( nownum == i->first );
257 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
258 : :
259 : 1 : CPPUNIT_ASSERT(nownum == 0);
260 : : }
261 : :
262 : : { // test reverse_iterator prefix++
263 : 1 : unsigned int nownum = maxnum;
264 : :
265 [ + + ]: 1001 : for(btree_type::reverse_iterator i = map.rbegin();
266 : : i != map.rend(); ++i)
267 : : {
268 : 1000 : nownum--;
269 : :
270 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
271 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
272 : : }
273 : :
274 : 1 : CPPUNIT_ASSERT(nownum == 0);
275 : : }
276 : :
277 : : { // test reverse_iterator prefix--
278 : 1 : unsigned int nownum = 0;
279 : :
280 : 1 : btree_type::reverse_iterator i;
281 [ - + ][ + + ]: 1000 : for(i = --map.rend(); i != map.rbegin(); --i)
282 : : {
283 : 999 : CPPUNIT_ASSERT( nownum == i->first );
284 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
285 : :
286 : 999 : nownum++;
287 : : }
288 : :
289 : 1 : CPPUNIT_ASSERT( nownum == i->first );
290 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
291 : :
292 : 1 : nownum++;
293 : :
294 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
295 : : }
296 : :
297 : : { // test const_reverse_iterator prefix++
298 : 1 : unsigned int nownum = maxnum;
299 : :
300 [ + + ]: 1001 : for(btree_type::const_reverse_iterator i = map.rbegin();
301 : : i != map.rend(); ++i)
302 : : {
303 : 1000 : nownum--;
304 : :
305 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
306 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
307 : : }
308 : :
309 : 1 : CPPUNIT_ASSERT(nownum == 0);
310 : : }
311 : :
312 : : { // test const_reverse_iterator prefix--
313 : 1 : unsigned int nownum = 0;
314 : :
315 : 1 : btree_type::const_reverse_iterator i;
316 [ - + ][ + + ]: 1000 : for(i = --map.rend(); i != map.rbegin(); --i)
317 : : {
318 : 999 : CPPUNIT_ASSERT( nownum == i->first );
319 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
320 : :
321 : 999 : nownum++;
322 : : }
323 : :
324 : 1 : CPPUNIT_ASSERT( nownum == i->first );
325 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
326 : :
327 : 1 : nownum++;
328 : :
329 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
330 : : }
331 : :
332 : : // postfix
333 : :
334 : : { // test iterator postfix++
335 : 1 : unsigned int nownum = 0;
336 : :
337 [ + + ]: 1001 : for(btree_type::iterator i = map.begin();
338 : : i != map.end(); i++)
339 : : {
340 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
341 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
342 : :
343 : 1000 : nownum++;
344 : : }
345 : :
346 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
347 : : }
348 : :
349 : : { // test iterator postfix--
350 : 1 : unsigned int nownum = maxnum;
351 : :
352 : 1 : btree_type::iterator i;
353 [ - + ][ + + ]: 1000 : for(i = --map.end(); i != map.begin(); i--)
354 : : {
355 : 999 : nownum--;
356 : :
357 : 999 : CPPUNIT_ASSERT( nownum == i->first );
358 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
359 : : }
360 : :
361 : 1 : nownum--;
362 : :
363 : 1 : CPPUNIT_ASSERT( nownum == i->first );
364 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
365 : :
366 : 1 : CPPUNIT_ASSERT(nownum == 0);
367 : : }
368 : :
369 : : { // test const_iterator postfix++
370 : 1 : unsigned int nownum = 0;
371 : :
372 [ + + ]: 1001 : for(btree_type::const_iterator i = map.begin();
373 : : i != map.end(); i++)
374 : : {
375 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
376 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
377 : :
378 : 1000 : nownum++;
379 : : }
380 : :
381 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
382 : : }
383 : :
384 : : { // test const_iterator postfix--
385 : 1 : unsigned int nownum = maxnum;
386 : :
387 : 1 : btree_type::const_iterator i;
388 [ - + ][ + + ]: 1000 : for(i = --map.end(); i != map.begin(); i--)
389 : : {
390 : 999 : nownum--;
391 : :
392 : 999 : CPPUNIT_ASSERT( nownum == i->first );
393 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
394 : : }
395 : :
396 : 1 : nownum--;
397 : :
398 : 1 : CPPUNIT_ASSERT( nownum == i->first );
399 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
400 : :
401 : 1 : CPPUNIT_ASSERT(nownum == 0);
402 : : }
403 : :
404 : : { // test reverse_iterator postfix++
405 : 1 : unsigned int nownum = maxnum;
406 : :
407 [ + + ]: 1001 : for(btree_type::reverse_iterator i = map.rbegin();
408 : : i != map.rend(); i++)
409 : : {
410 : 1000 : nownum--;
411 : :
412 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
413 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
414 : : }
415 : :
416 : 1 : CPPUNIT_ASSERT(nownum == 0);
417 : : }
418 : :
419 : : { // test reverse_iterator postfix--
420 : 1 : unsigned int nownum = 0;
421 : :
422 : 1 : btree_type::reverse_iterator i;
423 [ - + ][ + + ]: 1000 : for(i = --map.rend(); i != map.rbegin(); i--)
424 : : {
425 : 999 : CPPUNIT_ASSERT( nownum == i->first );
426 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
427 : :
428 : 999 : nownum++;
429 : : }
430 : :
431 : 1 : CPPUNIT_ASSERT( nownum == i->first );
432 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
433 : :
434 : 1 : nownum++;
435 : :
436 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
437 : : }
438 : :
439 : : { // test const_reverse_iterator postfix++
440 : 1 : unsigned int nownum = maxnum;
441 : :
442 [ + + ]: 1001 : for(btree_type::const_reverse_iterator i = map.rbegin();
443 : : i != map.rend(); i++)
444 : : {
445 : 1000 : nownum--;
446 : :
447 : 1000 : CPPUNIT_ASSERT( nownum == i->first );
448 : 1000 : CPPUNIT_ASSERT( nownum * 3 == i->second );
449 : : }
450 : :
451 : 1 : CPPUNIT_ASSERT(nownum == 0);
452 : : }
453 : :
454 : : { // test const_reverse_iterator postfix--
455 : 1 : unsigned int nownum = 0;
456 : :
457 : 1 : btree_type::const_reverse_iterator i;
458 [ - + ][ + + ]: 1000 : for(i = --map.rend(); i != map.rbegin(); i--)
459 : : {
460 : 999 : CPPUNIT_ASSERT( nownum == i->first );
461 : 999 : CPPUNIT_ASSERT( nownum * 3 == i->second );
462 : :
463 : 999 : nownum++;
464 : : }
465 : :
466 : 1 : CPPUNIT_ASSERT( nownum == i->first );
467 : 1 : CPPUNIT_ASSERT( nownum * 3 == i->second );
468 : :
469 : 1 : nownum++;
470 : :
471 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
472 : 1 : }
473 : 1 : }
474 : :
475 : 1 : void test_iterator4()
476 : : {
477 : : typedef stx::btree_set<unsigned int,
478 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
479 : :
480 : 1 : btree_type set;
481 : :
482 : 1 : unsigned int maxnum = 1000;
483 : :
484 [ + + ]: 1001 : for(unsigned int i = 0; i < maxnum; ++i)
485 : : {
486 : 1000 : set.insert(i);
487 : : }
488 : :
489 : : { // test iterator prefix++
490 : 1 : unsigned int nownum = 0;
491 : :
492 [ + + ]: 1001 : for(btree_type::iterator i = set.begin();
493 : : i != set.end(); ++i)
494 : : {
495 : 1000 : CPPUNIT_ASSERT( nownum == *i );
496 : 1000 : nownum++;
497 : : }
498 : :
499 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
500 : : }
501 : :
502 : : { // test iterator prefix--
503 : 1 : unsigned int nownum = maxnum;
504 : :
505 : 1 : btree_type::iterator i;
506 [ + + ]: 1000 : for(i = --set.end(); i != set.begin(); --i)
507 : : {
508 : 999 : CPPUNIT_ASSERT( --nownum == *i );
509 : : }
510 : :
511 : 1 : CPPUNIT_ASSERT( --nownum == *i );
512 : :
513 : 1 : CPPUNIT_ASSERT(nownum == 0);
514 : : }
515 : :
516 : : { // test const_iterator prefix++
517 : 1 : unsigned int nownum = 0;
518 : :
519 [ + + ]: 1001 : for(btree_type::const_iterator i = set.begin();
520 : : i != set.end(); ++i)
521 : : {
522 : 1000 : CPPUNIT_ASSERT( nownum++ == *i );
523 : : }
524 : :
525 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
526 : : }
527 : :
528 : : { // test const_iterator prefix--
529 : 1 : unsigned int nownum = maxnum;
530 : :
531 : 1 : btree_type::const_iterator i;
532 [ + + ]: 1000 : for(i = --set.end(); i != set.begin(); --i)
533 : : {
534 : 999 : CPPUNIT_ASSERT( --nownum == *i );
535 : : }
536 : :
537 : 1 : CPPUNIT_ASSERT( --nownum == *i );
538 : :
539 : 1 : CPPUNIT_ASSERT(nownum == 0);
540 : : }
541 : :
542 : : { // test reverse_iterator prefix++
543 : 1 : unsigned int nownum = maxnum;
544 : :
545 [ + + ]: 1001 : for(btree_type::reverse_iterator i = set.rbegin();
546 : : i != set.rend(); ++i)
547 : : {
548 : 1000 : CPPUNIT_ASSERT( --nownum == *i );
549 : : }
550 : :
551 : 1 : CPPUNIT_ASSERT(nownum == 0);
552 : : }
553 : :
554 : : { // test reverse_iterator prefix--
555 : 1 : unsigned int nownum = 0;
556 : :
557 : 1 : btree_type::reverse_iterator i;
558 [ + + ]: 1000 : for(i = --set.rend(); i != set.rbegin(); --i)
559 : : {
560 : 999 : CPPUNIT_ASSERT( nownum++ == *i );
561 : : }
562 : :
563 : 1 : CPPUNIT_ASSERT( nownum++ == *i );
564 : :
565 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
566 : : }
567 : :
568 : : { // test const_reverse_iterator prefix++
569 : 1 : unsigned int nownum = maxnum;
570 : :
571 [ + + ]: 1001 : for(btree_type::const_reverse_iterator i = set.rbegin();
572 : : i != set.rend(); ++i)
573 : : {
574 : 1000 : CPPUNIT_ASSERT( --nownum == *i );
575 : : }
576 : :
577 : 1 : CPPUNIT_ASSERT(nownum == 0);
578 : : }
579 : :
580 : : { // test const_reverse_iterator prefix--
581 : 1 : unsigned int nownum = 0;
582 : :
583 : 1 : btree_type::const_reverse_iterator i;
584 [ + + ]: 1000 : for(i = --set.rend(); i != set.rbegin(); --i)
585 : : {
586 : 999 : CPPUNIT_ASSERT( nownum++ == *i );
587 : : }
588 : :
589 : 1 : CPPUNIT_ASSERT( nownum++ == *i );
590 : :
591 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
592 : : }
593 : :
594 : : // postfix
595 : :
596 : : { // test iterator postfix++
597 : 1 : unsigned int nownum = 0;
598 : :
599 [ + + ]: 1001 : for(btree_type::iterator i = set.begin();
600 : : i != set.end(); i++)
601 : : {
602 : 1000 : CPPUNIT_ASSERT( nownum++ == *i );
603 : : }
604 : :
605 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
606 : : }
607 : :
608 : : { // test iterator postfix--
609 : 1 : unsigned int nownum = maxnum;
610 : :
611 : 1 : btree_type::iterator i;
612 [ + + ]: 1000 : for(i = --set.end(); i != set.begin(); i--)
613 : : {
614 : :
615 : 999 : CPPUNIT_ASSERT( --nownum == *i );
616 : : }
617 : :
618 : 1 : CPPUNIT_ASSERT( --nownum == *i );
619 : :
620 : 1 : CPPUNIT_ASSERT(nownum == 0);
621 : : }
622 : :
623 : : { // test const_iterator postfix++
624 : 1 : unsigned int nownum = 0;
625 : :
626 [ + + ]: 1001 : for(btree_type::const_iterator i = set.begin();
627 : : i != set.end(); i++)
628 : : {
629 : 1000 : CPPUNIT_ASSERT( nownum++ == *i );
630 : : }
631 : :
632 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
633 : : }
634 : :
635 : : { // test const_iterator postfix--
636 : 1 : unsigned int nownum = maxnum;
637 : :
638 : 1 : btree_type::const_iterator i;
639 [ + + ]: 1000 : for(i = --set.end(); i != set.begin(); i--)
640 : : {
641 : 999 : CPPUNIT_ASSERT( --nownum == *i );
642 : : }
643 : :
644 : 1 : CPPUNIT_ASSERT( --nownum == *i );
645 : :
646 : 1 : CPPUNIT_ASSERT(nownum == 0);
647 : : }
648 : :
649 : : { // test reverse_iterator postfix++
650 : 1 : unsigned int nownum = maxnum;
651 : :
652 [ + + ]: 1001 : for(btree_type::reverse_iterator i = set.rbegin();
653 : : i != set.rend(); i++)
654 : : {
655 : 1000 : CPPUNIT_ASSERT( --nownum == *i );
656 : : }
657 : :
658 : 1 : CPPUNIT_ASSERT(nownum == 0);
659 : : }
660 : :
661 : : { // test reverse_iterator postfix--
662 : 1 : unsigned int nownum = 0;
663 : :
664 : 1 : btree_type::reverse_iterator i;
665 [ + + ]: 1000 : for(i = --set.rend(); i != set.rbegin(); i--)
666 : : {
667 : 999 : CPPUNIT_ASSERT( nownum++ == *i );
668 : : }
669 : :
670 : 1 : CPPUNIT_ASSERT( nownum++ == *i );
671 : :
672 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
673 : : }
674 : :
675 : : { // test const_reverse_iterator postfix++
676 : 1 : unsigned int nownum = maxnum;
677 : :
678 [ + + ]: 1001 : for(btree_type::const_reverse_iterator i = set.rbegin();
679 : : i != set.rend(); i++)
680 : : {
681 : 1000 : CPPUNIT_ASSERT( --nownum == *i );
682 : : }
683 : :
684 : 1 : CPPUNIT_ASSERT(nownum == 0);
685 : : }
686 : :
687 : : { // test const_reverse_iterator postfix--
688 : 1 : unsigned int nownum = 0;
689 : :
690 : 1 : btree_type::const_reverse_iterator i;
691 [ + + ]: 1000 : for(i = --set.rend(); i != set.rbegin(); i--)
692 : : {
693 : 999 : CPPUNIT_ASSERT( nownum++ == *i );
694 : : }
695 : :
696 : 1 : CPPUNIT_ASSERT( nownum++ == *i );
697 : :
698 : 1 : CPPUNIT_ASSERT(nownum == maxnum);
699 : 1 : }
700 : 1 : }
701 : :
702 : 1 : void test_iterator5()
703 : : {
704 : : typedef stx::btree_set<unsigned int,
705 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
706 : :
707 : 1 : btree_type set;
708 : :
709 : 1 : unsigned int maxnum = 100;
710 : :
711 [ + + ]: 101 : for(unsigned int i = 0; i < maxnum; ++i)
712 : : {
713 : 100 : set.insert(i);
714 : : }
715 : :
716 : : {
717 : 1 : btree_type::iterator it;
718 : :
719 : 1 : it = set.begin();
720 : 1 : it--;
721 : 1 : CPPUNIT_ASSERT( it == set.begin() );
722 : :
723 : 1 : it = set.begin();
724 : 1 : --it;
725 : 1 : CPPUNIT_ASSERT( it == set.begin() );
726 : :
727 : 1 : it = set.end();
728 : 1 : it++;
729 : 1 : CPPUNIT_ASSERT( it == set.end() );
730 : :
731 : 1 : it = set.end();
732 : 1 : ++it;
733 : 1 : CPPUNIT_ASSERT( it == set.end() );
734 : : }
735 : :
736 : : {
737 : 1 : btree_type::const_iterator it;
738 : :
739 : 1 : it = set.begin();
740 : 1 : it--;
741 : 1 : CPPUNIT_ASSERT( it == set.begin() );
742 : :
743 : 1 : it = set.begin();
744 : 1 : --it;
745 : 1 : CPPUNIT_ASSERT( it == set.begin() );
746 : :
747 : 1 : it = set.end();
748 : 1 : it++;
749 : 1 : CPPUNIT_ASSERT( it == set.end() );
750 : :
751 : 1 : it = set.end();
752 : 1 : ++it;
753 : 1 : CPPUNIT_ASSERT( it == set.end() );
754 : : }
755 : :
756 : : {
757 : 1 : btree_type::reverse_iterator it;
758 : :
759 : 1 : it = set.rbegin();
760 : 1 : it--;
761 : 1 : CPPUNIT_ASSERT( it == set.rbegin() );
762 : :
763 : 1 : it = set.rbegin();
764 : 1 : --it;
765 : 1 : CPPUNIT_ASSERT( it == set.rbegin() );
766 : :
767 : 1 : it = set.rend();
768 : 1 : it++;
769 : 1 : CPPUNIT_ASSERT( it == set.rend() );
770 : :
771 : 1 : it = set.rend();
772 : 1 : ++it;
773 : 1 : CPPUNIT_ASSERT( it == set.rend() );
774 : : }
775 : :
776 : : {
777 : 1 : btree_type::const_reverse_iterator it;
778 : :
779 : 1 : it = set.rbegin();
780 : 1 : it--;
781 : 1 : CPPUNIT_ASSERT( it == set.rbegin() );
782 : :
783 : 1 : it = set.rbegin();
784 : 1 : --it;
785 : 1 : CPPUNIT_ASSERT( it == set.rbegin() );
786 : :
787 : 1 : it = set.rend();
788 : 1 : it++;
789 : 1 : CPPUNIT_ASSERT( it == set.rend() );
790 : :
791 : 1 : it = set.rend();
792 : 1 : ++it;
793 : 1 : CPPUNIT_ASSERT( it == set.rend() );
794 : 1 : }
795 : 1 : }
796 : :
797 : 1 : void test_erase_iterator1()
798 : : {
799 : : typedef stx::btree_multimap<int, int,
800 : : std::less<int>, struct traits_nodebug> btree_type;
801 : :
802 : 1 : btree_type map;
803 : :
804 : 1 : const int size1 = 32;
805 : 1 : const int size2 = 256;
806 : :
807 [ + + ]: 33 : for (int i = 0; i < size1; ++i)
808 : : {
809 [ + + ]: 8224 : for (int j = 0; j < size2; ++j)
810 : : {
811 : 8192 : map.insert2(i,j);
812 : : }
813 : : }
814 : :
815 : 1 : CPPUNIT_ASSERT( map.size() == size1 * size2 );
816 : :
817 : : // erase in reverse order. that should be the worst case for
818 : : // erase_iter()
819 : :
820 [ + + ]: 33 : for (int i = size1-1; i >= 0; --i)
821 : : {
822 [ + + ]: 8224 : for (int j = size2-1; j >= 0; --j)
823 : : {
824 : : // find iterator
825 : 8192 : btree_type::iterator it = map.find(i);
826 : :
827 [ + - ][ + - ]: 52736 : while (it != map.end() && it.key() == i && it.data() != j)
[ + + ][ + + ]
828 : 44544 : ++it;
829 : :
830 : 8192 : CPPUNIT_ASSERT( it.key() == i );
831 : 8192 : CPPUNIT_ASSERT( it.data() == j );
832 : :
833 : 8192 : unsigned int mapsize = map.size();
834 : 8192 : map.erase(it);
835 : 8192 : CPPUNIT_ASSERT( map.size() == mapsize - 1 );
836 : : }
837 : : }
838 : :
839 : 1 : CPPUNIT_ASSERT( map.size() == 0 );
840 : 1 : }
841 : : };
842 : :
843 [ + - ][ + - ]: 3 : CPPUNIT_TEST_SUITE_REGISTRATION( IteratorTest );
|