OpenMS
KDTree.h File Reference
#include <cstddef>
#include <cmath>
#include <iterator>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
Include dependency graph for KDTree.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  _Node_base
 
struct  _Node< _Val >
 
class  _Node_compare< _Val, _Acc, _Cmp >
 
struct  _Bracket_accessor< _Val >
 
struct  always_true< _Tp >
 
struct  squared_difference< _Tp, _Dist >
 
struct  squared_difference_counted< _Tp, _Dist >
 
class  _Alloc_base< _Tp, _Alloc >
 
class  _Alloc_base< _Tp, _Alloc >::NoLeakAlloc
 
class  _Base_iterator
 
class  _Iterator< _Val, _Ref, _Ptr >
 
struct  _Region< __K, _Val, _SubVal, _Acc, _Cmp >
 
class  KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >
 

Namespaces

 KDTree
 

Macros

#define INCLUDE_KDTREE_ACCESSOR_HPP
 
#define INCLUDE_KDTREE_ALLOCATOR_HPP
 
#define INCLUDE_KDTREE_ITERATOR_HPP
 
#define INCLUDE_KDTREE_REGION_HPP
 
#define INCLUDE_KDTREE_KDTREE_HPP
 
#define KDTREE_VERSION   701
 
#define KDTREE_LIB_VERSION   "0_7_1"
 

Functions

template<typename _ValA , typename _ValB , typename _Cmp , typename _Acc >
bool _S_node_compare (const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
 
template<typename _ValA , typename _ValB , typename _Dist , typename _Acc >
_Dist::distance_type _S_node_distance (const size_t __dim, const _Dist &__dist, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
 
template<typename _ValA , typename _ValB , typename _Dist , typename _Acc >
_Dist::distance_type _S_accumulate_node_distance (const size_t __dim, const _Dist &__dist, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
 
template<typename _Val , typename _Cmp , typename _Acc , typename NodeType >
const NodeType * _S_node_descend (const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _Val &__val, const NodeType *__node)
 
template<class SearchVal , typename NodeType , typename _Cmp , typename _Acc , typename _Dist , typename _Predicate >
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)
 
template<typename _Val , typename _Ref , typename _Ptr >
bool operator== (_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
 
template<typename _Val >
bool operator== (_Iterator< _Val, const _Val &, const _Val * > const &, _Iterator< _Val, _Val &, _Val * > const &)
 
template<typename _Val >
bool operator== (_Iterator< _Val, _Val &, _Val * > const &, _Iterator< _Val, const _Val &, const _Val * > const &)
 
template<typename _Val , typename _Ref , typename _Ptr >
bool operator!= (_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
 
template<typename _Val >
bool operator!= (_Iterator< _Val, const _Val &, const _Val * > const &, _Iterator< _Val, _Val &, _Val * > const &)
 
template<typename _Val >
bool operator!= (_Iterator< _Val, _Val &, _Val * > const &, _Iterator< _Val, const _Val &, const _Val * > const &)
 

Detailed Description

Defines interfaces for nodes as used by the KDTree class.

Author
Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines the various functors and interfaces used for KDTree.

Author
Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net
Sylvain Bougerel sylva.nosp@m.in.b.nosp@m.ouger.nosp@m.el.d.nosp@m.evel@.nosp@m.gmai.nosp@m.l.com

Defines the allocator interface as used by the KDTree class.

Author
Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines interfaces for iterators as used by the KDTree class.

Author
Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines the interface of the _Region class.

Author
Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines the interface for the KDTree class.

Author
Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Paul Harris figured this stuff out (below) Notes: This is similar to a binary tree, but its not the same. There are a few important differences:

  • Each level is sorted by a different criteria (this is fundamental to the design).
  • It is possible to have children IDENTICAL to its parent in BOTH branches This is different to a binary tree, where identical children are always to the right So, KDTree has the relationships:

    • The left branch is <= its parent (in binary tree, this relationship is a plain < )
    • The right branch is <= its parent (same as binary tree)

    This is done for mostly for performance. Its a LOT easier to maintain a consistent tree if we use the <= relationship. Note that this relationship only makes a difference when searching for an exact item with find() or find_exact, other search, erase and insert functions don't notice the difference.

    In the case of binary trees, you can safely assume that the next identical item will be the child leaf, but in the case of KDTree, the next identical item might be a long way down a subtree, because of the various different sort criteria.

    So to erase() a node from a KDTree could require serious and complicated tree rebalancing to maintain consistency... IF we required binary-tree-like relationships.

    This has no effect on insert()s, a < test is good enough to keep consistency.

    It has an effect on find() searches:

    • Instead of using compare(child,node) for a < relationship and following 1 branch, we must use !compare(node,child) for a <= relationship, and test BOTH branches, as we could potentially go down both branches.

    It has no real effect on bounds-based searches (like find_nearest, find_within_range) as it compares vs a boundary and would follow both branches if required.

    This has no real effect on erase()s, a < test is good enough to keep consistency.

Macro Definition Documentation

◆ INCLUDE_KDTREE_ACCESSOR_HPP

#define INCLUDE_KDTREE_ACCESSOR_HPP

◆ INCLUDE_KDTREE_ALLOCATOR_HPP

#define INCLUDE_KDTREE_ALLOCATOR_HPP

◆ INCLUDE_KDTREE_ITERATOR_HPP

#define INCLUDE_KDTREE_ITERATOR_HPP

◆ INCLUDE_KDTREE_KDTREE_HPP

#define INCLUDE_KDTREE_KDTREE_HPP

◆ INCLUDE_KDTREE_REGION_HPP

#define INCLUDE_KDTREE_REGION_HPP

◆ KDTREE_LIB_VERSION

#define KDTREE_LIB_VERSION   "0_7_1"

◆ KDTREE_VERSION

#define KDTREE_VERSION   701