17 #ifndef SPATIAL_MAPPING_HPP
18 #define SPATIAL_MAPPING_HPP
54 template <
typename NodePtr,
typename Rank,
typename KeyCompare>
55 inline std::pair<NodePtr, dimension_type>
59 SPATIAL_ASSERT_CHECK(map < rank());
60 SPATIAL_ASSERT_CHECK(dim < rank());
61 SPATIAL_ASSERT_CHECK(!
header(node));
62 NodePtr end = node->parent;
63 while (node->left != 0)
64 { node = node->left; dim =
incr_dim(rank, dim); }
69 if (node->right != 0 && dim != map)
71 node = node->right; dim =
incr_dim(rank, dim);
72 while (node->left != 0)
73 { node = node->left; dim =
incr_dim(rank, dim); }
77 NodePtr prev_node = node;
78 node = node->parent; dim =
decr_dim(rank, dim);
80 && prev_node == node->right)
83 node = node->parent; dim =
decr_dim(rank, dim);
85 if (node == end)
break;
88 { best = node; best_dim = dim; }
90 SPATIAL_ASSERT_CHECK(best_dim < rank());
91 SPATIAL_ASSERT_CHECK(best != 0);
92 SPATIAL_ASSERT_CHECK(best != end);
93 return std::make_pair(best, best_dim);
128 template <
typename NodePtr,
typename Rank,
typename KeyCompare>
129 inline std::pair<NodePtr, dimension_type>
133 SPATIAL_ASSERT_CHECK(map < rank());
134 SPATIAL_ASSERT_CHECK(dim < rank());
135 SPATIAL_ASSERT_CHECK(!
header(node));
136 NodePtr end = node->parent;
137 while (node->right != 0)
138 { node = node->right; dim =
incr_dim(rank, dim); }
143 if (node->left != 0 && dim != map)
145 node = node->left; dim =
incr_dim(rank, dim);
146 while (node->right != 0)
147 { node = node->right; dim =
incr_dim(rank, dim); }
151 NodePtr prev_node = node;
152 node = node->parent; dim =
decr_dim(rank, dim);
154 && prev_node == node->left)
157 node = node->parent; dim =
decr_dim(rank, dim);
159 if (node == end)
break;
162 { best = node; best_dim = dim; }
164 SPATIAL_ASSERT_CHECK(best_dim < rank());
165 SPATIAL_ASSERT_CHECK(best != 0);
166 SPATIAL_ASSERT_CHECK(best != end);
167 return std::make_pair(best, best_dim);
173 #endif // SPATIAL_MAPPING_HPP
std::pair< NodePtr, dimension_type > minimum_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
Move the iterator given in parameter to the minimum value along the iterator's mapping dimension but ...
const Kdtree_link< Value, Value >::key_type & const_key(const Node< Kdtree_link< Value, Value > > *node)
This function converts a pointer on a node into a key for a Kdtree_link type.
bool header(const Node< Link > *x)
Check if node is a header node.
std::size_t dimension_type
Defines the type for the dimension as being a size.
std::pair< NodePtr, dimension_type > maximum_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
Move the iterator given in parameter to the maximum value along the iterator's mapping dimension but ...
The main namespace used in the library.
dimension_type decr_dim(Rank rank, dimension_type node_dim)
Decrement dimension node_dim, given rank.
dimension_type incr_dim(Rank rank, dimension_type node_dim)
Increment dimension node_dim, given rank.