node.hpp File Reference

Defines interfaces for nodes as used by the KDTree class. More...

#include <cstddef>
#include <cmath>

Include dependency graph for node.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	kd_tree::_Node_base
struct	kd_tree::_Node< _Val >
class	kd_tree::_Node_compare< _Val, _Acc, _Cmp >

Functions
template<typename _ValA , typename _ValB , typename _Cmp , typename _Acc >
bool	kd_tree::_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	kd_tree::_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	kd_tree::_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 >
_Node_base *	kd_tree::_S_node_descend (const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _Val &__val, const _Node_base *__node)
template<class SearchVal , typename _Val , typename _Cmp , typename _Acc , typename _Dist , typename _Predicate >
std::pair< const _Node< _Val > *, std::pair< size_t, typename _Dist::distance_type > >	kd_tree::_S_node_nearest (const size_t __k, size_t __dim, SearchVal const &__val, const _Node< _Val > *__node, const _Node_base *__end, const _Node< _Val > *__best, typename _Dist::distance_type __max, const _Cmp &__cmp, const _Acc &__acc, const _Dist &__dist, _Predicate __p)

Detailed Description

Defines interfaces for nodes as used by the KDTree class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Function Documentation

_S_accumulate_node_distance()

template<typename _ValA , typename _ValB , typename _Dist , typename _Acc >

_Dist::distance_type kd_tree::_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.

_S_node_compare()

template<typename _ValA , typename _ValB , typename _Cmp , typename _Acc >

bool kd_tree::_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.

_S_node_descend()

template<typename _Val , typename _Cmp , typename _Acc >

_Node_base* kd_tree::_S_node_descend ( const size_t  __dim, const _Cmp &  __cmp, const _Acc &  __acc, const _Val &  __val, const _Node_base *  __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.

_S_node_distance()

template<typename _ValA , typename _ValB , typename _Dist , typename _Acc >

_Dist::distance_type kd_tree::_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.

_S_node_nearest()

template<class SearchVal , typename _Val , typename _Cmp , typename _Acc , typename _Dist , typename _Predicate >

std::pair<const _Node<_Val>*, std::pair<size_t, typename _Dist::distance_type> > kd_tree::_S_node_nearest ( const size_t  __k, size_t  __dim, SearchVal const &  __val, const _Node< _Val > *  __node, const _Node_base *  __end, const _Node< _Val > *  __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.