| OpenMS 2.5.0

Public Types | Public Member Functions | Protected Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc > Class Template Reference

`#include <OpenMS/DATASTRUCTURES/KDTree.h>`

Inheritance diagram for KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >:

## Public Types

typedef _Region< __K, _Val, typename _Acc::result_type, _Acc, _Cmp > | _Region_
typedef _Val | value_type
typedef value_type * | pointer
typedef value_type const * | const_pointer
typedef value_type & | reference
typedef value_type const & | const_reference
typedef _Acc::result_type | subvalue_type
typedef _Dist::distance_type | distance_type
typedef size_t | size_type
typedef ptrdiff_t | difference_type
typedef _Iterator< _Val, const_reference, const_pointer > | const_iterator
typedef const_iterator | iterator
typedef std::reverse_iterator< const_iterator > | const_reverse_iterator
typedef std::reverse_iterator< iterator > | reverse_iterator

## Public Member Functions

| KDTree (_Acc const &__acc=_Acc(), _Dist const &__dist=_Dist(), _Cmp const &__cmp=_Cmp(), const allocator_type &__a=allocator_type())
| KDTree (const KDTree &__x)
template<typename _InputIterator >
| KDTree (_InputIterator __first, _InputIterator __last, _Acc const &acc=_Acc(), _Dist const &__dist=_Dist(), _Cmp const &__cmp=_Cmp(), const allocator_type &__a=allocator_type())
void | efficient_replace_and_optimise (std::vector< value_type > &writable_vector)
KDTree & | operator= (const KDTree &__x)
| ~KDTree ()
allocator_type | get_allocator () const
size_type | size () const
size_type | max_size () const
bool | empty () const
void | clear ()
_Cmp | value_comp () const
| Comparator for the values in the KDTree. More...
_Acc | value_acc () const
| Accessor to the value's elements. More...
const _Dist & | value_distance () const
| Distance calculator between 2 value's element. More...
_Dist & | value_distance ()
const_iterator | begin () const
const_iterator | end () const
const_reverse_iterator | rbegin () const
const_reverse_iterator | rend () const
iterator | insert (iterator, const_reference __V)
iterator | insert (const_reference __V)
template<class _InputIterator >
void | insert (_InputIterator __first, _InputIterator __last)
void | insert (iterator __pos, size_type __n, const value_type &__x)
template<typename _InputIterator >
void | insert (iterator __pos, _InputIterator __first, _InputIterator __last)
void | erase (const_reference __V)
void | erase_exact (const_reference __V)
void | erase (const_iterator const &__IT)
template<class SearchVal >
const_iterator | find (SearchVal const &__V) const
template<class SearchVal >
const_iterator | find_exact (SearchVal const &__V) const
size_type | count_within_range (const_reference __V, subvalue_type const __R) const
size_type | count_within_range (_Region_ const &__REGION) const
template<typename SearchVal , class Visitor >
Visitor | visit_within_range (SearchVal const &V, subvalue_type const R, Visitor visitor) const
template<class Visitor >
Visitor | visit_within_range (_Region_ const &REGION, Visitor visitor) const
template<typename SearchVal , typename _OutputIterator >
_OutputIterator | find_within_range (SearchVal const &val, subvalue_type const range, _OutputIterator out) const
template<typename _OutputIterator >
_OutputIterator | find_within_range (_Region_ const &region, _OutputIterator out) const
template<class SearchVal >
std::pair< const_iterator, distance_type > | find_nearest (SearchVal const &__val) const
template<class SearchVal >
std::pair< const_iterator, distance_type > | find_nearest (SearchVal const &__val, distance_type __max) const
template<class SearchVal , class _Predicate >
std::pair< const_iterator, distance_type > | find_nearest_if (SearchVal const &__val, distance_type __max, _Predicate __p) const
void | optimise ()
void | optimize ()
void | check_tree ()

## Protected Types

