Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > Class Template Reference

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

#include <spatial_relaxed_kdtree.hpp>

Classes

struct  Implementation
 The tree header. More...
 
struct  safe_allocator
 

Public Types

typedef Rank rank_type
 
typedef mutate< Key >::type key_type
 
typedef mutate< Value >::type value_type
 
typedef Relaxed_kdtree_link< Key, Value > mode_type
 
typedef Compare key_compare
 
typedef ValueCompare< value_type, key_comparevalue_compare
 
typedef Alloc allocator_type
 
typedef Balancing balancing_policy
 
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_typeiterator
 
typedef Const_node_iterator< mode_typeconst_iterator
 
typedef std::reverse_iterator< iteratorreverse_iterator
 
typedef std::reverse_iterator< const_iteratorconst_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
 
balancing_policy balancing () const
 Returns the balancing policy for the container. More...
 
rank_type rank () const
 Returns the rank type used internally to get the number of dimensions in the container. More...
 
dimension_type dimension () const
 Returns the dimension of the container. 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...
 
size_type max_size () const
 The maximum number of elements that can be allocated. More...
 
 Relaxed_kdtree ()
 
 Relaxed_kdtree (const rank_type &rank_)
 
 Relaxed_kdtree (const rank_type &rank_, const key_compare &compare_)
 
 Relaxed_kdtree (const rank_type &rank_, const key_compare &compare_, const balancing_policy &balancing_)
 
 Relaxed_kdtree (const rank_type &rank_, const key_compare &compare_, const balancing_policy &balancing_, const allocator_type &allocator_)
 
 Relaxed_kdtree (const Relaxed_kdtree &other)
 Deep copy of other into the new tree. More...
 
Relaxed_kdtreeoperator= (const Relaxed_kdtree &other)
 Assignment of other into the tree, with deep copy. More...
 
 ~Relaxed_kdtree ()
 Deallocate all nodes in the destructor. More...
 
void swap (Self &other)
 Swap the K-d tree content with others. More...
 
void clear ()
 Erase all elements in the K-d tree. More...
 
iterator insert (const value_type &value)
 Insert a single key key in the tree. More...
 
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
 Insert a serie of values in the tree at once. More...
 
void erase (iterator position)
 Deletes the node pointed to by the iterator. More...
 
size_type erase (const key_type &key)
 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 Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > Self
 
typedef Alloc::template rebind< Relaxed_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_typeget_rank ()
 
key_compareget_compare ()
 
balancing_policyget_balancing ()
 
Link_allocatorget_link_allocator ()
 
Value_allocator get_value_allocator () const
 
node_ptr create_node (const value_type &value)
 
node_ptr clone_node (const_node_ptr node)
 
void destroy_node (node_ptr node)
 Destroy and deallocate node. More...
 
void destroy_all_nodes ()
 Destroy and deallocate all nodes in the container. 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...
 
iterator insert_node (dimension_type node_dim, node_ptr node, node_ptr new_node)
 Insert the new node new_node into the tree located at node. More...
 
node_ptr erase_node (dimension_type dim, node_ptr node)
 Erase the node pointed by node. More...
 
void erase_node_balance (dimension_type dim, node_ptr node)
 Erase the node pointed by node and balance tree up to header. More...
 
node_ptr balance_node (dimension_type dim, node_ptr node)
 Attempt to balance the current node. More...
 

Private Attributes

spatial::details::Relaxed_kdtree::Implementation _impl
 

Detailed Description

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
class spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, 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.

Definition at line 148 of file spatial_relaxed_kdtree.hpp.

Member Typedef Documentation

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Alloc spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::allocator_type

Definition at line 161 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Balancing spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::balancing_policy

Definition at line 162 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Const_node_iterator<mode_type> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::const_iterator

Definition at line 176 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef mode_type::const_link_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::const_link_ptr
private

Definition at line 190 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef mode_type::const_node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::const_node_ptr
private

Definition at line 188 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef const Value* spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::const_pointer

Definition at line 166 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef const Value& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::const_reference

