OpenMS  2.8.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-2021.
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 MERCHANTABILITY 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 {
76  typedef _Node_base const* _Base_const_ptr;
77 
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
89  {
90  while (__x->_M_left) __x = __x->_M_left;
91  return __x;
92  }
93 
94  static _Base_ptr
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>
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 MERCHANTABILITY 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>
433 {
434  typedef typename _Val::value_type result_type;
435 
437  operator()(_Val const& V, size_t const N) const
438  {
439  return V[N];
440  }
441 };
442 
443 template <typename _Tp>
445 {
446  bool operator() (const _Tp& ) const { return true; }
447 };
448 
449 template <typename _Tp, typename _Dist>
451 {
452  typedef _Dist distance_type;
453 
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>
464 {
465  typedef _Dist distance_type;
466 
468  : _M_count(0)
469  { }
470 
471  void reset ()
472  { _M_count = 0; }
473 
474  long&
475  count () const
476  { return _M_count; }
477 
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 MERCHANTABILITY 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>
522 {
523 public:
525  typedef typename _Node_::_Base_ptr _Base_ptr;
526  typedef _Alloc allocator_type;
527 
529  : _M_node_allocator(__A) {}
530 
533  {
534  return _M_node_allocator;
535  }
536 
537 
539  {
542 
543  public:
545 
546  _Node_ * get() { return new_node; }
547  void disconnect() { new_node = nullptr; }
548 
550  };
551 
552 
553 protected:
555 
556  _Node_*
558  {
559  return _M_node_allocator.allocate(1);
560  }
561 
562  void
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
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 MERCHANTABILITY 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 
647 {
648 protected:
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
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 segfault, similar to standard iterator.
675  _M_node = __p;
676  }
677  }
678 
679  inline void
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 segfault, 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;
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 
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
751  {
752  _M_increment();
753  return *this;
754  }
755 
756  _Self
758  {
759  _Self ret = *this;
760  _M_increment();
761  return ret;
762  }
763 
764  _Self&
766  {
767  _M_decrement();
768  return *this;
769  }
770 
771  _Self
773  {
774  _Self ret = *this;
775  _M_decrement();
776  return ret;
777  }
778 
779  friend bool
780  operator== <>(_Iterator<_Val, _Ref, _Ptr> const&,
782 
783  friend bool
784  operator== <>(_Iterator<_Val, const _Val&, const _Val*> const&,
786 
787  friend bool
788  operator== <>(_Iterator<_Val, _Val&, _Val*> const&,
790 
791  friend bool
792  operator!= <>(_Iterator<_Val, _Ref, _Ptr> const&,
794 
795  friend bool
796  operator!= <>(_Iterator<_Val, const _Val&, const _Val*> const&,
798 
799  friend bool
800  operator!= <>(_Iterator<_Val, _Val&, _Val*> const&,
802 };
803 
804 template<typename _Val, typename _Ref, typename _Ptr>
805 bool
807  _Iterator<_Val, _Ref, _Ptr> const& __Y)
808 { return __X._M_node == __Y._M_node; }
809 
810 template<typename _Val>
811 bool
814 { return __X._M_node == __Y._M_node; }
815 
816 template<typename _Val>
817 bool
820 { return __X._M_node == __Y._M_node; }
821 
822 template<typename _Val, typename _Ref, typename _Ptr>
823 bool
825  _Iterator<_Val, _Ref, _Ptr> const& __Y)
826 { return __X._M_node != __Y._M_node; }
827 
828 template<typename _Val>
829 bool
832 { return __X._M_node != __Y._M_node; }
833 
834 template<typename _Val>
835 bool
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 MERCHANTABILITY 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 
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 MERCHANTABILITY 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:
1083 
1085  typedef _Node_base const* _Base_const_ptr;
1088 
1090 
1091 public:
1093  typedef _Val value_type;
1095  typedef value_type const* const_pointer;
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 
1202  {
1203  this->clear();
1204  }
1205 
1206  allocator_type
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
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&
1266  { return _M_dist; }
1267 
1268  _Dist&
1270  { return _M_dist; }
1271 
1272  // typedef _Iterator<_Val, reference, pointer> iterator;
1274  // No mutable iterator at this stage
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 convertible to a _Link_type), but
1280  // that's 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)); }
1286 
1287  iterator
1288  insert(iterator /* ignored */, const_reference __V)
1289  {
1290  return this->insert(__V);
1291  }
1292 
1293  iterator
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
1340  const_iterator b = this->find(__V);
1341  this->erase(b);
1342  }
1343 
1344  void
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 comparisons,
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  // e.g.
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
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
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,
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,
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
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
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 
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
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
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
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 substitute...
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
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
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
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
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
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
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
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
2026  {
2027  return _M_root;
2028  }
2029 
2031  {
2032  _M_root = n;
2033  }
2034 
2035  _Link_const_type
2037  {
2038  return static_cast<_Link_type>(_M_header._M_left);
2039  }
2040 
2041  void
2043  {
2044  _M_header._M_left = a;
2045  }
2046 
2047  _Link_const_type
2049  {
2050  return static_cast<_Link_type>( _M_header._M_right );
2051  }
2052 
2053  void
2055  {
2056  _M_header._M_right = a;
2057  }
2058 
2059  static _Link_type
2061  {
2062  return static_cast<_Link_type>( N->_M_parent );
2063  }
2064 
2065  static _Link_const_type
2067  {
2068  return static_cast<_Link_const_type>( N->_M_parent );
2069  }
2070 
2071  static void
2073  {
2074  N->_M_parent = p;
2075  }
2076 
2077  static void
2079  {
2080  N->_M_left = l;
2081  }
2082 
2083  static _Link_type
2085  {
2086  return static_cast<_Link_type>( N->_M_left );
2087  }
2088 
2089  static _Link_const_type
2091  {
2092  return static_cast<_Link_const_type>( N->_M_left );
2093  }
2094 
2095  static void
2097  {
2098  N->_M_right = r;
2099  }
2100 
2101  static _Link_type
2103  {
2104  return static_cast<_Link_type>( N->_M_right );
2105  }
2106 
2107  static _Link_const_type
2109  {
2110  return static_cast<_Link_const_type>( N->_M_right );
2111  }
2112 
2113  static bool
2115  {
2116  return !_S_left(N) && !_S_right(N);
2117  }
2118 
2119  static const_reference
2121  {
2122  return N->_M_value;
2123  }
2124 
2125  static const_reference
2127  {
2128  return static_cast<_Link_const_type>(N)->_M_value;
2129  }
2130 
2131  static _Link_const_type
2133  {
2134  return static_cast<_Link_const_type> ( _Node_base::_S_minimum(__X) );
2135  }
2136 
2137  static _Link_const_type
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
2169  {
2170  _Base::_M_destroy_node(__p);
2171  _Base::_M_deallocate_node(__p);
2172  }
2173 
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,
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 
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 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
2233  */
Definition: KDTree.h:1079
static _Link_type _S_left(_Base_ptr N)
Definition: KDTree.h:2084
KDTree(const KDTree &__x)
Definition: KDTree.h:1111
bool _M_matches_node_in_other_ds(_Link_const_type __N, const_reference __V, size_type const __L=0) const
Definition: KDTree.h:1891
iterator insert(iterator, const_reference __V)
Definition: KDTree.h:1288
_OutputIterator find_within_range(SearchVal const &val, subvalue_type const range, _OutputIterator out) const
Definition: KDTree.h:1467
bool _M_matches_node_in_d(_Link_const_type __N, const_reference __V, size_type const __L) const
Definition: KDTree.h:1883
const_reverse_iterator rend() const
Definition: KDTree.h:1285
void efficient_replace_and_optimise(std::vector< value_type > &writable_vector)
Definition: KDTree.h:1169
void erase_exact(const_reference __V)
Definition: KDTree.h:1345
void erase(const_reference __V)
Definition: KDTree.h:1339
_Node_compare< _Val, _Acc, _Cmp > _Node_compare_
Definition: KDTree.h:1089
bool _M_matches_node(_Link_const_type __N, const_reference __V, size_type __L=0) const
Definition: KDTree.h:1901
static _Link_const_type _S_maximum(_Link_const_type __X)
Definition: KDTree.h:2138
Visitor visit_within_range(_Region_ const &REGION, Visitor visitor) const
Definition: KDTree.h:1445
_Link_const_type _M_get_rightmost() const
Definition: KDTree.h:2048
iterator _M_insert_left(_Link_type __N, const_reference __V)
Definition: KDTree.h:1634
static void _S_set_parent(_Base_ptr N, _Base_ptr p)
Definition: KDTree.h:2072
value_type const * const_pointer
Definition: KDTree.h:1095
void check_tree()
Definition: KDTree.h:1586
static _Link_const_type _S_minimum(_Link_const_type __X)
Definition: KDTree.h:2132
static void _S_set_left(_Base_ptr N, _Base_ptr l)
Definition: KDTree.h:2078
const_iterator begin() const
Definition: KDTree.h:1282
void _M_set_root(_Link_type n)
Definition: KDTree.h:2030
_Link_type _M_get_root()
Definition: KDTree.h:2025
iterator _M_insert(_Link_type __N, const_reference __V, size_type const __L)
Definition: KDTree.h:1654
void optimise()
Definition: KDTree.h:1573
void _M_delete_node(_Link_type __p)
Definition: KDTree.h:2168
_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
_Node< _Val > const * _Link_const_type
Definition: KDTree.h:1087
KDTree & operator=(const KDTree &__x)
Definition: KDTree.h:1178
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: KDTree.h:1276
_Link_type _M_get_erase_replacement(_Link_type node, size_type const level)
Definition: KDTree.h:1715
static _Link_const_type _S_parent(_Base_const_ptr N)
Definition: KDTree.h:2066
size_t size_type
Definition: KDTree.h:1100
size_type count_within_range(const_reference __V, subvalue_type const __R) const
Definition: KDTree.h:1416
_Node_base * _Base_ptr
Definition: KDTree.h:1084
std::pair< const_iterator, distance_type > find_nearest(SearchVal const &__val, distance_type __max) const
Definition: KDTree.h:1511
void _M_empty_initialise()
Definition: KDTree.h:1625
size_type size() const
Definition: KDTree.h:1213
_Dist _M_dist
Definition: KDTree.h:2179
bool empty() const
Definition: KDTree.h:1225
void _M_erase_subtree(_Link_type __n)
Definition: KDTree.h:1823
_Node< _Val > * _Link_type
Definition: KDTree.h:1086
value_type const & const_reference
Definition: KDTree.h:1097
allocator_type get_allocator() const
Definition: KDTree.h:1207
_Link_type _M_erase(_Link_type dead_dad, size_type const level)
Definition: KDTree.h:1672
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
iterator insert(const_reference __V)
Definition: KDTree.h:1294
static _Link_const_type _S_right(_Base_const_ptr N)
Definition: KDTree.h:2108
Visitor visit_within_range(SearchVal const &V, subvalue_type const R, Visitor visitor) const
Definition: KDTree.h:1436
const_iterator find(SearchVal const &__V) const
Definition: KDTree.h:1386
void _M_check_node(_Link_const_type node, size_type const level)
Definition: KDTree.h:1610
void insert(iterator __pos, _InputIterator __first, _InputIterator __last)
Definition: KDTree.h:1323
_Node_base _M_header
Definition: KDTree.h:2175
void _M_optimise(_Iter const &__A, _Iter const &__B, size_type const __L)
Definition: KDTree.h:2006
size_type count_within_range(_Region_ const &__REGION) const
Definition: KDTree.h:1424
_Base::allocator_type allocator_type
Definition: KDTree.h:1082
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
std::reverse_iterator< iterator > reverse_iterator
Definition: KDTree.h:1277
size_type max_size() const
Definition: KDTree.h:1219
~KDTree()
Definition: KDTree.h:1201
_Alloc_base< _Val, _Alloc > _Base
Definition: KDTree.h:1081
static _Link_const_type _S_left(_Base_const_ptr N)
Definition: KDTree.h:2090
std::pair< const_iterator, distance_type > find_nearest(SearchVal const &__val) const
Definition: KDTree.h:1491
_Cmp value_comp() const
Comparator for the values in the KDTree.
Definition: KDTree.h:1246
_Acc _M_acc
Definition: KDTree.h:2177
void erase(const_iterator const &__IT)
Definition: KDTree.h:1351
void insert(iterator __pos, size_type __n, const value_type &__x)
Definition: KDTree.h:1315
void _M_set_leftmost(_Node_base *a)
Definition: KDTree.h:2042
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
void insert(_InputIterator __first, _InputIterator __last)
Definition: KDTree.h:1309
void optimize()
Definition: KDTree.h:1581
_Link_const_type _M_get_leftmost() const
Definition: KDTree.h:2036
_Node_base const * _Base_const_ptr
Definition: KDTree.h:1085
static bool _S_is_leaf(_Base_const_ptr N)
Definition: KDTree.h:2114
_Val value_type
Definition: KDTree.h:1093
const_iterator _M_find(_Link_const_type node, const_reference value, size_type const level) const
Definition: KDTree.h:1835
static const_reference _S_value(_Link_const_type N)
Definition: KDTree.h:2120
value_type & reference
Definition: KDTree.h:1096
void _M_check_children(_Link_const_type child, _Link_const_type parent, size_type const level, bool to_the_left)
Definition: KDTree.h:1593
_Acc value_acc() const
Accessor to the value's elements.
Definition: KDTree.h:1255
_Link_type _M_root
Definition: KDTree.h:2174
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
const _Dist & value_distance() const
Distance calculator between 2 value's element.
Definition: KDTree.h:1265
void clear()
Definition: KDTree.h:1231
const_iterator iterator
Definition: KDTree.h:1275
const_iterator end() const
Definition: KDTree.h:1283
ptrdiff_t difference_type
Definition: KDTree.h:1101
value_type * pointer
Definition: KDTree.h:1094
size_type _M_count
Definition: KDTree.h:2176
_Cmp _M_cmp
Definition: KDTree.h:2178
_Iterator< _Val, const_reference, const_pointer > const_iterator
Definition: KDTree.h:1273
std::pair< const_iterator, distance_type > find_nearest_if(SearchVal const &__val, distance_type __max, _Predicate __p) const
Definition: KDTree.h:1541
iterator _M_insert_right(_Link_type __N, const_reference __V)
Definition: KDTree.h:1644
_Dist & value_distance()
Definition: KDTree.h:1269
static void _S_set_right(_Base_ptr N, _Base_ptr r)
Definition: KDTree.h:2096
_Region< __K, _Val, typename _Acc::result_type, _Acc, _Cmp > _Region_
Definition: KDTree.h:1092
KDTree(_Acc const &__acc=_Acc(), _Dist const &__dist=_Dist(), _Cmp const &__cmp=_Cmp(), const allocator_type &__a=allocator_type())
Definition: KDTree.h:1103
_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
const_iterator find_exact(SearchVal const &__V) const
Definition: KDTree.h:1408
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
_Link_const_type _M_get_root() const
Definition: KDTree.h:2019
const_iterator _M_find_exact(_Link_const_type node, const_reference value, size_type const level) const
Definition: KDTree.h:1858
const_reverse_iterator rbegin() const
Definition: KDTree.h:1284
static _Link_type _S_parent(_Base_ptr N)
Definition: KDTree.h:2060
void _M_set_rightmost(_Node_base *a)
Definition: KDTree.h:2054
static _Link_type _S_right(_Base_ptr N)
Definition: KDTree.h:2102
_Dist::distance_type distance_type
Definition: KDTree.h:1099
_Acc::result_type subvalue_type
Definition: KDTree.h:1098
_OutputIterator find_within_range(_Region_ const &region, _OutputIterator out) const
Definition: KDTree.h:1477
static const_reference _S_value(_Base_const_ptr N)
Definition: KDTree.h:2126
Definition: KDTree.h:539
_Node_ * new_node
Definition: KDTree.h:541
~NoLeakAlloc()
Definition: KDTree.h:549
void disconnect()
Definition: KDTree.h:547
NoLeakAlloc(_Alloc_base *b)
Definition: KDTree.h:544
_Node_ * get()
Definition: KDTree.h:546
_Alloc_base * base
Definition: KDTree.h:540
Definition: KDTree.h:522
_Node_::_Base_ptr _Base_ptr
Definition: KDTree.h:525
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
_Node< _Tp > _Node_
Definition: KDTree.h:524
_Alloc_base(allocator_type const &__A)
Definition: KDTree.h:528
allocator_type get_allocator() const
Definition: KDTree.h:532
void _M_deallocate_node(_Node_ *const __P)
Definition: KDTree.h:563
_Alloc allocator_type
Definition: KDTree.h:526
_Node_ * _M_allocate_node()
Definition: KDTree.h:557
void _M_destroy_node(_Node_ *__p)
Definition: KDTree.h:578
allocator_type _M_node_allocator
Definition: KDTree.h:554
Definition: KDTree.h:647
void _M_decrement()
Definition: KDTree.h:680
_Base_iterator(_Base_iterator const &__THAT)
Definition: KDTree.h:654
_Node_base::_Base_const_ptr _Base_const_ptr
Definition: KDTree.h:649
_Base_const_ptr _M_node
Definition: KDTree.h:650
_Base_iterator(_Base_const_ptr const __N=nullptr)
Definition: KDTree.h:652
void _M_increment()
Definition: KDTree.h:658
Definition: KDTree.h:713
_Iterator< _Val, _Ref, _Ptr > _Self
Definition: KDTree.h:720
std::bidirectional_iterator_tag iterator_category
Definition: KDTree.h:722
_Iterator< _Val, _Val &, _Val * > iterator
Definition: KDTree.h:718
_Self & operator--()
Definition: KDTree.h:765
_Ptr pointer
Definition: KDTree.h:717
_Node< _Val > const * _Link_const_type
Definition: KDTree.h:721
_Self operator++(int)
Definition: KDTree.h:757
_Iterator(_Link_const_type const __N)
Definition: KDTree.h:727
_Link_const_type get_raw_node() const
Definition: KDTree.h:732
_Iterator(iterator const &__THAT)
Definition: KDTree.h:729
_Ref reference
Definition: KDTree.h:716
_Self operator++()
Definition: KDTree.h:750
_Iterator< _Val, _Val const &, _Val const * > const_iterator
Definition: KDTree.h:719
reference operator*() const
Definition: KDTree.h:738
_Val value_type
Definition: KDTree.h:715
_Iterator()
Definition: KDTree.h:725
ptrdiff_t difference_type
Definition: KDTree.h:723
_Self operator--(int)
Definition: KDTree.h:772
pointer operator->() const
Definition: KDTree.h:744
Definition: KDTree.h:150
bool operator()(_Val const &__A, _Val const &__B) const
Definition: KDTree.h:156
_Node_compare(size_t const __DIM, _Acc const &acc, _Cmp const &cmp)
Definition: KDTree.h:152
_Acc _M_acc
Definition: KDTree.h:163
_Cmp _M_cmp
Definition: KDTree.h:164
size_t _M_DIM
Definition: KDTree.h:162
Definition: KDTree.h:72
bool _S_node_compare(const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
Definition: KDTree.h:177
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
bool operator==(_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
Definition: KDTree.h:806
bool operator!=(_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
Definition: KDTree.h:824
_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
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
_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
const double R
Definition: Constants.h:170
std::ostream & operator<<(std::ostream &os, const AccurateMassSearchResult &amsr)
Definition: KDTree.h:433
result_type operator()(_Val const &V, size_t const N) const
Definition: KDTree.h:437
_Val::value_type result_type
Definition: KDTree.h:434
Definition: KDTree.h:74
_Node_base * _Base_ptr
Definition: KDTree.h:75
_Base_ptr _M_parent
Definition: KDTree.h:78
static _Base_ptr _S_minimum(_Base_ptr __x)
Definition: KDTree.h:88
_Base_ptr _M_right
Definition: KDTree.h:80
_Node_base const * _Base_const_ptr
Definition: KDTree.h:76
static _Base_ptr _S_maximum(_Base_ptr __x)
Definition: KDTree.h:95
_Base_ptr _M_left
Definition: KDTree.h:79
_Node_base(_Base_ptr const __PARENT=nullptr, _Base_ptr const __LEFT=nullptr, _Base_ptr const __RIGHT=nullptr)
Definition: KDTree.h:82
Definition: KDTree.h:104
_Node(_Val const &__VALUE=_Val(), _Base_ptr const __PARENT=nullptr, _Base_ptr const __LEFT=nullptr, _Base_ptr const __RIGHT=nullptr)
Definition: KDTree.h:110
_Val _M_value
Definition: KDTree.h:108
_Node * _Link_type
Definition: KDTree.h:106
Definition: KDTree.h:873
_Region & set_low_bound(value_type const &__V, size_t const __L)
Definition: KDTree.h:958
bool encloses(value_type const &__V) const
Definition: KDTree.h:939
bool intersects_with(_Region const &__THAT) const
Definition: KDTree.h:927
_Region(_Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:882
_SubVal subvalue_type
Definition: KDTree.h:875
_Region(Val const &__V, subvalue_type const &__R, _Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:897
_Acc _M_acc
Definition: KDTree.h:965
std::pair< _Region, _SubVal > _CenterPt
Definition: KDTree.h:880
_Val value_type
Definition: KDTree.h:874
_Region & set_high_bound(value_type const &__V, size_t const __L)
Definition: KDTree.h:951
subvalue_type _M_low_bounds[__K]
Definition: KDTree.h:964
_Cmp _M_cmp
Definition: KDTree.h:966
bool intersects_with(_CenterPt const &__THAT) const
Definition: KDTree.h:909
subvalue_type _M_high_bounds[__K]
Definition: KDTree.h:964
_Region(Val const &__V, _Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:886
Definition: KDTree.h:445
bool operator()(const _Tp &) const
Definition: KDTree.h:446
Definition: KDTree.h:464
distance_type operator()(const _Tp &__a, const _Tp &__b) const
Definition: KDTree.h:479
long _M_count
Definition: KDTree.h:487
squared_difference_counted()
Definition: KDTree.h:467
long & count() const
Definition: KDTree.h:475
void reset()
Definition: KDTree.h:471
_Dist distance_type
Definition: KDTree.h:465
Definition: KDTree.h:451
distance_type operator()(const _Tp &__a, const _Tp &__b) const
Definition: KDTree.h:455
_Dist distance_type
Definition: KDTree.h:452