Defines the namespace that contains all implementation-level utilities needed by the component of the library. More...

Classes
class	Bidirectional_iterator
	A common template for bidirectional iterators that work on identical modes of linking. More...

struct	builtin_difference
	This internal type casting is used to resolve a built-in compare functor (provided by the library) into a built-in difference functor. More...

struct	builtin_difference< accessor_less< Accessor, Key > >

struct	builtin_difference< bracket_less< Key > >

struct	builtin_difference< iterator_less< Key > >

struct	builtin_difference< paren_less< Key > >

struct	Compress
	Uses the empty base class optimization in order to compress a potentially empty base class with a member of a class. More...

struct	condition

struct	condition< false, Tp1, Tp2 >

class	Const_bidirectional_iterator
	A common template for constant bidirectional iterators that work on identical modes of linking. More...

class	Const_node_iterator
	A bidirectional iterator traversing all node in the tree in inorder traversal. More...

struct	Dynamic_rank
	The dimension value is stored by a member of the object, but can be modified at run time. More...

struct	Equal

struct	is_compare_builtin
	Statically resolve if key_compare used in the container `corresponds` to one of the builtin library comparators or not. More...

struct	is_compare_builtin_helper
	Help to resolve whether the type used is a builtin comparator or not. More...

struct	is_compare_builtin_helper< accessor_less< Accessor, Tp > >

struct	is_compare_builtin_helper< bracket_less< Tp > >

struct	is_compare_builtin_helper< iterator_less< Tp > >

struct	is_compare_builtin_helper< paren_less< Tp > >

struct	is_difference_builtin
	Help to resolve whether the type used is a builtin difference or not. More...

struct	is_difference_builtin< accessor_minus< Accessor, Tp, Unit > >

struct	is_difference_builtin< bracket_minus< Tp, Unit > >

struct	is_difference_builtin< iterator_minus< Tp, Unit > >

struct	is_difference_builtin< paren_minus< Tp, Unit > >

class	Kdtree
	Detailed implementation of the kd-tree. More...

struct	Kdtree_link
	Define the link type for a Kdtree that contains the value member. More...

struct	Mapping
	Extra information needed by the iterator to perform its work. More...

struct	mapping_compare

struct	mutate
	Changes a const type into a mutable type. More...

struct	mutate< const Tp >

struct	Neighbor_data
	Extra information needed by the iterator to perform its work. More...

struct	Node
	The basic node for any tree in the library. More...

class	Node_iterator
	A bidirectional iterator traversing all node in the tree in inorder traversal. More...

struct	Preorder_node_iterator
	A forward iterator that iterates through the node of the container in preorder transversal. More...

struct	rebind_builtin_difference
	If `Diff` is a builtin difference type, change the current unit of Diff to the DistanceType specified in the template parameter. More...

struct	rebind_builtin_difference< accessor_minus< Accessor, Tp, Unit >, DistanceType >
	Specialization of rebind_builtin_difference for the built-in spatial::accessor_minus functor. More...

struct	rebind_builtin_difference< bracket_minus< Tp, Unit >, DistanceType >
	Specialization of rebind_builtin_difference for the built-in spatial::bracket_minus functor. More...

struct	rebind_builtin_difference< iterator_minus< Tp, Unit >, DistanceType >
	Specialization of rebind_builtin_difference for the built-in spatial::iterator_minus functor. More...

struct	rebind_builtin_difference< paren_minus< Tp, Unit >, DistanceType >
	Specialization of rebind_builtin_difference for the built-in spatial::paren_minus functor. More...

struct	relaxed_invariant_tag
	The category of invariants for a k-d tree node: strict or relaxed. More...

class	Relaxed_kdtree
	Detailed implementation of the kd-tree. More...

struct	Relaxed_kdtree_link
	Define a weighted link type for the relaxed k-d tree. More...

struct	Static_rank
	The dimension value is set by a template value, thus consuming no memory. More...

struct	strict_invariant_tag

struct	template_member_assign

struct	template_member_assign_provider
	Perform a specialized assign for empty classes. More...

struct	template_member_assign_provider< true, Tp >

struct	template_member_swap

struct	template_member_swap_provider
	Perform a specialized swap for empty classes. More...

struct	template_member_swap_provider< true, Tp >

struct	ValueCompare
	Value compare functor for container storing pairs of (Key, Mapped) types, such as in spatial::point_multimap, spatial::box_multimap, etc. More...

struct	with_builtin_difference
	The generic helper class to determine if a container uses a built-in compare type. More...

struct	with_builtin_difference < Container, typename enable_if< is_compare_builtin< Container > >::type >
	Retrieve the builtin difference functor on the condition that the compare functor used in Container is a builtin comparator. More...

Functions
template<typename Type1 , typename Type2 >
void	assign (Type1 &first, Type2 &second, const std::pair< Type1, Type2 > &pair)

template<typename Container >
bool	right_traversal (typename Container::mode_type::const_node_ptr node, dimension_type dim, const Equal< Container > &equal)

template<typename Container >
bool	stop_traversal (typename Container::mode_type::const_node_ptr node, typename Container::rank_type rank, const Equal< Container > &equal)
	Return a boolean indicating whether all of `x's` coordinates are equal to `y's` coordinates. More...

template<typename Container >
bool	left_traversal (typename Container::mode_type::const_node_ptr node, dimension_type dim, const Equal< Container > &equal, relaxed_invariant_tag)

template<typename Container >
bool	left_traversal (typename Container::mode_type::const_node_ptr node, dimension_type dim, const Equal< Container > &equal, strict_invariant_tag)

template<typename Container >
bool	left_traversal (typename Container::mode_type::const_node_ptr node, dimension_type dim, const Equal< Container > &equal)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key >
std::pair< NodePtr, dimension_type >	first_equal (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Key &key)

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
void	swap (Kdtree< Rank, Key, Value, Compare, Alloc > &left, Kdtree< Rank, Key, Value, Compare, Alloc > &right)
	Swap the content of the tree `left` and `right`. More...

template<typename InputIterator >
std::ptrdiff_t	random_access_iterator_distance (InputIterator first, InputIterator last, std::random_access_iterator_tag)

template<typename InputIterator >
std::ptrdiff_t	random_access_iterator_distance (InputIterator, InputIterator, std::input_iterator_tag)