typedef _Alloc_base< _Val, _Alloc > | _Base
typedef _Base::allocator_type | allocator_type
typedef _Node_base * | _Base_ptr
typedef _Node_base const * | _Base_const_ptr
typedef _Node< _Val > * | _Link_type
typedef _Node< _Val > const * | _Link_const_type
typedef _Node_compare< _Val, _Acc, _Cmp > | _Node_compare_
Protected Types inherited from _Alloc_base< _Val, _Alloc >
typedef _Node< _Val > | _Node_
typedef _Node_::_Base_ptr | _Base_ptr
typedef _Alloc | allocator_type

## Protected Member Functions

void | _M_check_children (_Link_const_type child, _Link_const_type parent, size_type const level, bool to_the_left)
void | _M_check_node (_Link_const_type node, size_type const level)
void | _M_empty_initialise ()
iterator | _M_insert_left (_Link_type __N, const_reference __V)
iterator | _M_insert_right (_Link_type __N, const_reference __V)
iterator | _M_insert (_Link_type __N, const_reference __V, size_type const __L)
_Link_type | _M_erase (_Link_type dead_dad, size_type const level)
_Link_type | _M_get_erase_replacement (_Link_type node, size_type const level)
std::pair< _Link_type, size_type > | _M_get_j_min (std::pair< _Link_type, size_type > const node, size_type const level)
std::pair< _Link_type, size_type > | _M_get_j_max (std::pair< _Link_type, size_type > const node, size_type const level)
void | _M_erase_subtree (_Link_type __n)
const_iterator | _M_find (_Link_const_type node, const_reference value, size_type const level) const
const_iterator | _M_find_exact (_Link_const_type node, const_reference value, size_type const level) const
bool | _M_matches_node_in_d (_Link_const_type __N, const_reference __V, size_type const __L) const
bool | _M_matches_node_in_other_ds (_Link_const_type __N, const_reference __V, size_type const __L=0) const
bool | _M_matches_node (_Link_const_type __N, const_reference __V, size_type __L=0) const
size_type | _M_count_within_range (_Link_const_type __N, _Region_ const &__REGION, _Region_ const &__BOUNDS, size_type const __L) const
template<class Visitor >
Visitor | _M_visit_within_range (Visitor visitor, _Link_const_type N, _Region_ const &REGION, _Region_ const &BOUNDS, size_type const L) const
template<typename _OutputIterator >
_OutputIterator | _M_find_within_range (_OutputIterator out, _Link_const_type __N, _Region_ const &__REGION, _Region_ const &__BOUNDS, size_type const __L) const
template<typename _Iter >
void | _M_optimise (_Iter const &__A, _Iter const &__B, size_type const __L)
_Link_const_type | _M_get_root () const
_Link_type | _M_get_root ()
void | _M_set_root (_Link_type n)
_Link_const_type | _M_get_leftmost () const
void | _M_set_leftmost (_Node_base *a)
_Link_const_type | _M_get_rightmost () const
void | _M_set_rightmost (_Node_base *a)
_Link_type | _M_new_node (const_reference __V, _Base_ptr const __PARENT=nullptr, _Base_ptr const __LEFT=nullptr, _Base_ptr const __RIGHT=nullptr)
void | _M_delete_node (_Link_type __p)
Protected Member Functions inherited from _Alloc_base< _Val, _Alloc >
_Node_ * | _M_allocate_node ()
void | _M_deallocate_node (_Node_ *const __P)
void | _M_construct_node (_Node_ *__p, _Val const __V=_Val(), _Base_ptr const __PARENT=NULL, _Base_ptr const __LEFT=NULL, _Base_ptr const __RIGHT=NULL)
void | _M_destroy_node (_Node_ *__p)
| _Alloc_base (allocator_type const &__A)
allocator_type | get_allocator () const

## Static Protected Member Functions

