Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
|
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_compare > | value_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_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 |
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_kdtree & | operator= (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 Attributes | |
spatial::details::Relaxed_kdtree::Implementation | _impl |
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.
typedef Alloc spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::allocator_type |
Definition at line 161 of file spatial_relaxed_kdtree.hpp.
typedef Balancing spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::balancing_policy |
Definition at line 162 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 190 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 188 of file spatial_relaxed_kdtree.hpp.
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.
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.
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.
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.
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.
typedef Compare spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::key_compare |
Definition at line 159 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 182 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 189 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 187 of file spatial_relaxed_kdtree.hpp.
typedef Value* spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::pointer |
Definition at line 165 of file spatial_relaxed_kdtree.hpp.
typedef Rank spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rank_type |
Definition at line 155 of file spatial_relaxed_kdtree.hpp.
typedef Value& spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::reference |
Definition at line 167 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 151 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 184 of file spatial_relaxed_kdtree.hpp.
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.
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.
spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::Relaxed_kdtree | ( | ) |
Definition at line 533 of file spatial_relaxed_kdtree.hpp.
|
explicit |
Definition at line 537 of file spatial_relaxed_kdtree.hpp.
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.
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.
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.
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.
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.
|
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.
dim | The current dimension for node |
node | The node to erase |
Definition at line 908 of file spatial_relaxed_kdtree.hpp.
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.
iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::begin | ( | ) |
Definition at line 392 of file spatial_relaxed_kdtree.hpp.
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::begin | ( | ) | const |
Definition at line 395 of file spatial_relaxed_kdtree.hpp.
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::cbegin | ( | ) | const |
Definition at line 398 of file spatial_relaxed_kdtree.hpp.
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::cend | ( | ) | const |
Definition at line 407 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 304 of file spatial_relaxed_kdtree.hpp.
|
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.
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().
Definition at line 490 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 289 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Destroy and deallocate all nodes in the container.
Definition at line 808 of file spatial_relaxed_kdtree.hpp.
|
private |
Destroy and deallocate node
.
Definition at line 315 of file spatial_relaxed_kdtree.hpp.
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.
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.
iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::end | ( | ) |
Definition at line 401 of file spatial_relaxed_kdtree.hpp.
const_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::end | ( | ) | const |
Definition at line 404 of file spatial_relaxed_kdtree.hpp.
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.
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
.
key | To be compared with the tree nodes. |
The type key_type
must be equally comparable.
Definition at line 1156 of file spatial_relaxed_kdtree.hpp.
|
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.
dim | The current dimension for node |
node | The node to erase |
node
if it was a leaf. Definition at line 1017 of file spatial_relaxed_kdtree.hpp.
|
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.
dim | The current dimension for node |
node | The node to erase |
Definition at line 1096 of file spatial_relaxed_kdtree.hpp.
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().
key | The value search. |
Definition at line 515 of file spatial_relaxed_kdtree.hpp.
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().
key | The value search. |
Definition at line 523 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 266 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 263 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 227 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 230 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 233 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 236 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 269 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 260 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 242 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 245 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 251 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 254 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 272 of file spatial_relaxed_kdtree.hpp.
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.
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.
|
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.
node_dim | The current dimension for the node. |
node | The node below which the new key shall be inserted. |
new_node | The new node to insert |
Definition at line 927 of file spatial_relaxed_kdtree.hpp.
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.
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.
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.
Definition at line 576 of file spatial_relaxed_kdtree.hpp.
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.
reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rbegin | ( | ) |
Definition at line 410 of file spatial_relaxed_kdtree.hpp.
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.
reverse_iterator spatial::details::Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc >::rend | ( | ) |
Definition at line 419 of file spatial_relaxed_kdtree.hpp.
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.
|
private |
Definition at line 239 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 248 of file spatial_relaxed_kdtree.hpp.
|
private |
Definition at line 257 of file spatial_relaxed_kdtree.hpp.
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.
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.
Definition at line 609 of file spatial_relaxed_kdtree.hpp.
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.
|
private |