1 : /*
2 : * $Id: KDTree.h 5871 2005-10-28 02:10:33Z 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 : /**
21 : * @file
22 : * This header defines the KDTree class and its support classes.
23 : */
24 :
25 : #ifndef __SAVA_SPATIAL_KDTREE_H
26 : #define __SAVA_SPATIAL_KDTREE_H
27 :
28 : #include <algorithm>
29 : #include <utility>
30 : #include <vector>
31 :
32 : #include <libsava/spatial/detail/KDTree.h>
33 : #include <libsava/spatial/Point.h>
34 :
35 : __BEGIN_PACKAGE_SAVA_SPATIAL
36 :
37 : /**
38 : * KDTreeTraits stores metadata about KDTree instances.
39 : */
40 : template<typename Tree>
41 : struct KDTreeTraits {
42 : typedef typename Tree::key_type key_type;
43 : typedef typename Tree::mapped_type mapped_type;
44 : typedef typename Tree::value_type value_type;
45 : typedef typename Tree::pointer pointer;
46 : typedef typename Tree::const_pointer const_pointer;
47 : typedef typename Tree::reference reference;
48 : typedef typename Tree::const_reference const_reference;
49 : typedef typename Tree::discriminator_type discriminator_type;
50 : typedef typename Tree::node_type node_type;
51 : typedef typename node_type::child_type child_type;
52 : typedef typename Tree::iterator iterator;
53 : typedef typename Tree::const_iterator const_iterator;
54 : typedef typename Tree::point_traits point_traits;
55 : typedef Tree tree_type;
56 :
57 : static inline const unsigned int dimensions() {
58 : return Tree::dimensions();
59 : }
60 : };
61 :
62 :
63 : /**
64 : * KDTreeConstTraits stores metadata about const KDTree instances.
65 : *
66 : * @author <a href="https://www.savarese.com/">Daniel F. Savarese</a>
67 : */
68 : template<typename Tree>
69 : struct KDTreeConstTraits : public KDTreeTraits<Tree> {
70 : typedef typename Tree::const_pointer pointer;
71 : typedef typename Tree::const_reference reference;
72 : };
73 :
74 :
75 : // Note: we store the discriminator in each node to avoid modulo division,
76 : // trading space for time.
77 : /**
78 : * A k-d tree divides a k-dimensional space relative to the points it
79 : * contains by storing them in a binary tree, discriminating by a
80 : * different dimension at each level of the tree. It allows efficient
81 : * point data retrieval (<em>O(lg(n))</em>) and range searching.
82 : *
83 : * <p>KDTree tries to conform to the map interface from the STL where
84 : * it makes sense. Therefore, you will find it can be used with some
85 : * STL algorithms.</p>
86 : *
87 : * @author <a href="https://www.savarese.com/">Daniel F. Savarese</a>
88 : */
89 : template <typename Point,
90 : typename Value,
91 : unsigned int Dimensions = 2,
92 : typename Discriminator = unsigned char,
93 : typename Size = unsigned int>
94 : class KDTree {
95 :
96 : public:
97 :
98 : typedef KDTreeTraits<KDTree> traits;
99 : typedef KDTreeConstTraits<KDTree> const_traits;
100 : typedef Point key_type;
101 : typedef Value mapped_type;
102 : typedef std::pair<const key_type, mapped_type> value_type;
103 : typedef value_type* pointer;
104 : typedef pointer const const_pointer;
105 : typedef value_type& reference;
106 : typedef const reference const_reference;
107 : typedef Discriminator discriminator_type;
108 : typedef detail::KDTreeRangeSearchIterator<traits> iterator;
109 : typedef detail::KDTreeRangeSearchIterator<const_traits> const_iterator;
110 : typedef PointTraits<key_type> point_traits;
111 :
112 : typedef Size size_type;
113 :
114 335960 : static inline const unsigned int dimensions() {
115 335960 : return Dimensions;
116 : }
117 :
118 : typedef detail::KDTreeNode<traits> node_type;
119 : typedef typename node_type::child_type child_type;
120 :
121 : private:
122 :
123 : struct NodeComparator {
124 : discriminator_type discriminator;
125 :
126 5 : explicit NodeComparator() : discriminator(0) { }
127 :
128 : bool operator()(const node_type* const & n1,
129 7901923 : const node_type* const & n2) const
130 : {
131 7901923 : return (n1->point()[discriminator] < n2->point()[discriminator]);
132 : }
133 : };
134 :
135 : node_type *_root;
136 : size_type _size;
137 : iterator _endIterator;
138 : const_iterator _constEndIterator;
139 :
140 491532 : node_type * getNode(const key_type & point, node_type **parent = 0) const {
141 : discriminator_type discriminator;
142 : child_type child;
143 491532 : node_type *node = _root, *last = 0;
144 :
145 8697265 : while(node != 0) {
146 7910815 : discriminator = node->discriminator();
147 :
148 7910815 : if(point[discriminator] > node->point()[discriminator])
149 3944312 : child = node_type::ChildHigh;
150 3966503 : else if(point[discriminator] < node->point()[discriminator])
151 3768049 : child = node_type::ChildLow;
152 198454 : else if(node->point() == point) {
153 196614 : if(parent != 0)
154 98308 : *parent = last;
155 196614 : return node;
156 : } else
157 1840 : child = node_type::ChildHigh;
158 :
159 7714201 : last = node;
160 7714201 : node = node->child(child);
161 : }
162 :
163 294918 : if(parent != 0)
164 294916 : *parent = last;
165 :
166 294918 : return 0;
167 : }
168 :
169 : node_type * getMinimumNode(node_type *node, node_type *p,
170 : const discriminator_type discriminator,
171 222788 : node_type **parent)
172 : {
173 : node_type *result;
174 :
175 222788 : if(discriminator == node->discriminator()) {
176 105928 : if(node->child(node_type::ChildLow) != 0)
177 : return
178 : getMinimumNode(node->child(node_type::ChildLow), node,
179 47760 : discriminator, parent);
180 : else
181 58168 : result = node;
182 : } else {
183 116860 : node_type *nlow = 0, *nhigh = 0;
184 : node_type *plow, *phigh;
185 :
186 116860 : if(node->child(node_type::ChildLow) != 0)
187 49354 : nlow =
188 : getMinimumNode(node->child(node_type::ChildLow), node,
189 : discriminator, &plow);
190 :
191 116860 : if(node->child(node_type::ChildHigh) != 0)
192 56574 : nhigh =
193 : getMinimumNode(node->child(node_type::ChildHigh), node,
194 : discriminator, &phigh);
195 :
196 134414 : if(nlow != 0 && nhigh != 0) {
197 34712 : if(nlow->point()[discriminator] < nhigh->point()[discriminator]) {
198 17158 : result = nlow;
199 17158 : *parent = plow;
200 : } else {
201 17554 : result = nhigh;
202 17554 : *parent = phigh;
203 : }
204 82148 : } else if(nlow != 0) {
205 14642 : result = nlow;
206 14642 : *parent = plow;
207 67506 : } else if(nhigh != 0) {
208 21862 : result = nhigh;
209 21862 : *parent = phigh;
210 : } else
211 45644 : result = node;
212 : }
213 :
214 175028 : if(result == node)
215 103812 : *parent = p;
216 71216 : else if(node->point()[discriminator] < result->point()[discriminator]) {
217 18760 : result = node;
218 18760 : *parent = p;
219 : }
220 :
221 175028 : return result;
222 : }
223 :
224 :
225 134636 : node_type * recursiveRemoveNode(node_type *node) {
226 : discriminator_type discriminator;
227 : node_type *newRoot, *parent;
228 :
229 134636 : if(node->child(node_type::ChildLow) == 0 &&
230 : node->child(node_type::ChildHigh) == 0)
231 65536 : return 0;
232 : else
233 69100 : discriminator = node->discriminator();
234 :
235 69100 : if(node->child(node_type::ChildHigh) == 0) {
236 12238 : node->child(node_type::ChildHigh) = node->child(node_type::ChildLow);
237 12238 : node->child(node_type::ChildLow) = 0;
238 : }
239 :
240 69100 : newRoot =
241 : getMinimumNode(node->child(node_type::ChildHigh), node,
242 : discriminator, &parent);
243 :
244 : child_type child = (parent->child(node_type::ChildLow) == newRoot ?
245 69100 : node_type::ChildLow : node_type::ChildHigh);
246 69100 : parent->child(child) = recursiveRemoveNode(newRoot);
247 :
248 69100 : newRoot->child(node_type::ChildLow) = node->child(node_type::ChildLow);
249 69100 : newRoot->child(node_type::ChildHigh) = node->child(node_type::ChildHigh);
250 69100 : newRoot->discriminator() = node->discriminator();
251 :
252 69100 : return newRoot;
253 : }
254 :
255 :
256 : bool add(const key_type & point, const mapped_type & value,
257 : node_type **node, node_type *parent,
258 294918 : mapped_type *replaced = 0)
259 : {
260 294918 : if(parent == 0) {
261 20 : if(_root != 0)
262 0 : *node = _root;
263 : else {
264 20 : _root = *node = new node_type(0, point, value);
265 20 : ++_size;
266 20 : return false;
267 : }
268 294898 : } else if(*node == 0) {
269 : discriminator_type discriminator;
270 : child_type child;
271 :
272 294894 : discriminator = parent->discriminator();
273 294894 : child = (point[discriminator] >= parent->point()[discriminator] ?
274 : node_type::ChildHigh : node_type::ChildLow);
275 :
276 294894 : if(++discriminator >= dimensions())
277 147402 : discriminator = 0;
278 :
279 294894 : parent->child(child) = *node =
280 : new node_type(discriminator, point, value);
281 :
282 294894 : ++_size;
283 294894 : return false;
284 : }
285 :
286 4 : if(replaced != 0)
287 4 : *replaced = (*node)->value();
288 :
289 4 : (*node)->value() = value;
290 :
291 4 : return true;
292 : }
293 :
294 : template<template<typename> class Container>
295 : static inline
296 : node_type * optimize(typename Container<node_type*>::iterator begin,
297 : typename Container<node_type*>::iterator end,
298 82137 : NodeComparator & comparator)
299 : {
300 82137 : node_type *midpoint = 0;
301 : typename Container<node_type*>::iterator::difference_type diff;
302 :
303 82137 : diff = end - begin;
304 :
305 82137 : if(diff > 1) {
306 41066 : discriminator_type discriminator = comparator.discriminator;
307 41066 : typename Container<node_type*>::iterator nth = begin + (diff >> 1);
308 41066 : typename Container<node_type*>::iterator nthprev = nth - 1;
309 :
310 : //nth_element(begin, nth, end, comparator);
311 41066 : stable_sort(begin, end, comparator);
312 :
313 : // Ties go in the right subtree.
314 82240 : while(nth > begin &&
315 : (*nth)->point()[discriminator] ==
316 : (*nthprev)->point()[discriminator])
317 : {
318 108 : --nth;
319 108 : --nthprev;
320 : }
321 :
322 41066 : midpoint = *nth;
323 41066 : midpoint->discriminator() = discriminator;
324 :
325 41066 : if(++discriminator >= dimensions())
326 13761 : discriminator = 0;
327 :
328 41066 : comparator.discriminator = discriminator;
329 :
330 : // Left subtree
331 41066 : midpoint->child(node_type::ChildLow) =
332 : optimize<Container>(begin, nth, comparator);
333 :
334 41066 : comparator.discriminator = discriminator;
335 :
336 : // Right subtree
337 41066 : midpoint->child(node_type::ChildHigh) =
338 : optimize<Container>(nth + 1, end, comparator);
339 41071 : } else if(diff == 1) {
340 40854 : midpoint = *begin;
341 40854 : midpoint->discriminator() = comparator.discriminator;
342 40854 : midpoint->child(node_type::ChildLow) = 0;
343 40854 : midpoint->child(node_type::ChildHigh) = 0;
344 : }
345 :
346 82137 : return midpoint;
347 : }
348 :
349 : template<template<typename> class Container>
350 163845 : static inline void fillContainer(Container<node_type*> & c, node_type *node)
351 : {
352 163845 : if(node == 0)
353 81920 : return;
354 81920 : c.push_back(node);
355 81920 : fillContainer(c, node->child(node_type::ChildLow));
356 81920 : fillContainer(c, node->child(node_type::ChildHigh));
357 : }
358 :
359 : static inline
360 : void initPoint(key_type & point,
361 131092 : const typename point_traits::coordinate_type & value)
362 : {
363 393276 : for(unsigned int i=0; i < point_traits::dimensions(); ++i)
364 262184 : point[i] = value;
365 : }
366 :
367 131084 : static inline const key_type upperBound() {
368 131084 : key_type bound;
369 131084 : initPoint(bound, point_traits::max_coordinate());
370 : return bound;
371 : }
372 :
373 8 : static inline const key_type lowerBound() {
374 8 : key_type bound;
375 8 : initPoint(bound, point_traits::min_coordinate());
376 : return bound;
377 : }
378 :
379 : public:
380 :
381 : // TODO: need assignment operator.
382 :
383 : /**
384 : * Constructs an empty KDTree.
385 : */
386 16 : explicit KDTree() : _root(0), _size(0), _endIterator(), _constEndIterator()
387 16 : { }
388 :
389 : /**
390 : * Constructs a copy of a KDTree.
391 : *
392 : * @param tree The KDTree to copy.
393 : */
394 : KDTree(const KDTree & tree) :
395 : _root(0), _size(0), _endIterator(), _constEndIterator()
396 : {
397 : for(const_iterator p = tree.begin(); !p.endOfRange(); ++p)
398 : insert(p->first, p->second);
399 : }
400 :
401 : /**
402 : * Deallocates the memory allocated by the KDTree.
403 : */
404 16 : virtual ~KDTree() { delete _root; }
405 :
406 : /**
407 : * Removes all elements from the container, leaving it empty.
408 : */
409 4 : void clear() {
410 4 : delete _root;
411 4 : _root = 0;
412 4 : _size = 0;
413 : }
414 :
415 : /**
416 : * Returns the number of point-value mappings in the KDTree.
417 : *
418 : * @return The number of point-value mappings in the KDTree.
419 : */
420 23 : const size_type size() const {
421 23 : return _size;
422 : }
423 :
424 : /**
425 : * Returns the maximum number of elements that can be contained.
426 : *
427 : * @return The maximum number of elements that can be contained.
428 : */
429 2 : const size_type max_size() const {
430 2 : return std::numeric_limits<size_type>::max();
431 : }
432 :
433 : /**
434 : * Returns true if the container has no elements, false if it
435 : * contains one or more elements.
436 : *
437 : * @return true if the container has no elements, false if it
438 : * contains one or more elements.
439 : */
440 13 : bool empty() const {
441 13 : return (_root == 0);
442 : }
443 :
444 : /**
445 : * Returns an iterator pointing to the leftmost bottommost point in
446 : * the container. If empty, it equals end().
447 : *
448 : * @return An iterator pointing to the leftmost bottommost point in
449 : * the container. If empty, it equals end().
450 : */
451 8 : iterator begin() {
452 8 : return iterator(lowerBound(), upperBound(), _root);
453 : }
454 :
455 : /**
456 : * Returns a const iterator pointing to the leftmost bottommost point in
457 : * the container. If empty, it equals end().
458 : *
459 : * @return A const iterator pointing to the leftmost bottommost point in
460 : * the container. If empty, it equals end().
461 : */
462 : const_iterator begin() const {
463 : return const_iterator(lowerBound(), upperBound(), _root);
464 : }
465 :
466 : /**
467 : * Returns an iterator denoting the end of a range.
468 : *
469 : * @return An iterator denoting the end of a range.
470 : */
471 32776 : iterator & end() {
472 32776 : return _endIterator;
473 : }
474 :
475 : /**
476 : * Returns a const iterator denoting the end of a range.
477 : *
478 : * @return A const iterator denoting the end of a range.
479 : */
480 32768 : const const_iterator & end() const {
481 32768 : return _constEndIterator;
482 : }
483 :
484 : /**
485 : * Inserts a key value pair, replacing any existing value that may
486 : * be present, and optionally retrieving the replaced value.
487 : *
488 : * @param point The key corresponding to the value to be inserted
489 : * @param value The value to be inserted.
490 : * @param replaced If you want to retrieve a value that was
491 : * replaced, have this parameter point to a valid object to store
492 : * the value. If not, its default value of zero will prevent it
493 : * from being retrieved.
494 : * @return true if value is replaced, false if not.
495 : */
496 : bool insert(const key_type & point, const mapped_type & value,
497 98308 : mapped_type *replaced = 0)
498 : {
499 : node_type *parent;
500 98308 : node_type *node = getNode(point, &parent);
501 :
502 98308 : return add(point, value, &node, parent, replaced);
503 : }
504 :
505 : /**
506 : * Inserts a key value pair, but--in conformance with the STL
507 : * container interface--doesn't replace any existing value that may
508 : * be present. Note, this method is slower than
509 : * bool insert(const key_type &, const mapped_type, mapped_type*)
510 : *
511 : * @return A pair containing the iterator pointing to the inserted
512 : * value and true if the mapping is inserted. If the value is not
513 : * inserted, a pair containing the iterator pointing to the existing
514 : * value and false.
515 : */
516 32770 : std::pair<iterator,bool> insert(const value_type & mapping) {
517 : // Ideally, we'd do this all in one step, but that will have
518 : // to wait until we optimize the way we handle iterators.
519 : bool replaced;
520 : mapped_type existing;
521 32770 : iterator value;
522 :
523 32770 : replaced = insert(mapping.first, mapping.second, &existing);
524 32770 : value = find(mapping.first);
525 :
526 32770 : if(replaced)
527 2 : value._node->value() = existing;
528 :
529 32770 : return std::pair<iterator,bool>(value,!replaced);
530 : }
531 :
532 :
533 : /**
534 : * Retrieves the value at the given location. In conformance with
535 : * the STL map interface, if the point key does not occur in the
536 : * KDTree, a new value is inserted and returned using the default
537 : * constructor for KDTree::mapped_type.
538 : *
539 : * @param point The location from which to retrieve the value.
540 : * @return The value at the given location.
541 : */
542 229378 : mapped_type & operator[](const key_type & point) {
543 : node_type *parent;
544 229378 : node_type *node = getNode(point, &parent);
545 :
546 229378 : if(node == 0)
547 196610 : add(point, mapped_type(), &node, parent);
548 :
549 229378 : return node->value();
550 : }
551 :
552 : /**
553 : * Removes the point-value mapping corresponding to the given point key.
554 : * Optionally, retrieves the removed value if a mapping was present.
555 : *
556 : * @param point The point key of the mapping to remove.
557 : * @param erased A pointer to a mapped_type in which to store the
558 : * erased value. This pointer may be null if you do not want to
559 : * retrieve the removed value and only want to remove the mapping.
560 : * @return true if a mapping was present and removed, false if not.
561 : */
562 65538 : bool remove(const key_type & point, mapped_type *erased = 0) {
563 : node_type *parent;
564 65538 : node_type *node = getNode(point, &parent);
565 : node_type *child;
566 :
567 65538 : if(node == 0)
568 2 : return false;
569 :
570 65536 : if(erased != 0)
571 32768 : *erased = node->value();
572 :
573 65536 : child = node;
574 65536 : node = recursiveRemoveNode(child);
575 :
576 65536 : if(parent == 0)
577 46 : _root = node;
578 65490 : else if(child == parent->child(node_type::ChildLow))
579 31178 : parent->child(node_type::ChildLow) = node;
580 : else
581 34312 : parent->child(node_type::ChildHigh) = node;
582 :
583 : // Must zero children so they are not deleted by ~node_type()
584 65536 : child->child(node_type::ChildLow) = 0;
585 65536 : child->child(node_type::ChildHigh) = 0;
586 :
587 65536 : --_size;
588 65536 : delete child;
589 :
590 65536 : return true;
591 : }
592 :
593 : /**
594 : * Removes the point-value mapping corresponding to the given point key.
595 : *
596 : * @param point The point key of the mapping to remove.
597 : * @return The number of mappings erased (0 or 1).
598 : */
599 2 : size_type erase(const key_type & point) {
600 2 : return remove(point);
601 : }
602 :
603 : /**
604 : * Removes the point-value mapping at the specified position.
605 : *
606 : * @param pos The KDTree::iterator denoting the location of the mapping.
607 : */
608 32768 : void erase(iterator pos) {
609 32768 : remove(pos->first);
610 : }
611 :
612 : /**
613 : * Returns an iterator for mappings that are contained in the
614 : * rectangle defined by the given lower left-hand and upper
615 : * right-hand corners. The mappings returned include those occuring
616 : * at points on the bounding rectangle, not just those inside.
617 : *
618 : * @param lower The lower left-hand corner of the bounding
619 : * rectangle.
620 : * @param upper The upper right-hand corner of the bounding
621 : * rectangle.
622 : * @return A KDTree::iterator for mappings that are contained in the
623 : * specified rectangle.
624 : */
625 2 : iterator begin(const key_type & lower, const key_type & upper) {
626 2 : return iterator(lower, upper, _root);
627 : }
628 :
629 : /**
630 : * Returns a const iterator for mappings that are contained in the
631 : * rectangle defined by the given lower left-hand and upper
632 : * right-hand corners. The mappings returned include those occuring
633 : * at points on the bounding rectangle, not just those inside.
634 : *
635 : * @param lower The lower left-hand corner of the bounding
636 : * rectangle.
637 : * @param upper The upper right-hand corner of the bounding
638 : * rectangle.
639 : * @return A KDTree::const_iterator for mappings that are contained in the
640 : * specified rectangle.
641 : */
642 : const_iterator begin(const key_type & lower, const key_type & upper) const {
643 : return const_iterator(lower, upper, _root);
644 : }
645 :
646 : /**
647 : * Returns true if the KDTree contains a point-value mapping for the
648 : * specified point, false if not. Optionally, retrieves the value
649 : * at the given location (faster than find()).
650 : *
651 : * @param point The location from which to retrieve the value.
652 : * @param value A pointer to a KDTree::mapped_type in which to store the
653 : * retrieved value. This pointer may be null if you do not want to
654 : * retrieve the value and only want to see if the point is present in
655 : * the KDTree.
656 : * @return true if the KDTree contains a point-value mapping for the
657 : * specified point, false if not.
658 : */
659 98308 : bool get(const key_type & point, mapped_type *value = 0) const {
660 98308 : node_type *node = getNode(point);
661 :
662 98308 : if(node == 0)
663 2 : return false;
664 98306 : else if(value != 0)
665 32770 : *value = node->value();
666 :
667 98306 : return true;
668 : }
669 :
670 : /**
671 : * Returns the location of the point-value mapping for the specified
672 : * point (slower than get()). If there is no mapping present, the
673 : * iiterator is equivalent to end().
674 : *
675 : * @param point The key of the poinit-value mapping to find.
676 : * @return true A KDTree::iterator for the location of the
677 : * point-value mapping matching the specified point. end() if there
678 : * is no mapping.
679 : */
680 98308 : iterator find(const key_type & point) {
681 98308 : return iterator(point, upperBound(), _root, true);
682 : }
683 :
684 : /**
685 : * Returns the location of the point-value mapping for the specified
686 : * point (slower than get()). If there is no mapping present, the
687 : * iiterator is equivalent to end().
688 : *
689 : * @param point The key of the poinit-value mapping to find.
690 : * @return true A KDTree::const_iterator for the location of the
691 : * point-value mapping matching the specified point. end() if there
692 : * is no mapping.
693 : */
694 32768 : const_iterator find(const key_type & point) const {
695 32768 : return const_iterator(point, upperBound(), _root, true);
696 : }
697 :
698 : // Balances the tree. Very expensive!
699 : /**
700 : * Optimizes the performance of future search operations by balancing the
701 : * KDTree. The balancing operation is relatively expensive, but can
702 : * significantly improve the performance of searches. Usually, you
703 : * don't have to optimize a tree which contains random key values
704 : * inserted in a random order.
705 : */
706 5 : void optimize() {
707 5 : if(empty())
708 5 : return;
709 :
710 : typedef std::vector<node_type*> container;
711 5 : container nodes;
712 :
713 5 : nodes.reserve(size());
714 5 : fillContainer<std::vector>(nodes, _root);
715 :
716 5 : NodeComparator comparator;
717 5 : _root =
718 : optimize<std::vector>(nodes.begin(), nodes.end(), comparator);
719 : }
720 :
721 : };
722 :
723 :
724 : __END_PACKAGE_SAVA_SPATIAL
725 :
726 : #endif
727 :
|
Sava Algorithms 0.1.1 C++ Unit Test Coverage