static _Link_type | _S_parent (_Base_ptr N)
static _Link_const_type | _S_parent (_Base_const_ptr N)
static void | _S_set_parent (_Base_ptr N, _Base_ptr p)
static void | _S_set_left (_Base_ptr N, _Base_ptr l)
static _Link_type | _S_left (_Base_ptr N)
static _Link_const_type | _S_left (_Base_const_ptr N)
static void | _S_set_right (_Base_ptr N, _Base_ptr r)
static _Link_type | _S_right (_Base_ptr N)
static _Link_const_type | _S_right (_Base_const_ptr N)
static bool | _S_is_leaf (_Base_const_ptr N)
static const_reference | _S_value (_Link_const_type N)
static const_reference | _S_value (_Base_const_ptr N)
static _Link_const_type | _S_minimum (_Link_const_type __X)
static _Link_const_type | _S_maximum (_Link_const_type __X)

## Protected Attributes

_Link_type | _M_root
_Node_base | _M_header
size_type | _M_count
_Acc | _M_acc
_Cmp | _M_cmp
_Dist | _M_dist
Protected Attributes inherited from _Alloc_base< _Val, _Alloc >
allocator_type | _M_node_allocator

## Member Typedef Documentation

## ◆ _Base

typedef _Alloc_base<_Val, _Alloc> _Base

protected

## ◆ _Base_const_ptr

typedef _Node_base const* _Base_const_ptr

protected

## ◆ _Base_ptr

typedef _Node_base* _Base_ptr

protected

## ◆ _Link_const_type

typedef _Node<_Val> const* _Link_const_type

protected

## ◆ _Link_type

typedef _Node<_Val>* _Link_type

protected

## ◆ _Node_compare_

typedef _Node_compare<_Val, _Acc, _Cmp> _Node_compare_

protected

## ◆ _Region_

typedef _Region<__K, _Val, typename _Acc::result_type, _Acc, _Cmp> _Region_

## ◆ allocator_type

typedef _Base::allocator_type allocator_type

protected

## ◆ const_iterator

typedef _Iterator<_Val, const_reference, const_pointer> const_iterator

## ◆ const_pointer

typedef value_type const* const_pointer

## ◆ const_reference

typedef value_type const& const_reference

## ◆ const_reverse_iterator

typedef std::reverse_iterator<const_iterator> const_reverse_iterator

## ◆ difference_type

typedef ptrdiff_t difference_type

## ◆ distance_type

typedef _Dist::distance_type distance_type

## ◆ iterator

typedef const_iterator iterator

## ◆ pointer

typedef value_type* pointer

## ◆ reference

typedef value_type& reference

## ◆ reverse_iterator

typedef std::reverse_iterator<iterator> reverse_iterator

## ◆ size_type

typedef size_t size_type

## ◆ subvalue_type

typedef _Acc::result_type subvalue_type

## ◆ value_type

typedef _Val value_type

## Constructor & Destructor Documentation

## ◆ KDTree() [1/3]

KDTree | ( | _Acc const & | __acc = `_Acc()`,
|  | _Dist const & | __dist = `_Dist()`,
|  | _Cmp const & | __cmp = `_Cmp()`,
|  | const allocator_type & | __a = `allocator_type()`
| ) |  |

inline

## ◆ KDTree() [2/3]

KDTree | ( | const KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc > & | __x | ) |

inline

## ◆ KDTree() [3/3]

KDTree | ( | _InputIterator | __first,
|  | _InputIterator | __last,
|  | _Acc const & | acc = `_Acc()`,
|  | _Dist const & | __dist = `_Dist()`,
|  | _Cmp const & | __cmp = `_Cmp()`,
|  | const allocator_type & | __a = `allocator_type()`
| ) |  |

inline

## ◆ ~KDTree()

~KDTree | ( |  | ) |

inline

## Member Function Documentation

## ◆ _M_check_children()

void _M_check_children | ( | _Link_const_type | child,
|  | _Link_const_type | parent,
|  | size_type const | level,
|  | bool | to_the_left
| ) |  |

inline protected

## ◆ _M_check_node()

void _M_check_node | ( | _Link_const_type | node,
|  | size_type const | level
| ) |  |

