1 : /*
2 : * $Id: RangeSearchTreeTest.cc 5866 2005-10-25 21:13:32Z dfs $
3 : *
4 : * Copyright 2003-2005 Daniel F. Savarese
5 : * Copyright 2005 Savarese Software Research
6 : *
7 : * Licensed under the Apache License, Version 2.0 (the "License");
8 : * you may not use this file except in compliance with the License.
9 : * You may obtain a copy of the License at
10 : *
11 : * https://www.savarese.com/software/ApacheLicense-2.0
12 : *
13 : * Unless required by applicable law or agreed to in writing, software
14 : * distributed under the License is distributed on an "AS IS" BASIS,
15 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 : * See the License for the specific language governing permissions and
17 : * limitations under the License.
18 : */
19 :
20 : #include <cstdlib>
21 : #include <list>
22 : #include <set>
23 : #include <algorithm>
24 :
25 : #include <libsava/spatial/KDTree.h>
26 :
27 : #include <cppunit/TestCase.h>
28 : #include <cppunit/extensions/HelperMacros.h>
29 : #include <cppunit/extensions/TestFactoryRegistry.h>
30 : #include <cppunit/TextTestRunner.h>
31 :
32 : using namespace sava::spatial;
33 : using namespace CppUnit;
34 :
35 : template<typename T>
36 : struct TruePred {
37 32768 : bool operator()(const T &) { return true; }
38 : };
39 :
40 : const unsigned int SquareSize = 16;
41 :
42 : template <typename Tree>
43 : class RangeSearchTreeTest : public TestCase {
44 :
45 : typedef TruePred<typename Tree::value_type> True;
46 : typedef std::list<Point<> *> PointList;
47 : typedef std::set<Point<> > PointSet;
48 :
49 : // static inline const unsigned int NumPoints() { return 16; }
50 262160 : static inline const unsigned int NumPoints() { return 16384; }
51 1048580 : static inline const unsigned int MinCoord() { return 0; }
52 524292 : static inline const unsigned int MaxCoord() { return (1 << SquareSize); }
53 :
54 : //static inline const unsigned int MinCoord() { return 8192; }
55 : //static inline const unsigned int MaxCoord() { return 12287; }
56 :
57 : PointList points;
58 :
59 : protected:
60 10 : virtual void fillTree(Tree & tree) {
61 163850 : for(PointList::iterator p = points.begin(); p != points.end(); ++p)
62 163840 : tree[**p] = *p;
63 : }
64 :
65 : public:
66 :
67 16 : RangeSearchTreeTest() {
68 : // ensures no duplicate coordinates
69 16 : PointSet set;
70 :
71 262160 : for(unsigned int i = 0; i < NumPoints(); ++i) {
72 : Point<> *point =
73 : new Point2D<>(MinCoord() + std::rand() % (MaxCoord() - MinCoord()),
74 262144 : MinCoord() + std::rand() % (MaxCoord() - MinCoord()));
75 262144 : std::pair<PointSet::iterator, bool> result = set.insert(*point);
76 :
77 262144 : if(result.second)
78 262144 : points.push_back(point);
79 : else
80 16 : delete point;
81 : }
82 : }
83 :
84 16 : virtual ~RangeSearchTreeTest() {
85 262176 : while(!points.empty()) {
86 262144 : Point<> *point = points.back();
87 262144 : points.pop_back();
88 262160 : delete point;
89 : }
90 16 : }
91 : /*
92 : virtual void setUp() {
93 :
94 : }
95 :
96 : virtual void tearDown() {
97 :
98 : }
99 : */
100 2 : void testBegin() {
101 2 : Tree tree;
102 2 : Point2D<> point(15,17);
103 :
104 2 : CPPUNIT_ASSERT(tree.begin() == tree.end());
105 :
106 4 : tree[point] = &point;
107 :
108 2 : CPPUNIT_ASSERT(tree.begin() != tree.end());
109 :
110 4 : CPPUNIT_ASSERT(tree.begin()->first == point);
111 4 : CPPUNIT_ASSERT(tree.begin()->second == &point);
112 : }
113 :
114 2 : void testSize() {
115 2 : Tree tree;
116 2 : typename Tree::size_type size = typename Tree::size_type();
117 :
118 2 : CPPUNIT_ASSERT(tree.size() == 0);
119 :
120 32770 : for(PointList::iterator p = points.begin(); p != points.end(); ++p) {
121 32768 : if(!tree.insert(**p, *p))
122 32768 : ++size;
123 : }
124 :
125 2 : CPPUNIT_ASSERT(tree.size() == size);
126 4 : CPPUNIT_ASSERT(tree.size() <= tree.max_size());
127 4 : CPPUNIT_ASSERT(tree.empty() == (tree.size() == 0));
128 : }
129 :
130 2 : void testIndexedAccess() {
131 2 : Tree tree;
132 65540 : for(PointList::iterator p = points.begin(); p != points.end(); ++p) {
133 32768 : tree[**p] = *p;
134 32770 : CPPUNIT_ASSERT(tree[**p] == *p);
135 : }
136 : }
137 :
138 2 : void testClear() {
139 2 : Tree tree;
140 :
141 2 : fillTree(tree);
142 :
143 2 : CPPUNIT_ASSERT(tree.size() > 0);
144 :
145 2 : tree.clear();
146 :
147 2 : CPPUNIT_ASSERT(tree.empty());
148 4 : CPPUNIT_ASSERT(tree.size() == 0);
149 : }
150 :
151 : // TODO: Add search of a known subrange
152 2 : void testRangeSearch() {
153 2 : Tree tree;
154 :
155 2 : fillTree(tree);
156 :
157 2 : CPPUNIT_ASSERT(tree.size() ==
158 : (std::count_if<typename Tree::iterator, True>(
159 : tree.begin(Point2D<>(MinCoord(), MinCoord()),
160 : Point2D<>(MaxCoord(), MaxCoord())),
161 : tree.end(), True())));
162 : }
163 :
164 2 : void testFind() {
165 2 : Tree tree;
166 2 : const Tree & constTree = tree;
167 :
168 2 : CPPUNIT_ASSERT(!tree.get(*points.back()));
169 :
170 4 : CPPUNIT_ASSERT(tree.find(*points.back()) == tree.end());
171 :
172 2 : fillTree(tree);
173 :
174 32770 : for(PointList::iterator p = points.begin(); p != points.end(); ++p) {
175 : typename Tree::mapped_type value;
176 :
177 32768 : CPPUNIT_ASSERT(tree.get(**p, &value));
178 65536 : CPPUNIT_ASSERT(value == *p);
179 :
180 32768 : typename Tree::iterator it = tree.find(**p);
181 :
182 32768 : CPPUNIT_ASSERT(it != tree.end());
183 65536 : CPPUNIT_ASSERT(it->first == **p);
184 65536 : CPPUNIT_ASSERT(it->second == *p);
185 :
186 32768 : typename Tree::const_iterator cit = constTree.find(**p);
187 :
188 32768 : CPPUNIT_ASSERT(cit != constTree.end());
189 65536 : CPPUNIT_ASSERT(cit->first == **p);
190 65538 : CPPUNIT_ASSERT(cit->second == *p);
191 : }
192 : }
193 :
194 :
195 2 : void testInsert() {
196 2 : Tree tree;
197 :
198 65540 : for(PointList::iterator p = points.begin(); p != points.end(); ++p) {
199 32768 : tree.insert(**p, *p);
200 32768 : CPPUNIT_ASSERT(tree.get(**p));
201 : }
202 :
203 2 : tree.clear();
204 :
205 32770 : for(PointList::iterator p = points.begin(); p != points.end(); ++p) {
206 32768 : typename Tree::value_type value(**p, *p);
207 32768 : std::pair<typename Tree::iterator,bool> pair = tree.insert(value);
208 :
209 32768 : CPPUNIT_ASSERT(pair.second);
210 65536 : CPPUNIT_ASSERT(tree.get(**p));
211 65536 : CPPUNIT_ASSERT(*(pair.first) == value);
212 : }
213 :
214 : typename Tree::mapped_type original, replaced;
215 :
216 2 : CPPUNIT_ASSERT(tree.get(*points.back(), &original));
217 4 : CPPUNIT_ASSERT(tree.insert(*points.back(), original, &replaced));
218 4 : CPPUNIT_ASSERT(original == replaced);
219 :
220 2 : std::pair<typename Tree::iterator,bool> result;
221 :
222 2 : result = tree.insert(typename Tree::value_type(*points.back(), replaced));
223 4 : CPPUNIT_ASSERT(!result.second);
224 4 : CPPUNIT_ASSERT(result.first->second == replaced);
225 : }
226 :
227 2 : void testErase() {
228 2 : Tree tree;
229 :
230 2 : fillTree(tree);
231 :
232 65540 : for(PointList::iterator p = points.begin(); p != points.end(); ++p) {
233 : typename Tree::mapped_type erased;
234 32768 : CPPUNIT_ASSERT(tree.remove(**p, &erased));
235 65536 : CPPUNIT_ASSERT(erased == *p);
236 : }
237 :
238 2 : CPPUNIT_ASSERT(tree.empty());
239 4 : CPPUNIT_ASSERT(tree.size() == 0);
240 :
241 2 : fillTree(tree);
242 :
243 32770 : for(PointList::iterator p = points.begin(); p != points.end(); ++p)
244 32768 : tree.erase(tree.find(**p));
245 :
246 2 : CPPUNIT_ASSERT(tree.empty());
247 4 : CPPUNIT_ASSERT(tree.size() == 0);
248 :
249 4 : CPPUNIT_ASSERT(tree.erase(*points.back()) == 0);
250 :
251 : }
252 :
253 3 : CPPUNIT_TEST_SUITE(RangeSearchTreeTest<Tree>);
254 1 : CPPUNIT_TEST(testBegin);
255 2 : CPPUNIT_TEST(testSize);
256 2 : CPPUNIT_TEST(testIndexedAccess);
257 2 : CPPUNIT_TEST(testClear);
258 2 : CPPUNIT_TEST(testRangeSearch);
259 2 : CPPUNIT_TEST(testFind);
260 2 : CPPUNIT_TEST(testInsert);
261 2 : CPPUNIT_TEST(testErase);
262 1 : CPPUNIT_TEST_SUITE_END();
263 : };
264 :
265 : template <typename Tree>
266 16 : class OptimizedTreeTest : public RangeSearchTreeTest<Tree> {
267 : protected:
268 : typedef RangeSearchTreeTest<Tree> Super;
269 :
270 5 : virtual void fillTree(Tree & tree) {
271 5 : Super::fillTree(tree);
272 5 : tree.optimize();
273 : }
274 :
275 : public:
276 3 : CPPUNIT_TEST_SUITE(OptimizedTreeTest<Tree>);
277 1 : CPPUNIT_TEST(testBegin);
278 2 : CPPUNIT_TEST(testSize);
279 2 : CPPUNIT_TEST(testIndexedAccess);
280 2 : CPPUNIT_TEST(testClear);
281 2 : CPPUNIT_TEST(testRangeSearch);
282 2 : CPPUNIT_TEST(testFind);
283 2 : CPPUNIT_TEST(testInsert);
284 2 : CPPUNIT_TEST(testErase);
285 1 : CPPUNIT_TEST_SUITE_END();
286 : };
287 :
288 : typedef RangeSearchTreeTest<KDTree<Point<>, Point<>*> > KDTreeTest;
289 : typedef OptimizedTreeTest<KDTree<Point<>, Point<>*> > OptimizedKDTreeTest;
290 :
291 2 : CPPUNIT_TEST_SUITE_REGISTRATION(KDTreeTest);
292 2 : CPPUNIT_TEST_SUITE_REGISTRATION(OptimizedKDTreeTest);
293 :
294 1 : int main(int argc, char **argv) {
295 1 : TextTestRunner runner;
296 1 : TestFactoryRegistry & registry = TestFactoryRegistry::getRegistry();
297 :
298 1 : std::srand(time(NULL));
299 :
300 2 : runner.addTest(registry.makeTest());
301 :
302 1 : return (runner.run() ? 0 : -1);
303 1 : }
|
Sava Algorithms 0.1.1 C++ Unit Test Coverage