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

Collaboration diagram for KDTree::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 std::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)

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.

_Acc	value_acc () const
	Accessor to the value's elements.

const _Dist &	value_distance () const
	Distance calculator between 2 value's element.

_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

const_iterator	find_within_range_iterative (const_reference __a, const_reference __b)

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 KDTree::_Alloc_base< _Tp, _Alloc >
typedef _Node< _Tp >	_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=NULL, _Base_ptr const __LEFT=NULL, _Base_ptr const __RIGHT=NULL)

void	_M_delete_node (_Link_type __p)

Protected Member Functions inherited from KDTree::_Alloc_base< _Tp, _Alloc >
_Node_ *	_M_allocate_node ()

void	_M_deallocate_node (_Node_ *const __P)

void	_M_construct_node (_Node_ *__p, _Tp const __V=_Tp(), _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 KDTree::_Alloc_base< _Tp, _Alloc >
allocator_type	_M_node_allocator

Member Function Documentation

◆ value_acc()

template<size_t const __K, typename _Val, typename _Acc = _Bracket_accessor<_Val>, typename _Dist = squared_difference<typename _Acc::result_type, typename _Acc::result_type>, typename _Cmp = std::less<typename _Acc::result_type>, typename _Alloc = std::allocator<_Node<_Val> >>

_Acc KDTree::KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::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()

template<size_t const __K, typename _Val, typename _Acc = _Bracket_accessor<_Val>, typename _Dist = squared_difference<typename _Acc::result_type, typename _Acc::result_type>, typename _Cmp = std::less<typename _Acc::result_type>, typename _Alloc = std::allocator<_Node<_Val> >>

_Cmp KDTree::KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::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()

template<size_t const __K, typename _Val, typename _Acc = _Bracket_accessor<_Val>, typename _Dist = squared_difference<typename _Acc::result_type, typename _Acc::result_type>, typename _Cmp = std::less<typename _Acc::result_type>, typename _Alloc = std::allocator<_Node<_Val> >>

const _Dist & KDTree::KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::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.

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Member Function Documentation

◆ value_acc()

◆ value_comp()

◆ value_distance()