1 : // $Id: BoundTest.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 <stx/btree_multimap.h>
27 : #include <set>
28 :
29 : class BoundTest : public CPPUNIT_NS::TestFixture
30 4 : {
31 3 : CPPUNIT_TEST_SUITE( BoundTest );
32 1 : CPPUNIT_TEST(test_3200_10);
33 2 : CPPUNIT_TEST(test_320_1000);
34 2 : CPPUNIT_TEST_SUITE_END();
35 :
36 : protected:
37 :
38 : struct traits_nodebug
39 : {
40 : static const bool selfverify = true;
41 : static const bool debug = false;
42 :
43 : static const int leafslots = 8;
44 : static const int innerslots = 8;
45 : };
46 :
47 2 : void test_multi(const unsigned int insnum, const int modulo)
48 : {
49 : typedef stx::btree_multimap<unsigned int, unsigned int, std::less<unsigned int>, struct traits_nodebug> btree_type;
50 2 : btree_type bt;
51 :
52 : typedef std::multiset<unsigned int> multiset_type;
53 2 : multiset_type set;
54 :
55 : // *** insert
56 2 : srand(34234235);
57 7044 : for(unsigned int i = 0; i < insnum; i++)
58 : {
59 3520 : unsigned int k = rand() % modulo;
60 3520 : unsigned int v = 234;
61 :
62 3520 : CPPUNIT_ASSERT( bt.size() == set.size() );
63 3520 : bt.insert2(k, v);
64 3520 : set.insert(k);
65 3520 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
66 :
67 7040 : CPPUNIT_ASSERT( bt.size() == set.size() );
68 : }
69 :
70 2 : CPPUNIT_ASSERT( bt.size() == insnum );
71 :
72 : // *** iterate
73 : {
74 2 : btree_type::iterator bi = bt.begin();
75 2 : multiset_type::const_iterator si = set.begin();
76 7044 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
77 : {
78 3520 : CPPUNIT_ASSERT( *si == bi.key() );
79 : }
80 2 : CPPUNIT_ASSERT( bi == bt.end() );
81 4 : CPPUNIT_ASSERT( si == set.end() );
82 : }
83 :
84 : // *** existance
85 2 : srand(34234235);
86 7044 : for(unsigned int i = 0; i < insnum; i++)
87 : {
88 3520 : unsigned int k = rand() % modulo;
89 :
90 3520 : CPPUNIT_ASSERT( bt.exists(k) );
91 : }
92 :
93 : // *** counting
94 2 : srand(34234235);
95 7044 : for(unsigned int i = 0; i < insnum; i++)
96 : {
97 3520 : unsigned int k = rand() % modulo;
98 :
99 3520 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
100 : }
101 :
102 : // *** lower_bound
103 1212 : for(int k = 0; k < modulo + 100; k++)
104 : {
105 1210 : multiset_type::const_iterator si = set.lower_bound(k);
106 1210 : btree_type::const_iterator bi = bt.lower_bound(k);
107 :
108 1210 : if ( bi == bt.end() )
109 203 : CPPUNIT_ASSERT( si == set.end() );
110 1007 : else if ( si == set.end() )
111 0 : CPPUNIT_ASSERT( bi == bt.end() );
112 : else
113 1007 : CPPUNIT_ASSERT( *si == bi.key() );
114 : }
115 :
116 : // *** upper_bound
117 1212 : for(int k = 0; k < modulo + 100; k++)
118 : {
119 1210 : multiset_type::const_iterator si = set.upper_bound(k);
120 1210 : btree_type::const_iterator bi = bt.upper_bound(k);
121 :
122 1210 : if ( bi == bt.end() )
123 205 : CPPUNIT_ASSERT( si == set.end() );
124 1005 : else if ( si == set.end() )
125 0 : CPPUNIT_ASSERT( bi == bt.end() );
126 : else
127 1005 : CPPUNIT_ASSERT( *si == bi.key() );
128 : }
129 :
130 : // *** equal_range
131 1212 : for(int k = 0; k < modulo + 100; k++)
132 : {
133 1210 : std::pair<multiset_type::const_iterator, multiset_type::const_iterator> si = set.equal_range(k);
134 1210 : std::pair<btree_type::const_iterator, btree_type::const_iterator> bi = bt.equal_range(k);
135 :
136 1210 : if ( bi.first == bt.end() )
137 203 : CPPUNIT_ASSERT( si.first == set.end() );
138 1007 : else if ( si.first == set.end() )
139 0 : CPPUNIT_ASSERT( bi.first == bt.end() );
140 : else
141 1007 : CPPUNIT_ASSERT( *si.first == bi.first.key() );
142 :
143 1210 : if ( bi.second == bt.end() )
144 205 : CPPUNIT_ASSERT( si.second == set.end() );
145 1005 : else if ( si.second == set.end() )
146 0 : CPPUNIT_ASSERT( bi.second == bt.end() );
147 : else
148 1005 : CPPUNIT_ASSERT( *si.second == bi.second.key() );
149 : }
150 :
151 : // *** deletion
152 2 : srand(34234235);
153 3522 : for(unsigned int i = 0; i < insnum; i++)
154 : {
155 3520 : unsigned int k = rand() % modulo;
156 :
157 3520 : if (set.find(k) != set.end())
158 : {
159 3520 : CPPUNIT_ASSERT( bt.size() == set.size() );
160 :
161 7040 : CPPUNIT_ASSERT( bt.exists(k) );
162 7040 : CPPUNIT_ASSERT( bt.erase_one(k) );
163 7040 : set.erase( set.find(k) );
164 :
165 3520 : CPPUNIT_ASSERT( bt.size() == set.size() );
166 : }
167 : }
168 :
169 2 : CPPUNIT_ASSERT( bt.empty() );
170 4 : CPPUNIT_ASSERT( set.empty() );
171 2 : }
172 :
173 1 : void test_3200_10()
174 : {
175 1 : test_multi(3200, 10);
176 1 : }
177 :
178 1 : void test_320_1000()
179 : {
180 1 : test_multi(320, 1000);
181 1 : }
182 : };
183 0 :
184 3 : CPPUNIT_TEST_SUITE_REGISTRATION( BoundTest );
|