Definition at line 168 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef std::reverse_iterator<const_iterator> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::const_reverse_iterator

Definition at line 178 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef std::ptrdiff_t spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::difference_type

Definition at line 170 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Node_iterator<mode_type> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::iterator

Definition at line 175 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Compare spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::key_compare

Definition at line 159 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef mutate<Key>::type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::key_type

Definition at line 156 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Alloc::template rebind<Relaxed_kdtree_link<Key, Value> >::other spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Link_allocator
private

Definition at line 182 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef mode_type::link_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::link_ptr
private

Definition at line 189 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Relaxed_kdtree_link<Key, Value> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::mode_type

Definition at line 158 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef mode_type::node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::node_ptr
private

Definition at line 187 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Value* spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::pointer

Definition at line 165 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Rank spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rank_type

Definition at line 155 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Value& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::reference

Definition at line 167 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef std::reverse_iterator<iterator> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::reverse_iterator

Definition at line 177 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Relaxed_kdtree<Rank, Key, Value, Compare, Balancing, Alloc> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Self
private

Definition at line 151 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef std::size_t spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::size_type

Definition at line 169 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef Alloc::template rebind<value_type>::other spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Value_allocator
private

Definition at line 184 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef ValueCompare<value_type, key_compare> spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::value_compare

Definition at line 160 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
typedef mutate<Value>::type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::value_type

Definition at line 157 of file spatial_relaxed_kdtree.hpp.

Constructor & Destructor Documentation

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree ( )

Definition at line 533 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree ( const rank_type rank_)
explicit

Definition at line 537 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree ( const rank_type rank_,
const key_compare compare_ 
)

Definition at line 541 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree ( const rank_type rank_,
const key_compare compare_,
const balancing_policy balancing_ 
)

Definition at line 545 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree ( const rank_type rank_,
const key_compare compare_,
const balancing_policy balancing_,
const allocator_type allocator_ 
)

Definition at line 550 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree ( const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &  other)

Deep copy of other into the new tree.

This operation results in an identical the structure to the other tree. Therefore, all operations should behave similarly to both trees after the copy.

Definition at line 563 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::~Relaxed_kdtree ( )

Deallocate all nodes in the destructor.

Definition at line 596 of file spatial_relaxed_kdtree.hpp.

Member Function Documentation

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::balance_node ( dimension_type  dim,
node_ptr  node 
)
private

Attempt to balance the current node.

node cannot be null or a root node, or else dire things may happen. This function does not destroy the node and it does not modify weight of the parents of node.

Parameters
dimThe current dimension for node
nodeThe node to erase
Returns
The address of the node that has replaced the current node.

Definition at line 908 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
balancing_policy spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::balancing ( ) const

Returns the balancing policy for the container.

Definition at line 433 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::begin ( )

Definition at line 392 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::begin ( ) const

Definition at line 395 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::cbegin ( ) const

Definition at line 398 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::cend ( ) const

Definition at line 407 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::clear ( )

Erase all elements in the K-d tree.

Definition at line 645 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::clone_node ( const_node_ptr  node)
private

Definition at line 304 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, 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 842 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
size_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::count ( ) const

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

Same as size().

See also
size()

Definition at line 490 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::crbegin ( ) const

Definition at line 416 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::create_node ( const value_type value)
private

Definition at line 289 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::crend ( ) const

Definition at line 425 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::destroy_all_nodes ( )
private

Destroy and deallocate all nodes in the container.

Definition at line 808 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::destroy_node ( node_ptr  node)
private

Destroy and deallocate node.

Definition at line 315 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
dimension_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::dimension ( ) const

Returns the dimension of the container.

Definition at line 447 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
bool spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::empty ( ) const

True if the tree is empty.

Definition at line 472 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::end ( )

Definition at line 401 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::end ( ) const

Definition at line 404 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::erase ( iterator  position)

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 1133 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::size_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::erase ( const key_type key)

Deletes all nodes that match key value.

Parameters
keyTo be compared with the tree nodes.

The type key_type must be equally comparable.

