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 >:

Collaboration 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, 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

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  )

inlineprotected

References _Node< _Val >::_M_value.

_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

References _Region< __K, _Val, _SubVal, _Acc, _Cmp >::encloses(), _Region< __K, _Val, _SubVal, _Acc, _Cmp >::intersects_with(), _Region< __K, _Val, _SubVal, _Acc, _Cmp >::set_high_bound(), and _Region< __K, _Val, _SubVal, _Acc, _Cmp >::set_low_bound().

_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

References _Node< _Val >::_M_value.

_M_find_exact()

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

inlineprotected

References _Node< _Val >::_M_value.

_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

References _Region< __K, _Val, _SubVal, _Acc, _Cmp >::encloses(), _Region< __K, _Val, _SubVal, _Acc, _Cmp >::intersects_with(), _Region< __K, _Val, _SubVal, _Acc, _Cmp >::set_high_bound(), and _Region< __K, _Val, _SubVal, _Acc, _Cmp >::set_low_bound().

_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

References _Node< _Val >::_M_value.

_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

References _Node< _Val >::_M_value.

_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

References _Alloc_base< _Tp, _Alloc >::NoLeakAlloc::disconnect(), and _Alloc_base< _Tp, _Alloc >::NoLeakAlloc::get().

_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

References _Region< __K, _Val, _SubVal, _Acc, _Cmp >::encloses(), _Region< __K, _Val, _SubVal, _Acc, _Cmp >::intersects_with(), _Region< __K, _Val, _SubVal, _Acc, _Cmp >::set_high_bound(), and _Region< __K, _Val, _SubVal, _Acc, _Cmp >::set_low_bound().

_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

References _Node_base::_S_maximum().

_S_minimum()

static _Link_const_type _S_minimum ( _Link_const_type  __X )

inlinestaticprotected

References _Node_base::_S_minimum().

_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

References _Node< _Val >::_M_value.

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

References _Iterator< _Val, _Ref, _Ptr >::get_raw_node().

erase() [2/2]

void erase ( const_reference  __V )

inline

References seqan::find().

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

References KDTree::_S_accumulate_node_distance(), and KDTree::_S_node_nearest().

find_nearest() [2/2]

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

inline

References KDTree::_S_accumulate_node_distance(), and KDTree::_S_node_nearest().

find_nearest_if()

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

inline

References KDTree::_S_accumulate_node_distance(), and KDTree::_S_node_nearest().

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

References KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::_M_acc.

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

Referenced by KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::operator=().

_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