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