OpenMS  2.8.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 >:
[legend]
Collaboration diagram for KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >:
[legend]

Public Types

typedef _Region< __K, _Val, typename _Acc::result_type, _Acc, _Cmp > _Region_
 
typedef _Val value_type
 
typedef value_typepointer
 
typedef value_type const * const_pointer
 
typedef value_typereference
 
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_pointerconst_iterator
 
typedef const_iterator iterator
 
typedef std::reverse_iterator< const_iteratorconst_reverse_iterator
 
typedef std::reverse_iterator< iteratorreverse_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)
 
KDTreeoperator= (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_typefind_nearest (SearchVal const &__val) const
 
template<class SearchVal >
std::pair< const_iterator, distance_typefind_nearest (SearchVal const &__val, distance_type __max) const
 
template<class SearchVal , class _Predicate >
std::pair< const_iterator, distance_typefind_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, std::allocator< _Node< _Val > > >
typedef _Node< _Val > _Node_
 
typedef _Node_::_Base_ptr _Base_ptr
 
typedef std::allocator< _Node< _Val > > 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, std::allocator< _Node< _Val > > >
_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, std::allocator< _Node< _Val > > >
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

◆ 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

◆ pointer

typedef value_type* pointer

◆ 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 
)
inlineprotected

◆ _M_check_node()

void _M_check_node ( _Link_const_type  node,
size_type const  level 
)
inlineprotected

◆ _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
inlineprotected

◆ _M_delete_node()

void _M_delete_node ( _Link_type  __p)
inlineprotected

◆ _M_empty_initialise()

void _M_empty_initialise ( )
inlineprotected

◆ _M_erase()

_Link_type _M_erase ( _Link_type  dead_dad,
size_type const  level 
)
inlineprotected

◆ _M_erase_subtree()

void _M_erase_subtree ( _Link_type  __n)
inlineprotected

◆ _M_find()

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

◆ _M_find_exact()

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

◆ _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
inlineprotected

◆ _M_get_erase_replacement()

_Link_type _M_get_erase_replacement ( _Link_type  node,
size_type const  level 
)
inlineprotected

◆ _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 
)
inlineprotected

◆ _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 
)
inlineprotected

◆ _M_get_leftmost()

_Link_const_type _M_get_leftmost ( ) const
inlineprotected

◆ _M_get_rightmost()

_Link_const_type _M_get_rightmost ( ) const
inlineprotected

◆ _M_get_root() [1/2]

_Link_type _M_get_root ( )
inlineprotected

◆ _M_get_root() [2/2]

_Link_const_type _M_get_root ( ) const
inlineprotected

◆ _M_insert()

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

◆ _M_insert_left()

iterator _M_insert_left ( _Link_type  __N,
const_reference  __V 
)
inlineprotected

◆ _M_insert_right()

iterator _M_insert_right ( _Link_type  __N,
const_reference  __V 
)
inlineprotected

◆ _M_matches_node()

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

◆ _M_matches_node_in_d()

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

◆ _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
inlineprotected

◆ _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 
)
inlineprotected

◆ _M_optimise()

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

◆ _M_set_leftmost()

void _M_set_leftmost ( _Node_base a)
inlineprotected

◆ _M_set_rightmost()

void _M_set_rightmost ( _Node_base a)
inlineprotected

◆ _M_set_root()

void _M_set_root ( _Link_type  n)
inlineprotected

◆ _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
inlineprotected

◆ _S_is_leaf()

static bool _S_is_leaf ( _Base_const_ptr  N)
inlinestaticprotected

◆ _S_left() [1/2]

static _Link_const_type _S_left ( _Base_const_ptr  N)
inlinestaticprotected

◆ _S_left() [2/2]

static _Link_type _S_left ( _Base_ptr  N)
inlinestaticprotected

References _Node_base::_M_left.

◆ _S_maximum()

static _Link_const_type _S_maximum ( _Link_const_type  __X)
inlinestaticprotected

◆ _S_minimum()

static _Link_const_type _S_minimum ( _Link_const_type  __X)
inlinestaticprotected

◆ _S_parent() [1/2]

static _Link_const_type _S_parent ( _Base_const_ptr  N)
inlinestaticprotected

◆ _S_parent() [2/2]

static _Link_type _S_parent ( _Base_ptr  N)
inlinestaticprotected

References _Node_base::_M_parent.

◆ _S_right() [1/2]

static _Link_const_type _S_right ( _Base_const_ptr  N)
inlinestaticprotected

◆ _S_right() [2/2]

static _Link_type _S_right ( _Base_ptr  N)
inlinestaticprotected

References _Node_base::_M_right.

◆ _S_set_left()

static void _S_set_left ( _Base_ptr  N,
_Base_ptr  l 
)
inlinestaticprotected

References _Node_base::_M_left.

◆ _S_set_parent()

static void _S_set_parent ( _Base_ptr  N,
_Base_ptr  p 
)
inlinestaticprotected

References _Node_base::_M_parent.

◆ _S_set_right()

static void _S_set_right ( _Base_ptr  N,
_Base_ptr  r 
)
inlinestaticprotected

References _Node_base::_M_right.

◆ _S_value() [1/2]

static const_reference _S_value ( _Base_const_ptr  N)
inlinestaticprotected

◆ _S_value() [2/2]

static const_reference _S_value ( _Link_const_type  N)
inlinestaticprotected

◆ 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 ( _Region_ const &  __REGION) const
inline

◆ count_within_range() [2/2]

size_type count_within_range ( const_reference  __V,
subvalue_type const  __R 
) 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_iterator const &  __IT)
inline

◆ erase() [2/2]

void erase ( const_reference  __V)
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 ( _Region_ const &  region,
_OutputIterator  out 
) const
inline

◆ find_within_range() [2/2]

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

◆ get_allocator()

allocator_type get_allocator ( ) const
inline

◆ insert() [1/5]

void insert ( _InputIterator  __first,
_InputIterator  __last 
)
inline

◆ insert() [2/5]

iterator insert ( const_reference  __V)
inline

◆ insert() [3/5]

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

◆ insert() [4/5]

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

◆ insert() [5/5]

iterator insert ( iterator  ,
const_reference  __V 
)
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]

_Dist& value_distance ( )
inline

◆ value_distance() [2/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.

◆ visit_within_range() [1/2]

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

◆ visit_within_range() [2/2]

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

References OpenMS::Constants::R.

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