KDTree Namespace Reference

Classes
class	_Alloc_base
class	_Base_iterator
struct	_Bracket_accessor
class	_Iterator
struct	_Node
struct	_Node_base
class	_Node_compare
struct	_Region
struct	always_true
class	KDTree
struct	squared_difference
struct	squared_difference_counted

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 &)

Function Documentation

_S_accumulate_node_distance()

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  )

inline

Compute the distance between two values and accumulate the result for all dimensions.

The distance functor and the accessor are references to the template parameters of the KDTree.

Referenced by KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::find_nearest(), KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::find_nearest(), and KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::find_nearest_if().

_S_node_compare()

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  )

inline

Compare two values on the same dimension using a comparison functor _Cmp and an accessor _Acc.

The comparison functor and the accessor are references to the template parameters of the KDTree.

Referenced by _S_node_descend(), and _S_node_nearest().

_S_node_descend()

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  )

inline

Descend on the left or the right of the node according to the comparison between the node's value and the value.

Note

it's the caller responsibility to check if node is NULL.

References _S_node_compare().

Referenced by _S_node_nearest().

_S_node_distance()

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  )

inline

Compute the distance between two values for one dimension only.

The distance functor and the accessor are references to the template parameters of the KDTree.

Referenced by _S_node_nearest().

_S_node_nearest()

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  )

inline

Find the nearest node to __val from __node

If many nodes are equidistant to __val, the node with the lowest memory address is returned.

Returns

the nearest node of __end node if no nearest node was found for the given arguments.

References _S_node_compare(), _S_node_descend(), and _S_node_distance().

Referenced by KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::find_nearest(), KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::find_nearest(), and KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >::find_nearest_if().

operator!=() [1/3]

template<typename _Val , typename _Ref , typename _Ptr >

bool operator!= ( _Iterator< _Val, _Ref, _Ptr > const &  __X, _Iterator< _Val, _Ref, _Ptr > const &  __Y  )

inline

operator!=() [2/3]

template<typename _Val >

bool operator!= ( _Iterator< _Val, _Val &, _Val * > const &  __X, _Iterator< _Val, const _Val &, const _Val * > const &  __Y  )

inline

operator!=() [3/3]

template<typename _Val >

bool operator!= ( _Iterator< _Val, const _Val &, const _Val * > const &  __X, _Iterator< _Val, _Val &, _Val * > const &  __Y  )

inline

operator==() [1/3]

template<typename _Val , typename _Ref , typename _Ptr >

bool operator== ( _Iterator< _Val, _Ref, _Ptr > const &  __X, _Iterator< _Val, _Ref, _Ptr > const &  __Y  )

inline

operator==() [2/3]

template<typename _Val >

bool operator== ( _Iterator< _Val, _Val &, _Val * > const &  __X, _Iterator< _Val, const _Val &, const _Val * > const &  __Y  )

inline

operator==() [3/3]

template<typename _Val >

bool operator== ( _Iterator< _Val, const _Val &, const _Val * > const &  __X, _Iterator< _Val, _Val &, _Val * > const &  __Y  )

inline