Definition at line 1156 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::erase_node ( dimension_type  dim,
node_ptr  node 
)
private

Erase the node pointed by node.

node cannot be null or a root node, or else dire things may happen. This function does not destroy the node and it does not decrement weight to the parents of node.

Parameters
dimThe current dimension for node
nodeThe node to erase
Returns
The address of the node that has replaced the erased one or node if it was a leaf.

Definition at line 1017 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::erase_node_balance ( dimension_type  dim,
node_ptr  node 
)
private

Erase the node pointed by node and balance tree up to header.

Finish the work started by erase_node by reducing weight in parent of node, up to the header.

node cannot be null or a root node, or else dire things may happen. This function does not destroy the node.

Parameters
dimThe current dimension for node
nodeThe node to erase

Definition at line 1096 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, 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 spatial::equal_range().

Parameters
keyThe value search.
Returns
An iterator to that value or an iterator to the element past the end of the container.

Definition at line 515 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, 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 spatial::equal_range().

Parameters
keyThe value search.
Returns
An iterator to that value or an iterator to the element past the end of the container.

Definition at line 523 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
allocator_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_allocator ( ) const

Returns the allocator used by the tree.

Definition at line 466 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
balancing_policy& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_balancing ( )
private

Definition at line 266 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
key_compare& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_compare ( )
private

Definition at line 263 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_header ( )
private

Definition at line 227 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_header ( ) const
private

Definition at line 230 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_leftmost ( )
private

Definition at line 233 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_leftmost ( ) const
private

Definition at line 236 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
Link_allocator& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_link_allocator ( )
private

Definition at line 269 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
rank_type& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_rank ( )
private

Definition at line 260 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_rightmost ( )
private

Definition at line 242 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_rightmost ( ) const
private

Definition at line 245 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_root ( )
private

Definition at line 251 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_node_ptr spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_root ( ) const
private

Definition at line 254 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
Value_allocator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::get_value_allocator ( ) const
private

Definition at line 272 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::insert ( const value_type value)

Insert a single key key in the tree.

Definition at line 655 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
template<typename InputIterator >
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::insert ( InputIterator  first,
InputIterator  last 
)

Insert a serie of values in the tree at once.

Definition at line 681 of file spatial_relaxed_kdtree.hpp.

template<typename Rank , typename Key , typename Value , typename Compare , typename Balancing , typename Alloc >
Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::insert_node ( dimension_type  node_dim,
node_ptr  node,
node_ptr  new_node 
)
private

Insert the new node new_node into the tree located at node.

If the last parameter is 0, the node will also be created.

Parameters
node_dimThe current dimension for the node.
nodeThe node below which the new key shall be inserted.
new_nodeThe new node to insert

Definition at line 927 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
key_compare spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::key_comp ( ) const

Returns the compare function used for the key.

Definition at line 453 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
size_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::max_size ( ) const

The maximum number of elements that can be allocated.

Definition at line 497 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
Relaxed_kdtree& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::operator= ( const Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > &  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
Allocator is not modified with this assignment and remains the same.

Definition at line 576 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
rank_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rank ( ) const

Returns the rank type used internally to get the number of dimensions in the container.

Definition at line 440 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rbegin ( )

Definition at line 410 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rbegin ( ) const

Definition at line 413 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rend ( )

Definition at line 419 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
const_reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rend ( ) const

Definition at line 422 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::set_leftmost ( node_ptr  x)
private

Definition at line 239 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::set_rightmost ( node_ptr  x)
private

Definition at line 248 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::set_root ( node_ptr  x)
private

Definition at line 257 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
size_type spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::size ( ) const

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

Definition at line 479 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
void spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, 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 609 of file spatial_relaxed_kdtree.hpp.

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
value_compare spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::value_comp ( ) const

Returns the compare function used for the value.

Definition at line 459 of file spatial_relaxed_kdtree.hpp.

Member Data Documentation

template<typename Rank, typename Key, typename Value, typename Compare, typename Balancing, typename Alloc>
spatial::details::Relaxed_kdtree::Implementation spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::_impl
private

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