template<typename NodePtr , typename Rank , typename KeyCompare >
std::pair< NodePtr, dimension_type >	minimum_mapping (NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
	Move the iterator given in parameter to the minimum value along the iterator's mapping dimension but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename NodePtr , typename Rank , typename KeyCompare >
std::pair< NodePtr, dimension_type >	maximum_mapping (NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
	Move the iterator given in parameter to the maximum value along the iterator's mapping dimension but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	last_neighbor_sub (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type best_dist)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	last_neighbor (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	first_neighbor_sub (NodePtr node, dimension_type dim, Rank rank, const KeyCompare &key_comp, const Metric &met, const Key &target, typename Metric::distance_type best_dist)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	first_neighbor (NodePtr node, dimension_type dim, Rank rank, const KeyCompare &key_comp, const Metric &met, const Key &target)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	lower_bound_neighbor_sub (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type bound, typename Metric::distance_type best_dist)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	lower_bound_neighbor (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type bound)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	upper_bound_neighbor_sub (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, Metric met, const Key &target, typename Metric::distance_type bound, typename Metric::distance_type best_dist)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	upper_bound_neighbor (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type bound)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	increment_neighbor (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type node_dist)

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >
import::tuple< NodePtr, dimension_type, typename Metric::distance_type >	decrement_neighbor (NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type node_dist)

template<typename Link >
bool	header (const Node< Link > *x)
	Check if node is a header node. More...

template<typename Link >
const Node< Link > *	preorder_increment (const Node< Link > *x)
	Reach the next node in preorder transversal. More...

template<typename Link >
Link::invariant_category	invariant_category (const Node< Link > *)
	For a given node, this function returns the invariant category of the node. More...

template<typename Value >
const Kdtree_link< Value, Value >::key_type &	const_key (const Node< Kdtree_link< Value, Value > > *node)
	This function converts a pointer on a node into a key for a Kdtree_link type. More...

template<typename Key , typename Value >
const Kdtree_link< Key, Value >::key_type &	const_key (const Node< Kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a key for a Kdtree_link type. More...

template<typename Value >
const Relaxed_kdtree_link< Value, Value >::key_type &	const_key (const Node< Relaxed_kdtree_link< Value, Value > > *node)
	This function converts a pointer on a node into a key for a Relaxed_kdtree_link type. More...

template<typename Key , typename Value >
const Relaxed_kdtree_link< Key, Value >::key_type &	const_key (const Node< Relaxed_kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a key for a Relaxed_kdtree_link type. More...

template<typename Container >
ordered_iterator< Container > &	increment_ordered (ordered_iterator< Container > &iter)
	Move the pointer given in parameter to the next element in the ordered iteration of values along the ordered dimension. More...

template<typename Container >
ordered_iterator< Container > &	decrement_ordered (ordered_iterator< Container > &iter)
	Move the pointer given in parameter to the previous element in the ordered iteration of values along the ordered dimension. More...

template<typename Container >
ordered_iterator< Container > &	minimum_ordered (ordered_iterator< Container > &iter)
	Move the iterator given in parameter to the minimum value along the iterator's ordered dimension but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename Container >
ordered_iterator< Container > &	maximum_ordered (ordered_iterator< Container > &iter)
	Move the iterator given in parameter to the maximum value along the iterator's ordered dimension but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename Cmp , typename Rank , typename Key >
bool	order_ref (const Cmp &cmp, const Rank &rank, const Key &a, const Key &b)

template<typename Container >
ordered_iterator< Container > &	increment_ordered (ordered_iterator< Container > &iter, relaxed_invariant_tag)
	Specialization for iterators pointing to node using the relaxed invariant. More...

template<typename Container >
ordered_iterator< Container > &	increment_ordered (ordered_iterator< Container > &iter, strict_invariant_tag)
	Specialization for iterators pointing to node using the strict invariant. More...

template<typename Container >
ordered_iterator< Container > &	decrement_ordered (ordered_iterator< Container > &iter, relaxed_invariant_tag)

template<typename Container >
ordered_iterator< Container > &	decrement_ordered (ordered_iterator< Container > &iter, strict_invariant_tag)

template<typename Container >
ordered_iterator< Container > &	maximum_ordered (ordered_iterator< Container > &iter, relaxed_invariant_tag)
	Specialization for iterators pointed to node using the relaxed invariant. More...

template<typename Container >
ordered_iterator< Container > &	maximum_ordered (ordered_iterator< Container > &iter, strict_invariant_tag)
	Specialization for iterators pointed to node using the strict invariant. More...

template<typename NodePtr , typename Rank , typename Query >
std::pair< NodePtr, dimension_type >	preorder_first (NodePtr node, dimension_type dim, Rank rank, const Query &query)

template<typename NodePtr , typename Rank , typename Query >
std::pair< NodePtr, dimension_type >	preorder_last (NodePtr node, dimension_type dim, Rank rank, const Query &query)

template<typename NodePtr , typename Rank , typename Query >
std::pair< NodePtr, dimension_type >	preorder_increment (NodePtr node, dimension_type dim, Rank rank, const Query &query)

template<typename NodePtr , typename Rank , typename Query >
std::pair< NodePtr, dimension_type >	preorder_decrement (NodePtr node, dimension_type dim, Rank rank, const Query &query)

template<typename Rank >
dimension_type	incr_dim (Rank rank, dimension_type node_dim)
	Increment dimension `node_dim`, given `rank`. More...

template<typename Rank >
dimension_type	decr_dim (Rank rank, dimension_type node_dim)
	Decrement dimension `node_dim`, given `rank`. More...

template<typename Link , typename Rank >
dimension_type	modulo (const Node< Link > *x, Rank r)
	Returns the modulo of a node's heigth by a container's rank. More...

template<typename Ct , typename Predicate >
region_iterator< Ct, Predicate > &	increment_region (region_iterator< Ct, Predicate > &iter)
	From `iter`, returns the next matching iterator in the region delimited by `Predicate`, using in-order transversal. More...

template<typename Ct , typename Predicate >
region_iterator< Ct, Predicate > &	decrement_region (region_iterator< Ct, Predicate > &iter)
	From `iter`, returns the previous matching iterator in the region delimited by `Predicate`, using in-order transversal. More...

template<typename Ct , typename Predicate >
region_iterator< Ct, Predicate > &	minimum_region (region_iterator< Ct, Predicate > &iter)
	In the children of the node pointed to by `iter`, find the first matching iterator in the region delimited by `Predicate`, using in-order transversal. More...

template<typename Ct , typename Predicate >
region_iterator< Ct, Predicate > &	maximum_region (region_iterator< Ct, Predicate > &iter)
	In the children of the node pointed to by `iter`, find the last matching iterator in the region delimited by `Predicate`, using in-order transversal. More...

template<typename Rank , typename Key , typename Predicate >
bool	match_all (const Rank &rank, const Key &key, const Predicate &predicate)
	Return a boolean indicating whether all of `key's` coordinates are within range or not. More...

template<typename Container , typename Predicate >
region_iterator< Container, Predicate > &	increment_region (region_iterator< Container, Predicate > &iter)

template<typename Container , typename Predicate >
region_iterator< Container, Predicate > &	decrement_region (region_iterator< Container, Predicate > &iter)

template<typename Container , typename Predicate >
region_iterator< Container, Predicate > &	minimum_region (region_iterator< Container, Predicate > &iter)

template<typename Container , typename Predicate >
region_iterator< Container, Predicate > &	maximum_region (region_iterator< Container, Predicate > &iter)

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
void	swap (Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &left, Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &right)
	Swap the content of the relaxed k-d tree `left` and `right`. More...

template<typename NodePtr , typename Rank , typename KeyCompare >
std::pair< NodePtr, dimension_type >	increment_mapping (NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
	Move the pointer given in parameter to the next element in the ordered iteration of values along the mapping dimension. More...

template<typename NodePtr , typename Rank , typename KeyCompare >
std::pair< NodePtr, dimension_type >	decrement_mapping (NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
	Move the pointer given in parameter to the previous element in the ordered iteration of values along the mapping dimension. More...

template<typename NodePtr , typename Rank , typename KeyCompare , typename KeyType >
std::pair< NodePtr, dimension_type >	lower_bound_mapping (NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp, const KeyType &bound)
	Move the iterator given in parameter to the value with the smallest coordinate greater or equal to `bound` along the mapping dimension of `iter`, but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename NodePtr , typename Rank , typename KeyCompare , typename KeyType >
std::pair< NodePtr, dimension_type >	upper_bound_mapping (NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp, const KeyType &bound)
	Move the iterator given in parameter to the value with the largest coordinate strictly lower than `bound` along the mapping dimension of `iter`, but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename Container >
ordered_iterator< Container > &	lower_bound_ordered (ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound)
	Move the iterator given in parameter to the value with the smallest coordinate greater or equal to `bound` along the ordered dimension of `iter`, but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename Container >
ordered_iterator< Container > &	upper_bound_ordered (ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound)
	Move the iterator given in parameter to the value with the largest coordinate strictly lower than `bound` along the ordered dimension of `iter`, but only in the sub-tree composed of the node pointed to by the iterator and its children. More...

template<typename Cmp , typename Key >
bool	order_less (const Cmp &cmp, dimension_type set_dim, const Key &a, const Key &b)

template<typename Container >
ordered_iterator< Container > &	lower_bound_ordered (ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound, relaxed_invariant_tag)

template<typename Container >
ordered_iterator< Container > &	lower_bound_ordered (ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound, strict_invariant_tag)

template<typename Container >
ordered_iterator< Container > &	upper_bound_ordered (ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound, relaxed_invariant_tag)

template<typename Container >
ordered_iterator< Container > &	upper_bound_ordered (ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound, strict_invariant_tag)


template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
bool	operator== (const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
	The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
bool	operator!= (const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
	The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch. More...


template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
bool	operator< (const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
bool	operator> (const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
bool	operator<= (const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >
bool	operator>= (const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...


template<typename Tp >
Tp *	mutate_pointer (const Tp *p)
	A helper functions that mutates pointers. More...

template<typename Tp >
Tp *	mutate_pointer (Tp *p)
	A helper functions that mutates pointers. More...


template<typename Link >
Node< Link > *	minimum (Node< Link > *x)
	Reach the left most node. More...

template<typename Link >
const Node< Link > *	minimum (const Node< Link > *x)
	Reach the left most node. More...


template<typename Link >
Node< Link > *	maximum (Node< Link > *x)
	Reach the left most node. More...

template<typename Link >
const Node< Link > *	maximum (const Node< Link > *x)
	Reach the left most node. More...


template<typename Link >
Node< Link > *	increment (Node< Link > *x)
	Reach the next node in symetric transversal order. More...

template<typename Link >
const Node< Link > *	increment (const Node< Link > *x)
	Reach the next node in symetric transversal order. More...


template<typename Link >
Node< Link > *	decrement (Node< Link > *x)
	Reach the previous node in symetric transversal order. More...

template<typename Link >
const Node< Link > *	decrement (const Node< Link > *x)
	Reach the previous node in symetric transversal order. More...


template<typename Key , typename Value >
Kdtree_link< Key, Value > *	link (Node< Kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a link for a Kdtree_link type. More...

template<typename Key , typename Value >
const Kdtree_link< Key, Value > *	const_link (const Node< Kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a link for a Kdtree_link type. More...


template<typename Key , typename Value >
Kdtree_link< Key, Value >::value_type &	value (Node< Kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a value for a Kdtree_link type. More...

template<typename Key , typename Value >
const Kdtree_link< Key, Value >::value_type &	const_value (const Node< Kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a value for a Kdtree_link type. More...


template<typename Key , typename Value >
Relaxed_kdtree_link< Key, Value > *	link (Node< Relaxed_kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a link for a Relaxed_kdtree_link type. More...

template<typename Key , typename Value >
const Relaxed_kdtree_link< Key, Value > *	const_link (const Node< Relaxed_kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a link for a Relaxed_kdtree_link type. More...


template<typename Key , typename Value >
Relaxed_kdtree_link< Key, Value >::value_type &	value (Node< Relaxed_kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a value for a Relaxed_kdtree_link type. More...

template<typename Key , typename Value >
const Relaxed_kdtree_link< Key, Value >::value_type &	const_value (const Node< Relaxed_kdtree_link< Key, Value > > *node)
	This function converts a pointer on a node into a value for a Relaxed_kdtree_link type. More...


template<typename Link >
void	swap_node_aux (Node< Link > a, Node< Link > b)
	Swaps nodes position in the tree. More...

template<typename Key , typename Value >
void	swap_node (Node< Kdtree_link< Key, Value > > &a, Node< Kdtree_link< Key, Value > > &b)
	Swaps nodes position in the tree. More...

template<typename Key , typename Value >
void	swap_node (Node< Relaxed_kdtree_link< Key, Value > > &a, Node< Relaxed_kdtree_link< Key, Value > > &b)
	Swaps nodes position in the tree. More...


template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
bool	operator== (const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &lhs, const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &rhs)
	The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
bool	operator!= (const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &lhs, const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &rhs)
	The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch. More...


template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
bool	operator< (const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &lhs, const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
bool	operator> (const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &lhs, const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
bool	operator<= (const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &lhs, const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
bool	operator>= (const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &lhs, const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &rhs)
	Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch. More...


template<typename KeyCompare , typename Key >
bool	left_compare_mapping (KeyCompare key_comp, dimension_type map, const Key &x, const Key &y, strict_invariant_tag)
	This function provides a common interface for the two k-d tree invariants. More...

template<typename KeyCompare , typename Key >
bool	left_compare_mapping (KeyCompare key_comp, dimension_type map, const Key &x, const Key &y, relaxed_invariant_tag)
	This function provides a common interface for the two k-d tree invariants. More...

Detailed Description

Defines the namespace that contains all implementation-level utilities needed by the component of the library.

The types and functions defined within this namespace should not normally be needed by end-users of the library. If you are currently using one of them, please refer to the documentation for these functions or object as there may be more appropriate functions for you to use.

If you do not find a more appropriate function to use, then you may suggest a feature improvement to the library author.

Class Documentation

struct spatial::details::with_builtin_difference < Container, typename enable_if< is_compare_builtin< Container > >::type >::builtin_difference

template<typename>
struct spatial::details::builtin_difference< typename >

This internal type casting is used to resolve a built-in compare functor (provided by the library) into a built-in difference functor.

It will not work for user defined comparators; it means that if you are using a user-defined comparator in your container, you should also use a user-defined metric.

Template Parameters

Compare	The comparator used in the container.
DistanceType	The type used to express distances.

Definition at line 104 of file spatial_builtin.hpp.

struct spatial::details::condition

template<bool, typename Tp1, typename Tp2>
struct spatial::details::condition< bool, Tp1, Tp2 >

Definition at line 25 of file spatial_condition.hpp.

Class Members
typedef Tp1	type

struct spatial::details::condition< false, Tp1, Tp2 >

template<typename Tp1, typename Tp2>
struct spatial::details::condition< false, Tp1, Tp2 >

Definition at line 28 of file spatial_condition.hpp.

Class Members
typedef Tp2	type

struct spatial::details::mutate

template<typename Tp>
struct spatial::details::mutate< Tp >

Changes a const type into a mutable type.

Definition at line 25 of file spatial_mutate.hpp.

Class Members
typedef Tp	type

struct spatial::details::mutate< const Tp >

template<typename Tp>
struct spatial::details::mutate< const Tp >

Definition at line 27 of file spatial_mutate.hpp.

Class Members
typedef Tp	type

struct spatial::details::Node

template<typename Link>
struct spatial::details::Node< Link >

The basic node for any tree in the library.

It contains only the information necessary to iterate through all nodes and the library, as well as access the values of a node. However it does not link to the value by itself.

All nodes in all containers in the library obey the invariant: if at the head, the left points to the head itself, always, by convention. This way, the header node can be identified readily. It is a very important feature of the library that only by looking at a node, one can tell whether the head of the tree has been reached or not.

Once at the head, the parent pointer will point to the root of the tree, while the right pointer will point to the right most node in the tree. Therefore, to store the left-most node in the tree, an additional pointer is required in each container.

This class also holds a model of Link Mode to access the key and values of the node, without holding these values. It deliberately does not hold these values for 2 reasons:

Not all nodes store their keys and values in the same way.
Some nodes have more information than just key and values.

Additionally, when deferencing a pointer from a node, only the minimum amount of information is transferred to the variable holding the node, which happens in several algorithms.

Template Parameters

Mode	A model of Link Mode

Definition at line 57 of file spatial_node.hpp.

Class Members
typedef Link	link_type	The link type that indicate how to reach the key and/or the value from the node.

Class Members
Node *	left	A pointer to the left child node of the current node. If we are at the head, this pointer will always points to the head: this is an important property of the nodes that is exploited by the header() function used in nearly every algorithm to identify the header node. If there are no node to the left, the pointer is null.
Node *	parent	A pointer to the parent of the current node. When we are at head, the parent pointer is equal to the current node. In all other cases it is different. When this value is null, the node has not been initialized and it is dangling.
Node *	right	A pointer to the right child node of the current node. If we are at the head, this pointer points to the right most node in the tree. If there are no node to the right, the pointer is null.

struct spatial::details::rebind_builtin_difference

template<typename Diff, typename DistanceType>
struct spatial::details::rebind_builtin_difference< Diff, DistanceType >

If Diff is a builtin difference type, change the current unit of Diff to the DistanceType specified in the template parameter.

If not, type is simply equivalent to Diff.

This type is used to rebind the metric from one unit into another when using built-in difference type. This is necessary because when calling spatial::euclidian_neighbor_begin(), you do not have the possibility of specifying a type for the unit to use (the library assumes double). However that type can be defined in the return type, similarly to:

spatial::euclidian_neighbor_iterator<container_type, float> iter

= spatial::euclidian_neighbor_begin(container, target);

spatial::euclidian_neighbor_begin() first creates a metric of type spatial::euclidian with spatial::euclidian<container_type, double>, then this metric is rebound into a metric of type spatial::euclidian<container_type, float>.

Template Parameters

Diff	Either a built-in difference functor, or one provided by the user.
DistanceType	The distance to use for `Diff`, if `Diff` is a built-in difference functor.

See also: spatial::bracket_minus; spatial::paren_minus; spatial::accessor_minus; spatial::iterator_minus

Definition at line 213 of file spatial_builtin.hpp.

Class Members
typedef Diff	type

struct spatial::details::rebind_builtin_difference< accessor_minus< Accessor, Tp, Unit >, DistanceType >

template<typename Accessor, typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< accessor_minus< Accessor, Tp, Unit >, DistanceType >

Specialization of rebind_builtin_difference for the built-in spatial::accessor_minus functor.

Rebinds the functor to the requested unit type.

Definition at line 250 of file spatial_builtin.hpp.

Class Members
typedef accessor_minus < Accessor, Tp, DistanceType >	type

struct spatial::details::rebind_builtin_difference< bracket_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< bracket_minus< Tp, Unit >, DistanceType >

Specialization of rebind_builtin_difference for the built-in spatial::bracket_minus functor.

Rebinds the functor to the requested unit type.

Definition at line 222 of file spatial_builtin.hpp.

Class Members
typedef bracket_minus< Tp, DistanceType >	type

struct spatial::details::rebind_builtin_difference< iterator_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< iterator_minus< Tp, Unit >, DistanceType >

Specialization of rebind_builtin_difference for the built-in spatial::iterator_minus functor.

Rebinds the functor to the requested unit type.

Definition at line 240 of file spatial_builtin.hpp.

Class Members
typedef iterator_minus< Tp, DistanceType >	type

struct spatial::details::rebind_builtin_difference< paren_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< paren_minus< Tp, Unit >, DistanceType >

Specialization of rebind_builtin_difference for the built-in spatial::paren_minus functor.

Rebinds the functor to the requested unit type.

Definition at line 231 of file spatial_builtin.hpp.

Class Members
typedef paren_minus< Tp, DistanceType >	type

struct spatial::details::relaxed_invariant_tag

The category of invariants for a k-d tree node: strict or relaxed.

This tag is an indicator for one of the library's most central concepts: different types of node use different sets of invariant, or "rules" on their nodes.

With $N$ the current node, $d$ the current dimension of comparison for the node (or: the node's dimension), $k(N)$ the function that associate a node to its key, $l(N)$ and $r(N)$ the functions that associate a node to its left node and right node respectively, then for each tag, the following invarient rules are respected:

$\{ k(N)_d \geq k(l(N))_d \\ k(N)_d \leq k(r(N))_d \}$

for relaxed invarient tags, and:

$\{ k(N)_d > k(l(N))_d \\ k(N)_d \leq k(r(N))_d \}$

for strict invarient tags.

In other words, in relaxed invarient k-d tree, values equal to the node's value can be found both in the left and right sub-trees of the node, while in strict invarient k-d tree, value equal to the node's value can only be found on the right side of the node. This allows strict invarient k-d tree to be slightly faster during search if many similar values are present in the nodes. But it on the contrary, it makes them much harder to rebalance.

See also: LibraryInternals

Definition at line 220 of file spatial_node.hpp.

struct spatial::details::strict_invariant_tag

Definition at line 221 of file spatial_node.hpp.

struct spatial::details::with_builtin_difference

template<typename Container, typename Enable = void>
struct spatial::details::with_builtin_difference< Container, Enable >

The generic helper class to determine if a container uses a built-in compare type.

See the specializations of this class.

Definition at line 70 of file spatial_builtin.hpp.

Function Documentation

template<typename Type1 , typename Type2 >

void spatial::details::assign	(	Type1 &	first,
		Type2 &	second,
		const std::pair< Type1, Type2 > &	pair
	)

Definition at line 26 of file spatial_assign.hpp.

template<typename Value >

const Kdtree_link<Value, Value>::key_type& spatial::details::const_key ( const Node< Kdtree_link< Value, Value > > * node )

This function converts a pointer on a node into a key for a Kdtree_link type.

A key is always a constant type, hence only const_key is declared.

This overload is used when both the key type and the value type of the Relaxed_kdtree_link are of the same type, e.g. in set containers.

Template Parameters

Value the value type for the Kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 387 of file spatial_node.hpp.

template<typename Key , typename Value >

const Kdtree_link<Key, Value>::key_type& spatial::details::const_key ( const Node< Kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a key for a Kdtree_link type.

A key is always a constant type, hence only const_key is declared.

Template Parameters

Key	the key type for the Kdtree_link.
Value	the value type for the Kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 403 of file spatial_node.hpp.

template<typename Value >

const Relaxed_kdtree_link<Value, Value>::key_type& spatial::details::const_key ( const Node< Relaxed_kdtree_link< Value, Value > > * node )

This function converts a pointer on a node into a key for a Relaxed_kdtree_link type.

A key is always a constant type, hence only const_key exists.

This overload is used when both the key type and the value type of the Relaxed_kdtree_link are of the same type, e.g. in set containers.

Template Parameters

Value the value type for the Relaxed_kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 466 of file spatial_node.hpp.

template<typename Key , typename Value >

const Relaxed_kdtree_link<Key, Value>::key_type& spatial::details::const_key ( const Node< Relaxed_kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a key for a Relaxed_kdtree_link type.

A key is always a constant type, hence only const_key exists.

Template Parameters

Key	the key type for the Relaxed_kdtree_link
Value	the value type for the Relaxed_kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 483 of file spatial_node.hpp.

template<typename Key , typename Value >

const Kdtree_link<Key, Value>* spatial::details::const_link ( const Node< Kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a link for a Kdtree_link type.

Template Parameters

Key	the key type for the Kdtree_link.
Value	the value type for the Kdtree_link.

Parameters

node	the node to convert to a link.

Definition at line 369 of file spatial_node.hpp.

template<typename Key , typename Value >

const Relaxed_kdtree_link<Key, Value>* spatial::details::const_link ( const Node< Relaxed_kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a link for a Relaxed_kdtree_link type.

Template Parameters

Key	the key type for the Relaxed_kdtree_link.
Value	the value type for the Relaxed_kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 448 of file spatial_node.hpp.

template<typename Key , typename Value >

const Kdtree_link<Key, Value>::value_type& spatial::details::const_value ( const Node< Kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a value for a Kdtree_link type.

Template Parameters

Key	the key type for the Kdtree_link.
Value	the value type for the Kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 425 of file spatial_node.hpp.

template<typename Key , typename Value >

const Relaxed_kdtree_link<Key, Value>::value_type& spatial::details::const_value ( const Node< Relaxed_kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a value for a Relaxed_kdtree_link type.

Template Parameters

Key	the key type for the Relaxed_kdtree_link.
Value	the value type for the Relaxed_kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 506 of file spatial_node.hpp.

template<typename Rank >

dimension_type spatial::details::decr_dim	(	Rank	rank,
		dimension_type	node_dim
	)

Decrement dimension node_dim, given rank.

Template Parameters

Rank	Either spatial::details::Static_rank or spatial::details::Dynamic_rank.

Parameters

rank	The magnitude of the rank.
node_dim	The value of the dimension for the node.

Definition at line 79 of file spatial_rank.hpp.

template<typename Link >

Node< Link > * spatial::details::decrement ( Node< Link > * x )

Reach the previous node in symetric transversal order.

Should not be used on empty trees, but can be used on header nodes when the tree is not empty.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 756 of file spatial_node.hpp.

template<typename Link >

const Node<Link>* spatial::details::decrement ( const Node< Link > * x )

Reach the previous node in symetric transversal order.

Should not be used on empty trees, but can be used on header nodes when the tree is not empty.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 177 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare >

std::pair<NodePtr, dimension_type> spatial::details::decrement_mapping	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		dimension_type	map,
		KeyCompare	key_comp
	)

Move the pointer given in parameter to the previous element in the ordered iteration of values along the mapping dimension.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. You should use the overload operator-- on the spatial::mapping_iterator instead. This function does not perform any sanity checks on the iterator given in parameter.

Parameters

node	The pointer to the starting node for the iteration.
dim	The dimension use to compare the key at `node`.
rank	The cardinality or number of dimensions of the container being iterated.
map	The dimension along which all values in the container must be sorted.
key_comp	A functor to compare two keys in the container along a particular dimension.

Returns: An iterator pointing to the value with the smallest coordinate along iter's mapping_dim, and among the children of the node pointed to by iter.

Since Container is based on k-d tree and k-d tree exhibit good locality of reference (for arranging values in space, not for values location in memory), the function will run with time complexity close to $O(n (\log n)^{1/k})\,$ in practice.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 925 of file mapping_iterator.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::decrement_neighbor	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	node_dist
	)

Definition at line 1540 of file spatial_neighbor.hpp.

template<typename Container >

ordered_iterator< Container > & spatial::details::decrement_ordered ( ordered_iterator< Container > & iter )

Move the pointer given in parameter to the previous element in the ordered iteration of values along the ordered dimension.

Template Parameters

Container The type of container to iterate.

Parameters

iter	The reference iterator that points to the current node.

Returns: An iterator pointing to the value with the smallest coordinate along iter's ordered_dim, and among the children of the node pointed to by iter.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking to decrement an spatial::ordered_iterator via the overloaded operator--().

Since Container is based on a k-d tree and k-d trees exhibit good locality of reference (for arranging values in space, not for values location in memory), the function will run with time complexity close to $O(\log n)\,$ in practice.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 1014 of file spatial_ordered.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::decrement_ordered	(	ordered_iterator< Container > &	iter,
		relaxed_invariant_tag
	)

Definition at line 739 of file spatial_ordered.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::decrement_ordered	(	ordered_iterator< Container > &	iter,
		strict_invariant_tag
	)

Definition at line 877 of file spatial_ordered.hpp.

template<typename Ct , typename Predicate >

region_iterator<Ct, Predicate>& spatial::details::decrement_region ( region_iterator< Ct, Predicate > & iter )

From iter, returns the previous matching iterator in the region delimited by Predicate, using in-order transversal.

Parameters

iter	A valid region iterator or a past-the-end iterator.

Template Parameters

Predicate	The type of predicate for the orthogonal query.
Ct	The type of container to iterate.

Returns: An iterator pointing the previous value.

If iter is a past-the-end iterator (pointing to a header node), the function will return the maximum iterator in region.

template<typename Container , typename Predicate >

region_iterator<Container, Predicate>& spatial::details::decrement_region ( region_iterator< Container, Predicate > & iter )

Definition at line 692 of file spatial_region.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key >

std::pair<NodePtr, dimension_type> spatial::details::first_equal	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Key &	key
	)

Definition at line 419 of file spatial_equal.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::first_neighbor	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		const KeyCompare &	key_comp,
		const Metric &	met,
		const Key &	target
	)

Definition at line 1252 of file spatial_neighbor.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::first_neighbor_sub	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		const KeyCompare &	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	best_dist
	)

Definition at line 1193 of file spatial_neighbor.hpp.

template<typename Link >

bool spatial::details::header ( const Node< Link > * x )

Check if node is a header node.

This is done by checking that the left node points to itself. Only at the head, should this be the case. This important propriety is a convention of the library to identify the header node.

Definition at line 96 of file spatial_node.hpp.

template<typename Rank >

dimension_type spatial::details::incr_dim	(	Rank	rank,
		dimension_type	node_dim
	)

Increment dimension node_dim, given rank.

Template Parameters

Rank	Either spatial::details::Static_rank or spatial::details::Dynamic_rank.

Parameters

rank	The magnitude of the rank.
node_dim	The value of the dimension for the node.

Definition at line 68 of file spatial_rank.hpp.

template<typename Link >

Node< Link > * spatial::details::increment ( Node< Link > * x )

Reach the next node in symetric transversal order.

Should not be used on header nodes.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 738 of file spatial_node.hpp.

template<typename Link >

const Node<Link>* spatial::details::increment ( const Node< Link > * x )

Reach the next node in symetric transversal order.

Should not be used on header nodes.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 158 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare >

std::pair<NodePtr, dimension_type> spatial::details::increment_mapping	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		dimension_type	map,
		KeyCompare	key_comp
	)

Move the pointer given in parameter to the next element in the ordered iteration of values along the mapping dimension.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. You should use the overload operator++ on the spatial::mapping_iterator instead. This function does not perform any sanity checks on the iterator given in parameter.

Since Container is based on k-d tree and k-d tree exhibit good locality of reference (for arranging values in space, not for values location in memory), the function will run with time complexity close to $O(n (\log n)^{1/k})\,$ in practice.

Parameters

node	The pointer to the starting node for the iteration.
dim	The dimension use to compare the key at `node`.
rank	The cardinality or number of dimensions of the container being iterated.
map	The dimension along which all values in the container must be sorted.
key_comp	A functor to compare two keys in the container along a particular dimension.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 803 of file mapping_iterator.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::increment_neighbor	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	node_dist
	)

Definition at line 1417 of file spatial_neighbor.hpp.

template<typename Container >

ordered_iterator< Container > & spatial::details::increment_ordered ( ordered_iterator< Container > & iter )

Move the pointer given in parameter to the next element in the ordered iteration of values along the ordered dimension.

Template Parameters

Container The type of container to iterate.

Parameters

iter	The reference iterator that points to the current node.

Returns: An iterator pointing to the value with the smallest coordinate along iter's ordered_dim, and among the children of the node pointed to by iter.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking to increment an spatial::ordered_iterator via the overloaded operator++().

Since Container is based on a k-d tree and k-d trees exhibit good locality of reference (for arranging values in space, not for values location in memory), the function will run with time complexity close to $O(\log n)\,$ in practice.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 727 of file spatial_ordered.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::increment_ordered	(	ordered_iterator< Container > &	iter,
		relaxed_invariant_tag
	)

Specialization for iterators pointing to node using the relaxed invariant.

Definition at line 462 of file spatial_ordered.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::increment_ordered	(	ordered_iterator< Container > &	iter,
		strict_invariant_tag
	)

Specialization for iterators pointing to node using the strict invariant.

Definition at line 594 of file spatial_ordered.hpp.

template<typename Ct , typename Predicate >

region_iterator<Ct, Predicate>& spatial::details::increment_region ( region_iterator< Ct, Predicate > & iter )

From iter, returns the next matching iterator in the region delimited by Predicate, using in-order transversal.

Parameters

iter	A valid region iterator.

Template Parameters

Predicate	The type of predicate for the orthogonal query.
Ct	The type of container to iterate.

Returns: An iterator pointing the next matching value.

template<typename Container , typename Predicate >

region_iterator<Container, Predicate>& spatial::details::increment_region ( region_iterator< Container, Predicate > & iter )

Definition at line 647 of file spatial_region.hpp.

template<typename Link >

Link::invariant_category spatial::details::invariant_category ( const Node< Link > * )

For a given node, this function returns the invariant category of the node.

Definition at line 229 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::last_neighbor	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target
	)

Definition at line 1182 of file spatial_neighbor.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::last_neighbor_sub	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	best_dist
	)

Definition at line 1123 of file spatial_neighbor.hpp.

template<typename KeyCompare , typename Key >

bool spatial::details::left_compare_mapping	(	KeyCompare	key_comp,
		dimension_type	map,
		const Key &	x,
		const Key &	y,
		strict_invariant_tag
	)

This function provides a common interface for the two k-d tree invariants.

Definition at line 763 of file mapping_iterator.hpp.

template<typename KeyCompare , typename Key >

bool spatial::details::left_compare_mapping	(	KeyCompare	key_comp,
		dimension_type	map,
		const Key &	x,
		const Key &	y,
		relaxed_invariant_tag
	)

This function provides a common interface for the two k-d tree invariants.

Definition at line 770 of file mapping_iterator.hpp.

template<typename Container >

bool spatial::details::left_traversal	(	typename Container::mode_type::const_node_ptr	node,
		dimension_type	dim,
		const Equal< Container > &	equal,
		relaxed_invariant_tag
	)

Definition at line 83 of file spatial_equal.hpp.

template<typename Container >

bool spatial::details::left_traversal	(	typename Container::mode_type::const_node_ptr	node,
		dimension_type	dim,
		const Equal< Container > &	equal,
		strict_invariant_tag
	)

Definition at line 93 of file spatial_equal.hpp.

template<typename Container >

bool spatial::details::left_traversal	(	typename Container::mode_type::const_node_ptr	node,
		dimension_type	dim,
		const Equal< Container > &	equal
	)

Definition at line 103 of file spatial_equal.hpp.

template<typename Key , typename Value >

Kdtree_link<Key, Value>* spatial::details::link ( Node< Kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a link for a Kdtree_link type.

Template Parameters

Key	the key type for the Kdtree_link.
Value	the value type for the Kdtree_link.

Parameters

node	the node to convert to a link.

Definition at line 362 of file spatial_node.hpp.

template<typename Key , typename Value >

Relaxed_kdtree_link<Key, Value>* spatial::details::link ( Node< Relaxed_kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a link for a Relaxed_kdtree_link type.

Template Parameters

Key	the key type for the Relaxed_kdtree_link.
Value	the value type for the Relaxed_kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 441 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename KeyType >

std::pair<NodePtr, dimension_type> spatial::details::lower_bound_mapping	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		dimension_type	map,
		KeyCompare	key_comp,
		const KeyType &	bound
	)

Move the iterator given in parameter to the value with the smallest coordinate greater or equal to bound along the mapping dimension of iter, but only in the sub-tree composed of the node pointed to by the iterator and its children.

If no such value exists, then move the iterator to the parent of the value currently pointed to.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for mapping_begin(). In any case, use it cautiously, as this function does not perform any sanity checks on the iterator given in parameter.

Parameters

node	The pointer to the starting node for the iteration.
dim	The dimension use to compare the key at `node`.
rank	The cardinality or number of dimensions of the container being iterated.
map	The dimension along which all values in the container must be sorted.
key_comp	A functor to compare two keys in the container along a particular dimension.
bound	A boundary value to stop the search.

Returns: An iterator pointing to the value with the smallest coordinate greater or equal to bound along iter's mapping_dim, or to the parent of the value pointed to.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 1047 of file mapping_iterator.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::lower_bound_neighbor	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	bound
	)

Definition at line 1330 of file spatial_neighbor.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::lower_bound_neighbor_sub	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	bound,
		typename Metric::distance_type	best_dist
	)

Definition at line 1264 of file spatial_neighbor.hpp.

template<typename Container >

ordered_iterator< Container > & spatial::details::lower_bound_ordered	(	ordered_iterator< Container > &	iter,
		const typename container_traits< Container >::key_type &	bound
	)

Move the iterator given in parameter to the value with the smallest coordinate greater or equal to bound along the ordered dimension of iter, but only in the sub-tree composed of the node pointed to by the iterator and its children.

If no such value exists, then move the iterator to the parent of the value currently pointed to.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for ordered_begin(). In any case, use it cautiously, as this function does not perform any sanity checks on the iterator given in parameter.

Template Parameters

Container The type of container to iterate.

Parameters

iter	An iterator that points to the root node of the search.
bound	The lower bound to the iterator position.

Returns: An iterator pointing to the value with the smallest coordinate greater or equal to bound along iter's ordered_dim, or to the parent of the value pointed to.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 514 of file ordered_iterator.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::lower_bound_ordered	(	ordered_iterator< Container > &	iter,
		const typename container_traits< Container >::key_type &	bound,
		relaxed_invariant_tag
	)

Definition at line 355 of file ordered_iterator.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::lower_bound_ordered	(	ordered_iterator< Container > &	iter,
		const typename container_traits< Container >::key_type &	bound,
		strict_invariant_tag
	)

Definition at line 435 of file ordered_iterator.hpp.

template<typename Rank , typename Key , typename Predicate >

bool spatial::details::match_all	(	const Rank &	rank,
		const Key &	key,
		const Predicate &	predicate
	)

Return a boolean indicating whether all of key's coordinates are within range or not.

The key is simply tested across all dimesions over the predicate.

Template Parameters

Rank	Either spatial::details::Static_rank or spatial::details::Dynamic_rank.
Key	The key type that is used in the comparison.
Predicate	A type that is a model of Region Predicate.

Parameters

rank	The magnitude of the rank.
key	The key whose coordinates are verified to be within the range.
predicate	The Region Predicate object used to represent the range.

Definition at line 638 of file spatial_region.hpp.

template<typename Link >

Node<Link>* spatial::details::maximum ( Node< Link > * x )

Reach the left most node.

Should not be used on header nodes.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 131 of file spatial_node.hpp.

template<typename Link >

const Node<Link>* spatial::details::maximum ( const Node< Link > * x )

Reach the left most node.

Should not be used on header nodes.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 138 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare >

std::pair<NodePtr, dimension_type> spatial::details::maximum_mapping	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		dimension_type	map,
		KeyCompare	key_comp
	)

Move the iterator given in parameter to the maximum value along the iterator's mapping dimension but only in the sub-tree composed of the node pointed to by the iterator and its children.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for spatial::mapping_end(). This function does not perform any sanity checks on the iterator given in parameter.

The maximum element in the dimenion map is found by looking through the tree in reversed pre-order fashion. That means we start from the deepest, right-most element in the tree, and iterate all the way to the root node. We never, however, visit a left sub-tree when the dimension of the current node is equal to map: it's impossible to find a greater element in the sub-tree in this case.

Parameters

node	The pointer to the starting node for the iteration.
dim	The dimension use to compare the key at `node`.
rank	The cardinality or number of dimensions of the container being iterated.
map	The dimension along which all values in the container must be sorted.
key_comp	A functor to compare two keys in the container along a particular dimension.

Returns: The iterator given in parameter is moved to the value with the largest coordinate along the dimension map, among the children of the node pointed to by iter.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 130 of file spatial_mapping.hpp.

template<typename Container >

ordered_iterator< Container > & spatial::details::maximum_ordered ( ordered_iterator< Container > & iter )

Move the iterator given in parameter to the maximum value along the iterator's ordered dimension but only in the sub-tree composed of the node pointed to by the iterator and its children.

Template Parameters

Container The type of container to iterate.

Parameters

iter	An iterator that points to the root node of the search.

Returns: The iterator given in parameter is moved to the value with the largest coordinate along iter's ordered_dim, among the children of the node pointed to by iter.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for ordered_begin(). In any case, use it cautiously, as this function does not perform any sanity checks on the iterator given in parameter.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 1222 of file spatial_ordered.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::maximum_ordered	(	ordered_iterator< Container > &	iter,
		relaxed_invariant_tag
	)

Specialization for iterators pointed to node using the relaxed invariant.

Definition at line 1091 of file spatial_ordered.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::maximum_ordered	(	ordered_iterator< Container > &	iter,
		strict_invariant_tag
	)

Specialization for iterators pointed to node using the strict invariant.

Definition at line 1158 of file spatial_ordered.hpp.

template<typename Ct , typename Predicate >

region_iterator<Ct, Predicate>& spatial::details::maximum_region ( region_iterator< Ct, Predicate > & iter )

In the children of the node pointed to by iter, find the last matching iterator in the region delimited by Predicate, using in-order transversal.

If no match can be found, returns past-the-end.

Parameters

iter	A valid region iterator.

Template Parameters

Predicate	The type of predicate for the orthogonal query.
Ct	The type of container to look up.

Returns: An iterator pointing the maximum, or past-the-end.

template<typename Container , typename Predicate >

region_iterator<Container, Predicate>& spatial::details::maximum_region ( region_iterator< Container, Predicate > & iter )

Definition at line 804 of file spatial_region.hpp.

template<typename Link >

Node<Link>* spatial::details::minimum ( Node< Link > * x )

Reach the left most node.

Should not be used on header nodes.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 108 of file spatial_node.hpp.

template<typename Link >

const Node<Link>* spatial::details::minimum ( const Node< Link > * x )

Reach the left most node.

Should not be used on header nodes.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 115 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare >

std::pair<NodePtr, dimension_type> spatial::details::minimum_mapping	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		dimension_type	map,
		KeyCompare	key_comp
	)

Move the iterator given in parameter to the minimum value along the iterator's mapping dimension but only in the sub-tree composed of the node pointed to by the iterator and its children.

The tree in the container will be iterated in in-order fashion. As soon as the minimum is found, the first minimum is retained.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for spatial::mapping_begin(). This function does not perform any sanity checks on the iterator given in parameter.

Parameters

node	The pointer to the starting node for the iteration.
dim	The dimension use to compare the key at `node`.
rank	The cardinality or number of dimensions of the container being iterated.
map	The dimension along which all values in the container must be sorted.
key_comp	A functor to compare two keys in the container along a particular dimension.

Returns: The iterator given in parameter is moved to the value with the smallest coordinate along iter's mapping_dim, and among the children of the node pointed to by iter.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 56 of file spatial_mapping.hpp.

template<typename Container >

ordered_iterator< Container > & spatial::details::minimum_ordered ( ordered_iterator< Container > & iter )

Move the iterator given in parameter to the minimum value along the iterator's ordered dimension but only in the sub-tree composed of the node pointed to by the iterator and its children.

Template Parameters

Container The type of container to iterate.

Parameters

iter	An iterator that points to the root node of the search.

Returns: The iterator given in parameter is moved to the value with the smallest coordinate along iter's ordered_dim, and among the children of the node pointed to by iter.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for ordered_begin(). In any case, use it cautiously, as this function does not perform any sanity checks on the iterator given in parameter.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 1025 of file spatial_ordered.hpp.

template<typename Ct , typename Predicate >

region_iterator<Ct, Predicate>& spatial::details::minimum_region ( region_iterator< Ct, Predicate > & iter )

In the children of the node pointed to by iter, find the first matching iterator in the region delimited by Predicate, using in-order transversal.

If no match can be found, returns past-the-end.

Parameters

iter	A valid region iterator.

Template Parameters

Predicate	The type of predicate for the orthogonal query.
Ct	The type of container to look up.

Returns: An iterator pointing the minimum, or past-the-end.

template<typename Container , typename Predicate >

region_iterator<Container, Predicate>& spatial::details::minimum_region ( region_iterator< Container, Predicate > & iter )

Definition at line 742 of file spatial_region.hpp.

template<typename Link , typename Rank >

dimension_type spatial::details::modulo	(	const Node< Link > *	x,
		Rank	r
	)

Returns the modulo of a node's heigth by a container's rank.

This, in effect, gives the current dimension along which the node's invarient is evaluated.

If x points to the header, by convention the highest dimension for a node invariant is returned.

Template Parameters

Link	A model of Link Mode.
Rank	Either spatial::details::Static_rank or spatial::details::Dynamic_rank.

Parameters

x	A constant pointer to a node.
r	The rank used in the container.

Definition at line 97 of file spatial_rank.hpp.

template<typename Tp >

Tp* spatial::details::mutate_pointer ( const Tp * p )

A helper functions that mutates pointers.

Required to unallocate key values, which are always constant.

Definition at line 37 of file spatial_mutate.hpp.

template<typename Tp >

Tp* spatial::details::mutate_pointer ( Tp * p )

A helper functions that mutates pointers.

Required to unallocate key values, which are always constant.

Definition at line 41 of file spatial_mutate.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

bool spatial::details::operator!=	(	const Kdtree< Rank, Key, Value, Compare, Alloc > &	lhs,
		const Kdtree< Rank, Key, Value, Compare, Alloc > &	rhs
	)

The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide equal comparison operator in order to use this operation.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 626 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

bool spatial::details::operator!=	(	const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	lhs,
		const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	rhs
	)

The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide equal comparison operator in order to use this operation.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 743 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

bool spatial::details::operator<	(	const Kdtree< Rank, Key, Value, Compare, Alloc > &	lhs,
		const Kdtree< Rank, Key, Value, Compare, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 647 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

bool spatial::details::operator<	(	const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	lhs,
		const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 766 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

bool spatial::details::operator<=	(	const Kdtree< Rank, Key, Value, Compare, Alloc > &	lhs,
		const Kdtree< Rank, Key, Value, Compare, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 665 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

bool spatial::details::operator<=	(	const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	lhs,
		const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 788 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

bool spatial::details::operator==	(	const Kdtree< Rank, Key, Value, Compare, Alloc > &	lhs,
		const Kdtree< Rank, Key, Value, Compare, Alloc > &	rhs
	)

The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide equal comparison operator in order to use this operation.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 615 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

bool spatial::details::operator==	(	const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	lhs,
		const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	rhs
	)

The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide equal comparison operator in order to use this operation.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 730 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

bool spatial::details::operator>	(	const Kdtree< Rank, Key, Value, Compare, Alloc > &	lhs,
		const Kdtree< Rank, Key, Value, Compare, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 658 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

bool spatial::details::operator>	(	const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	lhs,
		const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 779 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

bool spatial::details::operator>=	(	const Kdtree< Rank, Key, Value, Compare, Alloc > &	lhs,
		const Kdtree< Rank, Key, Value, Compare, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 672 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

bool spatial::details::operator>=	(	const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	lhs,
		const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	rhs
	)

Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< reflexively, stopping at the first mismatch.

The sequence of element in each container is extracted using ordered_iterator.

The Value type of containers must provide less than comparison operator in order to use these operations.

Parameters

lhs	Left-hand side container.
rhs	Right-hand side container.

Definition at line 797 of file spatial_relaxed_kdtree.hpp.

template<typename Cmp , typename Key >

bool spatial::details::order_less	(	const Cmp &	cmp,
		dimension_type	set_dim,
		const Key &	a,
		const Key &	b
	)

Definition at line 339 of file ordered_iterator.hpp.

template<typename Cmp , typename Rank , typename Key >

bool spatial::details::order_ref	(	const Cmp &	cmp,
		const Rank &	rank,
		const Key &	a,
		const Key &	b
	)

Definition at line 447 of file spatial_ordered.hpp.

template<typename NodePtr , typename Rank , typename Query >

std::pair<NodePtr, dimension_type> spatial::details::preorder_decrement	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		const Query &	query
	)

Definition at line 161 of file spatial_preorder.hpp.

template<typename NodePtr , typename Rank , typename Query >

std::pair<NodePtr, dimension_type> spatial::details::preorder_first	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		const Query &	query
	)

Definition at line 25 of file spatial_preorder.hpp.

template<typename NodePtr , typename Rank , typename Query >

std::pair<NodePtr, dimension_type> spatial::details::preorder_increment	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		const Query &	query
	)

Definition at line 113 of file spatial_preorder.hpp.

template<typename Link >

const Node< Link > * spatial::details::preorder_increment ( const Node< Link > * x )

Reach the next node in preorder transversal.

Should not be used on empty trees or when the pointer to the node is a the head, which results in undefined behavior.

Template Parameters

Link	a model of Link Mode.

Parameters

x	a pointer to a node.

Definition at line 872 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename Query >

std::pair<NodePtr, dimension_type> spatial::details::preorder_last	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		const Query &	query
	)

Definition at line 58 of file spatial_preorder.hpp.

template<typename InputIterator >

std::ptrdiff_t spatial::details::random_access_iterator_distance	(	InputIterator	first,
		InputIterator	last,
		std::random_access_iterator_tag
	)

Definition at line 889 of file spatial_kdtree.hpp.

template<typename InputIterator >

std::ptrdiff_t spatial::details::random_access_iterator_distance	(	InputIterator	,
		InputIterator	,
		std::input_iterator_tag
	)

Definition at line 895 of file spatial_kdtree.hpp.

template<typename Container >

bool spatial::details::right_traversal	(	typename Container::mode_type::const_node_ptr	node,
		dimension_type	dim,
		const Equal< Container > &	equal
	)

Definition at line 46 of file spatial_equal.hpp.

template<typename Container >

bool spatial::details::stop_traversal	(	typename Container::mode_type::const_node_ptr	node,
		typename Container::rank_type	rank,
		const Equal< Container > &	equal
	)

Return a boolean indicating whether all of x's coordinates are equal to y's coordinates.

The key at node y are tested across all dimensions using the comparator equal provided by a container.

Template Parameters

Rank	Either spatial::details::Static_rank or spatial::details::Dynamic_rank.
Key	A key type defined in the container as the `Compare`.
Compare	A Trivial Comparison type defined in the same container as `Key`.

Parameters

rank	The magnitude of the rank.
node	A pointer to the node being inspected.
equal	A functor with all parameters for the query

Definition at line 69 of file spatial_equal.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Alloc >

void spatial::details::swap	(	Kdtree< Rank, Key, Value, Compare, Alloc > &	left,
		Kdtree< Rank, Key, Value, Compare, Alloc > &	right
	)

Swap the content of the tree left and right.

Definition at line 595 of file spatial_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >

void spatial::details::swap	(	Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	left,
		Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &	right
	)

Swap the content of the relaxed k-d tree left and right.

Definition at line 710 of file spatial_relaxed_kdtree.hpp.

template<typename Key , typename Value >

void spatial::details::swap_node	(	Node< Kdtree_link< Key, Value > > *&	a,
		Node< Kdtree_link< Key, Value > > *&	b
	)

Swaps nodes position in the tree.

This function does not updates the left-most and right-most pointers of the tree where the nodes belongs to. This is left to the responsibility of the caller.

See also: Node; Kdtree_link; Relaxed_kdtree_link

Definition at line 527 of file spatial_node.hpp.

template<typename Key , typename Value >

void spatial::details::swap_node	(	Node< Relaxed_kdtree_link< Key, Value > > *&	a,
		Node< Relaxed_kdtree_link< Key, Value > > *&	b
	)

Swaps nodes position in the tree.

This function does not updates the left-most and right-most pointers of the tree where the nodes belongs to. This is left to the responsibility of the caller.

See also: Node; Kdtree_link; Relaxed_kdtree_link

Definition at line 532 of file spatial_node.hpp.

template<typename Link >

void spatial::details::swap_node_aux	(	Node< Link > *	a,
		Node< Link > *	b
	)

Swaps nodes position in the tree.

This function does not updates the left-most and right-most pointers of the tree where the nodes belongs to. This is left to the responsibility of the caller.

See also: Node; Kdtree_link; Relaxed_kdtree_link

Definition at line 779 of file spatial_node.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename KeyType >

std::pair<NodePtr, dimension_type> spatial::details::upper_bound_mapping	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		dimension_type	map,
		KeyCompare	key_comp,
		const KeyType &	bound
	)

Move the iterator given in parameter to the value with the largest coordinate strictly lower than bound along the mapping dimension of iter, but only in the sub-tree composed of the node pointed to by the iterator and its children.

If no such value exists, then move the iterator to the parent of the value currently pointed to.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for mapping_begin(). In any case, use it cautiously, as this function does not perform any sanity checks on the iterator given in parameter.

Parameters

node	The pointer to the starting node for the iteration.
dim	The dimension use to compare the key at `node`.
rank	The cardinality or number of dimensions of the container being iterated.
map	The dimension along which all values in the container must be sorted.
key_comp	A functor to compare two keys in the container along a particular dimension.
bound	A boundary value to stop the search.

Returns: iter moved to the value with the largest coordinate strictly less than bound along iter's mapping_dim, or to the parent of the value pointed to.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 1132 of file mapping_iterator.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::upper_bound_neighbor	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		const Metric &	met,
		const Key &	target,
		typename Metric::distance_type	bound
	)

Definition at line 1403 of file spatial_neighbor.hpp.

template<typename NodePtr , typename Rank , typename KeyCompare , typename Key , typename Metric >

import::tuple<NodePtr, dimension_type, typename Metric::distance_type> spatial::details::upper_bound_neighbor_sub	(	NodePtr	node,
		dimension_type	dim,
		Rank	rank,
		KeyCompare	key_comp,
		Metric	met,
		const Key &	target,
		typename Metric::distance_type	bound,
		typename Metric::distance_type	best_dist
	)

Definition at line 1344 of file spatial_neighbor.hpp.

template<typename Container >

ordered_iterator< Container > & spatial::details::upper_bound_ordered	(	ordered_iterator< Container > &	iter,
		const typename container_traits< Container >::key_type &	bound
	)

Move the iterator given in parameter to the value with the largest coordinate strictly lower than bound along the ordered dimension of iter, but only in the sub-tree composed of the node pointed to by the iterator and its children.

If no such value exists, then move the iterator to the parent of the value currently pointed to.

Attention: This function is meant to be used by other algorithms in the library, but not by the end users of the library. If you feel that you must use this function, maybe you were actually looking for ordered_begin(). In any case, use it cautiously, as this function does not perform any sanity checks on the iterator given in parameter.

Template Parameters

Container The type of container to iterate.

Parameters

iter	An iterator that points to the root node of the search.
bound	The upper bound to the iterator position.

Returns: iter moved to the value with the largest coordinate strictly less than bound along iter's ordered_dim, or to the parent of the value pointed to.

Complexity:: This function has average fractional time complexity: $O(n^{1\,-\,1/d})\,$

Definition at line 689 of file ordered_iterator.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::upper_bound_ordered	(	ordered_iterator< Container > &	iter,
		const typename container_traits< Container >::key_type &	bound,
		relaxed_invariant_tag
	)

Definition at line 528 of file ordered_iterator.hpp.

template<typename Container >

ordered_iterator<Container>& spatial::details::upper_bound_ordered	(	ordered_iterator< Container > &	iter,
		const typename container_traits< Container >::key_type &	bound,
		strict_invariant_tag
	)

Definition at line 609 of file ordered_iterator.hpp.

template<typename Key , typename Value >

Kdtree_link<Key, Value>::value_type& spatial::details::value ( Node< Kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a value for a Kdtree_link type.

Template Parameters

Key	the key type for the Kdtree_link.
Value	the value type for the Kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 418 of file spatial_node.hpp.

template<typename Key , typename Value >

Relaxed_kdtree_link<Key, Value>::value_type& spatial::details::value ( Node< Relaxed_kdtree_link< Key, Value > > * node )

This function converts a pointer on a node into a value for a Relaxed_kdtree_link type.

Template Parameters

Key	the key type for the Relaxed_kdtree_link.
Value	the value type for the Relaxed_kdtree_link.

Parameters

node	the node to convert to a key.

Definition at line 499 of file spatial_node.hpp.

Classes

Functions

Detailed Description

Class Documentation

template<typename> struct spatial::details::builtin_difference< typename >

template<bool, typename Tp1, typename Tp2> struct spatial::details::condition< bool, Tp1, Tp2 >

template<typename Tp1, typename Tp2> struct spatial::details::condition< false, Tp1, Tp2 >

template<typename Tp> struct spatial::details::mutate< Tp >

template<typename Tp> struct spatial::details::mutate< const Tp >

template<typename Link> struct spatial::details::Node< Link >

template<typename Diff, typename DistanceType> struct spatial::details::rebind_builtin_difference< Diff, DistanceType >

template<typename Accessor, typename Tp, typename Unit, typename DistanceType> struct spatial::details::rebind_builtin_difference< accessor_minus< Accessor, Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType> struct spatial::details::rebind_builtin_difference< bracket_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType> struct spatial::details::rebind_builtin_difference< iterator_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType> struct spatial::details::rebind_builtin_difference< paren_minus< Tp, Unit >, DistanceType >

template<typename Container, typename Enable = void> struct spatial::details::with_builtin_difference< Container, Enable >

Function Documentation

template<typename>
struct spatial::details::builtin_difference< typename >

template<bool, typename Tp1, typename Tp2>
struct spatial::details::condition< bool, Tp1, Tp2 >

template<typename Tp1, typename Tp2>
struct spatial::details::condition< false, Tp1, Tp2 >

template<typename Tp>
struct spatial::details::mutate< Tp >

template<typename Tp>
struct spatial::details::mutate< const Tp >

template<typename Link>
struct spatial::details::Node< Link >

template<typename Diff, typename DistanceType>
struct spatial::details::rebind_builtin_difference< Diff, DistanceType >

template<typename Accessor, typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< accessor_minus< Accessor, Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< bracket_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< iterator_minus< Tp, Unit >, DistanceType >

template<typename Tp, typename Unit, typename DistanceType>
struct spatial::details::rebind_builtin_difference< paren_minus< Tp, Unit >, DistanceType >

template<typename Container, typename Enable = void>
struct spatial::details::with_builtin_difference< Container, Enable >