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

#include <spatial_kdtree.hpp>

Classes
struct	Implementation
	The tree header. More...

struct	Maximum

struct	safe_allocator

Public Types
typedef Rank	rank_type

typedef mutate< Key >::type	key_type

typedef mutate< Value >::type	value_type

typedef Compare	key_compare

typedef ValueCompare< value_type, key_compare >	value_compare

typedef Alloc	allocator_type

typedef Kdtree_link< Key, Value >	mode_type

typedef Value *	pointer

typedef const Value *	const_pointer

typedef Value &	reference

typedef const Value &	const_reference

typedef std::size_t	size_type

typedef std::ptrdiff_t	difference_type

typedef Node_iterator< mode_type >	iterator

typedef Const_node_iterator< mode_type >	const_iterator

typedef std::reverse_iterator< iterator >	reverse_iterator

typedef std::reverse_iterator< const_iterator >	const_reverse_iterator

Public Member Functions
iterator	begin ()

const_iterator	begin () const

const_iterator	cbegin () const

iterator	end ()

const_iterator	end () const

const_iterator	cend () const

reverse_iterator	rbegin ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	crbegin () const

reverse_iterator	rend ()

const_reverse_iterator	rend () const

const_reverse_iterator	crend () const

rank_type	rank () const
	Returns the rank used to create the tree. More...

dimension_type	dimension () const
	Returns the dimension of the tree. More...

key_compare	key_comp () const
	Returns the compare function used for the key. More...

value_compare	value_comp () const
	Returns the compare function used for the value. More...

allocator_type	get_allocator () const
	Returns the allocator used by the tree. More...

bool	empty () const
	True if the tree is empty. More...

size_type	size () const
	Returns the number of elements in the K-d tree. More...

size_type	count () const
	Returns the number of elements in the K-d tree. More...

void	clear ()
	Erase all elements in the K-d tree. More...

size_type	max_size () const
	The maximum number of elements that can be allocated. More...

	Kdtree ()

	Kdtree (const rank_type &rank_)

	Kdtree (const key_compare &compare_)

	Kdtree (const rank_type &rank_, const key_compare &compare_)

	Kdtree (const rank_type &rank_, const key_compare &compare_, const allocator_type &allocator_)

	Kdtree (const Self &other, bool balancing=false)
	Deep copy of `other` into the new tree. More...

Self &	operator= (const Self &other)
	Assignment of `other` into the tree, with deep copy. More...

	~Kdtree ()
	Deallocate all nodes in the destructor. More...

void	swap (Self &other)
	Swap the K-d tree content with others. More...

void	rebalance ()
	Rebalance the k-d tree near-optimally, resulting in $O(\log n)\,$ order of complexity on most search functions. More...

iterator	insert (const value_type &value)
	Insert a single `value` element in the container. More...

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	Insert a serie of values in the container at once. More...

template<typename InputIterator >
void	insert_rebalance (InputIterator first, InputIterator last)
	Insert a serie of values in the container at once and rebalance the container after insertion. More...

void	erase (iterator pointer)
	Deletes the node pointed to by the iterator. More...

size_type	erase (const key_type &value)
	Deletes all nodes that match key `value`. More...


iterator	find (const key_type &key)
	Find the first node that matches with `key` and returns an iterator to it found, otherwise it returns an iterator to the element past the end of the container. More...

const_iterator	find (const key_type &key) const
	Find the first node that matches with `key` and returns an iterator to it found, otherwise it returns an iterator to the element past the end of the container. More...

Private Types
typedef Kdtree< Rank, Key, Value, Compare, Alloc >	Self

typedef Alloc::template rebind< Kdtree_link< Key, Value > >::other	Link_allocator

typedef Alloc::template rebind< value_type >::other	Value_allocator

typedef mode_type::node_ptr	node_ptr

typedef mode_type::const_node_ptr	const_node_ptr

typedef mode_type::link_ptr	link_ptr

typedef mode_type::const_link_ptr	const_link_ptr

Private Member Functions
node_ptr	get_header ()

const_node_ptr	get_header () const

node_ptr	get_leftmost ()

const_node_ptr	get_leftmost () const

void	set_leftmost (node_ptr x)

