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