Branch data Line data Source code
1 : : /*
2 : : * Copyright 2003-2005 Daniel F. Savarese
3 : : * Copyright 2006-2009 Savarese Software Research Corporation
4 : : *
5 : : * Licensed under the Apache License, Version 2.0 (the "License");
6 : : * you may not use this file except in compliance with the License.
7 : : * You may obtain a copy of the License at
8 : : *
9 : : * https://www.savarese.com/software/ApacheLicense-2.0
10 : : *
11 : : * Unless required by applicable law or agreed to in writing, software
12 : : * distributed under the License is distributed on an "AS IS" BASIS,
13 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : : * See the License for the specific language governing permissions and
15 : : * limitations under the License.
16 : : */
17 : :
18 : : /**
19 : : * @file
20 : : * This header defines the kd_tree class and its support classes.
21 : : */
22 : :
23 : : #ifndef __SSRC_SPATIAL_KDTREE_H
24 : : #define __SSRC_SPATIAL_KDTREE_H
25 : :
26 : : #include <ssrc/spatial/detail/kd_tree_range_search_iterator.h>
27 : : #include <ssrc/spatial/detail/kd_tree_node.h>
28 : : #include <ssrc/spatial/detail/kd_tree_nearest_neighbor.h>
29 : :
30 : : #ifdef LIBSSRCKDTREE_HAVE_BOOST
31 : : #include <ssrc/spatial/detail/kd_tree_nearest_neighbors.h>
32 : : #endif
33 : :
34 : : #include <ssrc/spatial/rectangle_region.h>
35 : :
36 : : #include <algorithm>
37 : : #include <utility>
38 : : #include <vector>
39 : :
40 : : __BEGIN_NS_SSRC_SPATIAL
41 : :
42 : : /**
43 : : * kd_tree_traits stores metadata about kd_tree instances.
44 : : */
45 : : template<typename Tree>
46 : : struct kd_tree_traits {
47 : : typedef typename Tree::key_type key_type;
48 : : typedef typename Tree::mapped_type mapped_type;
49 : : typedef typename Tree::value_type value_type;
50 : : typedef typename Tree::pointer pointer;
51 : : typedef typename Tree::const_pointer const_pointer;
52 : : typedef typename Tree::reference reference;
53 : : typedef typename Tree::const_reference const_reference;
54 : : typedef typename Tree::discriminator_type discriminator_type;
55 : : typedef typename Tree::node_type node_type;
56 : : typedef typename Tree::iterator iterator;
57 : : typedef typename Tree::const_iterator const_iterator;
58 : : typedef typename Tree::size_type size_type;
59 : : typedef typename key_type::value_type coordinate_type;
60 : : typedef Tree tree_type;
61 : :
62 : : /**
63 : : * Returns the maximum value a coordinate may assume.
64 : : *
65 : : * @return The maximum value a coordinate may assume.
66 : : */
67 : 3 : static const coordinate_type max_coordinate() {
68 : 3 : return detail::coordinate_limits<coordinate_type>::highest();
69 : : }
70 : :
71 : : /**
72 : : * Returns the minimum value a coordinate may assume.
73 : : *
74 : : * @return The minimum value a coordinate may assume.
75 : : */
76 : 3 : static const coordinate_type min_coordinate() {
77 : 3 : return detail::coordinate_limits<coordinate_type>::lowest();
78 : : }
79 : :
80 : : /** The highest possible key value. */
81 : : static const key_type upper_bound;
82 : :
83 : : /** The lowest possible key value. */
84 : : static const key_type lower_bound;
85 : :
86 : : /** The number of dimensions of a key. */
87 : : static const unsigned int dimensions = NS_TR1::tuple_size<key_type>::value;
88 : :
89 : : private:
90 : 6 : static key_type init_point(const coordinate_type & value) {
91 : : key_type point;
92 [ + + ][ + + ]: 18 : for(unsigned int i=0; i < dimensions; ++i)
[ + + ]
93 : 12 : point[i] = value;
94 : 6 : return point;
95 : : }
96 : :
97 : 3 : static const key_type _upper_bound() {
98 : 3 : return init_point(max_coordinate());
99 : : }
100 : :
101 : 3 : static const key_type _lower_bound() {
102 : 3 : return init_point(min_coordinate());
103 : : }
104 : : };
105 : :
106 : : template<class Tree>
107 : : typename kd_tree_traits<Tree>::key_type const
108 [ + - ][ + - ]: 3 : kd_tree_traits<Tree>::upper_bound(kd_tree_traits<Tree>::_upper_bound());
[ + - ]
109 : :
110 : : template<class Tree>
111 : : typename kd_tree_traits<Tree>::key_type const
112 [ + - ][ + - ]: 3 : kd_tree_traits<Tree>::lower_bound(kd_tree_traits<Tree>::_lower_bound());
[ + - ][ - + ]
[ # # ]
113 : :
114 : : /**
115 : : * kd_tree_const_traits stores metadata about const kd_tree instances.
116 : : */
117 : : template<typename Tree>
118 : : struct kd_tree_const_traits : public kd_tree_traits<Tree> {
119 : : typedef typename Tree::const_pointer pointer;
120 : : typedef typename Tree::const_reference reference;
121 : : };
122 : :
123 : :
124 : : // Note: we store the discriminator in each node to avoid modulo division,
125 : : // trading space for time.
126 : : /**
127 : : * A k-d tree divides a k-dimensional space relative to the points it
128 : : * contains by storing them in a binary tree, discriminating by a
129 : : * different dimension at each level of the tree. It allows efficient
130 : : * point data retrieval (<em>O(lg(n))</em>) and range searching.
131 : : *
132 : : * <p>kd_tree tries to conform to the map interface from the STL where
133 : : * it makes sense. Therefore, you will find it can be used with some
134 : : * STL algorithms.</p>
135 : : */
136 : : template<typename Point,
137 : : typename Value,
138 : : typename Discriminator = unsigned char,
139 : : typename Size = unsigned int>
140 : : class kd_tree {
141 : : public:
142 : :
143 : : typedef kd_tree_traits<kd_tree> traits;
144 : : typedef kd_tree_const_traits<kd_tree> const_traits;
145 : : typedef Point key_type;
146 : : typedef Value mapped_type;
147 : : typedef std::pair<const key_type, mapped_type> value_type;
148 : : typedef value_type* pointer;
149 : : typedef pointer const const_pointer;
150 : : typedef value_type& reference;
151 : : typedef const reference const_reference;
152 : : typedef Discriminator discriminator_type;
153 : : typedef rectangle_region<key_type> default_region_type;
154 : : // Is this really what we want--two distinct types as
155 : : // opposed to iterator and const iterator?
156 : : typedef
157 : : detail::kd_tree_range_search_iterator<traits, default_region_type> iterator;
158 : : typedef
159 : : detail::kd_tree_range_search_iterator<const_traits, default_region_type>
160 : : const_iterator;
161 : :
162 : : typedef Size size_type;
163 : :
164 : : typedef detail::kd_tree_node<traits> node_type;
165 : :
166 : : private:
167 : :
168 : : struct node_comparator {
169 : : mutable discriminator_type discriminator;
170 : :
171 : 21 : explicit node_comparator() : discriminator(0) { }
172 : :
173 : 33267969 : bool operator()(const node_type* const & n1,
174 : : const node_type* const & n2) const
175 : : {
176 : 33267969 : return (n1->point()[discriminator] < n2->point()[discriminator]);
177 : : }
178 : : };
179 : :
180 : : node_type *_root;
181 : : size_type _size;
182 : : iterator _end_iterator;
183 : : const_iterator _const_end_iterator;
184 : :
185 : : node_type *
186 : 1917110 : get_node(const key_type & point, node_type ** const parent = 0) const {
187 : : discriminator_type discriminator;
188 : 1917110 : node_type *node = _root, *last = 0;
189 : :
190 [ + + ][ + + ]: 32481499 : while(node != 0) {
[ + + ]
191 : 31301806 : discriminator = node->discriminator;
192 : :
193 [ + + ][ + + ]: 31301806 : if(point[discriminator] > node->point()[discriminator]) {
[ + + ]
194 : 14953399 : last = node;
195 : 14953399 : node = node->child_high;
196 [ + + ][ + + ]: 16348407 : } else if(point[discriminator] < node->point()[discriminator]) {
[ + + ]
197 : 15596289 : last = node;
198 : 15596289 : node = node->child_low;
199 [ + + ][ + + ]: 752118 : } else if(node->point() == point) {
[ + + ]
200 [ + + ][ + + ]: 737417 : if(parent != 0)
[ + + ]
201 : 393350 : *parent = last;
202 : 737417 : return node;
203 : : } else {
204 : 14701 : last = node;
205 : 14701 : node = node->child_high;
206 : : }
207 : : }
208 : :
209 [ + + ][ + + ]: 1179693 : if(parent != 0)
[ + + ]
210 : 1179687 : *parent = last;
211 : :
212 : 1917110 : return 0;
213 : : }
214 : :
215 : 5798157 : node_type * get_minimum_node(node_type * const node, node_type * const p,
216 : : const discriminator_type discriminator,
217 : : node_type ** const parent)
218 : : {
219 : : node_type *result;
220 : :
221 [ + + ][ + + ]: 5798157 : if(discriminator == node->discriminator) {
[ + + ]
222 [ + + ][ + + ]: 3442717 : if(node->child_low != 0)
[ + + ]
223 : : return
224 : : get_minimum_node(node->child_low, node,
225 : 1634435 : discriminator, parent);
226 : : else
227 : 1808282 : result = node;
228 : : } else {
229 : 2355440 : node_type *nlow = 0, *nhigh = 0;
230 : : node_type *plow, *phigh;
231 : :
232 [ + + ][ + + ]: 2355440 : if(node->child_low != 0)
[ + + ]
233 : 1679175 : nlow = get_minimum_node(node->child_low, node,
234 : : discriminator, &plow);
235 : :
236 [ + + ][ + + ]: 2355440 : if(node->child_high != 0)
[ + + ]
237 : 1763542 : nhigh = get_minimum_node(node->child_high, node,
238 : : discriminator, &phigh);
239 : :
240 [ + + ][ + + ]: 2355440 : if(nlow != 0 && nhigh != 0) {
[ + + ][ + + ]
[ + + ][ + + ]
241 [ + + ][ + + ]: 3038174 : if(nlow->point()[discriminator] < nhigh->point()[discriminator]) {
[ + + ]
242 : 772614 : result = nlow;
243 : 772614 : *parent = plow;
244 : : } else {
245 : 746473 : result = nhigh;
246 : 746473 : *parent = phigh;
247 : : }
248 [ + + ][ + + ]: 836353 : } else if(nlow != 0) {
[ + + ]
249 : 160088 : result = nlow;
250 : 160088 : *parent = plow;
251 [ + + ][ + + ]: 676265 : } else if(nhigh != 0) {
[ + + ]
252 : 244455 : result = nhigh;
253 : 244455 : *parent = phigh;
254 : : } else
255 : 431810 : result = node;
256 : : }
257 : :
258 [ + + ][ + + ]: 4163722 : if(result == node)
[ + + ]
259 : 2240092 : *parent = p;
260 [ + + ][ + + ]: 1923630 : else if(node->point()[discriminator] < result->point()[discriminator]) {
[ + + ]
261 : 229153 : result = node;
262 : 229153 : *parent = p;
263 : : }
264 : :
265 : 5798157 : return result;
266 : : }
267 : :
268 : 1065197 : node_type * recursive_remove_node(node_type * const node) {
269 : : discriminator_type discriminator;
270 : : node_type *new_root, *parent;
271 : :
272 [ + + ][ + + ]: 1065197 : if(node->child_low == 0 &&
[ + + ][ + + ]
[ + + ][ + + ]
273 : : node->child_high == 0)
274 : 344192 : return 0;
275 : : else
276 : 721005 : discriminator = node->discriminator;
277 : :
278 [ + + ][ + + ]: 721005 : if(node->child_high == 0) {
[ + + ]
279 : 55049 : node->child_high = node->child_low;
280 : 55049 : node->child_low = 0;
281 : : }
282 : :
283 : 721005 : new_root = get_minimum_node(node->child_high, node,
284 : : discriminator, &parent);
285 : :
286 [ + + + + : 721005 : if(parent->child_low == new_root)
+ + ]
287 : 297204 : parent->child_low = recursive_remove_node(new_root);
288 : : else
289 : 423801 : parent->child_high = recursive_remove_node(new_root);
290 : :
291 : 721005 : new_root->child_low = node->child_low;
292 : 721005 : new_root->child_high = node->child_high;
293 : 721005 : new_root->discriminator = node->discriminator;
294 : :
295 : 1065197 : return new_root;
296 : : }
297 : :
298 : : // Splitting up remove in this way allows us to implement
299 : : // iterator erase(iterator) properly.
300 : 344192 : bool remove(node_type * const node, node_type * const parent) {
301 : 344192 : node_type * const new_root = recursive_remove_node(node);
302 : :
303 [ + + + + : 344192 : if(parent == 0)
+ + ]
304 : 98426 : _root = new_root;
305 [ + + ][ + + ]: 245766 : else if(node == parent->child_low)
[ + + ]
306 : 118186 : parent->child_low = new_root;
307 : : else
308 : 127580 : parent->child_high = new_root;
309 : :
310 : : // Must zero children so they are not deleted by ~node_type()
311 : 344192 : node->child_low = 0;
312 : 344192 : node->child_high = 0;
313 : :
314 : 344192 : --_size;
315 [ + - ][ + - ]: 344192 : delete node;
[ + - ]
316 : :
317 : 344192 : return true;
318 : : }
319 : :
320 : 1179687 : bool add(const key_type & point, const mapped_type & value,
321 : : node_type ** const node, node_type *parent,
322 : : mapped_type * const replaced = 0)
323 : : {
324 [ + + ][ + + ]: 1179687 : if(parent == 0) {
[ + + ]
325 [ - + ][ - + ]: 83 : if(_root != 0)
[ - + ]
326 : 0 : *node = _root;
327 : : else {
328 : 83 : _root = *node = new node_type(0, point, value);
329 : 83 : ++_size;
330 : 83 : return false;
331 : : }
332 [ + + ][ + + ]: 1179604 : } else if(*node == 0) {
[ + + ]
333 : 1179598 : discriminator_type discriminator = parent->discriminator;
334 : : node_type* & child =
335 : : (point[discriminator] >= parent->point()[discriminator] ?
336 [ + + ][ + + ]: 1179598 : parent->child_high : parent->child_low);
[ + + ]
337 : :
338 [ + + ][ + + ]: 1179598 : if(++discriminator >= traits::dimensions)
[ + + ]
339 : 588685 : discriminator = 0;
340 : :
341 : 1179598 : child = *node = new node_type(discriminator, point, value);
342 : :
343 : 1179598 : ++_size;
344 : 1179598 : return false;
345 : : }
346 : :
347 [ + - ][ + - ]: 6 : if(replaced != 0)
[ + - ]
348 : 6 : *replaced = (*node)->value();
349 : :
350 : 6 : (*node)->value() = value;
351 : :
352 : 1179687 : return true;
353 : : }
354 : :
355 : : template<typename container_iterator>
356 : 345807 : static node_type * optimize(const container_iterator & begin,
357 : : const container_iterator & end,
358 : : const node_comparator & comparator)
359 : : {
360 : 345807 : node_type *midpoint = 0;
361 : : typename container_iterator::difference_type diff;
362 : :
363 : 345807 : diff = end - begin;
364 : :
365 [ + + + + : 345807 : if(diff > 1) {
+ + ]
366 : 172893 : discriminator_type discriminator = comparator.discriminator;
367 : 172893 : container_iterator nth = begin + (diff >> 1);
368 : 172893 : container_iterator nthprev = nth - 1;
369 : :
370 : : //std::nth_element(begin, nth, end, comparator);
371 : 172893 : std::stable_sort(begin, end, comparator);
372 : :
373 : : // Ties go in the right subtree.
374 [ + + ][ + + ]: 173796 : while(nth > begin &&
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
375 : : (*nth)->point()[discriminator] ==
376 : : (*nthprev)->point()[discriminator])
377 : : {
378 : 903 : --nth;
379 : 903 : --nthprev;
380 : : }
381 : :
382 : 172893 : midpoint = *nth;
383 : 172893 : midpoint->discriminator = discriminator;
384 : :
385 [ + + + + : 172893 : if(++discriminator >= traits::dimensions)
+ + ]
386 : 58212 : discriminator = 0;
387 : :
388 : 172893 : comparator.discriminator = discriminator;
389 : :
390 : : // Left subtree
391 : 172893 : midpoint->child_low = optimize(begin, nth, comparator);
392 : :
393 : 172893 : comparator.discriminator = discriminator;
394 : :
395 : : // Right subtree
396 : 172893 : midpoint->child_high = optimize(nth + 1, end, comparator);
397 [ + + ][ + + ]: 172914 : } else if(diff == 1) {
[ + + ]
398 : 171171 : midpoint = *begin;
399 : 171171 : midpoint->discriminator = comparator.discriminator;
400 : 171171 : midpoint->child_low = 0;
401 : 171171 : midpoint->child_high = 0;
402 : : }
403 : :
404 : 345807 : return midpoint;
405 : : }
406 : :
407 : : template<class container>
408 : 688149 : static void fill_container(container & c, node_type * const node) {
409 [ + + ][ + + ]: 688149 : if(node == 0)
[ + + ]
410 : 688149 : return;
411 : 344064 : c.push_back(node);
412 : 344064 : fill_container(c, node->child_low);
413 : 344064 : fill_container(c, node->child_high);
414 : : }
415 : :
416 : : public:
417 : :
418 : : /**
419 : : * Constructs an empty kd_tree.
420 : : */
421 : 48 : explicit kd_tree() :
422 [ + - ][ + - ]: 48 : _root(0), _size(0), _end_iterator(), _const_end_iterator()
[ + - ]
423 : 48 : { }
424 : :
425 : : /**
426 : : * Constructs a copy of a kd_tree.
427 : : *
428 : : * @param tree The kd_tree to copy.
429 : : */
430 : 3 : kd_tree(const kd_tree & tree) :
431 [ + - ][ + - ]: 3 : _root(0), _size(0), _end_iterator(), _const_end_iterator()
[ + - ]
432 : : {
433 [ + - ][ + - ]: 49155 : for(const_iterator p = tree.begin(); !p.end_of_range(); ++p)
[ + + ][ + - ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + + ][ + - ]
434 [ + - ][ + - ]: 49152 : insert(p->first, p->second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
435 : 3 : }
436 : :
437 : : /**
438 : : * Deallocates the memory allocated by the kd_tree.
439 : : */
440 [ + + ][ + - ]: 51 : virtual ~kd_tree() { delete _root; }
[ + - ][ - + ]
[ + + ][ + - ]
[ + - ][ - + ]
[ + + ][ + - ]
[ + - ][ - + ]
441 : :
442 : : /**
443 : : * Removes all elements from the container, leaving it empty.
444 : : */
445 : 26 : void clear() {
446 [ + - ][ + - ]: 26 : delete _root;
[ + - ]
447 : 26 : _root = 0;
448 : 26 : _size = 0;
449 : 26 : }
450 : :
451 : : /**
452 : : * Copies the contents of a kd_tree, destroying all existing
453 : : * values.
454 : : *
455 : : * @param tree The kd_tree to copy.
456 : : * @return *this
457 : : */
458 : 3 : kd_tree & operator=(const kd_tree & tree) {
459 : 3 : clear();
460 [ + - ][ + + ]: 49155 : for(const_iterator p = tree.begin(); !p.end_of_range(); ++p)
[ + - ][ + + ]
[ + - ][ + + ]
461 [ + - ][ + - ]: 49152 : insert(p->first, p->second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
462 : 3 : return *this;
463 : : }
464 : :
465 : : /**
466 : : * Returns the number of point-value mappings in the kd_tree.
467 : : *
468 : : * @return The number of point-value mappings in the kd_tree.
469 : : */
470 : 114 : const size_type size() const {
471 : 114 : return _size;
472 : : }
473 : :
474 : : /**
475 : : * Returns the maximum number of elements that can be contained.
476 : : *
477 : : * @return The maximum number of elements that can be contained.
478 : : */
479 : 3 : const size_type max_size() const {
480 : 3 : return std::numeric_limits<size_type>::max();
481 : : }
482 : :
483 : : /**
484 : : * Returns true if the container has no elements, false if it
485 : : * contains one or more elements.
486 : : *
487 : : * @return true if the container has no elements, false if it
488 : : * contains one or more elements.
489 : : */
490 : 48 : bool empty() const {
491 : 48 : return (_root == 0);
492 : : }
493 : :
494 : : /**
495 : : * Returns an iterator pointing to the leftmost bottommost point in
496 : : * the container. If empty, it equals end().
497 : : *
498 : : * @return An iterator pointing to the leftmost bottommost point in
499 : : * the container. If empty, it equals end().
500 : : */
501 : 27 : iterator begin() {
502 : 27 : return iterator(default_region_type(traits::lower_bound, traits::upper_bound), _root);
503 : : }
504 : :
505 : : /**
506 : : * Returns a const iterator pointing to the leftmost bottommost point in
507 : : * the container. If empty, it equals end().
508 : : *
509 : : * @return A const iterator pointing to the leftmost bottommost point in
510 : : * the container. If empty, it equals end().
511 : : */
512 : 15 : const_iterator begin() const {
513 : 15 : return const_iterator(default_region_type(traits::lower_bound, traits::upper_bound), _root);
514 : : }
515 : :
516 : : /**
517 : : * Returns an iterator denoting the end of a range.
518 : : *
519 : : * @return An iterator denoting the end of a range.
520 : : */
521 : 294968 : iterator & end() {
522 : 294968 : return _end_iterator;
523 : : }
524 : :
525 : : /**
526 : : * Returns a const iterator denoting the end of a range.
527 : : *
528 : : * @return A const iterator denoting the end of a range.
529 : : */
530 : 98304 : const const_iterator & end() const {
531 : 98304 : return _const_end_iterator;
532 : : }
533 : :
534 : : /**
535 : : * Inserts a key value pair, replacing any existing value that may
536 : : * be present, and optionally retrieving the replaced value.
537 : : *
538 : : * @param point The key corresponding to the value to be inserted
539 : : * @param value The value to be inserted.
540 : : * @param replaced If you want to retrieve a value that was
541 : : * replaced, have this parameter point to a valid object to store
542 : : * the value. If not, its default value of zero will prevent it
543 : : * from being retrieved.
544 : : * @return true if value is replaced, false if not.
545 : : */
546 : 294948 : bool insert(const key_type & point, const mapped_type & value,
547 : : mapped_type * const replaced = 0)
548 : : {
549 : : node_type *parent;
550 : 294948 : node_type *node = get_node(point, &parent);
551 : :
552 : 294948 : return add(point, value, &node, parent, replaced);
553 : : }
554 : :
555 : : /**
556 : : * Inserts a key value pair, but--in conformance with the STL
557 : : * container interface--doesn't replace any existing value that may
558 : : * be present. Note, this method is slower than
559 : : * bool insert(const key_type &, const mapped_type, mapped_type*)
560 : : *
561 : : * @return A pair containing the iterator pointing to the inserted
562 : : * value and true if the mapping is inserted. If the value is not
563 : : * inserted, a pair containing the iterator pointing to the existing
564 : : * value and false.
565 : : */
566 : 49155 : std::pair<iterator,bool> insert(const value_type & mapping) {
567 : : // Ideally, we'd do this all in one step, but that will have
568 : : // to wait until we optimize the way we handle iterators.
569 : : mapped_type existing;
570 : 49155 : const bool replaced = insert(mapping.first, mapping.second, &existing);
571 : 98310 : const iterator value = find(mapping.first);
572 : :
573 [ + + + + : 49155 : if(replaced)
+ + ]
574 : 3 : value._node->value() = existing;
575 : :
576 [ + - ][ + - ]: 98310 : return std::pair<iterator,bool>(value,!replaced);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
577 : : }
578 : :
579 : :
580 : : /**
581 : : * Retrieves the value at the given location. In conformance with
582 : : * the STL map interface, if the point key does not occur in the
583 : : * kd_tree, a new value is inserted and returned using the default
584 : : * constructor for kd_tree::mapped_type.
585 : : *
586 : : * @param point The location from which to retrieve the value.
587 : : * @return The value at the given location.
588 : : */
589 : 933891 : mapped_type & operator[](const key_type & point) {
590 : : node_type *parent;
591 : 933891 : node_type *node = get_node(point, &parent);
592 : :
593 [ + + + + : 933891 : if(node == 0)
+ + ]
594 : 884739 : add(point, mapped_type(), &node, parent);
595 : :
596 : 933891 : return node->value();
597 : : }
598 : :
599 : : /**
600 : : * Removes the point-value mapping corresponding to the given point key.
601 : : * Optionally, retrieves the removed value if a mapping was present.
602 : : *
603 : : * @param point The point key of the mapping to remove.
604 : : * @param erased A pointer to a mapped_type in which to store the
605 : : * erased value. This pointer may be null if you do not want to
606 : : * retrieve the removed value and only want to remove the mapping.
607 : : * @return true if a mapping was present and removed, false if not.
608 : : */
609 : 98313 : bool remove(const key_type & point, mapped_type * const erased = 0) {
610 : : node_type *parent;
611 : 98313 : node_type * const node = get_node(point, &parent);
612 : :
613 [ + + + + : 98313 : if(node == 0)
+ + ]
614 : 6 : return false;
615 : :
616 [ + + ][ + + ]: 98307 : if(erased != 0)
[ + + ]
617 : 98304 : *erased = node->value();
618 : :
619 : 98313 : return remove(node, parent);
620 : : }
621 : :
622 : : /**
623 : : * Removes the point-value mapping corresponding to the given point key.
624 : : *
625 : : * @param point The point key of the mapping to remove.
626 : : * @return The number of mappings erased (0 or 1).
627 : : */
628 : 9 : size_type erase(const key_type & point) {
629 : 9 : return remove(point);
630 : : }
631 : :
632 : : /**
633 : : * Removes the point-value mapping at the specified position. The
634 : : * supplied iterator becomes invalid upon a successful erasure.
635 : : *
636 : : * @param pos The kd_tree::iterator denoting the location of the mapping.
637 : : * @return An iterator pointing to the next element after pos in the
638 : : * range search sequence containing pos. If no such element exists,
639 : : * or if the element pointed to by pos is not contained in the tree
640 : : * (making it impossible to remove from the tree), end() is returned.
641 : : */
642 : 245885 : iterator erase(iterator pos) {
643 [ - + ][ - + ]: 245885 : if(pos.end_of_range())
[ - + ]
644 : 0 : return _end_iterator;
645 : :
646 : : node_type *parent;
647 : 245885 : node_type * const node = get_node(pos->first, &parent);
648 : :
649 [ - + - + : 245885 : if(node == 0)
- + ]
650 : 0 : return _end_iterator;
651 : :
652 : 245885 : typename iterator::stack_type & stack = pos._stack;
653 : :
654 : : // Pop any children. Tree at parent and above is unchanged.
655 : : // Low child is pushed last so check it first.
656 [ + + ][ + + ]: 245885 : if(!stack.empty() && node->child_low == stack.top()) {
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
657 : 55931 : stack.pop();
658 : : }
659 [ + + ][ + + ]: 245885 : if(!stack.empty() && node->child_high == stack.top()) {
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ]
660 : 187908 : stack.pop();
661 : : }
662 : :
663 [ + + ][ + + ]: 245885 : const bool low_child = (parent != 0 && parent->child_low == node);
[ + + ][ + + ]
[ + + ][ + + ]
664 : :
665 [ + - ][ + - ]: 245885 : if(remove(node, parent)) {
[ + - ]
666 [ + + ][ + + ]: 245885 : if(parent != 0) {
[ + + ]
667 [ + + ][ + + ]: 147516 : if(low_child && parent->child_low != 0) {
[ + + ][ + + ]
[ + + ][ + + ]
668 : 52198 : stack.push(parent->child_low);
669 [ + + ][ + + ]: 95318 : } else if(!low_child && parent->child_high != 0) {
[ + + ][ + + ]
[ + + ][ + + ]
670 : 55467 : stack.push(parent->child_high);
671 : : }
672 : 147516 : pos.advance();
673 : 147516 : return pos;
674 [ + + ][ + + ]: 98369 : } else if(_root != 0) {
[ + + ]
675 : 98357 : stack.push(_root);
676 : 98357 : pos.advance();
677 : 98357 : return pos;
678 : : }
679 : : }
680 : :
681 : 245885 : return _end_iterator;
682 : : }
683 : :
684 : : /**
685 : : * Returns an iterator for mappings that are contained in the
686 : : * rectangle defined by the given lower left-hand and upper
687 : : * right-hand corners. The mappings returned include those occuring
688 : : * at points on the bounding rectangle, not just those inside.
689 : : *
690 : : * @param lower The lower left-hand corner of the bounding
691 : : * rectangle.
692 : : * @param upper The upper right-hand corner of the bounding
693 : : * rectangle.
694 : : * @return A kd_tree::iterator for mappings that are contained in the
695 : : * specified rectangle.
696 : : */
697 : 6 : iterator begin(const key_type & lower, const key_type & upper) {
698 : 6 : return iterator(default_region_type(lower, upper), _root);
699 : : }
700 : :
701 : : /**
702 : : * Returns a const iterator for mappings that are contained in the
703 : : * rectangle defined by the given lower left-hand and upper
704 : : * right-hand corners. The mappings returned include those occuring
705 : : * at points on the bounding rectangle, not just those inside.
706 : : *
707 : : * @param lower The lower left-hand corner of the bounding
708 : : * rectangle.
709 : : * @param upper The upper right-hand corner of the bounding
710 : : * rectangle.
711 : : * @return A kd_tree::const_iterator for mappings that are contained in the
712 : : * specified rectangle.
713 : : */
714 : : const_iterator begin(const key_type & lower, const key_type & upper) const {
715 : : return const_iterator(default_region_type(lower, upper), _root);
716 : : }
717 : :
718 : : // TODO: Document these. Implement circle_region and sphere_region
719 : : // and write unit tests. Move kd_tree_range_search_iterator out of detail.
720 : : template<typename Region>
721 : : detail::kd_tree_range_search_iterator<traits, Region>
722 : : begin(const Region & region) {
723 : : return
724 : : detail::kd_tree_range_search_iterator<traits, Region>(region, _root);
725 : : }
726 : :
727 : : template<typename Region>
728 : : detail::kd_tree_range_search_iterator<traits, Region> end() {
729 : : return detail::kd_tree_range_search_iterator<traits, Region>();
730 : : }
731 : :
732 : : template<typename Region>
733 : : detail::kd_tree_range_search_iterator<const_traits, Region>
734 : : begin(const Region & region) const {
735 : : return
736 : : detail::kd_tree_range_search_iterator<const_traits, Region>(region, _root);
737 : : }
738 : :
739 : : template<typename Region>
740 : : detail::kd_tree_range_search_iterator<const_traits, Region> end() const {
741 : : return detail::kd_tree_range_search_iterator<const_traits, Region>();
742 : : }
743 : :
744 : : /**
745 : : * Returns true if the kd_tree contains a point-value mapping for the
746 : : * specified point, false if not. Optionally, retrieves the value
747 : : * at the given location (faster than find()).
748 : : *
749 : : * @param point The location from which to retrieve the value.
750 : : * @param value A pointer to a kd_tree::mapped_type in which to store the
751 : : * retrieved value. This pointer may be null if you do not want to
752 : : * retrieve the value and only want to see if the point is present in
753 : : * the kd_tree.
754 : : * @return true if the kd_tree contains a point-value mapping for the
755 : : * specified point, false if not.
756 : : */
757 : 344073 : bool get(const key_type & point, mapped_type * const value = 0) const {
758 : 344073 : const node_type * const node = get_node(point);
759 : :
760 [ + + + + : 344073 : if(node == 0)
+ + ]
761 : 6 : return false;
762 [ + + ][ + + ]: 344067 : else if(value != 0)
[ + + ]
763 : 245763 : *value = node->value();
764 : :
765 : 344073 : return true;
766 : : }
767 : :
768 : : /**
769 : : * Returns the location of the point-value mapping for the specified
770 : : * point (slower than get()). If there is no mapping present, the
771 : : * iterator is equivalent to end().
772 : : *
773 : : * @param point The key of the poinit-value mapping to find.
774 : : * @return A kd_tree::iterator for the location of the
775 : : * point-value mapping matching the specified point. end() if there
776 : : * is no mapping.
777 : : */
778 : 245769 : iterator find(const key_type & point) {
779 : 245769 : return iterator(default_region_type(point, traits::upper_bound), _root, true);
780 : : }
781 : :
782 : : /**
783 : : * Returns the location of the point-value mapping for the specified
784 : : * point (slower than get()). If there is no mapping present, the
785 : : * iterator is equivalent to end().
786 : : *
787 : : * @param point The key of the poinit-value mapping to find.
788 : : * @return A kd_tree::const_iterator for the location of the
789 : : * point-value mapping matching the specified point. end() if there
790 : : * is no mapping.
791 : : */
792 : 98304 : const_iterator find(const key_type & point) const {
793 : : return const_iterator(default_region_type(point, traits::upper_bound),
794 : 98304 : _root, true);
795 : : }
796 : :
797 : : /**
798 : : * Optimizes the performance of future search operations by balancing the
799 : : * kd_tree. The balancing operation is relatively expensive, but can
800 : : * significantly improve the performance of searches. Usually, you
801 : : * don't have to optimize a tree which contains random key values
802 : : * inserted in a random order.
803 : : */
804 : 21 : void optimize() {
805 [ - + ][ - + ]: 21 : if(empty())
[ - + ]
806 : 21 : return;
807 : :
808 : : typedef std::vector<node_type*> container;
809 : 42 : container nodes;
810 : :
811 [ + - + - : 21 : nodes.reserve(size());
+ - ]
812 [ + - ][ + - ]: 21 : fill_container(nodes, _root);
[ + - ]
813 : :
814 [ + - ][ + - ]: 21 : _root = optimize(nodes.begin(), nodes.end(), node_comparator());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
815 : : }
816 : :
817 : : /**
818 : : * Tests if two kd_tree instances contain exactly the same key-value
819 : : * pairs, but not necessarily in the same hierarchical arrangement.
820 : : * Note, this is an expensive operation that we don't expect will ever
821 : : * be used except in support of unit tests.
822 : : *
823 : : * Use namespace std::rel_ops from <utility> to gain the != operator.
824 : : *
825 : : * @param tree1 The first tree to compare.
826 : : * @param tree2 The second tree to compare.
827 : : * @return true if the two trees are equal, false if not.
828 : : */
829 : 15 : friend bool operator==(const kd_tree & tree1, const kd_tree & tree2) {
830 [ + + ][ + + ]: 15 : if(tree1.size() != tree2.size())
[ + + ]
831 : 6 : return false;
832 : :
833 : : mapped_type value;
834 : :
835 [ + - ][ + + ]: 147465 : for(const_iterator p = tree2.begin(); !p.end_of_range(); ++p) {
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ]
836 [ + - ][ + - ]: 147456 : if(!tree1.get(p->first, &value) || value != p->second)
[ + - ][ + - ]
[ - + ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ - + ]
837 : 0 : return false;
838 : : }
839 : :
840 : 15 : return true;
841 : : }
842 : :
843 : : // Experimental functions whose API may change or may become standalone
844 : : // functions or functor classes.
845 : :
846 : : /**
847 : : * Returns the location of the point-value mapping closest to the
848 : : * specified point in Euclidean space where the Euclidean distance
849 : : * between the points is non-zero (unless omit_query_point is set to
850 : : * false). If there is more than one mapping at the same closest
851 : : * distance, one of the mappings will be returned, but which mapping
852 : : * is returned is unspecified.
853 : : *
854 : : * Note, this implementation is efficient for low dimensionalities.
855 : : * High-dimensional data is better served by an approximation algorithm.
856 : : * An approximation algorithm for high-dimensional data will be provided
857 : : * in a future release after a satisfactory refactoring is achieved to
858 : : * separate specialized search algorithms from the kd_tree class template.
859 : : *
860 : : * @param point The nearest neighbor query point.
861 : : * @param omit_query_point If true, mappings at a distance of zero are
862 : : * omitted from the result. If false, mappings at a distance of
863 : : * zero are included. The default value of this parameter is
864 : : * true because our most common usage is to search for neighbors
865 : : * of points already contained in the tree.
866 : : * @return A kd_tree::iterator for the location of the point-value
867 : : * mapping closest to the query point. end() if there is no such
868 : : * mapping (e.g., the tree is empty).
869 : : */
870 : 23 : iterator find_nearest_neighbor(const key_type & point,
871 : : const bool omit_query_point = true)
872 : : {
873 : 23 : const detail::kd_tree_nearest_neighbor<traits, double> nn;
874 : 23 : return iterator(nn.find(_root, point, omit_query_point));
875 : : }
876 : :
877 : : #ifdef LIBSSRCKDTREE_HAVE_BOOST
878 : : typedef
879 : : typename detail::kd_tree_nearest_neighbors<traits, double>::iterator
880 : : knn_iterator;
881 : :
882 : : /**
883 : : * Returns the k-nearest neighbors to a query point as a pair of
884 : : * iterators that traverse the point-value mappings in order from
885 : : * closest to farthest.
886 : : *
887 : : * @param point The nearest neighbor query point.
888 : : * @param num_neighbors The number of neighbors to return.
889 : : * @param omit_query_point If true, mappings at a distance of zero are
890 : : * omitted from the result. If false, mappings at a distance of
891 : : * zero are included. The default value of this parameter is
892 : : * true because our most common usage is to search for neighbors
893 : : * of points already contained in the tree.
894 : : * @return A std::pair of kd_tree::knn_iterator instances that can
895 : : * be traversed to access the nearest neighbor point-value mappings
896 : : * in order from closest to farthest. The first iterator marks the
897 : : * beginning of the range and and the second iterator bounds the
898 : : * end of the range.
899 : : */
900 : : std::pair<knn_iterator, knn_iterator>
901 : 82 : find_nearest_neighbors(const key_type & point,
902 : : const unsigned int num_neighbors,
903 : : const bool omit_query_point = true)
904 : : {
905 : 82 : const detail::kd_tree_nearest_neighbors<traits, double> knn;
906 [ + - ][ + - ]: 82 : return knn.find(_root, point, num_neighbors, omit_query_point);
[ + - ]
907 : : }
908 : : #endif
909 : :
910 : : };
911 : :
912 : : __END_NS_SSRC_SPATIAL
913 : :
914 : : #endif
|