node_ptr	get_rightmost ()

const_node_ptr	get_rightmost () const

void	set_rightmost (node_ptr x)

node_ptr	get_root ()

const_node_ptr	get_root () const

void	set_root (node_ptr x)

rank_type &	get_rank ()

key_compare &	get_compare ()

Link_allocator &	get_link_allocator ()

Value_allocator	get_value_allocator () const

node_ptr	create_node (const value_type &value)

void	destroy_node (node_ptr node)
	Destroy and deallocate `node`. More...

void	destroy_all_nodes ()
	Destroy and deallocate all nodes in the container. More...

iterator	insert_node (node_ptr target_node)
	Insert a node already allocated into the tree. More...

node_ptr	rebalance_node_insert (typename std::vector< node_ptr >::iterator first, typename std::vector< node_ptr >::iterator last, dimension_type dim, node_ptr header)
	Insert all the nodes in [first,last) into the tree, by first sorting the nodes according to the dimension of interest. More...

std::vector< node_ptr >::iterator	median (typename std::vector< node_ptr >::iterator first, typename std::vector< node_ptr >::iterator last, dimension_type dim)
	This function finds the median node in a random iterator range. More...

void	copy_structure (const Self &other)
	Copy the exact sturcture of the sub-tree pointed to by `other_node` into the current empty tree. More...

void	copy_rebalance (const Self &other)
	Copy the content of `other` to the tree and rebalances the values in the tree resulting in most query having an `O(log(n))` order of complexity. More...

node_ptr	erase_node (dimension_type node_dim, node_ptr node)
	Erase the node located at `node` with current dimension `node_dim`. More...

Private Attributes
spatial::details::Kdtree::Implementation	_impl

Detailed Description

template<typename Rank, typename Key, typename Value, typename Compare, typename Alloc>
class spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >

Detailed implementation of the kd-tree.

Used by point_set, point_multiset, point_map, point_multimap, box_set, box_multiset and their equivalent in variant orders: variant_pointer_set, as chosen by the templates. Not used by neighbor_point_set, neighbor_point_multiset... Compare must provide strict unordered ordering along each dimension! Each node maintains the count of its children nodes plus one.

Definition at line 50 of file spatial_kdtree.hpp.

Member Typedef Documentation

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

typedef Alloc spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::allocator_type

Definition at line 61 of file spatial_kdtree.hpp.

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

typedef Const_node_iterator<mode_type> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::const_iterator

Definition at line 76 of file spatial_kdtree.hpp.

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

typedef mode_type::const_link_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::const_link_ptr

private

Definition at line 90 of file spatial_kdtree.hpp.

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

typedef mode_type::const_node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::const_node_ptr

private

Definition at line 88 of file spatial_kdtree.hpp.

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

typedef const Value* spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::const_pointer

Definition at line 66 of file spatial_kdtree.hpp.

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

typedef const Value& spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::const_reference

Definition at line 68 of file spatial_kdtree.hpp.

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

typedef std::reverse_iterator<const_iterator> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::const_reverse_iterator

Definition at line 78 of file spatial_kdtree.hpp.

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

typedef std::ptrdiff_t spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::difference_type

Definition at line 70 of file spatial_kdtree.hpp.

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

typedef Node_iterator<mode_type> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::iterator

Definition at line 75 of file spatial_kdtree.hpp.

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

typedef Compare spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::key_compare

Definition at line 59 of file spatial_kdtree.hpp.

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

typedef mutate<Key>::type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::key_type

Definition at line 57 of file spatial_kdtree.hpp.

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

typedef Alloc::template rebind<Kdtree_link<Key, Value> >::other spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Link_allocator

private

Definition at line 82 of file spatial_kdtree.hpp.

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

typedef mode_type::link_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::link_ptr

private

Definition at line 89 of file spatial_kdtree.hpp.

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

typedef Kdtree_link<Key, Value> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::mode_type

Definition at line 62 of file spatial_kdtree.hpp.

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

typedef mode_type::node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::node_ptr

private

Definition at line 87 of file spatial_kdtree.hpp.

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

typedef Value* spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::pointer

Definition at line 65 of file spatial_kdtree.hpp.

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

