Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_mapping.hpp
1 // -*- C++ -*-
2 //
3 // Copyright Sylvain Bougerel 2009 - 2013.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file COPYING or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 
17 #ifndef SPATIAL_MAPPING_HPP
18 #define SPATIAL_MAPPING_HPP
19 
20 #include <utility> // provides ::std::pair<> and ::std::make_pair()
21 
22 namespace spatial
23 {
24  namespace details
25  {
54  template <typename NodePtr, typename Rank, typename KeyCompare>
55  inline std::pair<NodePtr, dimension_type>
56  minimum_mapping(NodePtr node, dimension_type dim, Rank rank,
57  dimension_type map, KeyCompare key_comp)
58  {
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); }
65  NodePtr best = node;
66  dimension_type best_dim = dim;
67  for (;;)
68  {
69  if (node->right != 0 && dim != map)
70  {
71  node = node->right; dim = incr_dim(rank, dim);
72  while (node->left != 0)
73  { node = node->left; dim = incr_dim(rank, dim); }
74  }
75  else
76  {
77  NodePtr prev_node = node;
78  node = node->parent; dim = decr_dim(rank, dim);
79  while (node != end
80  && prev_node == node->right)
81  {
82  prev_node = node;
83  node = node->parent; dim = decr_dim(rank, dim);
84  }
85  if (node == end) break;
86  }
87  if (key_comp(map, const_key(node), const_key(best)))
88  { best = node; best_dim = dim; }
89  }
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);
94  }
95 
128  template <typename NodePtr, typename Rank, typename KeyCompare>
129  inline std::pair<NodePtr, dimension_type>
130  maximum_mapping(NodePtr node, dimension_type dim, Rank rank,
131  dimension_type map, KeyCompare key_comp)
132  {
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); }
139  NodePtr best = node;
140  dimension_type best_dim = dim;
141  for (;;)
142  {
143  if (node->left != 0 && dim != map)
144  {
145  node = node->left; dim = incr_dim(rank, dim);
146  while (node->right != 0)
147  { node = node->right; dim = incr_dim(rank, dim); }
148  }
149  else
150  {
151  NodePtr prev_node = node;
152  node = node->parent; dim = decr_dim(rank, dim);
153  while (node != end
154  && prev_node == node->left)
155  {
156  prev_node = node;
157  node = node->parent; dim = decr_dim(rank, dim);
158  }
159  if (node == end) break;
160  }
161  if (key_comp(map, const_key(best), const_key(node)))
162  { best = node; best_dim = dim; }
163  }
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);
168  }
169 
170  } // namespace details
171 } // namespace spatial
172 
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.
Definition: spatial.hpp:71
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.
Definition: algorithm.hpp:23
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.