 |
OpenMS
2.6.0
|
#include <cstddef>#include <cmath>#include <iterator>#include <vector>#include <algorithm>#include <functional>#include <cassert>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 | _Iterator< _Val, _Ref, _Ptr > |
| 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 &) |
Defines interfaces for nodes as used by the KDTree class.
Defines the various functors and interfaces used for KDTree.
Defines the allocator interface as used by the KDTree class.
Defines interfaces for iterators as used by the KDTree class.
Defines the interface of the _Region class.
Defines the interface for the KDTree class.
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 erase()ing 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.
| #define INCLUDE_KDTREE_ACCESSOR_HPP |
| #define INCLUDE_KDTREE_ALLOCATOR_HPP |
| #define INCLUDE_KDTREE_ITERATOR_HPP |
| #define INCLUDE_KDTREE_KDTREE_HPP |
| #define INCLUDE_KDTREE_REGION_HPP |
| #define KDTREE_LIB_VERSION "0_7_1" |
| #define KDTREE_VERSION 701 |
1.8.16