typedef Rank spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rank_type

Definition at line 56 of file spatial_kdtree.hpp.

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

typedef Value& spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::reference

Definition at line 67 of file spatial_kdtree.hpp.

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

typedef std::reverse_iterator<iterator> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::reverse_iterator

Definition at line 77 of file spatial_kdtree.hpp.

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

typedef Kdtree<Rank, Key, Value, Compare, Alloc> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Self

private

Definition at line 52 of file spatial_kdtree.hpp.

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

typedef std::size_t spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::size_type

Definition at line 69 of file spatial_kdtree.hpp.

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

typedef Alloc::template rebind<value_type>::other spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Value_allocator

private

Definition at line 84 of file spatial_kdtree.hpp.

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

typedef ValueCompare<value_type, key_compare> spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::value_compare

Definition at line 60 of file spatial_kdtree.hpp.

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

typedef mutate<Value>::type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::value_type

Definition at line 58 of file spatial_kdtree.hpp.

Constructor & Destructor Documentation

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Kdtree ( )

Definition at line 371 of file spatial_kdtree.hpp.

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Kdtree ( const rank_type & rank_ )

explicit

Definition at line 375 of file spatial_kdtree.hpp.

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Kdtree ( const key_compare & compare_ )

explicit

Definition at line 379 of file spatial_kdtree.hpp.

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Kdtree	(	const rank_type &	rank_,
		const key_compare &	compare_
	)

Definition at line 383 of file spatial_kdtree.hpp.

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Kdtree	(	const rank_type &	rank_,
		const key_compare &	compare_,
		const allocator_type &	allocator_
	)

Definition at line 387 of file spatial_kdtree.hpp.

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::Kdtree	(	const Self &	other,
		bool	balancing = `false`
	)

Deep copy of other into the new tree.

If balancing is false or unspecified, the copy preserve the structure of other tree. Therefore, all operations should behave similarly to both trees after the copy.

If balancing is true, the new tree is a balanced copy of a other tree, resulting in $O(n^{1\,-\,1/d})\,$ order of complexity on most search functions.

Definition at line 403 of file spatial_kdtree.hpp.

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

spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::~Kdtree ( )

Deallocate all nodes in the destructor.

Definition at line 440 of file spatial_kdtree.hpp.

Member Function Documentation

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

iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::begin ( )

Definition at line 277 of file spatial_kdtree.hpp.

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

const_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::begin ( ) const

Definition at line 280 of file spatial_kdtree.hpp.

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

const_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::cbegin ( ) const

Definition at line 283 of file spatial_kdtree.hpp.

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

const_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::cend ( ) const

Definition at line 291 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::clear ( )

Erase all elements in the K-d tree.

Definition at line 361 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::copy_rebalance ( const Self & other )

private

Copy the content of other to the tree and rebalances the values in the tree resulting in most query having an O(log(n)) order of complexity.

Definition at line 854 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::copy_structure ( const Self & other )

private

Copy the exact sturcture of the sub-tree pointed to by other_node into the current empty tree.

The structural copy preserve all characteristics of the sub-tree pointed to by other_node.

Definition at line 784 of file spatial_kdtree.hpp.

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

size_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::count ( ) const

Returns the number of elements in the K-d tree.

Same as size().

See also: size()

Definition at line 356 of file spatial_kdtree.hpp.

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

const_reverse_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::crbegin ( ) const

Definition at line 299 of file spatial_kdtree.hpp.

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

node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::create_node ( const value_type & value )

private

Definition at line 195 of file spatial_kdtree.hpp.

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

const_reverse_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::crend ( ) const

Definition at line 308 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::destroy_all_nodes ( )

private

Destroy and deallocate all nodes in the container.

Definition at line 681 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::destroy_node ( node_ptr node )

private

Destroy and deallocate node.

Definition at line 212 of file spatial_kdtree.hpp.

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

dimension_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::dimension ( ) const

Returns the dimension of the tree.

Definition at line 321 of file spatial_kdtree.hpp.

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

bool spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::empty ( ) const

True if the tree is empty.

Definition at line 345 of file spatial_kdtree.hpp.

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

iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::end ( )

Definition at line 285 of file spatial_kdtree.hpp.

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

const_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::end ( ) const

Definition at line 288 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::erase ( iterator pointer )

Deletes the node pointed to by the iterator.

The iterator must be pointing to an existing node belonging to the related tree, or dire things may happen.

Definition at line 1138 of file spatial_kdtree.hpp.

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

Kdtree< Rank, Key, Value, Compare, Alloc >::size_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::erase ( const key_type & value )

Deletes all nodes that match key value.

See also: find

Parameters

value that will be compared with the tree nodes.

The type key_type must be equally comparable.

Definition at line 1157 of file spatial_kdtree.hpp.

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

Kdtree< Rank, Key, Value, Compare, Alloc >::node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::erase_node	(	dimension_type	node_dim,
		node_ptr	node
	)

private

Erase the node located at node with current dimension node_dim.

The function returns the node that was used to replace the previous one, or null if no replacement was needed.

Definition at line 1058 of file spatial_kdtree.hpp.

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

iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::find ( const key_type & key )

Find the first node that matches with key and returns an iterator to it found, otherwise it returns an iterator to the element past the end of the container.

Notice that this function returns an iterator only to one of the elements with that key. To obtain the entire range of elements with a given value, you can use equal_range.

If this function is called on an empty container, returns an iterator past the end of the container.

Complexity:

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

Parameters

key	the value to be searched for.

Returns: An iterator to that value or an iterator to the element past the end of the container.

Definition at line 550 of file spatial_kdtree.hpp.

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

const_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::find ( const key_type & key ) const

Find the first node that matches with key and returns an iterator to it found, otherwise it returns an iterator to the element past the end of the container.

Notice that this function returns an iterator only to one of the elements with that key. To obtain the entire range of elements with a given value, you can use equal_range.

If this function is called on an empty container, returns an iterator past the end of the container.

Complexity:

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

Parameters

key	the value to be searched for.

Returns: An iterator to that value or an iterator to the element past the end of the container.

Definition at line 559 of file spatial_kdtree.hpp.

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

allocator_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_allocator ( ) const

Returns the allocator used by the tree.

Definition at line 340 of file spatial_kdtree.hpp.

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

key_compare& spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_compare ( )

private

Definition at line 172 of file spatial_kdtree.hpp.

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

node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_header ( )

private

Definition at line 136 of file spatial_kdtree.hpp.

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

const_node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_header ( ) const

private

Definition at line 139 of file spatial_kdtree.hpp.

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

node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_leftmost ( )

private

Definition at line 142 of file spatial_kdtree.hpp.

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

const_node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_leftmost ( ) const

private

Definition at line 145 of file spatial_kdtree.hpp.

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

Link_allocator& spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_link_allocator ( )

private

Definition at line 175 of file spatial_kdtree.hpp.

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

rank_type& spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_rank ( )

private

Definition at line 169 of file spatial_kdtree.hpp.

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

node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_rightmost ( )

private

Definition at line 151 of file spatial_kdtree.hpp.

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

const_node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_rightmost ( ) const

private

Definition at line 154 of file spatial_kdtree.hpp.

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

node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_root ( )

private

Definition at line 160 of file spatial_kdtree.hpp.

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

const_node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_root ( ) const

private

Definition at line 163 of file spatial_kdtree.hpp.

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

Value_allocator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::get_value_allocator ( ) const

private

Definition at line 178 of file spatial_kdtree.hpp.

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

iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::insert ( const value_type & value )

Insert a single value element in the container.

Definition at line 503 of file spatial_kdtree.hpp.

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

template<typename InputIterator >

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::insert	(	InputIterator	first,
		InputIterator	last
	)

Insert a serie of values in the container at once.

The parameter first and last only need to be a model of InputIterator. Elements are inserted in a single pass.

Definition at line 516 of file spatial_kdtree.hpp.

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

Kdtree< Rank, Key, Value, Compare, Alloc >::iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::insert_node ( typename mode_type::node_ptr target_node )

private

Insert a node already allocated into the tree.

Definition at line 715 of file spatial_kdtree.hpp.

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

template<typename InputIterator >

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::insert_rebalance	(	InputIterator	first,
		InputIterator	last
	)

