1 : // $Id: IteratorTest.cc 35 2007-04-27 11:26:33Z tb $
2 :
3 : /*
4 : * STX B+ Tree Template Classes v0.7
5 : * Copyright (C) 2007 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 :
31 : class IteratorTest : public CPPUNIT_NS::TestFixture
32 2 : {
33 3 : CPPUNIT_TEST_SUITE( IteratorTest );
34 1 : CPPUNIT_TEST(test_iterator1);
35 2 : CPPUNIT_TEST_SUITE_END();
36 :
37 : protected:
38 :
39 : struct traits_nodebug
40 : {
41 : static const bool selfverify = true;
42 : static const bool debug = false;
43 :
44 : static const int leafslots = 8;
45 : static const int innerslots = 8;
46 : };
47 :
48 1 : void test_iterator1()
49 : {
50 : typedef stx::btree_multiset<unsigned int,
51 : std::less<unsigned int>, struct traits_nodebug> btree_type;
52 :
53 1 : std::vector<unsigned int> vector;
54 :
55 1 : srand(34234235);
56 3201 : for(unsigned int i = 0; i < 3200; i++)
57 : {
58 3200 : vector.push_back( rand() % 1000 );
59 : }
60 :
61 1 : CPPUNIT_ASSERT( vector.size() == 3200 );
62 :
63 : // test construction and insert(iter, iter) function
64 2 : btree_type bt(vector.begin(), vector.end());
65 :
66 1 : CPPUNIT_ASSERT( bt.size() == 3200 );
67 :
68 : // copy for later use
69 1 : btree_type bt2 = bt;
70 :
71 : // empty out the first bt
72 1 : srand(34234235);
73 6402 : for(unsigned int i = 0; i < 3200; i++)
74 : {
75 3200 : CPPUNIT_ASSERT(bt.size() == 3200 - i);
76 6400 : CPPUNIT_ASSERT( bt.erase_one(rand() % 1000) );
77 6400 : CPPUNIT_ASSERT(bt.size() == 3200 - i - 1);
78 : }
79 :
80 1 : CPPUNIT_ASSERT( bt.empty() );
81 :
82 : // copy btree values back to a vector
83 :
84 2 : std::vector<unsigned int> vector2;
85 2 : vector2.assign( bt2.begin(), bt2.end() );
86 :
87 : // afer sorting the vector, the two must be the same
88 1 : std::sort(vector.begin(), vector.end());
89 :
90 1 : CPPUNIT_ASSERT( vector == vector2 );
91 :
92 : // test reverse iterator
93 1 : vector2.clear();
94 1 : vector2.assign( bt2.rbegin(), bt2.rend() );
95 :
96 1 : std::reverse(vector.begin(), vector.end());
97 :
98 1 : btree_type::reverse_iterator ri = bt2.rbegin();
99 3201 : for(unsigned int i = 0; i < vector2.size(); ++i)
100 : {
101 3200 : CPPUNIT_ASSERT( vector[i] == vector2[i] );
102 6400 : CPPUNIT_ASSERT( vector[i] == *ri );
103 :
104 3200 : ri++;
105 : }
106 :
107 1 : CPPUNIT_ASSERT( ri == bt2.rend() );
108 1 : }
109 :
110 : void test_iterator2()
111 : {
112 : typedef stx::btree_multimap<unsigned int, unsigned int,
113 : std::less<unsigned int>, struct traits_nodebug> btree_type;
114 :
115 : std::vector< btree_type::value_type > vector;
116 :
117 : srand(34234235);
118 : for(unsigned int i = 0; i < 3200; i++)
119 : {
120 : vector.push_back( btree_type::value_type(rand() % 1000, 0) );
121 : }
122 :
123 : CPPUNIT_ASSERT( vector.size() == 3200 );
124 :
125 : // test construction and insert(iter, iter) function
126 : btree_type bt(vector.begin(), vector.end());
127 :
128 : CPPUNIT_ASSERT( bt.size() == 3200 );
129 :
130 : // copy for later use
131 : btree_type bt2 = bt;
132 :
133 : // empty out the first bt
134 : srand(34234235);
135 : for(unsigned int i = 0; i < 3200; i++)
136 : {
137 : CPPUNIT_ASSERT(bt.size() == 3200 - i);
138 : CPPUNIT_ASSERT( bt.erase_one(rand() % 1000) );
139 : CPPUNIT_ASSERT(bt.size() == 3200 - i - 1);
140 : }
141 :
142 : CPPUNIT_ASSERT( bt.empty() );
143 :
144 : // copy btree values back to a vector
145 :
146 : std::vector< btree_type::value_type > vector2;
147 : vector2.assign( bt2.begin(), bt2.end() );
148 :
149 : // afer sorting the vector, the two must be the same
150 : std::sort(vector.begin(), vector.end());
151 :
152 : CPPUNIT_ASSERT( vector == vector2 );
153 :
154 : // test reverse iterator
155 : vector2.clear();
156 : vector2.assign( bt2.rbegin(), bt2.rend() );
157 :
158 : std::reverse(vector.begin(), vector.end());
159 :
160 : btree_type::reverse_iterator ri = bt2.rbegin();
161 : for(unsigned int i = 0; i < vector2.size(); ++i)
162 : {
163 : CPPUNIT_ASSERT( vector[i].first == vector2[i].first );
164 : CPPUNIT_ASSERT( vector[i].first == ri->first );
165 :
166 : // there are some undetermined problems with the second value
167 : // std::cout << vector[i].second << " " << vector2[i].second << " " << ri->second << "\n";
168 : ri++;
169 : }
170 :
171 : CPPUNIT_ASSERT( ri == bt2.rend() );
172 : }
173 : };
174 0 :
175 3 : CPPUNIT_TEST_SUITE_REGISTRATION( IteratorTest );
|