inline protected

## ◆ _M_count_within_range()

size_type _M_count_within_range | ( | _Link_const_type | __N,
|  | _Region_ const & | __REGION,
|  | _Region_ const & | __BOUNDS,
|  | size_type const | __L
| ) |  | const

inline protected

## ◆ _M_delete_node()

void _M_delete_node | ( | _Link_type | __p | ) |

inline protected

## ◆ _M_empty_initialise()

void _M_empty_initialise | ( |  | ) |

inline protected

## ◆ _M_erase()

_Link_type _M_erase | ( | _Link_type | dead_dad,
|  | size_type const | level
| ) |  |

inline protected

## ◆ _M_erase_subtree()

void _M_erase_subtree | ( | _Link_type | __n | ) |

inline protected

## ◆ _M_find()

const_iterator _M_find | ( | _Link_const_type | node,
|  | const_reference | value,
|  | size_type const | level
| ) |  | const

inline protected

## ◆ _M_find_exact()

const_iterator _M_find_exact | ( | _Link_const_type | node,
|  | const_reference | value,
|  | size_type const | level
| ) |  | const

inline protected

## ◆ _M_find_within_range()

_OutputIterator _M_find_within_range | ( | _OutputIterator | out,
|  | _Link_const_type | __N,
|  | _Region_ const & | __REGION,
|  | _Region_ const & | __BOUNDS,
|  | size_type const | __L
| ) |  | const

inline protected

## ◆ _M_get_erase_replacement()

_Link_type _M_get_erase_replacement | ( | _Link_type | node,
|  | size_type const | level
| ) |  |

inline protected

## ◆ _M_get_j_max()

std::pair<_Link_type,size_type> _M_get_j_max | ( | std::pair< _Link_type, size_type > const | node,
|  | size_type const | level
| ) |  |

inline protected

## ◆ _M_get_j_min()

std::pair<_Link_type,size_type> _M_get_j_min | ( | std::pair< _Link_type, size_type > const | node,
|  | size_type const | level
| ) |  |

inline protected

## ◆ _M_get_leftmost()

_Link_const_type _M_get_leftmost | ( |  | ) | const

inline protected

## ◆ _M_get_rightmost()

_Link_const_type _M_get_rightmost | ( |  | ) | const

inline protected

## ◆ _M_get_root() [1/2]

_Link_const_type _M_get_root | ( |  | ) | const

inline protected

## ◆ _M_get_root() [2/2]

_Link_type _M_get_root | ( |  | ) |

inline protected

## ◆ _M_insert()

iterator _M_insert | ( | _Link_type | __N,
|  | const_reference | __V,
|  | size_type const | __L
| ) |  |

inline protected

## ◆ _M_insert_left()

iterator _M_insert_left | ( | _Link_type | __N,
|  | const_reference | __V
| ) |  |

inline protected

## ◆ _M_insert_right()

iterator _M_insert_right | ( | _Link_type | __N,
|  | const_reference | __V
| ) |  |

inline protected

## ◆ _M_matches_node()

bool _M_matches_node | ( | _Link_const_type | __N,
|  | const_reference | __V,
|  | size_type | __L = `0`
| ) |  | const

inline protected

## ◆ _M_matches_node_in_d()

bool _M_matches_node_in_d | ( | _Link_const_type | __N,
|  | const_reference | __V,
|  | size_type const | __L
| ) |  | const

inline protected

## ◆ _M_matches_node_in_other_ds()

bool _M_matches_node_in_other_ds | ( | _Link_const_type | __N,
|  | const_reference | __V,
|  | size_type const | __L = `0`
| ) |  | const

inline protected

## ◆ _M_new_node()

_Link_type _M_new_node | ( | const_reference | __V,
|  | _Base_ptr const | __PARENT = `nullptr`,
|  | _Base_ptr const | __LEFT = `nullptr`,
|  | _Base_ptr const | __RIGHT = `nullptr`
| ) |  |

