61 #ifndef OPENMS_DATASTRUCTURES_KDTREE_H 62 #define OPENMS_DATASTRUCTURES_KDTREE_H 64 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS 83 _Base_ptr
const __LEFT = NULL,
84 _Base_ptr
const __RIGHT = NULL)
85 : _M_parent(__PARENT), _M_left(__LEFT), _M_right(__RIGHT) {}
102 template <
typename _Val>
114 :
_Node_base(__PARENT, __LEFT, __RIGHT), _M_value(__VALUE) {}
116 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS 118 template <
typename Char,
typename Traits>
120 std::basic_ostream<Char, Traits>&
121 operator<<(typename std::basic_ostream<Char, Traits>& out,
125 out <<
" parent: " << node._M_parent;
126 out <<
"; left: " << node._M_left;
127 out <<
"; right: " << node._M_right;
131 template <
typename Char,
typename Traits>
133 std::basic_ostream<Char, Traits>&
134 operator<<(typename std::basic_ostream<Char, Traits>& out,
138 out <<
' ' << node._M_value;
139 out <<
"; parent: " << node._M_parent;
140 out <<
"; left: " << node._M_left;
141 out <<
"; right: " << node._M_right;
148 template <
typename _Val,
typename _Acc,
typename _Cmp>
153 : _M_DIM(__DIM), _M_acc(acc), _M_cmp(cmp) {}
158 return _M_cmp(_M_acc(__A, _M_DIM), _M_acc(__B, _M_DIM));
173 template <
typename _ValA,
typename _ValB,
typename _Cmp,
178 const _Cmp& __cmp,
const _Acc& __acc,
179 const _ValA& __a,
const _ValB& __b)
181 return __cmp(__acc(__a, __dim), __acc(__b, __dim));
189 template <
typename _ValA,
typename _ValB,
typename _Dist,
192 typename _Dist::distance_type
194 const _Dist& __dist,
const _Acc& __acc,
195 const _ValA& __a,
const _ValB& __b)
197 return __dist(__acc(__a, __dim), __acc(__b, __dim));
206 template <
typename _ValA,
typename _ValB,
typename _Dist,
209 typename _Dist::distance_type
211 const _Dist& __dist,
const _Acc& __acc,
212 const _ValA& __a,
const _ValB& __b)
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));
225 template <
typename _Val,
typename _Cmp,
typename _Acc,
typename NodeType>
229 const _Cmp& __cmp,
const _Acc& __acc,
230 const _Val& __val,
const NodeType* __node)
233 return static_cast<const NodeType *
>(__node->_M_left);
234 return static_cast<const NodeType *
>(__node->_M_right);
245 template <
class SearchVal,
246 typename NodeType,
typename _Cmp,
247 typename _Acc,
typename _Dist,
250 std::pair<
const NodeType*,
251 std::pair<size_t, typename _Dist::distance_type> >
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,
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;
265 if (__p(cur->_M_value))
267 typename _Dist::distance_type d = 0;
268 for (
size_t i=0; i != __k; ++i)
292 NodePtr pprobe = probe;
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);
299 near_node =
static_cast<NodePtr
>(probe->_M_left);
302 && (std::sqrt(
_S_node_distance(probe_dim % __k, __dist, __acc, __val, probe->_M_value)) <= __max))
311 if (
_S_node_compare(probe_dim % __k, __cmp, __acc, __val, probe->_M_value))
313 near_node =
static_cast<NodePtr
>(probe->_M_left);
314 far_node =
static_cast<NodePtr
>(probe->_M_right);
318 near_node =
static_cast<NodePtr
>(probe->_M_right);
319 far_node =
static_cast<NodePtr
>(probe->_M_left);
321 if (pprobe == probe->_M_parent)
323 if (__p(probe->_M_value))
325 typename _Dist::distance_type d = 0;
326 for (
size_t i=0; i < __k; ++i)
344 std::sqrt(
_S_node_distance(probe_dim % __k, __dist, __acc, __val, probe->_M_value)) <= __max)
351 probe =
static_cast<NodePtr
>(probe->_M_parent);
357 if (pprobe == near_node && far_node
359 && std::sqrt(
_S_node_distance(probe_dim % __k, __dist, __acc, __val, probe->_M_value)) <= __max)
368 probe =
static_cast<NodePtr
>(probe->_M_parent);
374 cur =
static_cast<NodePtr
>(cur->_M_parent);
381 if (pcur == cur->_M_left)
382 near_node =
static_cast<NodePtr
>(cur->_M_right);
384 near_node =
static_cast<NodePtr
>(cur->_M_left);
387 && (std::sqrt(
_S_node_distance(cur_dim % __k, __dist, __acc, __val, cur->_M_value)) <= __max))
394 return std::pair<NodePtr,
395 std::pair<size_t, typename _Dist::distance_type> >
396 (__best, std::pair<size_t, typename _Dist::distance_type>
403 #endif // include guard 424 #ifndef INCLUDE_KDTREE_ACCESSOR_HPP 425 #define INCLUDE_KDTREE_ACCESSOR_HPP 431 template <
typename _Val>
443 template <
typename _Tp>
446 bool operator() (
const _Tp& )
const {
return true; }
449 template <
typename _Tp,
typename _Dist>
455 operator() (
const _Tp& __a,
const _Tp& __b)
const 457 distance_type d=__a - __b;
462 template <
typename _Tp,
typename _Dist>
479 operator() (
const _Tp& __a,
const _Tp& __b)
const 481 distance_type d=__a - __b;
492 #endif // include guard 512 #ifndef INCLUDE_KDTREE_ALLOCATOR_HPP 513 #define INCLUDE_KDTREE_ALLOCATOR_HPP 520 template <
typename _Tp,
typename _Alloc>
529 : _M_node_allocator(__A) {}
534 return _M_node_allocator;
546 _Node_ *
get() {
return new_node; }
559 return _M_node_allocator.allocate(1);
565 return _M_node_allocator.deallocate(__P, 1);
570 _Base_ptr
const __PARENT = NULL,
571 _Base_ptr
const __LEFT = NULL,
572 _Base_ptr
const __RIGHT = NULL)
574 new (__p) _Node_(__V, __PARENT, __LEFT, __RIGHT);
580 _M_node_allocator.destroy(__p);
586 #endif // include guard 606 #ifndef INCLUDE_KDTREE_ITERATOR_HPP 607 #define INCLUDE_KDTREE_ITERATOR_HPP 613 template <
typename _Val,
typename _Ref,
typename _Ptr>
616 template<
typename _Val,
typename _Ref,
typename _Ptr>
621 template<
typename _Val>
626 template<
typename _Val>
631 template<
typename _Val,
typename _Ref,
typename _Ptr>
636 template<
typename _Val>
641 template<
typename _Val>
655 : _M_node(__THAT._M_node) {}
660 if (_M_node->_M_right)
662 _M_node = _M_node->_M_right;
663 while (_M_node->_M_left) _M_node = _M_node->_M_left;
667 _Base_const_ptr __p = _M_node->_M_parent;
668 while (__p && _M_node == __p->_M_right)
671 __p = _M_node->_M_parent;
682 if (!_M_node->_M_parent)
684 _M_node = _M_node->_M_right;
686 else if (_M_node->_M_left)
688 _Base_const_ptr x = _M_node->_M_left;
689 while (x->_M_right) x = x->_M_right;
694 _Base_const_ptr __p = _M_node->_M_parent;
695 while (__p && _M_node == __p->_M_left)
698 __p = _M_node->_M_parent;
706 template <
size_t const __K,
typename _Val,
typename _Acc,
707 typename _Dist,
typename _Cmp,
typename _Alloc>
711 template <
typename _Val,
typename _Ref,
typename _Ptr>
734 return _Link_const_type(_M_node);
740 return _Link_const_type(_M_node)->_M_value;
804 template<
typename _Val,
typename _Ref,
typename _Ptr>
810 template<
typename _Val>
816 template<
typename _Val>
822 template<
typename _Val,
typename _Ref,
typename _Ptr>
828 template<
typename _Val>
834 template<
typename _Val>
842 #endif // include guard 862 #ifndef INCLUDE_KDTREE_REGION_HPP 863 #define INCLUDE_KDTREE_REGION_HPP 870 template <
size_t const __K,
typename _Val,
typename _SubVal,
871 typename _Acc,
typename _Cmp>
882 _Region(_Acc
const& __acc=_Acc(),
const _Cmp& __cmp=_Cmp())
883 : _M_acc(__acc), _M_cmp(__cmp) {}
885 template <
typename Val>
887 _Acc
const& __acc=_Acc(),
const _Cmp& __cmp=_Cmp())
888 : _M_acc(__acc), _M_cmp(__cmp)
890 for (
size_t __i = 0; __i != __K; ++__i)
892 _M_low_bounds[__i] = _M_high_bounds[__i] = _M_acc(__V,__i);
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)
901 for (
size_t __i = 0; __i != __K; ++__i)
903 _M_low_bounds[__i] = _M_acc(__V,__i) - __R;
904 _M_high_bounds[__i] = _M_acc(__V,__i) + __R;
911 for (
size_t __i = 0; __i != __K; ++__i)
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]))
929 for (
size_t __i = 0; __i != __K; ++__i)
941 for (
size_t __i = 0; __i != __K; ++__i)
943 if (_M_cmp(_M_acc(__V, __i), _M_low_bounds[__i])
944 || _M_cmp(_M_high_bounds[__i], _M_acc(__V, __i)))
953 _M_high_bounds[__L % __K] = _M_acc(__V, __L % __K);
960 _M_low_bounds[__L % __K] = _M_acc(__V, __L % __K);
964 subvalue_type _M_low_bounds[__K], _M_high_bounds[__K];
971 #endif // include guard 1030 #ifndef INCLUDE_KDTREE_KDTREE_HPP 1031 #define INCLUDE_KDTREE_KDTREE_HPP 1040 #define KDTREE_VERSION 701 1045 #define KDTREE_LIB_VERSION "0_7_1" 1050 #ifdef KDTREE_CHECK_PERFORMANCE_COUNTERS 1053 #include <algorithm> 1054 #include <functional> 1056 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS 1068 #ifdef KDTREE_CHECK_PERFORMANCE 1069 unsigned long long num_dist_calcs = 0;
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> > >
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)
1108 _M_empty_initialise();
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)
1115 _M_empty_initialise();
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);
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)
1137 _M_empty_initialise();
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);
1172 _M_optimise(writable_vector.begin(), writable_vector.end(), 0);
1182 _M_acc = __x._M_acc;
1183 _M_dist = __x._M_dist;
1184 _M_cmp = __x._M_cmp;
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);
1209 return _Base::get_allocator();
1221 return size_type(-1);
1227 return this->size() == 0;
1233 _M_erase_subtree(_M_get_root());
1234 _M_set_leftmost(&_M_header);
1235 _M_set_rightmost(&_M_header);
1282 const_iterator
begin()
const {
return const_iterator(_M_get_leftmost()); }
1283 const_iterator
end()
const {
return const_iterator(static_cast<_Link_const_type>(&_M_header)); }
1284 const_reverse_iterator
rbegin()
const {
return const_reverse_iterator(end()); }
1285 const_reverse_iterator
rend()
const {
return const_reverse_iterator(begin()); }
1290 return this->insert(__V);
1298 _Link_type __n = _M_new_node(__V, &_M_header);
1301 _M_set_leftmost(__n);
1302 _M_set_rightmost(__n);
1303 return iterator(__n);
1305 return _M_insert(_M_get_root(), __V, 0);
1308 template <
class _InputIterator>
1309 void insert(_InputIterator __first, _InputIterator __last) {
1310 for (; __first != __last; ++__first)
1311 this->insert(*__first);
1315 insert(iterator __pos, size_type __n,
const value_type& __x)
1317 for (; __n > 0; --__n)
1318 this->insert(__pos, __x);
1321 template<
typename _InputIterator>
1323 insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
1324 for (; __first != __last; ++__first)
1325 this->insert(__pos, *__first);
1340 const_iterator b = this->find(__V);
1346 this->erase(this->find_exact(__V));
1353 assert(__IT != this->end());
1355 _Link_const_type n = target;
1356 size_type level = 0;
1357 while ((n = _S_parent(n)) != &_M_header)
1359 _M_erase( const_cast<_Link_type>(target), level );
1360 _M_delete_node( const_cast<_Link_type>(target) );
1384 template <
class SearchVal>
1388 if (!_M_get_root())
return this->end();
1389 return _M_find(_M_get_root(), __V, 0);
1406 template <
class SearchVal>
1410 if (!_M_get_root())
return this->end();
1411 return _M_find_exact(_M_get_root(), __V, 0);
1418 if (!_M_get_root())
return 0;
1419 _Region_ __region(__V, __R, _M_acc, _M_cmp);
1420 return this->count_within_range(__region);
1426 if (!_M_get_root())
return 0;
1428 _Region_ __bounds(__REGION);
1429 return _M_count_within_range(_M_get_root(),
1430 __REGION, __bounds, 0);
1434 template <
typename SearchVal,
class Visitor>
1438 if (!_M_get_root())
return visitor;
1439 _Region_ region(V, R, _M_acc, _M_cmp);
1440 return this->visit_within_range(region, visitor);
1443 template <
class Visitor>
1449 _Region_ bounds(REGION);
1450 return _M_visit_within_range(visitor, _M_get_root(), REGION, bounds, 0);
1465 template <
typename SearchVal,
typename _OutputIterator>
1468 _OutputIterator out)
const 1470 if (!_M_get_root())
return out;
1471 _Region_ region(val, range, _M_acc, _M_cmp);
1472 return this->find_within_range(region, out);
1475 template <
typename _OutputIterator>
1478 _OutputIterator out)
const 1482 _Region_ bounds(region);
1483 out = _M_find_within_range(out, _M_get_root(),
1489 template <
class SearchVal>
1490 std::pair<const_iterator, distance_type>
1495 std::pair<const _Node<_Val>*,
1496 std::pair<size_type, typename _Acc::result_type> >
1498 _M_get_root(), &_M_header, _M_get_root(),
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);
1506 return std::pair<const_iterator, distance_type>(end(), 0);
1509 template <
class SearchVal>
1510 std::pair<const_iterator, distance_type>
1515 bool root_is_candidate =
false;
1519 (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val));
1520 if (root_dist <= __max)
1522 root_is_candidate =
true;
1526 std::pair<const _Node<_Val>*,
1527 std::pair<size_type, typename _Acc::result_type> >
1529 node, __max, _M_cmp, _M_acc, _M_dist,
1532 if (root_is_candidate || best.first != _M_get_root())
1533 return std::pair<const_iterator, distance_type>
1534 (best.first, best.second.second);
1536 return std::pair<const_iterator, distance_type>(end(), __max);
1539 template <
class SearchVal,
class _Predicate>
1540 std::pair<const_iterator, distance_type>
1542 _Predicate __p)
const 1546 bool root_is_candidate =
false;
1548 if (__p(_M_get_root()->_M_value))
1552 (__K, _M_dist, _M_acc, _M_get_root()->_M_value, __val));
1553 if (root_dist <= __max)
1555 root_is_candidate =
true;
1560 std::pair<const _Node<_Val>*,
1561 std::pair<size_type, typename _Acc::result_type> >
1563 node, __max, _M_cmp, _M_acc, _M_dist, __p);
1565 if (root_is_candidate || best.first != _M_get_root())
1566 return std::pair<const_iterator, distance_type>
1567 (best.first, best.second.second);
1569 return std::pair<const_iterator, distance_type>(end(), __max);
1575 std::vector<value_type> __v(this->begin(),this->end());
1577 _M_optimise(__v.begin(), __v.end(), 0);
1588 _M_check_node(_M_get_root(),0);
1593 void _M_check_children( _Link_const_type child, _Link_const_type parent, size_type
const level,
bool to_the_left )
1598 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1605 _M_check_children(_S_left(child),parent,level,to_the_left);
1606 _M_check_children(_S_right(child),parent,level,to_the_left);
1616 _M_check_children( _S_left(node), node, level,
true );
1618 _M_check_children( _S_right(node), node, level,
false );
1620 _M_check_node( _S_left(node), level+1 );
1621 _M_check_node( _S_right(node), level+1 );
1627 _M_set_leftmost(&_M_header);
1628 _M_set_rightmost(&_M_header);
1629 _M_header._M_parent = NULL;
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));
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));
1655 size_type
const __L)
1657 if (_Node_compare_(__L % __K, _M_acc, _M_cmp)(__V, __N->
_M_value))
1660 return _M_insert_left(__N, __V);
1661 return _M_insert(_S_left(__N), __V, __L+1);
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);
1675 _Link_type step_dad = _M_get_erase_replacement(dead_dad, level);
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);
1683 _S_set_right(_S_parent(dead_dad), step_dad);
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)) );
1696 _S_set_parent(step_dad, _S_parent(dead_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);
1705 _S_set_left(step_dad, _S_left(dead_dad));
1706 _S_set_right(step_dad, _S_right(dead_dad));
1718 if (_S_is_leaf(node))
1721 std::pair<_Link_type,size_type> candidate;
1724 candidate = _M_get_j_min( std::pair<_Link_type,size_type>(_S_right(node),level), level+1);
1726 else if ((!_S_right(node)))
1727 candidate = _M_get_j_max( std::pair<_Link_type,size_type>(_S_left(node),level), level+1);
1737 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1740 if (compare(_S_right(node)->_M_value, _S_left(node)->_M_value))
1742 candidate = _M_get_j_min(std::pair<_Link_type,size_type>(_S_right(node),level), level+1);
1744 candidate = _M_get_j_max( std::pair<_Link_type,size_type>(_S_left(node),level), level+1);
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));
1754 _S_set_right(parent, _M_erase(candidate.first, candidate.second));
1756 return candidate.first;
1761 std::pair<_Link_type,size_type>
1762 _M_get_j_min( std::pair<_Link_type,size_type>
const node, size_type
const level)
1764 typedef std::pair<_Link_type,size_type> Result;
1765 if (_S_is_leaf(node.first))
1766 return Result(node.first,level);
1768 _Node_compare_ compare(node.second % __K, _M_acc, _M_cmp);
1769 Result candidate = node;
1770 if (_S_left(node.first))
1772 Result left = _M_get_j_min(Result(_S_left(node.first), node.second), level+1);
1773 if (compare(left.first->_M_value, candidate.first->_M_value))
1776 if (_S_right(node.first))
1778 Result right = _M_get_j_min( Result(_S_right(node.first),node.second), level+1);
1779 if (compare(right.first->_M_value, candidate.first->_M_value))
1782 if (candidate.first == node.first)
1783 return Result(candidate.first,level);
1790 std::pair<_Link_type,size_type>
1791 _M_get_j_max( std::pair<_Link_type,size_type>
const node, size_type
const level)
1793 typedef std::pair<_Link_type,size_type> Result;
1795 if (_S_is_leaf(node.first))
1796 return Result(node.first,level);
1798 _Node_compare_ compare(node.second % __K, _M_acc, _M_cmp);
1799 Result candidate = node;
1800 if (_S_left(node.first))
1802 Result left = _M_get_j_max( Result(_S_left(node.first),node.second), level+1);
1803 if (compare(candidate.first->_M_value, left.first->_M_value))
1806 if (_S_right(node.first))
1808 Result right = _M_get_j_max(Result(_S_right(node.first),node.second), level+1);
1809 if (compare(candidate.first->_M_value, right.first->_M_value))
1813 if (candidate.first == node.first)
1814 return Result(candidate.first,level);
1825 _M_erase_subtree(_S_right(__n));
1826 _Link_type __t = _S_left(__n);
1827 _M_delete_node(__n);
1833 _M_find(_Link_const_type node, const_reference value, size_type
const level)
const 1839 const_iterator found = this->end();
1841 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1842 if (!compare(node->
_M_value,value))
1845 if (_M_matches_node(node, value, level))
1846 return const_iterator(node);
1848 found = _M_find(_S_left(node), value, level+1);
1850 if ( _S_right(node) && found == this->end() && !compare(value,node->
_M_value))
1851 found = _M_find(_S_right(node), value, level+1);
1856 _M_find_exact(_Link_const_type node, const_reference value, size_type
const level)
const 1862 const_iterator found = this->end();
1864 _Node_compare_ compare(level % __K, _M_acc, _M_cmp);
1865 if (!compare(node->
_M_value,value))
1868 if (value == *const_iterator(node))
1869 return const_iterator(node);
1871 found = _M_find_exact(_S_left(node), value, level+1);
1875 if ( _S_right(node) && found == this->end() && !compare(value,node->
_M_value))
1876 found = _M_find_exact(_S_right(node), value, level+1);
1882 size_type
const __L)
const 1884 _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);
1890 size_type
const __L = 0)
const 1892 size_type __i = __L;
1893 while ((__i = (__i + 1) % __K) != __L % __K)
1894 if (!_M_matches_node_in_d(__N, __V, __i))
return false;
1900 size_type __L = 0)
const 1902 return _M_matches_node_in_d(__N, __V, __L)
1903 && _M_matches_node_in_other_ds(__N, __V, __L);
1908 _Region_
const& __BOUNDS,
1909 size_type
const __L)
const 1911 size_type count = 0;
1912 if (__REGION.
encloses(_S_value(__N)))
1918 _Region_ __bounds(__BOUNDS);
1921 count += _M_count_within_range(_S_left(__N),
1922 __REGION, __bounds, __L+1);
1926 _Region_ __bounds(__BOUNDS);
1929 count += _M_count_within_range(_S_right(__N),
1930 __REGION, __bounds, __L+1);
1937 template <
class Visitor>
1940 _Link_const_type N, _Region_
const& REGION,
1941 _Region_
const& BOUNDS,
1942 size_type
const L)
const 1946 visitor(_S_value(N));
1950 _Region_ bounds(BOUNDS);
1953 visitor = _M_visit_within_range(visitor, _S_left(N),
1954 REGION, bounds, L+1);
1958 _Region_ bounds(BOUNDS);
1961 visitor = _M_visit_within_range(visitor, _S_right(N),
1962 REGION, bounds, L+1);
1970 template <
typename _OutputIterator>
1973 _Link_const_type __N, _Region_
const& __REGION,
1974 _Region_
const& __BOUNDS,
1975 size_type
const __L)
const 1977 if (__REGION.
encloses(_S_value(__N)))
1979 *out++ = _S_value(__N);
1983 _Region_ __bounds(__BOUNDS);
1986 out = _M_find_within_range(out, _S_left(__N),
1987 __REGION, __bounds, __L+1);
1991 _Region_ __bounds(__BOUNDS);
1994 out = _M_find_within_range(out, _S_right(__N),
1995 __REGION, __bounds, __L+1);
2002 template <
typename _Iter>
2005 size_type
const __L)
2007 if (__A == __B)
return;
2008 _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);
2009 _Iter __m = __A + (__B - __A) / 2;
2010 std::nth_element(__A, __m, __B, compare);
2012 if (__m != __A) _M_optimise(__A, __m, __L+1);
2013 if (++__m != __B) _M_optimise(__m, __B, __L+1);
2019 return const_cast<_Link_const_type
>(_M_root);
2036 return static_cast<_Link_type
>(_M_header._M_left);
2042 _M_header._M_left = a;
2048 return static_cast<_Link_type
>( _M_header._M_right );
2054 _M_header._M_right = a;
2060 return static_cast<_Link_type
>( N->
_M_parent );
2063 static _Link_const_type
2066 return static_cast<_Link_const_type
>( N->_M_parent );
2084 return static_cast<_Link_type
>( N->
_M_left );
2087 static _Link_const_type
2090 return static_cast<_Link_const_type
>( N->_M_left );
2102 return static_cast<_Link_type
>( N->
_M_right );
2105 static _Link_const_type
2108 return static_cast<_Link_const_type
>( N->_M_right );
2114 return !_S_left(N) && !_S_right(N);
2117 static const_reference
2123 static const_reference
2126 return static_cast<_Link_const_type
>(N)->_M_value;
2129 static _Link_const_type
2135 static _Link_const_type
2144 _Base_ptr
const __PARENT = NULL,
2145 _Base_ptr
const __LEFT = NULL,
2146 _Base_ptr
const __RIGHT = NULL)
2148 typename _Base::NoLeakAlloc noleak(
this);
2149 _Link_type new_node = noleak.get();
2150 _Base::_M_construct_node(new_node, __V, __PARENT, __LEFT, __RIGHT);
2151 noleak.disconnect();
2168 _Base::_M_destroy_node(__p);
2169 _Base::_M_deallocate_node(__p);
2179 #ifdef KDTREE_DEFINE_OSTREAM_OPERATORS 2180 friend std::ostream&
2184 o <<
"meta node: " << tree._M_header << std::endl;
2185 o <<
"root node: " << tree._M_root << std::endl;
2188 return o <<
"[empty " << __K <<
"d-tree " << &tree <<
"]";
2190 o <<
"nodes total: " << tree.size() << std::endl;
2191 o <<
"dimensions: " << __K << std::endl;
2194 typedef typename _Tree::_Link_type _Link_type;
2196 std::stack<_Link_const_type> s;
2197 s.push(tree._M_get_root());
2201 _Link_const_type n = s.top();
2203 o << *n << std::endl;
2204 if (_Tree::_S_left(n)) s.push(_Tree::_S_left(n));
2205 if (_Tree::_S_right(n)) s.push(_Tree::_S_right(n));
2217 #endif // include guard NoLeakAlloc(_Alloc_base *b)
Definition: KDTree.h:544
_Acc value_acc() const
Accessor to the value's elements.
Definition: KDTree.h:1255
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:1791
value_type const * const_pointer
Definition: KDTree.h:1095
Visitor _M_visit_within_range(Visitor visitor, _Link_const_type N, _Region_ const ®ION, _Region_ const &BOUNDS, size_type const L) const
Definition: KDTree.h:1939
_Dist _M_dist
Definition: KDTree.h:2177
bool operator()(_Val const &__A, _Val const &__B) const
Definition: KDTree.h:156
void reset()
Definition: KDTree.h:471
const_iterator _M_find_exact(_Link_const_type node, const_reference value, size_type const level) const
Definition: KDTree.h:1856
value_type & reference
Definition: KDTree.h:1096
_Node_compare< _Val, _Acc, _Cmp > _Node_compare_
Definition: KDTree.h:1089
_Region(Val const &__V, subvalue_type const &__R, _Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:897
std::reverse_iterator< iterator > reverse_iterator
Definition: KDTree.h:1277
subvalue_type _M_high_bounds[__K]
Definition: KDTree.h:964
allocator_type get_allocator() const
Definition: KDTree.h:532
_Iterator< _Val, _Val &, _Val * > iterator
Definition: KDTree.h:718
_Iterator(iterator const &__THAT)
Definition: KDTree.h:729
static _Link_type _S_parent(_Base_ptr N)
Definition: KDTree.h:2058
size_type max_size() const
Definition: KDTree.h:1219
_Acc::result_type subvalue_type
Definition: KDTree.h:1098
KDTree(_Acc const &__acc=_Acc(), _Dist const &__dist=_Dist(), _Cmp const &__cmp=_Cmp(), const allocator_type &__a=allocator_type())
Definition: KDTree.h:1103
static _Link_const_type _S_right(_Base_const_ptr N)
Definition: KDTree.h:2106
_Val value_type
Definition: KDTree.h:715
long & count() const
Definition: KDTree.h:475
iterator insert(const_reference __V)
Definition: KDTree.h:1294
_Node_base _M_header
Definition: KDTree.h:2173
result_type operator()(_Val const &V, size_t const N) const
Definition: KDTree.h:437
void _M_destroy_node(_Node_ *__p)
Definition: KDTree.h:578
_Link_type _M_root
Definition: KDTree.h:2172
_Node_ * _M_allocate_node()
Definition: KDTree.h:557
void optimise()
Definition: KDTree.h:1573
static void _S_set_left(_Base_ptr N, _Base_ptr l)
Definition: KDTree.h:2076
reference operator*() const
Definition: KDTree.h:738
void _M_check_children(_Link_const_type child, _Link_const_type parent, size_type const level, bool to_the_left)
Definition: KDTree.h:1593
Definition: KDTree.h:1078
_Self operator--(int)
Definition: KDTree.h:772
static _Base_ptr _S_minimum(_Base_ptr __x)
Definition: KDTree.h:88
_Acc _M_acc
Definition: KDTree.h:965
size_t size_type
Definition: KDTree.h:1100
void check_tree()
Definition: KDTree.h:1586
_Dist & value_distance()
Definition: KDTree.h:1269
_Link_type _M_get_root()
Definition: KDTree.h:2023
_Region< __K, _Val, typename _Acc::result_type, _Acc, _Cmp > _Region_
Definition: KDTree.h:1092
_Node< _Val > const * _Link_const_type
Definition: KDTree.h:721
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: KDTree.h:1276
std::pair< const_iterator, distance_type > find_nearest_if(SearchVal const &__val, distance_type __max, _Predicate __p) const
Definition: KDTree.h:1541
_Link_const_type _M_get_root() const
Definition: KDTree.h:2017
Visitor visit_within_range(SearchVal const &V, subvalue_type const R, Visitor visitor) const
Definition: KDTree.h:1436
void erase_exact(const_reference __V)
Definition: KDTree.h:1345
bool operator==(_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
Definition: KDTree.h:806
_Node_compare(size_t const __DIM, _Acc const &acc, _Cmp const &cmp)
Definition: KDTree.h:152
_Self operator++()
Definition: KDTree.h:750
void _M_increment()
Definition: KDTree.h:658
_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
allocator_type get_allocator() const
Definition: KDTree.h:1207
void _M_erase_subtree(_Link_type __n)
Definition: KDTree.h:1821
_Self operator++(int)
Definition: KDTree.h:757
_Acc _M_acc
Definition: KDTree.h:2175
_Node_base const * _Base_const_ptr
Definition: KDTree.h:1085
static _Base_ptr _S_maximum(_Base_ptr __x)
Definition: KDTree.h:95
KDTree(const KDTree &__x)
Definition: KDTree.h:1111
iterator insert(iterator, const_reference __V)
Definition: KDTree.h:1288
_Iterator()
Definition: KDTree.h:725
_Dist distance_type
Definition: KDTree.h:465
void _M_optimise(_Iter const &__A, _Iter const &__B, size_type const __L)
Definition: KDTree.h:2004
_Node_base * _Base_ptr
Definition: KDTree.h:75
void _M_deallocate_node(_Node_ *const __P)
Definition: KDTree.h:563
const _Dist & value_distance() const
Distance calculator between 2 value's element.
Definition: KDTree.h:1265
size_type count_within_range(_Region_ const &__REGION) const
Definition: KDTree.h:1424
~NoLeakAlloc()
Definition: KDTree.h:549
void _M_decrement()
Definition: KDTree.h:680
void insert(_InputIterator __first, _InputIterator __last)
Definition: KDTree.h:1309
~KDTree()
Definition: KDTree.h:1201
_Val value_type
Definition: KDTree.h:874
iterator _M_insert_right(_Link_type __N, const_reference __V)
Definition: KDTree.h:1644
_Alloc_base< _Val, _Alloc > _Base
Definition: KDTree.h:1081
size_t _M_DIM
Definition: KDTree.h:162
_Cmp _M_cmp
Definition: KDTree.h:966
_Region(Val const &__V, _Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:886
static _Link_const_type _S_left(_Base_const_ptr N)
Definition: KDTree.h:2088
void _M_set_root(_Link_type n)
Definition: KDTree.h:2028
iterator _M_insert(_Link_type __N, const_reference __V, size_type const __L)
Definition: KDTree.h:1654
_OutputIterator find_within_range(SearchVal const &val, subvalue_type const range, _OutputIterator out) const
Definition: KDTree.h:1467
_Link_type _M_erase(_Link_type dead_dad, size_type const level)
Definition: KDTree.h:1672
std::pair< const_iterator, distance_type > find_nearest(SearchVal const &__val) const
Definition: KDTree.h:1491
bool empty() const
Definition: KDTree.h:1225
long _M_count
Definition: KDTree.h:487
_Node_ * new_node
Definition: KDTree.h:541
const_reverse_iterator rbegin() const
Definition: KDTree.h:1284
_SubVal subvalue_type
Definition: KDTree.h:875
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:1762
_Cmp _M_cmp
Definition: KDTree.h:164
const_iterator find(SearchVal const &__V) const
Definition: KDTree.h:1386
size_type _M_count
Definition: KDTree.h:2174
value_type const & const_reference
Definition: KDTree.h:1097
_Dist distance_type
Definition: KDTree.h:452
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
_Region & set_high_bound(value_type const &__V, size_t const __L)
Definition: KDTree.h:951
allocator_type _M_node_allocator
Definition: KDTree.h:554
static bool _S_is_leaf(_Base_const_ptr N)
Definition: KDTree.h:2112
_Region(_Acc const &__acc=_Acc(), const _Cmp &__cmp=_Cmp())
Definition: KDTree.h:882
_Base::allocator_type allocator_type
Definition: KDTree.h:1082
static _Link_type _S_right(_Base_ptr N)
Definition: KDTree.h:2100
_Iterator< _Val, const_reference, const_pointer > const_iterator
Definition: KDTree.h:1273
_Node_::_Base_ptr _Base_ptr
Definition: KDTree.h:525
_Node< _Val > const * _Link_const_type
Definition: KDTree.h:1087
_Node_base const * _Base_const_ptr
Definition: KDTree.h:76
_Base_iterator(_Base_iterator const &__THAT)
Definition: KDTree.h:654
_Link_const_type _M_get_leftmost() const
Definition: KDTree.h:2034
std::ostream & operator<<(std::ostream &os, const AccurateMassSearchResult &amsr)
_Alloc_base(allocator_type const &__A)
Definition: KDTree.h:528
Visitor visit_within_range(_Region_ const ®ION, Visitor visitor) const
Definition: KDTree.h:1445
_Cmp value_comp() const
Comparator for the values in the KDTree.
Definition: KDTree.h:1246
void insert(iterator __pos, size_type __n, const value_type &__x)
Definition: KDTree.h:1315
void disconnect()
Definition: KDTree.h:547
std::pair< const NodeType *, std::pair< size_t, typename _Dist::distance_type > > _S_node_nearest(const size_t __k, size_t __dim, SearchVal const &__val, const NodeType *__node, const _Node_base *__end, const NodeType *__best, typename _Dist::distance_type __max, const _Cmp &__cmp, const _Acc &__acc, const _Dist &__dist, _Predicate __p)
Definition: KDTree.h:252
KDTree & operator=(const KDTree &__x)
Definition: KDTree.h:1178
_Region & set_low_bound(value_type const &__V, size_t const __L)
Definition: KDTree.h:958
void _M_set_rightmost(_Node_base *a)
Definition: KDTree.h:2052
const_iterator _M_find(_Link_const_type node, const_reference value, size_type const level) const
Definition: KDTree.h:1833
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
DPosition< D, TCoordinateType > operator*(DPosition< D, TCoordinateType > position, typename DPosition< D, TCoordinateType >::CoordinateType scalar)
Scalar multiplication (a bit inefficient)
Definition: DPosition.h:421
bool encloses(value_type const &__V) const
Definition: KDTree.h:939
_Link_const_type _M_get_rightmost() const
Definition: KDTree.h:2046
_Val _M_value
Definition: KDTree.h:108
bool _M_matches_node_in_other_ds(_Link_const_type __N, const_reference __V, size_type const __L=0) const
Definition: KDTree.h:1889
_Node< _Tp > _Node_
Definition: KDTree.h:524
_Val::value_type result_type
Definition: KDTree.h:434
bool _S_node_compare(const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
Definition: KDTree.h:177
_Cmp _M_cmp
Definition: KDTree.h:2176
std::bidirectional_iterator_tag iterator_category
Definition: KDTree.h:722
const_iterator begin() const
Definition: KDTree.h:1282
_Ptr pointer
Definition: KDTree.h:717
_Base_const_ptr _M_node
Definition: KDTree.h:650
void _M_delete_node(_Link_type __p)
Definition: KDTree.h:2166
std::pair< _Region, _SubVal > _CenterPt
Definition: KDTree.h:880
_Node_base * _Base_ptr
Definition: KDTree.h:1084
static const_reference _S_value(_Link_const_type N)
Definition: KDTree.h:2118
_Ref reference
Definition: KDTree.h:716
void _M_check_node(_Link_const_type node, size_type const level)
Definition: KDTree.h:1610
_OutputIterator find_within_range(_Region_ const ®ion, _OutputIterator out) const
Definition: KDTree.h:1477
static void _S_set_parent(_Base_ptr N, _Base_ptr p)
Definition: KDTree.h:2070
ptrdiff_t difference_type
Definition: KDTree.h:723
bool intersects_with(_Region const &__THAT) const
Definition: KDTree.h:927
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
_Base_ptr _M_left
Definition: KDTree.h:79
ptrdiff_t difference_type
Definition: KDTree.h:1101
subvalue_type _M_low_bounds[__K]
Definition: KDTree.h:964
pointer operator->() const
Definition: KDTree.h:744
_Link_type _M_new_node(const_reference __V, _Base_ptr const __PARENT=NULL, _Base_ptr const __LEFT=NULL, _Base_ptr const __RIGHT=NULL)
Definition: KDTree.h:2143
const_iterator iterator
Definition: KDTree.h:1275
bool operator!=(_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
Definition: KDTree.h:824
static _Link_const_type _S_minimum(_Link_const_type __X)
Definition: KDTree.h:2130
static void _S_set_right(_Base_ptr N, _Base_ptr r)
Definition: KDTree.h:2094
_Iterator(_Link_const_type const __N)
Definition: KDTree.h:727
size_type _M_count_within_range(_Link_const_type __N, _Region_ const &__REGION, _Region_ const &__BOUNDS, size_type const __L) const
Definition: KDTree.h:1907
_Base_iterator(_Base_const_ptr const __N=NULL)
Definition: KDTree.h:652
bool _M_matches_node(_Link_const_type __N, const_reference __V, size_type __L=0) const
Definition: KDTree.h:1899
void _M_empty_initialise()
Definition: KDTree.h:1625
void erase(const_iterator const &__IT)
Definition: KDTree.h:1351
_Node< _Val > * _Link_type
Definition: KDTree.h:1086
iterator _M_insert_left(_Link_type __N, const_reference __V)
Definition: KDTree.h:1634
_Alloc allocator_type
Definition: KDTree.h:526
_Node_base(_Base_ptr const __PARENT=NULL, _Base_ptr const __LEFT=NULL, _Base_ptr const __RIGHT=NULL)
Definition: KDTree.h:82
void _M_set_leftmost(_Node_base *a)
Definition: KDTree.h:2040
void insert(iterator __pos, _InputIterator __first, _InputIterator __last)
Definition: KDTree.h:1323
_Acc _M_acc
Definition: KDTree.h:163
_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:2064
_Val value_type
Definition: KDTree.h:1093
static const_reference _S_value(_Base_const_ptr N)
Definition: KDTree.h:2124
_Base_ptr _M_parent
Definition: KDTree.h:78
_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:1972
void optimize()
Definition: KDTree.h:1581
const_iterator find_exact(SearchVal const &__V) const
Definition: KDTree.h:1408
void clear()
Definition: KDTree.h:1231
_Link_const_type get_raw_node() const
Definition: KDTree.h:732
_Iterator< _Val, _Ref, _Ptr > _Self
Definition: KDTree.h:720
bool intersects_with(_CenterPt const &__THAT) const
Definition: KDTree.h:909
void efficient_replace_and_optimise(std::vector< value_type > &writable_vector)
Definition: KDTree.h:1169
void erase(const_reference __V)
Definition: KDTree.h:1339
value_type * pointer
Definition: KDTree.h:1094
size_type size() const
Definition: KDTree.h:1213
const_iterator end() const
Definition: KDTree.h:1283
_Dist::distance_type distance_type
Definition: KDTree.h:1099
static _Link_type _S_left(_Base_ptr N)
Definition: KDTree.h:2082
bool _M_matches_node_in_d(_Link_const_type __N, const_reference __V, size_type const __L) const
Definition: KDTree.h:1881
_Node(_Val const &__VALUE=_Val(), _Base_ptr const __PARENT=NULL, _Base_ptr const __LEFT=NULL, _Base_ptr const __RIGHT=NULL)
Definition: KDTree.h:110
size_type count_within_range(const_reference __V, subvalue_type const __R) const
Definition: KDTree.h:1416
_Alloc_base * base
Definition: KDTree.h:540
_Iterator< _Val, _Val const &, _Val const * > const_iterator
Definition: KDTree.h:719
std::pair< const_iterator, distance_type > find_nearest(SearchVal const &__val, distance_type __max) const
Definition: KDTree.h:1511
_Node_base::_Base_const_ptr _Base_const_ptr
Definition: KDTree.h:649
static _Link_const_type _S_maximum(_Link_const_type __X)
Definition: KDTree.h:2136
_Node * _Link_type
Definition: KDTree.h:106
const_reverse_iterator rend() const
Definition: KDTree.h:1285
squared_difference_counted()
Definition: KDTree.h:467
_Self & operator--()
Definition: KDTree.h:765
_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
_Base_ptr _M_right
Definition: KDTree.h:80