| OpenMS 2.5.0

KDTree.h
Go to the documentation of this file.
1 // --------------------------------------------------------------------------
2 // OpenMS -- Open-Source Mass Spectrometry
3 // --------------------------------------------------------------------------
4 // Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
5 // ETH Zurich, and Freie Universitaet Berlin 2002-2020.
6 //
7 // This software is released under a three-clause BSD license:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of any author or any participating institution
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
16 // For a full list of authors, refer to the file AUTHORS.
17 // --------------------------------------------------------------------------
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
22 // INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // --------------------------------------------------------------------------
31 // $Maintainer: Johannes Veit $
32 // $Authors: Johannes Veit $
33 // --------------------------------------------------------------------------
34
35 /* Note: This file contains a concatenation of the 6 header files comprising
36 * libkdtree++ (node.hpp, function.hpp, allocator.hpp, iterator.hpp,
37 * region.hpp, kdtree.hpp).
38 *
39 * Johannes Veit (2016)
40 */
41
42 /* COPYRIGHT --
43 *
44 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
45 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
46 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
47 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
48 * root for more information.
49 *
50 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
51 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
52 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
53 */
54
61 #ifndef OPENMS_DATASTRUCTURES_KDTREE_H
62 #define OPENMS_DATASTRUCTURES_KDTREE_H
63
64 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS
65 # include <ostream>
66 #endif
67
68 #include <cstddef>
69 #include <cmath>
70
71 namespace KDTree
72 {
73 struct _Node_base
74 {
75 typedef _Node_base* _Base_ptr;
76 typedef _Node_base const* _Base_const_ptr;
77
78 _Base_ptr _M_parent;
79 _Base_ptr _M_left;
80 _Base_ptr _M_right;
81
82 _Node_base(_Base_ptr const __PARENT = nullptr,
83 _Base_ptr const __LEFT = nullptr,
84 _Base_ptr const __RIGHT = nullptr)
85 : _M_parent(__PARENT), _M_left(__LEFT), _M_right(__RIGHT) {}
86
87 static _Base_ptr
88 _S_minimum(_Base_ptr __x)
89 {
90 while (__x->_M_left) __x = __x->_M_left;
91 return __x;
92 }
93
94 static _Base_ptr
95 _S_maximum(_Base_ptr __x)
96 {
97 while (__x->_M_right) __x = __x->_M_right;
98 return __x;
99 }
100 };
101
102 template <typename _Val>
103 struct _Node : public _Node_base
104 {
105 using _Node_base::_Base_ptr;
106 typedef _Node* _Link_type;
107
108 _Val _M_value;
109
110 _Node(_Val const& __VALUE = _Val(),
111 _Base_ptr const __PARENT = nullptr,
112 _Base_ptr const __LEFT = nullptr,
113 _Base_ptr const __RIGHT = nullptr)
114 : _Node_base(__PARENT, __LEFT, __RIGHT), _M_value(__VALUE) {}
115
116 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS
117
118 template <typename Char, typename Traits>
119 friend
120 std::basic_ostream<Char, Traits>&
121 operator<<(typename std::basic_ostream<Char, Traits>& out,
122 _Node_base const& node)
123 {
124 out << &node;
125 out << " parent: " << node._M_parent;
126 out << "; left: " << node._M_left;
127 out << "; right: " << node._M_right;
128 return out;
129 }
130
131 template <typename Char, typename Traits>
132 friend
133 std::basic_ostream<Char, Traits>&
134 operator<<(typename std::basic_ostream<Char, Traits>& out,
135 _Node<_Val> const& node)
136 {
137 out << &node;
138 out << ' ' << node._M_value;
139 out << "; parent: " << node._M_parent;
140 out << "; left: " << node._M_left;
141 out << "; right: " << node._M_right;
142 return out;
143 }
144
145 #endif
146 };
147
148 template <typename _Val, typename _Acc, typename _Cmp>
149 class _Node_compare
150 {
151 public:
152 _Node_compare(size_t const __DIM, _Acc const& acc, _Cmp const& cmp)
153 : _M_DIM(__DIM), _M_acc(acc), _M_cmp(cmp) {}
154
155 bool
156 operator()(_Val const& __A, _Val const& __B) const
157 {
158 return _M_cmp(_M_acc(__A, _M_DIM), _M_acc(__B, _M_DIM));
159 }
160
161 private:
162 size_t _M_DIM; // don't make this const so that an assignment operator can be auto-generated
163 _Acc _M_acc;
164 _Cmp _M_cmp;
165 };
166
173 template <typename _ValA, typename _ValB, typename _Cmp,
174 typename _Acc>
175 inline
176 bool
177 _S_node_compare (const size_t __dim,
178 const _Cmp& __cmp, const _Acc& __acc,
179 const _ValA& __a, const _ValB& __b)
180 {
181 return __cmp(__acc(__a, __dim), __acc(__b, __dim));
182 }
183
189 template <typename _ValA, typename _ValB, typename _Dist,
190 typename _Acc>
191 inline
192 typename _Dist::distance_type
193 _S_node_distance (const size_t __dim,
194 const _Dist& __dist, const _Acc& __acc,
195 const _ValA& __a, const _ValB& __b)
196 {
197 return __dist(__acc(__a, __dim), __acc(__b, __dim));
198 }
199
206 template <typename _ValA, typename _ValB, typename _Dist,
207 typename _Acc>
208 inline
209 typename _Dist::distance_type
210 _S_accumulate_node_distance (const size_t __dim,
211 const _Dist& __dist, const _Acc& __acc,
212 const _ValA& __a, const _ValB& __b)
213 {
214 typename _Dist::distance_type d = 0;
215 for (size_t i=0; i<__dim; ++i)
216 d += __dist(__acc(__a, i), __acc(__b, i));
217 return d;
218 }
219
225 template <typename _Val, typename _Cmp, typename _Acc, typename NodeType>
226 inline
227 const NodeType*
228 _S_node_descend (const size_t __dim,
229 const _Cmp& __cmp, const _Acc& __acc,
230 const _Val& __val, const NodeType* __node)
231 {
232 if (_S_node_compare(__dim, __cmp, __acc, __val, __node->_M_value))
233 return static_cast<const NodeType *>(__node->_M_left);
234 return static_cast<const NodeType *>(__node->_M_right);
235 }
236
245 template <class SearchVal,
246 typename NodeType, typename _Cmp,
247 typename _Acc, typename _Dist,
248 typename _Predicate>
249 inline
250 std::pair<const NodeType*,
251 std::pair<size_t, typename _Dist::distance_type> >
252 _S_node_nearest (const size_t __k, size_t __dim, SearchVal const& __val,
253 const NodeType* __node, const _Node_base* __end,
254 const NodeType* __best, typename _Dist::distance_type __max,
255 const _Cmp& __cmp, const _Acc& __acc, const _Dist& __dist,
256 _Predicate __p)
257 {
258 typedef const NodeType* NodePtr;
259 NodePtr pcur = __node;
260 NodePtr cur = _S_node_descend(__dim % __k, __cmp, __acc, __val, __node);
261 size_t cur_dim = __dim+1;
262 // find the smallest __max distance in direct descent
263 while (cur)
264 {
265 if (__p(cur->_M_value))
266 {
267 typename _Dist::distance_type d = 0;
268 for (size_t i=0; i != __k; ++i)
269 d += _S_node_distance(i, __dist, __acc, __val, cur->_M_value);
270 d = std::sqrt(d);
271 if (d <= __max)
272 // ("bad candidate notes")
273 // Changed: removed this test: || ( d == __max && cur < __best ))
274 // Can't do this optimisation without checking that the current 'best' is not the root AND is not a valid candidate...
275 // This is because find_nearest() etc will call this function with the best set to _M_root EVEN IF _M_root is not a valid answer (eg too far away or doesn't pass the predicate test)
276 {
277 __best = cur;
278 __max = d;
279 __dim = cur_dim;
280 }
281 }
282 pcur = cur;
283 cur = _S_node_descend(cur_dim % __k, __cmp, __acc, __val, cur);
284 ++cur_dim;
285 }
286 // Swap cur to prev, only prev is a valid node.
287 cur = pcur;
288 --cur_dim;
289 pcur = NULL;
290 // Probe all node's children not visited yet (siblings of the visited nodes).
291 NodePtr probe = cur;
292 NodePtr pprobe = probe;
293 NodePtr near_node;
294 NodePtr far_node;
295 size_t probe_dim = cur_dim;
296 if (_S_node_compare(probe_dim % __k, __cmp, __acc, __val, probe->_M_value))
297 near_node = static_cast<NodePtr>(probe->_M_right);
298 else
299 near_node = static_cast<NodePtr>(probe->_M_left);
300 if (near_node
301 // only visit node's children if node's plane intersect hypersphere
302 && (std::sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, probe->_M_value)) <= __max))
303 {
304 probe = near_node;
305 ++probe_dim;
306 }
307 while (cur != __end)
308 {
309 while (probe != cur)
310 {
311 if (_S_node_compare(probe_dim % __k, __cmp, __acc, __val, probe->_M_value))
312 {
313 near_node = static_cast<NodePtr>(probe->_M_left);
314 far_node = static_cast<NodePtr>(probe->_M_right);
315 }
316 else
317 {
318 near_node = static_cast<NodePtr>(probe->_M_right);
319 far_node = static_cast<NodePtr>(probe->_M_left);
320 }
321 if (pprobe == probe->_M_parent) // going downward ...
322 {
323 if (__p(probe->_M_value))
324 {
325 typename _Dist::distance_type d = 0;
326 for (size_t i=0; i < __k; ++i)
327 d += _S_node_distance(i, __dist, __acc, __val, probe->_M_value);
328 d = std::sqrt(d);
329 if (d <= __max) // CHANGED, see the above notes ("bad candidate notes")
330 {
331 __best = probe;
332 __max = d;
333 __dim = probe_dim;
334 }
335 }
336 pprobe = probe;
337 if (near_node)
338 {
339 probe = near_node;
340 ++probe_dim;
341 }
342 else if (far_node &&
343 // only visit node's children if node's plane intersect hypersphere
344 std::sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, probe->_M_value)) <= __max)
345 {
346 probe = far_node;
347 ++probe_dim;
348 }
349 else
350 {
351 probe = static_cast<NodePtr>(probe->_M_parent);
352 --probe_dim;
353 }
354 }
355 else // ... and going upward.
356 {
357 if (pprobe == near_node && far_node
358 // only visit node's children if node's plane intersect hypersphere
359 && std::sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, probe->_M_value)) <= __max)
360 {
361 pprobe = probe;
362 probe = far_node;
363 ++probe_dim;
364 }
365 else
366 {
367 pprobe = probe;
368 probe = static_cast<NodePtr>(probe->_M_parent);
369 --probe_dim;
370 }
371 }
372 }
373 pcur = cur;
374 cur = static_cast<NodePtr>(cur->_M_parent);
375 --cur_dim;
376 pprobe = cur;
377 probe = cur;
378 probe_dim = cur_dim;
379 if (cur != __end)
380 {
381 if (pcur == cur->_M_left)
382 near_node = static_cast<NodePtr>(cur->_M_right);
383 else
384 near_node = static_cast<NodePtr>(cur->_M_left);
385 if (near_node
386 // only visit node's children if node's plane intersect hypersphere
387 && (std::sqrt(_S_node_distance(cur_dim % __k, __dist, __acc, __val, cur->_M_value)) <= __max))
388 {
389 probe = near_node;
390 ++probe_dim;
391 }
392 }
393 }
394 return std::pair<NodePtr,
395 std::pair<size_t, typename _Dist::distance_type> >
396 (__best, std::pair<size_t, typename _Dist::distance_type>
397 (__dim, __max));
398 }
399
400
401 } // namespace KDTree
402
403 #endif // include guard
404
405 /* COPYRIGHT --
406 *
407 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
408 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
409 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
410 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
411 * root for more information.
412 *
413 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
414 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
415 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
416 */
424 #ifndef INCLUDE_KDTREE_ACCESSOR_HPP
425 #define INCLUDE_KDTREE_ACCESSOR_HPP
426
427 #include <cstddef>
428
429 namespace KDTree
430 {
431 template <typename _Val>
432 struct _Bracket_accessor
433 {
434 typedef typename _Val::value_type result_type;
435
436 result_type
437 operator()(_Val const& V, size_t const N) const
438 {
439 return V[N];
440 }
441 };
442
443 template <typename _Tp>
444 struct always_true
445 {
446 bool operator() (const _Tp& ) const { return true; }
447 };
448
449 template <typename _Tp, typename _Dist>
450 struct squared_difference
451 {
452 typedef _Dist distance_type;
453
454 distance_type
455 operator() (const _Tp& __a, const _Tp& __b) const
456 {
457 distance_type d=__a - __b;
458 return d*d;
459 }
460 };
461
462 template <typename _Tp, typename _Dist>
463 struct squared_difference_counted
464 {
465 typedef _Dist distance_type;
466
467 squared_difference_counted()
468 : _M_count(0)
469 { }
470
471 void reset ()
472 { _M_count = 0; }
473
474 long&
475 count () const
476 { return _M_count; }
477
478 distance_type
479 operator() (const _Tp& __a, const _Tp& __b) const
480 {
481 distance_type d=__a - __b;
482 ++_M_count;
483 return d*d;
484 }
485
486 private:
487 mutable long _M_count;
488 };
489
490 } // namespace KDTree
491
492 #endif // include guard
493
494 /* COPYRIGHT --
495 *
496 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
497 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
498 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
499 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
500 * root for more information.
501 *
502 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
503 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
504 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
505 */
512 #ifndef INCLUDE_KDTREE_ALLOCATOR_HPP
513 #define INCLUDE_KDTREE_ALLOCATOR_HPP
514
515 #include <cstddef>
516
517 namespace KDTree
518 {
519
520 template <typename _Tp, typename _Alloc>
521 class _Alloc_base
522 {
523 public:
524 typedef _Node<_Tp> _Node_;
525 typedef typename _Node_::_Base_ptr _Base_ptr;
526 typedef _Alloc allocator_type;
527
528 _Alloc_base(allocator_type const& __A)
529 : _M_node_allocator(__A) {}
530
531 allocator_type
532 get_allocator() const
533 {
534 return _M_node_allocator;
535 }
536
537
538 class NoLeakAlloc
539 {
540 _Alloc_base * base;
541 _Node_ * new_node;
542
543 public:
544 NoLeakAlloc(_Alloc_base * b) : base(b), new_node(base->_M_allocate_node()) {}
545
546 _Node_ * get() { return new_node; }
547 void disconnect() { new_node = nullptr; }
548
549 ~NoLeakAlloc() { if (new_node) base->_M_deallocate_node(new_node); }
550 };
551
552
553 protected:
554 allocator_type _M_node_allocator;
555
556 _Node_*
557 _M_allocate_node()
558 {
559 return _M_node_allocator.allocate(1);
560 }
561
562 void
563 _M_deallocate_node(_Node_* const __P)
564 {
565 return _M_node_allocator.deallocate(__P, 1);
566 }
567
568 void
569 _M_construct_node(_Node_* __p, _Tp const __V = _Tp(),
570 _Base_ptr const __PARENT = NULL,
571 _Base_ptr const __LEFT = NULL,
572 _Base_ptr const __RIGHT = NULL)
573 {
574 new (__p) _Node_(__V, __PARENT, __LEFT, __RIGHT);
575 }
576
577 void
578 _M_destroy_node(_Node_* __p)
579 {
580 _M_node_allocator.destroy(__p);
581 }
582 };
583
584 } // namespace KDTree
585
586 #endif // include guard
587
588 /* COPYRIGHT --
589 *
590 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
591 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
592 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
593 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
594 * root for more information.
595 *
596 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
597 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
598 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
599 */
606 #ifndef INCLUDE_KDTREE_ITERATOR_HPP
607 #define INCLUDE_KDTREE_ITERATOR_HPP
608
609 #include <iterator>
610
611 namespace KDTree
612 {
613 template <typename _Val, typename _Ref, typename _Ptr>
614 class _Iterator;
615
616 template<typename _Val, typename _Ref, typename _Ptr>
617 inline bool
618 operator==(_Iterator<_Val, _Ref, _Ptr> const&,
619 _Iterator<_Val, _Ref, _Ptr> const&);
620
621 template<typename _Val>
622 inline bool
623 operator==(_Iterator<_Val, const _Val&, const _Val*> const&,
624 _Iterator<_Val, _Val&, _Val*> const&);
625
626 template<typename _Val>
627 inline bool
628 operator==(_Iterator<_Val, _Val&, _Val*> const&,
629 _Iterator<_Val, const _Val&, const _Val*> const&);
630
631 template<typename _Val, typename _Ref, typename _Ptr>
632 inline bool
633 operator!=(_Iterator<_Val, _Ref, _Ptr> const&,
634 _Iterator<_Val, _Ref, _Ptr> const&);
635
636 template<typename _Val>
637 inline bool
638 operator!=(_Iterator<_Val, const _Val&, const _Val*> const&,
639 _Iterator<_Val, _Val&, _Val*> const&);
640
641 template<typename _Val>
642 inline bool
643 operator!=(_Iterator<_Val, _Val&, _Val*> const&,
644 _Iterator<_Val, const _Val&, const _Val*> const&);
645
646 class _Base_iterator
647 {
648 protected:
649 typedef _Node_base::_Base_const_ptr _Base_const_ptr;
650 _Base_const_ptr _M_node;
651
652 inline _Base_iterator(_Base_const_ptr const __N = nullptr)
653 : _M_node(__N) {}
654 inline _Base_iterator(_Base_iterator const& __THAT)
655 : _M_node(__THAT._M_node) {}
656
657 inline void
658 _M_increment()
659 {
660 if (_M_node->_M_right)
661 {
662 _M_node = _M_node->_M_right;
663 while (_M_node->_M_left) _M_node = _M_node->_M_left;
664 }
665 else
666 {
667 _Base_const_ptr __p = _M_node->_M_parent;
668 while (__p && _M_node == __p->_M_right)
669 {
670 _M_node = __p;
671 __p = _M_node->_M_parent;
672 }
673 if (__p) // (__p) provide undetermined behavior on end()++ rather
674 // than a seg fault, similar to standard iterator.
675 _M_node = __p;
676 }
677 }
678
679 inline void
680 _M_decrement()
681 {
682 if (!_M_node->_M_parent) // clearly identify the header node
683 {
684 _M_node = _M_node->_M_right;
685 }
686 else if (_M_node->_M_left)
687 {
688 _Base_const_ptr x = _M_node->_M_left;
689 while (x->_M_right) x = x->_M_right;
690 _M_node = x;
691 }
692 else
693 {
694 _Base_const_ptr __p = _M_node->_M_parent;
695 while (__p && _M_node == __p->_M_left) // see below
696 {
697 _M_node = __p;
698 __p = _M_node->_M_parent;
699 }
700 if (__p) // (__p) provide undetermined behavior on rend()++ rather
701 // than a seg fault, similar to standard iterator.
702 _M_node = __p;
703 }
704 }
705
706 template <size_t const __K, typename _Val, typename _Acc,
707 typename _Dist, typename _Cmp, typename _Alloc>
708 friend class KDTree;
709 };
710
711 template <typename _Val, typename _Ref, typename _Ptr>
712 class _Iterator : protected _Base_iterator
713 {
714 public:
715 typedef _Val value_type;
716 typedef _Ref reference;
717 typedef _Ptr pointer;
718 typedef _Iterator<_Val, _Val&, _Val*> iterator;
719 typedef _Iterator<_Val, _Val const&, _Val const*> const_iterator;
720 typedef _Iterator<_Val, _Ref, _Ptr> _Self;
721 typedef _Node<_Val> const* _Link_const_type;
722 typedef std::bidirectional_iterator_tag iterator_category;
723 typedef ptrdiff_t difference_type;
724
725 inline _Iterator()
726 : _Base_iterator() {}
727 inline _Iterator(_Link_const_type const __N)
728 : _Base_iterator(__N) {}
729 inline _Iterator(iterator const& __THAT)
730 : _Base_iterator(__THAT) {}
731
732 _Link_const_type get_raw_node() const
733 {
734 return _Link_const_type(_M_node);
735 }
736
737 reference
738 operator*() const
739 {
740 return _Link_const_type(_M_node)->_M_value;
741 }
742
743 pointer
744 operator->() const
745 {
746 return &(operator*());
747 }
748
749 _Self
750 operator++()
751 {
752 _M_increment();
753 return *this;
754 }
755
756 _Self
757 operator++(int)
758 {
759 _Self ret = *this;
760 _M_increment();
761 return ret;
762 }
763
764 _Self&
765 operator--()
766 {
767 _M_decrement();
768 return *this;
769 }
770
771 _Self
772 operator--(int)
773 {
774 _Self ret = *this;
775 _M_decrement();
776 return ret;
777 }
778
779 friend bool
780 operator== <>(_Iterator<_Val, _Ref, _Ptr> const&,
781 _Iterator<_Val, _Ref, _Ptr> const&);
782
783 friend bool
784 operator== <>(_Iterator<_Val, const _Val&, const _Val*> const&,
785 _Iterator<_Val, _Val&, _Val*> const&);
786
787 friend bool
788 operator== <>(_Iterator<_Val, _Val&, _Val*> const&,
789 _Iterator<_Val, const _Val&, const _Val*> const&);
790
791 friend bool
792 operator!= <>(_Iterator<_Val, _Ref, _Ptr> const&,
793 _Iterator<_Val, _Ref, _Ptr> const&);
794
795 friend bool
796 operator!= <>(_Iterator<_Val, const _Val&, const _Val*> const&,
797 _Iterator<_Val, _Val&, _Val*> const&);
798
799 friend bool
800 operator!= <>(_Iterator<_Val, _Val&, _Val*> const&,
801 _Iterator<_Val, const _Val&, const _Val*> const&);
802 };
803
804 template<typename _Val, typename _Ref, typename _Ptr>
805 bool
806 operator==(_Iterator<_Val, _Ref, _Ptr> const& __X,
807 _Iterator<_Val, _Ref, _Ptr> const& __Y)
808 { return __X._M_node == __Y._M_node; }
809
810 template<typename _Val>
811 bool
812 operator==(_Iterator<_Val, const _Val&, const _Val*> const& __X,
813 _Iterator<_Val, _Val&, _Val*> const& __Y)
814 { return __X._M_node == __Y._M_node; }
815
816 template<typename _Val>
817 bool
818 operator==(_Iterator<_Val, _Val&, _Val*> const& __X,
819 _Iterator<_Val, const _Val&, const _Val*> const& __Y)
820 { return __X._M_node == __Y._M_node; }
821
822 template<typename _Val, typename _Ref, typename _Ptr>
823 bool
824 operator!=(_Iterator<_Val, _Ref, _Ptr> const& __X,
825 _Iterator<_Val, _Ref, _Ptr> const& __Y)
826 { return __X._M_node != __Y._M_node; }
827
828 template<typename _Val>
829 bool
830 operator!=(_Iterator<_Val, const _Val&, const _Val*> const& __X,
831 _Iterator<_Val, _Val&, _Val*> const& __Y)
832 { return __X._M_node != __Y._M_node; }
833
834 template<typename _Val>
835 bool
836 operator!=(_Iterator<_Val, _Val&, _Val*> const& __X,
837 _Iterator<_Val, const _Val&, const _Val*> const& __Y)
838 { return __X._M_node != __Y._M_node; }
839
840 } // namespace KDTree
841
842 #endif // include guard
843
844 /* COPYRIGHT --
845 *
846 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
847 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
848 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
849 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
850 * root for more information.
851 *
852 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
853 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
854 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
855 */
862 #ifndef INCLUDE_KDTREE_REGION_HPP
863 #define INCLUDE_KDTREE_REGION_HPP
864
865 #include <cstddef>
866
867 namespace KDTree
868 {
869
870 template <size_t const __K, typename _Val, typename _SubVal,
871 typename _Acc, typename _Cmp>
872 struct _Region
873 {
874 typedef _Val value_type;
875 typedef _SubVal subvalue_type;
876
877 // special typedef for checking against a fuzzy point (for find_nearest)
878 // Note the region (first) component is not supposed to have an area, its
879 // bounds should all be set to a specific point.
880 typedef std::pair<_Region,_SubVal> _CenterPt;
881
882 _Region(_Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
883 : _M_acc(__acc), _M_cmp(__cmp) {}
884
885 template <typename Val>
886 _Region(Val const& __V,
887 _Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
888 : _M_acc(__acc), _M_cmp(__cmp)
889 {
890 for (size_t __i = 0; __i != __K; ++__i)
891 {
892 _M_low_bounds[__i] = _M_high_bounds[__i] = _M_acc(__V,__i);
893 }
894 }
895
896 template <typename Val>
897 _Region(Val const& __V, subvalue_type const& __R,
898 _Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
899 : _M_acc(__acc), _M_cmp(__cmp)
900 {
901 for (size_t __i = 0; __i != __K; ++__i)
902 {
903 _M_low_bounds[__i] = _M_acc(__V,__i) - __R;
904 _M_high_bounds[__i] = _M_acc(__V,__i) + __R;
905 }
906 }
907
908 bool
909 intersects_with(_CenterPt const& __THAT) const
910 {
911 for (size_t __i = 0; __i != __K; ++__i)
912 {
913 // does it fall outside the bounds?
914 // ! low-tolerance <= x <= high+tolerance
915 // ! (low-tol <= x and x <= high+tol)
916 // !low-tol<=x or !x<=high+tol
917 // low-tol>x or x>high+tol
918 // x<low-tol or high+tol<x
919 if (_M_cmp(__THAT.first._M_low_bounds[__i], _M_low_bounds[__i] - __THAT.second)
920 || _M_cmp(_M_high_bounds[__i] + __THAT.second, __THAT.first._M_low_bounds[__i]))
921 return false;
922 }
923 return true;
924 }
925
926 bool
927 intersects_with(_Region const& __THAT) const
928 {
929 for (size_t __i = 0; __i != __K; ++__i)
930 {
931 if (_M_cmp(__THAT._M_high_bounds[__i], _M_low_bounds[__i])
932 || _M_cmp(_M_high_bounds[__i], __THAT._M_low_bounds[__i]))
933 return false;
934 }
935 return true;
936 }
937
938 bool
939 encloses(value_type const& __V) const
940 {
941 for (size_t __i = 0; __i != __K; ++__i)
942 {
943 if (_M_cmp(_M_acc(__V, __i), _M_low_bounds[__i])
944 || _M_cmp(_M_high_bounds[__i], _M_acc(__V, __i)))
945 return false;
946 }
947 return true;
948 }
949
950 _Region&
951 set_high_bound(value_type const& __V, size_t const __L)
952 {
953 _M_high_bounds[__L % __K] = _M_acc(__V, __L % __K);
954 return *this;
955 }
956
957 _Region&
958 set_low_bound(value_type const& __V, size_t const __L)
959 {
960 _M_low_bounds[__L % __K] = _M_acc(__V, __L % __K);
961 return *this;
962 }
963
964 subvalue_type _M_low_bounds[__K], _M_high_bounds[__K];
965 _Acc _M_acc;
966 _Cmp _M_cmp;
967 };
968
969 } // namespace KDTree
970
971 #endif // include guard
972
973 /* COPYRIGHT --
974 *
975 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
976 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
977 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
978 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
979 * root for more information.
980 *
981 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
982 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
983 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
984 */
1030 #ifndef INCLUDE_KDTREE_KDTREE_HPP
1031 #define INCLUDE_KDTREE_KDTREE_HPP
1032
1033
1034 //
1035 // This number is guaranteed to change with every release.
1036 //
1037 // KDTREE_VERSION % 100 is the patch level
1038 // KDTREE_VERSION / 100 % 1000 is the minor version
1039 // KDTREE_VERSION / 100000 is the major version
1040 #define KDTREE_VERSION 701
1041 //
1042 // KDTREE_LIB_VERSION must be defined to be the same as KDTREE_VERSION
1043 // but as a *string* in the form "x_y[_z]" where x is the major version
1044 // number, y is the minor version number, and z is the patch level if not 0.
1045 #define KDTREE_LIB_VERSION "0_7_1"
1046
1047
1048 #include <vector>
1049
1050 #ifdef KDTREE_CHECK_PERFORMANCE_COUNTERS
1051 # include <map>
1052 #endif
1053 #include <algorithm>
1054 #include <functional>
1055
1056 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS
1057 # include <ostream>
1058 # include <stack>
1059 #endif
1060
1061 #include <cmath>
1062 #include <cstddef>
1063 #include <cassert>
1064
1065 namespace KDTree
1066 {
1067
1068 #ifdef KDTREE_CHECK_PERFORMANCE
1069 unsigned long long num_dist_calcs = 0;
1070 #endif
1071
1072 template <size_t const __K, typename _Val,
1073 typename _Acc = _Bracket_accessor<_Val>,
1074 typename _Dist = squared_difference<typename _Acc::result_type,
1075 typename _Acc::result_type>,
1076 typename _Cmp = std::less<typename _Acc::result_type>,
1077 typename _Alloc = std::allocator<_Node<_Val> > >
1078 class KDTree : protected _Alloc_base<_Val, _Alloc>
1079 {
1080 protected:
1081 typedef _Alloc_base<_Val, _Alloc> _Base;
1082 typedef typename _Base::allocator_type allocator_type;
1083
1084 typedef _Node_base* _Base_ptr;
1085 typedef _Node_base const* _Base_const_ptr;
1086 typedef _Node<_Val>* _Link_type;
1087 typedef _Node<_Val> const* _Link_const_type;
1088
1089 typedef _Node_compare<_Val, _Acc, _Cmp> _Node_compare_;
1090
1091 public:
1092 typedef _Region<__K, _Val, typename _Acc::result_type, _Acc, _Cmp> _Region_;
1093 typedef _Val value_type;
1094 typedef value_type* pointer;
1095 typedef value_type const* const_pointer;
1096 typedef value_type& reference;
1097 typedef value_type const& const_reference;
1098 typedef typename _Acc::result_type subvalue_type;
1099 typedef typename _Dist::distance_type distance_type;
1100 typedef size_t size_type;
1101 typedef ptrdiff_t difference_type;
1102
1103 KDTree(_Acc const& __acc = _Acc(), _Dist const& __dist = _Dist(),
1104 _Cmp const& __cmp = _Cmp(), const allocator_type& __a = allocator_type())
1105 : _Base(__a), _M_header(),
1106 _M_count(0), _M_acc(__acc), _M_cmp(__cmp), _M_dist(__dist)
1107 {
1108 _M_empty_initialise();
1109 }
1110
1111 KDTree(const KDTree& __x)
1112 : _Base(__x.get_allocator()), _M_header(), _M_count(0),
1113 _M_acc(__x._M_acc), _M_cmp(__x._M_cmp), _M_dist(__x._M_dist)
1114 {
1115 _M_empty_initialise();
1116 // this is slow:
1117 // this->insert(begin(), __x.begin(), __x.end());
1118 // this->optimise();
1119
1120 // this is much faster, as it skips a lot of useless work
1121 // do the optimisation before inserting
1122 // Needs to be stored in a vector first as _M_optimise()
1123 // sorts the data in the passed iterators directly.
1124 std::vector<value_type> temp;
1125 temp.reserve(__x.size());
1126 std::copy(__x.begin(),__x.end(),std::back_inserter(temp));
1127 _M_optimise(temp.begin(), temp.end(), 0);
1128 }
1129
1130 template<typename _InputIterator>
1131 KDTree(_InputIterator __first, _InputIterator __last,
1132 _Acc const& acc = _Acc(), _Dist const& __dist = _Dist(),
1133 _Cmp const& __cmp = _Cmp(), const allocator_type& __a = allocator_type())
1134 : _Base(__a), _M_header(), _M_count(0),
1135 _M_acc(acc), _M_cmp(__cmp), _M_dist(__dist)
1136 {
1137 _M_empty_initialise();
1138 // this is slow:
1139 // this->insert(begin(), __first, __last);
1140 // this->optimise();
1141
1142 // this is much faster, as it skips a lot of useless work
1143 // do the optimisation before inserting
1144 // Needs to be stored in a vector first as _M_optimise()
1145 // sorts the data in the passed iterators directly.
1146 std::vector<value_type> temp;
1147 temp.reserve(std::distance(__first,__last));
1148 std::copy(__first,__last,std::back_inserter(temp));
1149 _M_optimise(temp.begin(), temp.end(), 0);
1150
1151 // NOTE: this will BREAK users that are passing in
1152 // read-once data via the iterator...
1153 // We increment __first all the way to __last once within
1154 // the distance() call, and again within the copy() call.
1155 //
1156 // This should end up using some funky C++ concepts or
1157 // type traits to check that the iterators can be used in this way...
1158 }
1159
1160
1161 // this will CLEAR the tree and fill it with the contents
1162 // of 'writable_vector'. it will use the passed vector directly,
1163 // and will basically resort the vector many times over while
1164 // optimising the tree.
1165 //
1166 // Paul: I use this when I have already built up a vector of data
1167 // that I want to add, and I don't mind if its contents get shuffled
1168 // by the kdtree optimise routine.
1169 void efficient_replace_and_optimise( std::vector<value_type> & writable_vector )
1170 {
1171 this->clear();
1172 _M_optimise(writable_vector.begin(), writable_vector.end(), 0);
1173 }
1174
1175
1176
1177 KDTree&
1178 operator=(const KDTree& __x)
1179 {
1180 if (this != &__x)
1181 {
1182 _M_acc = __x._M_acc;
1183 _M_dist = __x._M_dist;
1184 _M_cmp = __x._M_cmp;
1185 // this is slow:
1186 // this->insert(begin(), __x.begin(), __x.end());
1187 // this->optimise();
1188
1189 // this is much faster, as it skips a lot of useless work
1190 // do the optimisation before inserting
1191 // Needs to be stored in a vector first as _M_optimise()
1192 // sorts the data in the passed iterators directly.
1193 std::vector<value_type> temp;
1194 temp.reserve(__x.size());
1195 std::copy(__x.begin(),__x.end(),std::back_inserter(temp));
1196 efficient_replace_and_optimise(temp);
1197 }
1198 return *this;
1199 }
1200
1201 ~KDTree()
1202 {
1203 this->clear();
1204 }
1205
1206 allocator_type
1207 get_allocator() const
1208 {
1209 return _Base::get_allocator();
1210 }
1211
1212 size_type
1213 size() const
1214 {
1215 return _M_count;
1216 }
1217
1218 size_type
1219 max_size() const
1220 {
1221 return size_type(-1);
1222 }
1223
1224 bool
1225 empty() const
1226 {
1227 return this->size() == 0;
1228 }
1229
1230 void
1231 clear()
1232 {
1233 _M_erase_subtree(_M_get_root());
1234 _M_set_leftmost(&_M_header);
1235 _M_set_rightmost(&_M_header);
1236 _M_set_root(nullptr);
1237 _M_count = 0;
1238 }
1239
1245 _Cmp
1246 value_comp() const
1247 { return _M_cmp; }
1248
1254 _Acc
1255 value_acc() const
1256 { return _M_acc; }
1257
1264 const _Dist&
1265 value_distance() const
1266 { return _M_dist; }
1267
1268 _Dist&
1269 value_distance()
1270 { return _M_dist; }
1271
1272 // typedef _Iterator<_Val, reference, pointer> iterator;
1273 typedef _Iterator<_Val, const_reference, const_pointer> const_iterator;
1274 // No mutable iterator at this stage
1275 typedef const_iterator iterator;
1276 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1277 typedef std::reverse_iterator<iterator> reverse_iterator;
1278
1279 // Note: the static_cast in end() is invalid (_M_header is not convertable to a _Link_type), but
1280 // thats ok as it just means undefined behaviour if the user dereferences the end() iterator.
1281
1282 const_iterator begin() const { return const_iterator(_M_get_leftmost()); }
1283 const_iterator end() const { return const_iterator(static_cast<_Link_const_type>(&_M_header)); }
1284 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
1285 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
1286
1287 iterator
1288 insert(iterator /* ignored */, const_reference __V)
1289 {
1290 return this->insert(__V);
1291 }
1292
1293 iterator
1294 insert(const_reference __V)
1295 {
1296 if (!_M_get_root())
1297 {
1298 _Link_type __n = _M_new_node(__V, &_M_header);
1299 ++_M_count;
1300 _M_set_root(__n);
1301 _M_set_leftmost(__n);
1302 _M_set_rightmost(__n);
1303 return iterator(__n);
1304 }
1305 return _M_insert(_M_get_root(), __V, 0);
1306 }
1307
1308 template <class _InputIterator>
1309 void insert(_InputIterator __first, _InputIterator __last) {
1310 for (; __first != __last; ++__first)
1311 this->insert(*__first);
1312 }
1313
1314 void
1315 insert(iterator __pos, size_type __n, const value_type& __x)
1316 {
1317 for (; __n > 0; --__n)
1318 this->insert(__pos, __x);
1319 }
1320
1321 template<typename _InputIterator>
1322 void
1323 insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
1324 for (; __first != __last; ++__first)
1325 this->insert(__pos, *__first);
1326 }
1327
1328 // Note: this uses the find() to location the item you want to erase.
1329 // find() compares by equivalence of location ONLY. See the comments
1330 // above find_exact() for why you may not want this.
1331 //
1332 // If you want to erase ANY item that has the same location as __V,
1333 // then use this function.
1334 //
1335 // If you want to erase a PARTICULAR item, and not any other item
1336 // that might happen to have the same location, then you should use
1337 // erase_exact().
1338 void
1339 erase(const_reference __V) {
1340 const_iterator b = this->find(__V);
1341 this->erase(b);
1342 }
1343
1344 void
1345 erase_exact(const_reference __V) {
1346 this->erase(this->find_exact(__V));
1347 }
1348
1349 // note: kept as const because its easier to const-cast it away
1350 void
1351 erase(const_iterator const& __IT)
1352 {
1353 assert(__IT != this->end());
1354 _Link_const_type target = __IT.get_raw_node();
1355 _Link_const_type n = target;
1356 size_type level = 0;
1357 while ((n = _S_parent(n)) != &_M_header)
1358 ++level;
1359 _M_erase( const_cast<_Link_type>(target), level );
1360 _M_delete_node( const_cast<_Link_type>(target) );
1361 --_M_count;
1362 }
1363
1364 /* this does not work since erasure changes sort order
1365 void
1366 erase(const_iterator __A, const_iterator const& __B)
1367 {
1368 if (0 && __A == this->begin() && __B == this->end())
1369 {
1370 this->clear();
1371 }
1372 else
1373 {
1374 while (__A != __B)
1375 this->erase(__A++);
1376 }
1377 }
1378 */
1379
1380 // compares via equivalence
1381 // so if you are looking for any item with the same location,
1382 // according to the standard accessor comparisions,
1383 // then this is the function for you.
1384 template <class SearchVal>
1385 const_iterator
1386 find(SearchVal const& __V) const
1387 {
1388 if (!_M_get_root()) return this->end();
1389 return _M_find(_M_get_root(), __V, 0);
1390 }
1391
1392 // compares via equality
1393 // if you are looking for a particular item in the tree,
1394 // and (for example) it has an ID that is checked via an == comparison
1395 // eg
1396 // struct Item
1397 // {
1398 // size_type unique_id;
1399 // bool operator==(Item const& a, Item const& b) { return a.unique_id == b.unique_id; }
1400 // Location location;
1401 // };
1402 // Two items may be equivalent in location. find() would return
1403 // either one of them. But no two items have the same ID, so
1404 // find_exact() would always return the item with the same location AND id.
1405 //
1406 template <class SearchVal>
1407 const_iterator
1408 find_exact(SearchVal const& __V) const
1409 {
1410 if (!_M_get_root()) return this->end();
1411 return _M_find_exact(_M_get_root(), __V, 0);
1412 }
1413
1414 // NOTE: see notes on find_within_range().
1415 size_type
1416 count_within_range(const_reference __V, subvalue_type const __R) const
1417 {
1418 if (!_M_get_root()) return 0;
1419 _Region_ __region(__V, __R, _M_acc, _M_cmp);
1420 return this->count_within_range(__region);
1421 }
1422
1423 size_type
1424 count_within_range(_Region_ const& __REGION) const
1425 {
1426 if (!_M_get_root()) return 0;
1427
1428 _Region_ __bounds(__REGION);
1429 return _M_count_within_range(_M_get_root(),
1430 __REGION, __bounds, 0);
1431 }
1432
1433 // NOTE: see notes on find_within_range().
1434 template <typename SearchVal, class Visitor>
1435 Visitor
1436 visit_within_range(SearchVal const& V, subvalue_type const R, Visitor visitor) const
1437 {
1438 if (!_M_get_root()) return visitor;
1439 _Region_ region(V, R, _M_acc, _M_cmp);
1440 return this->visit_within_range(region, visitor);
1441 }
1442
1443 template <class Visitor>
1444 Visitor
1445 visit_within_range(_Region_ const& REGION, Visitor visitor) const
1446 {
1447 if (_M_get_root())
1448 {
1449 _Region_ bounds(REGION);
1450 return _M_visit_within_range(visitor, _M_get_root(), REGION, bounds, 0);
1451 }
1452 return visitor;
1453 }
1454
1455 // NOTE: this will visit points based on 'Manhattan distance' aka city-block distance
1456 // aka taxicab metric. Meaning it will find all points within:
1457 // max(x_dist,max(y_dist,z_dist));
1458 // AND NOT than what you would expect: sqrt(x_dist*x_dist + y_dist*y_dist + z_dist*z_dist)
1459 //
1460 // This is because it converts the distance into a bounding-box 'region' and compares
1461 // against that.
1462 //
1463 // If you want the sqrt() behaviour, ask on the mailing list for different options.
1464 //
1465 template <typename SearchVal, typename _OutputIterator>
1466 _OutputIterator
1467 find_within_range(SearchVal const& val, subvalue_type const range,
1468 _OutputIterator out) const
1469 {
1470 if (!_M_get_root()) return out;
1471 _Region_ region(val, range, _M_acc, _M_cmp);
1472 return this->find_within_range(region, out);
1473 }
1474
1475 template <typename _OutputIterator>
1476 _OutputIterator
1477 find_within_range(_Region_ const& region,
1478 _OutputIterator out) const
1479 {
1480 if (_M_get_root())
1481 {
1482 _Region_ bounds(region);
1483 out = _M_find_within_range(out, _M_get_root(),
1484 region, bounds, 0);
1485 }
1486 return out;
1487 }
1488
1489 template <class SearchVal>
1490 std::pair<const_iterator, distance_type>
1491 find_nearest (SearchVal const& __val) const
1492 {
1493 if (_M_get_root())
1494 {
1495 std::pair<const _Node<_Val>*,
1496 std::pair<size_type, typename _Acc::result_type> >
1497 best = _S_node_nearest (__K, 0, __val,
1498 _M_get_root(), &_M_header, _M_get_root(),
1499 std::sqrt(_S_accumulate_node_distance
1500 (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val)),
1501 _M_cmp, _M_acc, _M_dist,
1502 always_true<value_type>());
1503 return std::pair<const_iterator, distance_type>
1504 (best.first, best.second.second);
1505 }
1506 return std::pair<const_iterator, distance_type>(end(), 0);
1507 }
1508
1509 template <class SearchVal>
1510 std::pair<const_iterator, distance_type>
1511 find_nearest (SearchVal const& __val, distance_type __max) const
1512 {
1513 if (_M_get_root())
1514 {
1515 bool root_is_candidate = false;
1516 const _Node<_Val>* node = _M_get_root();
1517 { // scope to ensure we don't use 'root_dist' anywhere else
1518 distance_type root_dist = std::sqrt(_S_accumulate_node_distance
1519 (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val));
1520 if (root_dist <= __max)
1521 {
1522 root_is_candidate = true;
1523 __max = root_dist;
1524 }
1525 }
1526 std::pair<const _Node<_Val>*,
1527 std::pair<size_type, typename _Acc::result_type> >
1528 best = _S_node_nearest (__K, 0, __val, _M_get_root(), &_M_header,
1529 node, __max, _M_cmp, _M_acc, _M_dist,
1530 always_true<value_type>());
1531 // make sure we didn't just get stuck with the root node...
1532 if (root_is_candidate || best.first != _M_get_root())
1533 return std::pair<const_iterator, distance_type>
1534 (best.first, best.second.second);
1535 }
1536 return std::pair<const_iterator, distance_type>(end(), __max);
1537 }
1538
1539 template <class SearchVal, class _Predicate>
1540 std::pair<const_iterator, distance_type>
1541 find_nearest_if (SearchVal const& __val, distance_type __max,
1542 _Predicate __p) const
1543 {
1544 if (_M_get_root())
1545 {
1546 bool root_is_candidate = false;
1547 const _Node<_Val>* node = _M_get_root();
1548 if (__p(_M_get_root()->_M_value))
1549 {
1550 { // scope to ensure we don't use root_dist anywhere else
1551 distance_type root_dist = std::sqrt(_S_accumulate_node_distance
1552 (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val));
1553 if (root_dist <= __max)
1554 {
1555 root_is_candidate = true;
1556 root_dist = __max;
1557 }
1558 }
1559 }
1560 std::pair<const _Node<_Val>*,
1561 std::pair<size_type, typename _Acc::result_type> >
1562 best = _S_node_nearest (__K, 0, __val, _M_get_root(), &_M_header,
1563 node, __max, _M_cmp, _M_acc, _M_dist, __p);
1564 // make sure we didn't just get stuck with the root node...
1565 if (root_is_candidate || best.first != _M_get_root())
1566 return std::pair<const_iterator, distance_type>
1567 (best.first, best.second.second);
1568 }
1569 return std::pair<const_iterator, distance_type>(end(), __max);
1570 }
1571
1572 void
1573 optimise()
1574 {
1575 std::vector<value_type> __v(this->begin(),this->end());
1576 this->clear();
1577 _M_optimise(__v.begin(), __v.end(), 0);
1578 }
1579
1580 void
1581 optimize()
1582 { // cater for people who cannot spell :)
1583 this->optimise();
1584 }
1585
1586 void check_tree()
1587 {
1588 _M_check_node(_M_get_root(),0);
1589 }
1590
1591 protected:
1592
1593 void _M_check_children( _Link_const_type child, _Link_const_type parent, size_type const level, bool to_the_left )
1594 {
1595 assert(parent);
1596 if (child)
1597 {
1598 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1599 // REMEMBER! its a <= relationship for BOTH branches
1600 // for left-case (true), child<=node --> !(node<child)
1601 // for right-case (false), node<=child --> !(child<node)
1602 assert(!to_the_left || !compare(parent->_M_value,child->_M_value)); // check the left
1603 assert(to_the_left || !compare(child->_M_value,parent->_M_value)); // check the right
1604 // and recurse down the tree, checking everything
1605 _M_check_children(_S_left(child),parent,level,to_the_left);
1606 _M_check_children(_S_right(child),parent,level,to_the_left);
1607 }
1608 }
1609
1610 void _M_check_node( _Link_const_type node, size_type const level )
1611 {
1612 if (node)
1613 {
1614 // (comparing on this level)
1615 // everything to the left of this node must be smaller than this
1616 _M_check_children( _S_left(node), node, level, true );
1617 // everything to the right of this node must be larger than this
1618 _M_check_children( _S_right(node), node, level, false );
1619
1620 _M_check_node( _S_left(node), level+1 );
1621 _M_check_node( _S_right(node), level+1 );
1622 }
1623 }
1624
1625 void _M_empty_initialise()
1626 {
1627 _M_set_leftmost(&_M_header);
1628 _M_set_rightmost(&_M_header);
1629 _M_header._M_parent = nullptr;
1630 _M_set_root(nullptr);
1631 }
1632
1633 iterator
1634 _M_insert_left(_Link_type __N, const_reference __V)
1635 {
1636 _S_set_left(__N, _M_new_node(__V)); ++_M_count;
1637 _S_set_parent( _S_left(__N), __N );
1638 if (__N == _M_get_leftmost())
1639 _M_set_leftmost( _S_left(__N) );
1640 return iterator(_S_left(__N));
1641 }
1642
1643 iterator
1644 _M_insert_right(_Link_type __N, const_reference __V)
1645 {
1646 _S_set_right(__N, _M_new_node(__V)); ++_M_count;
1647 _S_set_parent( _S_right(__N), __N );
1648 if (__N == _M_get_rightmost())
1649 _M_set_rightmost( _S_right(__N) );
1650 return iterator(_S_right(__N));
1651 }
1652
1653 iterator
1654 _M_insert(_Link_type __N, const_reference __V,
1655 size_type const __L)
1656 {
1657 if (_Node_compare_(__L % __K, _M_acc, _M_cmp)(__V, __N->_M_value))
1658 {
1659 if (!_S_left(__N))
1660 return _M_insert_left(__N, __V);
1661 return _M_insert(_S_left(__N), __V, __L+1);
1662 }
1663 else
1664 {
1665 if (!_S_right(__N) || __N == _M_get_rightmost())
1666 return _M_insert_right(__N, __V);
1667 return _M_insert(_S_right(__N), __V, __L+1);
1668 }
1669 }
1670
1671 _Link_type
1672 _M_erase(_Link_type dead_dad, size_type const level)
1673 {
1674 // find a new step_dad, he will become a drop-in replacement.
1675 _Link_type step_dad = _M_get_erase_replacement(dead_dad, level);
1676
1677 // tell dead_dad's parent that his new child is step_dad
1678 if (dead_dad == _M_get_root())
1679 _M_set_root(step_dad);
1680 else if (_S_left(_S_parent(dead_dad)) == dead_dad)
1681 _S_set_left(_S_parent(dead_dad), step_dad);
1682 else
1683 _S_set_right(_S_parent(dead_dad), step_dad);
1684
1685 // deal with the left and right edges of the tree...
1686 // if the dead_dad was at the edge, then substitude...
1687 // but if there IS no new dead, then left_most is the dead_dad's parent
1688 if (dead_dad == _M_get_leftmost())
1689 _M_set_leftmost( (step_dad ? step_dad : _S_parent(dead_dad)) );
1690 if (dead_dad == _M_get_rightmost())
1691 _M_set_rightmost( (step_dad ? step_dad : _S_parent(dead_dad)) );
1692
1693 if (step_dad)
1694 {
1695 // step_dad gets dead_dad's parent
1696 _S_set_parent(step_dad, _S_parent(dead_dad));
1697
1698 // first tell the children that step_dad is their new dad
1699 if (_S_left(dead_dad))
1700 _S_set_parent(_S_left(dead_dad), step_dad);
1701 if (_S_right(dead_dad))
1702 _S_set_parent(_S_right(dead_dad), step_dad);
1703
1704 // step_dad gets dead_dad's children
1705 _S_set_left(step_dad, _S_left(dead_dad));
1706 _S_set_right(step_dad, _S_right(dead_dad));
1707 }
1708
1709 return step_dad;
1710 }
1711
1712
1713
1714 _Link_type
1715 _M_get_erase_replacement(_Link_type node, size_type const level)
1716 {
1717 // if 'node' is null, then we can't do any better
1718 if (_S_is_leaf(node))
1719 return NULL;
1720
1721 std::pair<_Link_type,size_type> candidate;
1722 // if there is nothing to the left, find a candidate on the right tree
1723 if (!_S_left(node))
1724 candidate = _M_get_j_min( std::pair<_Link_type,size_type>(_S_right(node),level), level+1);
1725 // ditto for the right
1726 else if ((!_S_right(node)))
1727 candidate = _M_get_j_max( std::pair<_Link_type,size_type>(_S_left(node),level), level+1);
1728 // we have both children ...
1729 else
1730 {
1731 // we need to do a little more work in order to find a good candidate
1732 // this is actually a technique used to choose a node from either the
1733 // left or right branch RANDOMLY, so that the tree has a greater change of
1734 // staying balanced.
1735 // If this were a true binary tree, we would always hunt down the right branch.
1736 // See top for notes.
1737 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1738 // compare the children based on this level's criteria...
1739 // (this gives virtually random results)
1740 if (compare(_S_right(node)->_M_value, _S_left(node)->_M_value))
1741 // the right is smaller, get our replacement from the SMALLEST on the right
1742 candidate = _M_get_j_min(std::pair<_Link_type,size_type>(_S_right(node),level), level+1);
1743 else
1744 candidate = _M_get_j_max( std::pair<_Link_type,size_type>(_S_left(node),level), level+1);
1745 }
1746
1747 // we have a candidate replacement by now.
1748 // remove it from the tree, but don't delete it.
1749 // it must be disconnected before it can be reconnected.
1750 _Link_type parent = _S_parent(candidate.first);
1751 if (_S_left(parent) == candidate.first)
1752 _S_set_left(parent, _M_erase(candidate.first, candidate.second));
1753 else
1754 _S_set_right(parent, _M_erase(candidate.first, candidate.second));
1755
1756 return candidate.first;
1757 }
1758
1759
1760
1761 // TODO: why not pass node by const-ref?
1762 std::pair<_Link_type,size_type>
1763 _M_get_j_min( std::pair<_Link_type,size_type> const node, size_type const level)
1764 {
1765 typedef std::pair<_Link_type,size_type> Result;
1766 if (_S_is_leaf(node.first))
1767 return Result(node.first,level);
1768
1769 _Node_compare_ compare(node.second % __K, _M_acc, _M_cmp);
1770 Result candidate = node;
1771 if (_S_left(node.first))
1772 {
1773 Result left = _M_get_j_min(Result(_S_left(node.first), node.second), level+1);
1774 if (compare(left.first->_M_value, candidate.first->_M_value))
1775 candidate = left;
1776 }
1777 if (_S_right(node.first))
1778 {
1779 Result right = _M_get_j_min( Result(_S_right(node.first),node.second), level+1);
1780 if (compare(right.first->_M_value, candidate.first->_M_value))
1781 candidate = right;
1782 }
1783 if (candidate.first == node.first)
1784 return Result(candidate.first,level);
1785
1786 return candidate;
1787 }
1788
1789
1790
1791 // TODO: why not pass node by const-ref?
1792 std::pair<_Link_type,size_type>
1793 _M_get_j_max( std::pair<_Link_type,size_type> const node, size_type const level)
1794 {
1795 typedef std::pair<_Link_type,size_type> Result;
1796
1797 if (_S_is_leaf(node.first))
1798 return Result(node.first,level);
1799
1800 _Node_compare_ compare(node.second % __K, _M_acc, _M_cmp);
1801 Result candidate = node;
1802 if (_S_left(node.first))
1803 {
1804 Result left = _M_get_j_max( Result(_S_left(node.first),node.second), level+1);
1805 if (compare(candidate.first->_M_value, left.first->_M_value))
1806 candidate = left;
1807 }
1808 if (_S_right(node.first))
1809 {
1810 Result right = _M_get_j_max(Result(_S_right(node.first),node.second), level+1);
1811 if (compare(candidate.first->_M_value, right.first->_M_value))
1812 candidate = right;
1813 }
1814
1815 if (candidate.first == node.first)
1816 return Result(candidate.first,level);
1817
1818 return candidate;
1819 }
1820
1821
1822 void
1823 _M_erase_subtree(_Link_type __n)
1824 {
1825 while (__n)
1826 {
1827 _M_erase_subtree(_S_right(__n));
1828 _Link_type __t = _S_left(__n);
1829 _M_delete_node(__n);
1830 __n = __t;
1831 }
1832 }
1833
1834 const_iterator
1835 _M_find(_Link_const_type node, const_reference value, size_type const level) const
1836 {
1837 // be aware! This is very different to normal binary searches, because of the <=
1838 // relationship used. See top for notes.
1839 // Basically we have to check ALL branches, as we may have an identical node
1840 // in different branches.
1841 const_iterator found = this->end();
1842
1843 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1844 if (!compare(node->_M_value,value)) // note, this is a <= test
1845 {
1846 // this line is the only difference between _M_find_exact() and _M_find()
1847 if (_M_matches_node(node, value, level))
1848 return const_iterator(node); // return right away
1849 if (_S_left(node))
1850 found = _M_find(_S_left(node), value, level+1);
1851 }
1852 if ( _S_right(node) && found == this->end() && !compare(value,node->_M_value)) // note, this is a <= test
1853 found = _M_find(_S_right(node), value, level+1);
1854 return found;
1855 }
1856
1857 const_iterator
1858 _M_find_exact(_Link_const_type node, const_reference value, size_type const level) const
1859 {
1860 // be aware! This is very different to normal binary searches, because of the <=
1861 // relationship used. See top for notes.
1862 // Basically we have to check ALL branches, as we may have an identical node
1863 // in different branches.
1864 const_iterator found = this->end();
1865
1866 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1867 if (!compare(node->_M_value,value)) // note, this is a <= test
1868 {
1869 // this line is the only difference between _M_find_exact() and _M_find()
1870 if (value == *const_iterator(node))
1871 return const_iterator(node); // return right away
1872 if (_S_left(node))
1873 found = _M_find_exact(_S_left(node), value, level+1);
1874 }
1875
1876 // note: no else! items that are identical can be down both branches
1877 if ( _S_right(node) && found == this->end() && !compare(value,node->_M_value)) // note, this is a <= test
1878 found = _M_find_exact(_S_right(node), value, level+1);
1879 return found;
1880 }
1881
1882 bool
1883 _M_matches_node_in_d(_Link_const_type __N, const_reference __V,
1884 size_type const __L) const
1885 {
1886 _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);
1887 return !(compare(__N->_M_value, __V) || compare(__V, __N->_M_value));
1888 }
1889
1890 bool
1891 _M_matches_node_in_other_ds(_Link_const_type __N, const_reference __V,
1892 size_type const __L = 0) const
1893 {
1894 size_type __i = __L;
1895 while ((__i = (__i + 1) % __K) != __L % __K)
1896 if (!_M_matches_node_in_d(__N, __V, __i)) return false;
1897 return true;
1898 }
1899
1900 bool
1901 _M_matches_node(_Link_const_type __N, const_reference __V,
1902 size_type __L = 0) const
1903 {
1904 return _M_matches_node_in_d(__N, __V, __L)
1905 && _M_matches_node_in_other_ds(__N, __V, __L);
1906 }
1907
1908 size_type
1909 _M_count_within_range(_Link_const_type __N, _Region_ const& __REGION,
1910 _Region_ const& __BOUNDS,
1911 size_type const __L) const
1912 {
1913 size_type count = 0;
1914 if (__REGION.encloses(_S_value(__N)))
1915 {
1916 ++count;
1917 }
1918 if (_S_left(__N))
1919 {
1920 _Region_ __bounds(__BOUNDS);
1921 __bounds.set_high_bound(_S_value(__N), __L);
1922 if (__REGION.intersects_with(__bounds))
1923 count += _M_count_within_range(_S_left(__N),
1924 __REGION, __bounds, __L+1);
1925 }
1926 if (_S_right(__N))
1927 {
1928 _Region_ __bounds(__BOUNDS);
1929 __bounds.set_low_bound(_S_value(__N), __L);
1930 if (__REGION.intersects_with(__bounds))
1931 count += _M_count_within_range(_S_right(__N),
1932 __REGION, __bounds, __L+1);
1933 }
1934
1935 return count;
1936 }
1937
1938
1939 template <class Visitor>
1940 Visitor
1941 _M_visit_within_range(Visitor visitor,
1942 _Link_const_type N, _Region_ const& REGION,
1943 _Region_ const& BOUNDS,
1944 size_type const L) const
1945 {
1946 if (REGION.encloses(_S_value(N)))
1947 {
1948 visitor(_S_value(N));
1949 }
1950 if (_S_left(N))
1951 {
1952 _Region_ bounds(BOUNDS);
1953 bounds.set_high_bound(_S_value(N), L);
1954 if (REGION.intersects_with(bounds))
1955 visitor = _M_visit_within_range(visitor, _S_left(N),
1956 REGION, bounds, L+1);
1957 }
1958 if (_S_right(N))
1959 {
1960 _Region_ bounds(BOUNDS);
1961 bounds.set_low_bound(_S_value(N), L);
1962 if (REGION.intersects_with(bounds))
1963 visitor = _M_visit_within_range(visitor, _S_right(N),
1964 REGION, bounds, L+1);
1965 }
1966
1967 return visitor;
1968 }
1969
1970
1971
1972 template <typename _OutputIterator>
1973 _OutputIterator
1974 _M_find_within_range(_OutputIterator out,
1975 _Link_const_type __N, _Region_ const& __REGION,
1976 _Region_ const& __BOUNDS,
1977 size_type const __L) const
1978 {
1979 if (__REGION.encloses(_S_value(__N)))
1980 {
1981 *out++ = _S_value(__N);
1982 }
1983 if (_S_left(__N))
1984 {
1985 _Region_ __bounds(__BOUNDS);
1986 __bounds.set_high_bound(_S_value(__N), __L);
1987 if (__REGION.intersects_with(__bounds))
1988 out = _M_find_within_range(out, _S_left(__N),
1989 __REGION, __bounds, __L+1);
1990 }
1991 if (_S_right(__N))
1992 {
1993 _Region_ __bounds(__BOUNDS);
1994 __bounds.set_low_bound(_S_value(__N), __L);
1995 if (__REGION.intersects_with(__bounds))
1996 out = _M_find_within_range(out, _S_right(__N),
1997 __REGION, __bounds, __L+1);
1998 }
1999
2000 return out;
2001 }
2002
2003
2004 template <typename _Iter>
2005 void
2006 _M_optimise(_Iter const& __A, _Iter const& __B,
2007 size_type const __L)
2008 {
2009 if (__A == __B) return;
2010 _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);
2011 _Iter __m = __A + (__B - __A) / 2;
2012 std::nth_element(__A, __m, __B, compare);
2013 this->insert(*__m);
2014 if (__m != __A) _M_optimise(__A, __m, __L+1);
2015 if (++__m != __B) _M_optimise(__m, __B, __L+1);
2016 }
2017
2018 _Link_const_type
2019 _M_get_root() const
2020 {
2021 return const_cast<_Link_const_type>(_M_root);
2022 }
2023
2024 _Link_type
2025 _M_get_root()
2026 {
2027 return _M_root;
2028 }
2029
2030 void _M_set_root(_Link_type n)
2031 {
2032 _M_root = n;
2033 }
2034
2035 _Link_const_type
2036 _M_get_leftmost() const
2037 {
2038 return static_cast<_Link_type>(_M_header._M_left);
2039 }
2040
2041 void
2042 _M_set_leftmost( _Node_base * a )
2043 {
2044 _M_header._M_left = a;
2045 }
2046
2047 _Link_const_type
2048 _M_get_rightmost() const
2049 {
2050 return static_cast<_Link_type>( _M_header._M_right );
2051 }
2052
2053 void
2054 _M_set_rightmost( _Node_base * a )
2055 {
2056 _M_header._M_right = a;
2057 }
2058
2059 static _Link_type
2060 _S_parent(_Base_ptr N)
2061 {
2062 return static_cast<_Link_type>( N->_M_parent );
2063 }
2064
2065 static _Link_const_type
2066 _S_parent(_Base_const_ptr N)
2067 {
2068 return static_cast<_Link_const_type>( N->_M_parent );
2069 }
2070
2071 static void
2072 _S_set_parent(_Base_ptr N, _Base_ptr p)
2073 {
2074 N->_M_parent = p;
2075 }
2076
2077 static void
2078 _S_set_left(_Base_ptr N, _Base_ptr l)
2079 {
2080 N->_M_left = l;
2081 }
2082
2083 static _Link_type
2084 _S_left(_Base_ptr N)
2085 {
2086 return static_cast<_Link_type>( N->_M_left );
2087 }
2088
2089 static _Link_const_type
2090 _S_left(_Base_const_ptr N)
2091 {
2092 return static_cast<_Link_const_type>( N->_M_left );
2093 }
2094
2095 static void
2096 _S_set_right(_Base_ptr N, _Base_ptr r)
2097 {
2098 N->_M_right = r;
2099 }
2100
2101 static _Link_type
2102 _S_right(_Base_ptr N)
2103 {
2104 return static_cast<_Link_type>( N->_M_right );
2105 }
2106
2107 static _Link_const_type
2108 _S_right(_Base_const_ptr N)
2109 {
2110 return static_cast<_Link_const_type>( N->_M_right );
2111 }
2112
2113 static bool
2114 _S_is_leaf(_Base_const_ptr N)
2115 {
2116 return !_S_left(N) && !_S_right(N);
2117 }
2118
2119 static const_reference
2120 _S_value(_Link_const_type N)
2121 {
2122 return N->_M_value;
2123 }
2124
2125 static const_reference
2126 _S_value(_Base_const_ptr N)
2127 {
2128 return static_cast<_Link_const_type>(N)->_M_value;
2129 }
2130
2131 static _Link_const_type
2132 _S_minimum(_Link_const_type __X)
2133 {
2134 return static_cast<_Link_const_type> ( _Node_base::_S_minimum(__X) );
2135 }
2136
2137 static _Link_const_type
2138 _S_maximum(_Link_const_type __X)
2139 {
2140 return static_cast<_Link_const_type>( _Node_base::_S_maximum(__X) );
2141 }
2142
2143
2144 _Link_type
2145 _M_new_node(const_reference __V, // = value_type(),
2146 _Base_ptr const __PARENT = nullptr,
2147 _Base_ptr const __LEFT = nullptr,
2148 _Base_ptr const __RIGHT = nullptr)
2149 {
2150 typename _Base::NoLeakAlloc noleak(this);
2151 _Link_type new_node = noleak.get();
2152 _Base::_M_construct_node(new_node, __V, __PARENT, __LEFT, __RIGHT);
2153 noleak.disconnect();
2154 return new_node;
2155 }
2156
2157 /* WHAT was this for?
2158 _Link_type
2159 _M_clone_node(_Link_const_type __X)
2160 {
2161 _Link_type __ret = _M_allocate_node(__X->_M_value);
2162 // TODO
2163 return __ret;
2164 }
2165 */
2166
2167 void
2168 _M_delete_node(_Link_type __p)
2169 {
2170 _Base::_M_destroy_node(__p);
2171 _Base::_M_deallocate_node(__p);
2172 }
2173
2174 _Link_type _M_root;
2175 _Node_base _M_header;
2176 size_type _M_count;
2177 _Acc _M_acc;
2178 _Cmp _M_cmp;
2179 _Dist _M_dist;
2180
2181 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS
2182 friend std::ostream&
2183 operator<<(std::ostream& o,
2184 KDTree<__K, _Val, _Acc, _Dist, _Cmp, _Alloc> const& tree)
2185 {
2186 o << "meta node: " << tree._M_header << std::endl;
2187 o << "root node: " << tree._M_root << std::endl;
2188
2189 if (tree.empty())
2190 return o << "[empty " << __K << "d-tree " << &tree << "]";
2191
2192 o << "nodes total: " << tree.size() << std::endl;
2193 o << "dimensions: " << __K << std::endl;
2194
2195 typedef KDTree<__K, _Val, _Acc, _Dist, _Cmp, _Alloc> _Tree;
2196 typedef typename _Tree::_Link_type _Link_type;
2197
2198 std::stack<_Link_const_type> s;
2199 s.push(tree._M_get_root());
2200
2201 while (!s.empty())
2202 {
2203 _Link_const_type n = s.top();
2204 s.pop();
2205 o << *n << std::endl;
2206 if (_Tree::_S_left(n)) s.push(_Tree::_S_left(n));
2207 if (_Tree::_S_right(n)) s.push(_Tree::_S_right(n));
2208 }
2209
2210 return o;
2211 }
2212 #endif
2213
2214 };
2215
2216
2217 } // namespace KDTree
2218
2219 #endif // include guard
2220
2221 /* COPYRIGHT --
2222 *
2223 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
2224 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
2225 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
2226 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
2227 * root for more information.
2228 * Parts of this file are (c) 2004-2007 Paul Harris <paulharris@computer.org>.
2229 *
2230 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
2231 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
2232 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
2233 */
KDTree::_Node_base::_M_left
_Base_ptr _M_left
Definition: KDTree.h:79
KDTree::_Alloc_base::allocator_type
_Alloc allocator_type
Definition: KDTree.h:526
KDTree::KDTree::insert
void insert(_InputIterator __first, _InputIterator __last)
Definition: KDTree.h:1309
KDTree::_Base_iterator::_M_decrement
void _M_decrement()
Definition: KDTree.h:680
KDTree::_Iterator::_Self
_Iterator< _Val, _Ref, _Ptr > _Self
Definition: KDTree.h:720
KDTree::_Iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: KDTree.h:722
KDTree::_Iterator::operator--
_Self & operator--()
Definition: KDTree.h:765
KDTree::_Node_base::_S_maximum
static _Base_ptr _S_maximum(_Base_ptr __x)
Definition: KDTree.h:95
KDTree::KDTree::optimize
void optimize()
Definition: KDTree.h:1581
KDTree::_Base_iterator::_Base_iterator
_Base_iterator(_Base_const_ptr const __N=nullptr)
Definition: KDTree.h:652
KDTree::KDTree::value_acc
_Acc value_acc() const
Accessor to the value&#39;s elements.
Definition: KDTree.h:1255
KDTree::KDTree::KDTree
KDTree(_Acc const &__acc=_Acc(), _Dist const &__dist=_Dist(), _Cmp const &__cmp=_Cmp(), const allocator_type &__a=allocator_type())
Definition: KDTree.h:1103
KDTree::KDTree::find_within_range
_OutputIterator find_within_range(SearchVal const &val, subvalue_type const range, _OutputIterator out) const
Definition: KDTree.h:1467
KDTree::_Alloc_base
Definition: KDTree.h:521
KDTree::KDTree::count_within_range
size_type count_within_range(const_reference __V, subvalue_type const __R) const
Definition: KDTree.h:1416
KDTree::KDTree::_M_check_node
void _M_check_node(_Link_const_type node, size_type const level)
Definition: KDTree.h:1610
KDTree::_Node_compare::_M_DIM
size_t _M_DIM
Definition: KDTree.h:162
KDTree::KDTree::_M_cmp
_Cmp _M_cmp
Definition: KDTree.h:2178
KDTree::_Bracket_accessor::result_type
_Val::value_type result_type
Definition: KDTree.h:434
KDTree::KDTree::const_reference
value_type const & const_reference
Definition: KDTree.h:1097
KDTree::KDTree::rend
const_reverse_iterator rend() const
Definition: KDTree.h:1285
KDTree::_Iterator::operator++
_Self operator++(int)
Definition: KDTree.h:757
KDTree::KDTree::_M_new_node
_Link_type _M_new_node(const_reference __V, _Base_ptr const __PARENT=nullptr, _Base_ptr const __LEFT=nullptr, _Base_ptr const __RIGHT=nullptr)
Definition: KDTree.h:2145
KDTree::KDTree::insert
iterator insert(iterator, const_reference __V)
Definition: KDTree.h:1288
KDTree::KDTree::find_nearest_if
std::pair< const_iterator, distance_type > find_nearest_if(SearchVal const &__val, distance_type __max, _Predicate __p) const
Definition: KDTree.h:1541
KDTree::KDTree
Definition: KDTree.h:1078
KDTree::KDTree::find_within_range
_OutputIterator find_within_range(_Region_ const &region, _OutputIterator out) const
Definition: KDTree.h:1477
KDTree::KDTree::_S_value
static const_reference _S_value(_Link_const_type N)
Definition: KDTree.h:2120
KDTree::_Alloc_base::NoLeakAlloc::base
_Alloc_base * base
Definition: KDTree.h:540
KDTree::KDTree::_M_find
const_iterator _M_find(_Link_const_type node, const_reference value, size_type const level) const
Definition: KDTree.h:1835
KDTree::squared_difference_counted::reset
void reset()
Definition: KDTree.h:471
KDTree::KDTree::size_type
size_t size_type
Definition: KDTree.h:1100
KDTree::_Node_base::_Base_ptr
_Node_base * _Base_ptr
Definition: KDTree.h:75
KDTree::KDTree::_M_find_within_range
_OutputIterator _M_find_within_range(_OutputIterator out, _Link_const_type __N, _Region_ const &__REGION, _Region_ const &__BOUNDS, size_type const __L) const
Definition: KDTree.h:1974
KDTree::squared_difference::distance_type
_Dist distance_type
Definition: KDTree.h:452
KDTree::KDTree::_S_minimum
static _Link_const_type _S_minimum(_Link_const_type __X)
Definition: KDTree.h:2132
KDTree::KDTree::const_iterator
_Iterator< _Val, const_reference, const_pointer > const_iterator
Definition: KDTree.h:1273
KDTree::_Region::_Region
_Region(Val const &__V, subvalue_type const &__R, _Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:897
KDTree::KDTree::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: KDTree.h:1276
KDTree::always_true
Definition: KDTree.h:444
KDTree::KDTree::_Base_ptr
_Node_base * _Base_ptr
Definition: KDTree.h:1084
KDTree::_Region::set_high_bound
_Region & set_high_bound(value_type const &__V, size_t const __L)
Definition: KDTree.h:951
KDTree::_Region::encloses
bool encloses(value_type const &__V) const
Definition: KDTree.h:939
KDTree::_Base_iterator::_Base_iterator
_Base_iterator(_Base_iterator const &__THAT)
Definition: KDTree.h:654
KDTree::_Alloc_base::_Node_
_Node< _Tp > _Node_
Definition: KDTree.h:524
KDTree::KDTree::_S_parent
static _Link_type _S_parent(_Base_ptr N)
Definition: KDTree.h:2060
KDTree::_S_node_descend
const NodeType * _S_node_descend(const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _Val &__val, const NodeType *__node)
Definition: KDTree.h:228
KDTree::KDTree::insert
void insert(iterator __pos, size_type __n, const value_type &__x)
Definition: KDTree.h:1315
KDTree::_Node_base::_M_right
_Base_ptr _M_right
Definition: KDTree.h:80
KDTree::_Region::_M_high_bounds
subvalue_type _M_high_bounds[__K]
Definition: KDTree.h:964
KDTree::KDTree::_S_right
static _Link_type _S_right(_Base_ptr N)
Definition: KDTree.h:2102
KDTree::operator!=
bool operator!=(_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
Definition: KDTree.h:824
KDTree::KDTree::_M_dist
_Dist _M_dist
Definition: KDTree.h:2179
KDTree::_Alloc_base::_M_deallocate_node
void _M_deallocate_node(_Node_ *const __P)
Definition: KDTree.h:563
KDTree::_Iterator::difference_type
ptrdiff_t difference_type
Definition: KDTree.h:723
KDTree::_Alloc_base::_M_destroy_node
void _M_destroy_node(_Node_ *__p)
Definition: KDTree.h:578
KDTree::KDTree::_S_is_leaf
static bool _S_is_leaf(_Base_const_ptr N)
Definition: KDTree.h:2114
KDTree::_Iterator
Definition: KDTree.h:614
KDTree::_Base_iterator::_Base_const_ptr
_Node_base::_Base_const_ptr _Base_const_ptr
Definition: KDTree.h:649
KDTree::KDTree::erase
void erase(const_iterator const &__IT)
Definition: KDTree.h:1351
KDTree::squared_difference_counted
Definition: KDTree.h:463
KDTree::squared_difference_counted::count
long & count() const
Definition: KDTree.h:475
KDTree::_Bracket_accessor
Definition: KDTree.h:432
KDTree::KDTree::iterator
const_iterator iterator
Definition: KDTree.h:1275
KDTree::squared_difference_counted::operator()
distance_type operator()(const _Tp &__a, const _Tp &__b) const
Definition: KDTree.h:479
KDTree::KDTree::_M_set_rightmost
void _M_set_rightmost(_Node_base *a)
Definition: KDTree.h:2054
KDTree::_Region::value_type
_Val value_type
Definition: KDTree.h:874
KDTree::KDTree::_S_set_right
static void _S_set_right(_Base_ptr N, _Base_ptr r)
Definition: KDTree.h:2096
KDTree::_Alloc_base::NoLeakAlloc::new_node
_Node_ * new_node
Definition: KDTree.h:541
KDTree::_Region::set_low_bound
_Region & set_low_bound(value_type const &__V, size_t const __L)
Definition: KDTree.h:958
KDTree::_Iterator::iterator
_Iterator< _Val, _Val &, _Val * > iterator
Definition: KDTree.h:718
KDTree::_Base_iterator::_M_increment
void _M_increment()
Definition: KDTree.h:658
KDTree::KDTree::find_exact
const_iterator find_exact(SearchVal const &__V) const
Definition: KDTree.h:1408
KDTree::_Iterator::get_raw_node
_Link_const_type get_raw_node() const
Definition: KDTree.h:732
KDTree::KDTree::_M_insert
iterator _M_insert(_Link_type __N, const_reference __V, size_type const __L)
Definition: KDTree.h:1654
KDTree::_Iterator::pointer
_Ptr pointer
Definition: KDTree.h:717
KDTree::_Iterator::_Iterator
_Iterator(_Link_const_type const __N)
Definition: KDTree.h:727
KDTree::KDTree::pointer
value_type * pointer
Definition: KDTree.h:1094
KDTree::_Node_base::_S_minimum
static _Base_ptr _S_minimum(_Base_ptr __x)
Definition: KDTree.h:88
KDTree::_Region::_CenterPt
std::pair< _Region, _SubVal > _CenterPt
Definition: KDTree.h:880
KDTree::KDTree::find
const_iterator find(SearchVal const &__V) const
Definition: KDTree.h:1386
KDTree::_Region::subvalue_type
_SubVal subvalue_type
Definition: KDTree.h:875
KDTree::_Iterator::reference
_Ref reference
Definition: KDTree.h:716
KDTree::KDTree::_M_get_j_min
std::pair< _Link_type, size_type > _M_get_j_min(std::pair< _Link_type, size_type > const node, size_type const level)
Definition: KDTree.h:1763
KDTree::KDTree::_M_acc
_Acc _M_acc
Definition: KDTree.h:2177
KDTree::_Region
Definition: KDTree.h:872
KDTree::_Alloc_base::NoLeakAlloc::disconnect
void disconnect()
Definition: KDTree.h:547
KDTree::KDTree::_Base
_Alloc_base< _Val, _Alloc > _Base
Definition: KDTree.h:1081
KDTree::KDTree::end
const_iterator end() const
Definition: KDTree.h:1283
KDTree::_Iterator::_Iterator
_Iterator()
Definition: KDTree.h:725
KDTree::KDTree::_M_matches_node_in_d
bool _M_matches_node_in_d(_Link_const_type __N, const_reference __V, size_type const __L) const
Definition: KDTree.h:1883
KDTree::_Alloc_base::get_allocator
allocator_type get_allocator() const
Definition: KDTree.h:532
KDTree::_Alloc_base::NoLeakAlloc
Definition: KDTree.h:538
KDTree::KDTree::_S_set_parent
static void _S_set_parent(_Base_ptr N, _Base_ptr p)
Definition: KDTree.h:2072
KDTree::KDTree::_M_visit_within_range
Visitor _M_visit_within_range(Visitor visitor, _Link_const_type N, _Region_ const &REGION, _Region_ const &BOUNDS, size_type const L) const
Definition: KDTree.h:1941
KDTree::KDTree::_Region_
_Region< __K, _Val, typename _Acc::result_type, _Acc, _Cmp > _Region_
Definition: KDTree.h:1092
KDTree::KDTree::optimise
void optimise()
Definition: KDTree.h:1573
KDTree::KDTree::_Link_const_type
_Node< _Val > const * _Link_const_type
Definition: KDTree.h:1087
KDTree::squared_difference
Definition: KDTree.h:450
KDTree::KDTree::_Link_type
_Node< _Val > * _Link_type
Definition: KDTree.h:1086
KDTree::KDTree::empty
bool empty() const
Definition: KDTree.h:1225
KDTree::_Region::intersects_with
bool intersects_with(_CenterPt const &__THAT) const
Definition: KDTree.h:909
KDTree::KDTree::_M_count
size_type _M_count
Definition: KDTree.h:2176
OpenMS::Constants::R
const double R
KDTree::KDTree::clear
void clear()
Definition: KDTree.h:1231
KDTree::squared_difference_counted::_M_count
long _M_count
Definition: KDTree.h:487
KDTree::_Region::_M_acc
_Acc _M_acc
Definition: KDTree.h:965
KDTree::KDTree::reference
value_type & reference
Definition: KDTree.h:1096
KDTree::KDTree::const_pointer
value_type const * const_pointer
Definition: KDTree.h:1095
KDTree::KDTree::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Definition: KDTree.h:1277
KDTree
Definition: KDTree.h:71
KDTree::_Node::_M_value
_Val _M_value
Definition: KDTree.h:108
OpenMS::operator<<
std::ostream & operator<<(std::ostream &os, const AccurateMassSearchResult &amsr)
KDTree::KDTree::_M_count_within_range
size_type _M_count_within_range(_Link_const_type __N, _Region_ const &__REGION, _Region_ const &__BOUNDS, size_type const __L) const
Definition: KDTree.h:1909
KDTree::KDTree::_M_set_root
void _M_set_root(_Link_type n)
Definition: KDTree.h:2030
KDTree::_Alloc_base::_Alloc_base
_Alloc_base(allocator_type const &__A)
Definition: KDTree.h:528
KDTree::KDTree::get_allocator
allocator_type get_allocator() const
Definition: KDTree.h:1207
KDTree::_Node_base::_M_parent
_Base_ptr _M_parent
Definition: KDTree.h:78
KDTree::KDTree::insert
void insert(iterator __pos, _InputIterator __first, _InputIterator __last)
Definition: KDTree.h:1323
KDTree::KDTree::rbegin
const_reverse_iterator rbegin() const
Definition: KDTree.h:1284
KDTree::KDTree::value_type
_Val value_type
Definition: KDTree.h:1093
KDTree::KDTree::subvalue_type
_Acc::result_type subvalue_type
Definition: KDTree.h:1098
KDTree::_Base_iterator
Definition: KDTree.h:646
KDTree::_Region::intersects_with
bool intersects_with(_Region const &__THAT) const
Definition: KDTree.h:927
KDTree::_Iterator::_Iterator
_Iterator(iterator const &__THAT)
Definition: KDTree.h:729
KDTree::KDTree::value_distance
const _Dist & value_distance() const
Distance calculator between 2 value&#39;s element.
Definition: KDTree.h:1265
KDTree::KDTree::KDTree
KDTree(const KDTree &__x)
Definition: KDTree.h:1111
KDTree::_Node_base::_Base_const_ptr
_Node_base const * _Base_const_ptr
Definition: KDTree.h:76
KDTree::KDTree::value_comp
_Cmp value_comp() const
Comparator for the values in the KDTree.
Definition: KDTree.h:1246
KDTree::KDTree::_M_matches_node_in_other_ds
bool _M_matches_node_in_other_ds(_Link_const_type __N, const_reference __V, size_type const __L=0) const
Definition: KDTree.h:1891
KDTree::KDTree::_M_insert_left
iterator _M_insert_left(_Link_type __N, const_reference __V)
Definition: KDTree.h:1634
KDTree::KDTree::begin
const_iterator begin() const
Definition: KDTree.h:1282
KDTree::KDTree::distance_type
_Dist::distance_type distance_type
Definition: KDTree.h:1099
KDTree::_Iterator::operator++
_Self operator++()
Definition: KDTree.h:750
KDTree::KDTree::~KDTree
~KDTree()
Definition: KDTree.h:1201
KDTree::KDTree::visit_within_range
Visitor visit_within_range(_Region_ const &REGION, Visitor visitor) const
Definition: KDTree.h:1445
KDTree::_Alloc_base::NoLeakAlloc::~NoLeakAlloc
~NoLeakAlloc()
Definition: KDTree.h:549
KDTree::_Node_compare::_M_acc
_Acc _M_acc
Definition: KDTree.h:163
KDTree::KDTree::_M_delete_node
void _M_delete_node(_Link_type __p)
Definition: KDTree.h:2168
KDTree::KDTree::erase_exact
void erase_exact(const_reference __V)
Definition: KDTree.h:1345
KDTree::_Region::_Region
_Region(_Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:882
seqan::find
bool find(TFinder &finder, const Pattern< TNeedle, FuzzyAC > &me, PatternAuxData< TNeedle > &dh)
Definition: AhoCorasickAmbiguous.h:884
KDTree::_Iterator::operator*
reference operator*() const
Definition: KDTree.h:738
KDTree::KDTree::find_nearest
std::pair< const_iterator, distance_type > find_nearest(SearchVal const &__val) const
Definition: KDTree.h:1491
KDTree::_Alloc_base::_M_construct_node
void _M_construct_node(_Node_ *__p, _Tp const __V=_Tp(), _Base_ptr const __PARENT=NULL, _Base_ptr const __LEFT=NULL, _Base_ptr const __RIGHT=NULL)
Definition: KDTree.h:569
KDTree::KDTree::difference_type
ptrdiff_t difference_type
Definition: KDTree.h:1101
KDTree::KDTree::_S_set_left
static void _S_set_left(_Base_ptr N, _Base_ptr l)
Definition: KDTree.h:2078
KDTree::KDTree::_M_get_root
_Link_const_type _M_get_root() const
Definition: KDTree.h:2019
KDTree::KDTree::_M_erase
_Link_type _M_erase(_Link_type dead_dad, size_type const level)
Definition: KDTree.h:1672
KDTree::_Iterator::const_iterator
_Iterator< _Val, _Val const &, _Val const * > const_iterator
Definition: KDTree.h:719
KDTree::KDTree::efficient_replace_and_optimise
void efficient_replace_and_optimise(std::vector< value_type > &writable_vector)
Definition: KDTree.h:1169
KDTree::_Node
Definition: KDTree.h:103
KDTree::squared_difference_counted::squared_difference_counted
squared_difference_counted()
Definition: KDTree.h:467
KDTree::squared_difference::operator()
distance_type operator()(const _Tp &__a, const _Tp &__b) const
Definition: KDTree.h:455
KDTree::_Alloc_base::_M_allocate_node
_Node_ * _M_allocate_node()
Definition: KDTree.h:557
KDTree::_Node_compare::_Node_compare
_Node_compare(size_t const __DIM, _Acc const &acc, _Cmp const &cmp)
Definition: KDTree.h:152
KDTree::KDTree::_M_check_children
void _M_check_children(_Link_const_type child, _Link_const_type parent, size_type const level, bool to_the_left)
Definition: KDTree.h:1593
KDTree::_Node_base::_Node_base
_Node_base(_Base_ptr const __PARENT=nullptr, _Base_ptr const __LEFT=nullptr, _Base_ptr const __RIGHT=nullptr)
Definition: KDTree.h:82
KDTree::KDTree::value_distance
_Dist & value_distance()
Definition: KDTree.h:1269
KDTree::KDTree::_Base_const_ptr
_Node_base const * _Base_const_ptr
Definition: KDTree.h:1085
KDTree::KDTree::allocator_type
_Base::allocator_type allocator_type
Definition: KDTree.h:1082
KDTree::KDTree::visit_within_range
Visitor visit_within_range(SearchVal const &V, subvalue_type const R, Visitor visitor) const
Definition: KDTree.h:1436
KDTree::KDTree::_S_right
static _Link_const_type _S_right(_Base_const_ptr N)
Definition: KDTree.h:2108
KDTree::KDTree::_M_empty_initialise
void _M_empty_initialise()
Definition: KDTree.h:1625
KDTree::KDTree::_M_matches_node
bool _M_matches_node(_Link_const_type __N, const_reference __V, size_type __L=0) const
Definition: KDTree.h:1901
KDTree::_Alloc_base::_Base_ptr
_Node_::_Base_ptr _Base_ptr
Definition: KDTree.h:525
KDTree::_Node::_Node
_Node(_Val const &__VALUE=_Val(), _Base_ptr const __PARENT=nullptr, _Base_ptr const __LEFT=nullptr, _Base_ptr const __RIGHT=nullptr)
Definition: KDTree.h:110
KDTree::KDTree::_S_parent
static _Link_const_type _S_parent(_Base_const_ptr N)
Definition: KDTree.h:2066
KDTree::KDTree::find_nearest
std::pair< const_iterator, distance_type > find_nearest(SearchVal const &__val, distance_type __max) const
Definition: KDTree.h:1511
KDTree::squared_difference_counted::distance_type
_Dist distance_type
Definition: KDTree.h:465
KDTree::_Iterator::operator->
pointer operator->() const
Definition: KDTree.h:744
KDTree::_Region::_M_cmp
_Cmp _M_cmp
Definition: KDTree.h:966
KDTree::KDTree::operator=
KDTree & operator=(const KDTree &__x)
Definition: KDTree.h:1178
KDTree::KDTree::_M_set_leftmost
void _M_set_leftmost(_Node_base *a)
Definition: KDTree.h:2042
KDTree::_Iterator::_Link_const_type
_Node< _Val > const * _Link_const_type
Definition: KDTree.h:721
KDTree::_Alloc_base::NoLeakAlloc::NoLeakAlloc
NoLeakAlloc(_Alloc_base *b)
Definition: KDTree.h:544
KDTree::_S_accumulate_node_distance
_Dist::distance_type _S_accumulate_node_distance(const size_t __dim, const _Dist &__dist, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
Definition: KDTree.h:210
KDTree::KDTree::max_size
size_type max_size() const
Definition: KDTree.h:1219
KDTree::_Node::_Link_type
_Node * _Link_type
Definition: KDTree.h:106
KDTree::_Node_compare::operator()
bool operator()(_Val const &__A, _Val const &__B) const
Definition: KDTree.h:156
KDTree::KDTree::KDTree
KDTree(_InputIterator __first, _InputIterator __last, _Acc const &acc=_Acc(), _Dist const &__dist=_Dist(), _Cmp const &__cmp=_Cmp(), const allocator_type &__a=allocator_type())
Definition: KDTree.h:1131
KDTree::_Node_base
Definition: KDTree.h:73
KDTree::_S_node_distance
_Dist::distance_type _S_node_distance(const size_t __dim, const _Dist &__dist, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
Definition: KDTree.h:193
KDTree::_Node_compare::_M_cmp
_Cmp _M_cmp
Definition: KDTree.h:164
KDTree::_Bracket_accessor::operator()
result_type operator()(_Val const &V, size_t const N) const
Definition: KDTree.h:437
KDTree::KDTree::_M_get_erase_replacement
_Link_type _M_get_erase_replacement(_Link_type node, size_type const level)
Definition: KDTree.h:1715
KDTree::KDTree::insert
iterator insert(const_reference __V)
Definition: KDTree.h:1294
KDTree::_S_node_compare
bool _S_node_compare(const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
Definition: KDTree.h:177
KDTree::KDTree::_S_left
static _Link_type _S_left(_Base_ptr N)
Definition: KDTree.h:2084
KDTree::KDTree::size
size_type size() const
Definition: KDTree.h:1213
KDTree::KDTree::_Node_compare_
_Node_compare< _Val, _Acc, _Cmp > _Node_compare_
Definition: KDTree.h:1089
KDTree::_Region::_M_low_bounds
subvalue_type _M_low_bounds[__K]
Definition: KDTree.h:964
KDTree::KDTree::_M_get_rightmost
_Link_const_type _M_get_rightmost() const
Definition: KDTree.h:2048
KDTree::KDTree::_S_value
static const_reference _S_value(_Base_const_ptr N)
Definition: KDTree.h:2126
KDTree::_Alloc_base::_M_node_allocator
allocator_type _M_node_allocator
Definition: KDTree.h:554
KDTree::_Iterator::operator--
_Self operator--(int)
Definition: KDTree.h:772
KDTree::_Region::_Region
_Region(Val const &__V, _Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:886
KDTree::KDTree::erase
void erase(const_reference __V)
Definition: KDTree.h:1339
KDTree::KDTree::_S_maximum
static _Link_const_type _S_maximum(_Link_const_type __X)
Definition: KDTree.h:2138
KDTree::KDTree::_S_left
static _Link_const_type _S_left(_Base_const_ptr N)
Definition: KDTree.h:2090
KDTree::KDTree::_M_erase_subtree
void _M_erase_subtree(_Link_type __n)
Definition: KDTree.h:1823
KDTree::KDTree::_M_get_leftmost
_Link_const_type _M_get_leftmost() const
Definition: KDTree.h:2036
KDTree::_Iterator::value_type
_Val value_type
Definition: KDTree.h:715
KDTree::KDTree::_M_get_j_max
std::pair< _Link_type, size_type > _M_get_j_max(std::pair< _Link_type, size_type > const node, size_type const level)
Definition: KDTree.h:1793
KDTree::_Node_compare
Definition: KDTree.h:149
KDTree::KDTree::_M_get_root
_Link_type _M_get_root()
Definition: KDTree.h:2025
KDTree::KDTree::_M_insert_right
iterator _M_insert_right(_Link_type __N, const_reference __V)
Definition: KDTree.h:1644
KDTree::_S_node_nearest
std::pair< const NodeType *, std::pair< size_t, typename _Dist::distance_type > > _S_node_nearest(const size_t __k, size_t __dim, SearchVal const &__val, const NodeType *__node, const _Node_base *__end, const NodeType *__best, typename _Dist::distance_type __max, const _Cmp &__cmp, const _Acc &__acc, const _Dist &__dist, _Predicate __p)
Definition: KDTree.h:252
KDTree::KDTree::_M_root
_Link_type _M_root
Definition: KDTree.h:2174
KDTree::KDTree::_M_optimise
void _M_optimise(_Iter const &__A, _Iter const &__B, size_type const __L)
Definition: KDTree.h:2006
KDTree::KDTree::_M_find_exact
const_iterator _M_find_exact(_Link_const_type node, const_reference value, size_type const level) const
Definition: KDTree.h:1858
KDTree::KDTree::count_within_range
size_type count_within_range(_Region_ const &__REGION) const
Definition: KDTree.h:1424
KDTree::_Base_iterator::_M_node
_Base_const_ptr _M_node
Definition: KDTree.h:650
KDTree::KDTree::_M_header
_Node_base _M_header
Definition: KDTree.h:2175
KDTree::KDTree::check_tree
void check_tree()
Definition: KDTree.h:1586
KDTree::operator==
bool operator==(_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
Definition: KDTree.h:806
KDTree::always_true::operator()
bool operator()(const _Tp &) const
Definition: KDTree.h:446