Insert a serie of values in the container at once and rebalance the container after insertion.

This method performs generally more efficiently than calling insert() then reblance() independantly.

The parameter first and last only need to be a model of InputIterator. Elements are inserted in a single pass.

Definition at line 903 of file spatial_kdtree.hpp.

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

key_compare spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::key_comp ( ) const

Returns the compare function used for the key.

Definition at line 327 of file spatial_kdtree.hpp.

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

size_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::max_size ( ) const

The maximum number of elements that can be allocated.

Definition at line 367 of file spatial_kdtree.hpp.

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

std::vector< typename Kdtree< Rank, Key, Value, Compare, Alloc >::node_ptr >::iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::median	(	typename std::vector< node_ptr >::iterator	first,
		typename std::vector< node_ptr >::iterator	last,
		dimension_type	dim
	)

private

This function finds the median node in a random iterator range.

It respects the invariant of the tree even when equal values are found in the tree.

Definition at line 985 of file spatial_kdtree.hpp.

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

Self& spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::operator= ( const Self & other )

Assignment of other into the tree, with deep copy.

The copy preserve the structure of the tree other. Therefore, all operations should behave similarly to both trees after the copy.

Note: The allocator of the tree is not modified by the assignment.

Definition at line 421 of file spatial_kdtree.hpp.

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

rank_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rank ( ) const

Returns the rank used to create the tree.

Definition at line 315 of file spatial_kdtree.hpp.

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

reverse_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rbegin ( )

Definition at line 293 of file spatial_kdtree.hpp.

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

const_reverse_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rbegin ( ) const

Definition at line 296 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rebalance ( )

Rebalance the k-d tree near-optimally, resulting in $O(\log n)\,$ order of complexity on most search functions.

This function is time & memory consuming. Internally, it creates a vector of pointer to the node, and thus requires a substantial amount of memory for a large k-d tree. Ideally, this function should be called only once, when all the elements you will be working on have been inserted in the tree.

If you need to insert and erase multiple elements continuously, consider using other containers than the "idle" family of containers.

Definition at line 943 of file spatial_kdtree.hpp.

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

Kdtree< Rank, Key, Value, Compare, Alloc >::node_ptr spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rebalance_node_insert	(	typename std::vector< node_ptr >::iterator	first,
		typename std::vector< node_ptr >::iterator	last,
		dimension_type	dim,
		node_ptr	header
	)

private

Insert all the nodes in [first,last) into the tree, by first sorting the nodes according to the dimension of interest.

This function is semi-recursive. It iterates when walking down left nodes and recurse when walking down right nodes.

Definition at line 1019 of file spatial_kdtree.hpp.

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

reverse_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rend ( )

Definition at line 302 of file spatial_kdtree.hpp.

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

const_reverse_iterator spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::rend ( ) const

Definition at line 305 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::set_leftmost ( node_ptr x )

private

Definition at line 148 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::set_rightmost ( node_ptr x )

private

Definition at line 157 of file spatial_kdtree.hpp.

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

void spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::set_root ( node_ptr x )

private

Definition at line 166 of file spatial_kdtree.hpp.

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

size_type spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::size ( ) const

Returns the number of elements in the K-d tree.

Definition at line 350 of file spatial_kdtree.hpp.

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

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

Swap the K-d tree content with others.

The extra overhead of the test is not required in common cases: users intentionally swap different objects.

Warning: This function do not test: (this != &other)

Definition at line 452 of file spatial_kdtree.hpp.

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

value_compare spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::value_comp ( ) const

Returns the compare function used for the value.

Definition at line 333 of file spatial_kdtree.hpp.

Member Data Documentation

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

spatial::details::Kdtree::Implementation spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >::_impl

private

The documentation for this class was generated from the following file:

/home/sylvain/Projects/spatial_build/spatial_2.1.8/src/bits/spatial_kdtree.hpp

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename Rank, typename Key, typename Value, typename Compare, typename Alloc> class spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Rank, typename Key, typename Value, typename Compare, typename Alloc>
class spatial::details::Kdtree< Rank, Key, Value, Compare, Alloc >