inline protected

## ◆ _M_optimise()

void _M_optimise | ( | _Iter const & | __A,
|  | _Iter const & | __B,
|  | size_type const | __L
| ) |  |

inline protected

## ◆ _M_set_leftmost()

void _M_set_leftmost | ( | _Node_base * | a | ) |

inline protected

## ◆ _M_set_rightmost()

void _M_set_rightmost | ( | _Node_base * | a | ) |

inline protected

## ◆ _M_set_root()

void _M_set_root | ( | _Link_type | n | ) |

inline protected

## ◆ _M_visit_within_range()

Visitor _M_visit_within_range | ( | Visitor | visitor,
|  | _Link_const_type | N,
|  | _Region_ const & | REGION,
|  | _Region_ const & | BOUNDS,
|  | size_type const | L
| ) |  | const

inline protected

## ◆ _S_is_leaf()

static bool _S_is_leaf | ( | _Base_const_ptr | N | ) |

inline static protected

## ◆ _S_left() [1/2]

static _Link_type _S_left | ( | _Base_ptr | N | ) |

inline static protected

## ◆ _S_left() [2/2]

static _Link_const_type _S_left | ( | _Base_const_ptr | N | ) |

inline static protected

## ◆ _S_maximum()

static _Link_const_type _S_maximum | ( | _Link_const_type | __X | ) |

inline static protected

## ◆ _S_minimum()

static _Link_const_type _S_minimum | ( | _Link_const_type | __X | ) |

inline static protected

## ◆ _S_parent() [1/2]

static _Link_type _S_parent | ( | _Base_ptr | N | ) |

inline static protected

## ◆ _S_parent() [2/2]

static _Link_const_type _S_parent | ( | _Base_const_ptr | N | ) |

inline static protected

## ◆ _S_right() [1/2]

static _Link_type _S_right | ( | _Base_ptr | N | ) |

inline static protected

## ◆ _S_right() [2/2]

static _Link_const_type _S_right | ( | _Base_const_ptr | N | ) |

inline static protected

## ◆ _S_set_left()

static void _S_set_left | ( | _Base_ptr | N,
|  | _Base_ptr | l
| ) |  |

inline static protected

## ◆ _S_set_parent()

static void _S_set_parent | ( | _Base_ptr | N,
|  | _Base_ptr | p
| ) |  |

inline static protected

## ◆ _S_set_right()

static void _S_set_right | ( | _Base_ptr | N,
|  | _Base_ptr | r
| ) |  |

inline static protected

## ◆ _S_value() [1/2]

static const_reference _S_value | ( | _Link_const_type | N | ) |

inline static protected

## ◆ _S_value() [2/2]

static const_reference _S_value | ( | _Base_const_ptr | N | ) |

inline static protected

## ◆ begin()

const_iterator begin | ( |  | ) | const

inline

## ◆ check_tree()

void check_tree | ( |  | ) |

inline

## ◆ clear()

void clear | ( |  | ) |

inline

## ◆ count_within_range() [1/2]

size_type count_within_range | ( | const_reference | __V,
|  | subvalue_type const | __R
| ) |  | const

inline

## ◆ count_within_range() [2/2]

size_type count_within_range | ( | _Region_ const & | __REGION | ) | const

inline

## ◆ efficient_replace_and_optimise()

void efficient_replace_and_optimise | ( | std::vector< value_type > & | writable_vector | ) |

inline

## ◆ empty()

bool empty | ( |  | ) | const

inline

## ◆ end()

const_iterator end | ( |  | ) | const

inline

## ◆ erase() [1/2]

void erase | ( | const_reference | __V | ) |

inline

## ◆ erase() [2/2]

void erase | ( | const_iterator const & | __IT | ) |

inline

## ◆ erase_exact()

void erase_exact | ( | const_reference | __V | ) |

inline

## ◆ find()

const_iterator find | ( | SearchVal const & | __V | ) | const

inline

## ◆ find_exact()

