Branch data Line data Source code
1 : : // $Id: BoundTest.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 <stx/btree_multimap.h>
27 : : #include <set>
28 : :
29 : : class BoundTest : public CPPUNIT_NS::TestFixture
30 [ + - ][ # # ]: 4 : {
31 [ + - ][ + - ]: 2 : CPPUNIT_TEST_SUITE( BoundTest );
[ # # ]
32 : 1 : CPPUNIT_TEST(test_3200_10);
33 : 1 : 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 [ + + ]: 3522 : 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 : 3520 : 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 [ + + ][ + - ]: 3522 : 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 : 2 : CPPUNIT_ASSERT( si == set.end() );
82 : : }
83 : :
84 : : // *** existance
85 : 2 : srand(34234235);
86 [ + + ]: 3522 : 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 [ + + ]: 3522 : 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 : 3520 : CPPUNIT_ASSERT( bt.exists(k) );
162 : 3520 : CPPUNIT_ASSERT( bt.erase_one(k) );
163 : 3520 : set.erase( set.find(k) );
164 : :
165 : 3520 : CPPUNIT_ASSERT( bt.size() == set.size() );
166 : : }
167 : : }
168 : :
169 : 2 : CPPUNIT_ASSERT( bt.empty() );
170 : 2 : 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 : :
184 [ + - ][ + - ]: 3 : CPPUNIT_TEST_SUITE_REGISTRATION( BoundTest );
|