const_iterator find_exact | ( | SearchVal const & | __V | ) | const

inline

## ◆ find_nearest() [1/2]

std::pair<const_iterator, distance_type> find_nearest | ( | SearchVal const & | __val | ) | const

inline

## ◆ find_nearest() [2/2]

std::pair<const_iterator, distance_type> find_nearest | ( | SearchVal const & | __val,
|  | distance_type | __max
| ) |  | const

inline

## ◆ find_nearest_if()

std::pair<const_iterator, distance_type> find_nearest_if | ( | SearchVal const & | __val,
|  | distance_type | __max,
|  | _Predicate | __p
| ) |  | const

inline

## ◆ find_within_range() [1/2]

_OutputIterator find_within_range | ( | SearchVal const & | val,
|  | subvalue_type const | range,
|  | _OutputIterator | out
| ) |  | const

inline

## ◆ find_within_range() [2/2]

_OutputIterator find_within_range | ( | _Region_ const & | region,
|  | _OutputIterator | out
| ) |  | const

inline

## ◆ get_allocator()

allocator_type get_allocator | ( |  | ) | const

inline

## ◆ insert() [1/5]

iterator insert | ( | iterator | ,
|  | const_reference | __V
| ) |  |

inline

## ◆ insert() [2/5]

iterator insert | ( | const_reference | __V | ) |

inline

## ◆ insert() [3/5]

void insert | ( | _InputIterator | __first,
|  | _InputIterator | __last
| ) |  |

inline

## ◆ insert() [4/5]

void insert | ( | iterator | __pos,
|  | size_type | __n,
|  | const value_type & | __x
| ) |  |

inline

## ◆ insert() [5/5]

void insert | ( | iterator | __pos,
|  | _InputIterator | __first,
|  | _InputIterator | __last
| ) |  |

inline

## ◆ max_size()

size_type max_size | ( |  | ) | const

inline

## ◆ operator=()

KDTree& operator= | ( | const KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc > & | __x | ) |

inline

## ◆ optimise()

void optimise | ( |  | ) |

inline

## ◆ optimize()

void optimize | ( |  | ) |

inline

## ◆ rbegin()

const_reverse_iterator rbegin | ( |  | ) | const

inline

## ◆ rend()

const_reverse_iterator rend | ( |  | ) | const

inline

## ◆ size()

size_type size | ( |  | ) | const

inline

## ◆ value_acc()

_Acc value_acc | ( |  | ) | const

inline

Accessor to the value's elements.

This accessor shall not be modified, it could invalidate the tree.

Returns
  a copy of the accessor used by the KDTree.

## ◆ value_comp()

_Cmp value_comp | ( |  | ) | const

inline

Comparator for the values in the KDTree.

The comparator shall not be modified, it could invalidate the tree.

Returns
  a copy of the comparator used by the KDTree.

## ◆ value_distance() [1/2]

const _Dist& value_distance | ( |  | ) | const

inline

Distance calculator between 2 value's element.

This functor can be modified. It's modification will only affect the behavior of the find and find_nearest functions.

Returns
  a reference to the distance calculator used by the KDTree.

## ◆ value_distance() [2/2]

_Dist& value_distance | ( |  | ) |

inline

## ◆ visit_within_range() [1/2]

Visitor visit_within_range | ( | SearchVal const & | V,
|  | subvalue_type const | R,
|  | Visitor | visitor
| ) |  | const

inline

## ◆ visit_within_range() [2/2]

Visitor visit_within_range | ( | _Region_ const & | REGION,
|  | Visitor | visitor
| ) |  | const

inline

## Member Data Documentation

## ◆ _M_acc

_Acc _M_acc

protected

## ◆ _M_cmp

_Cmp _M_cmp

protected

## ◆ _M_count

size_type _M_count

protected

## ◆ _M_dist

_Dist _M_dist

protected

## ◆ _M_header

_Node_base _M_header

protected

## ◆ _M_root

_Link_type _M_root

protected