Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_preorder.hpp
1 // -*- C++ -*-
2 //
3 // Copyright Sylvain Bougerel 2009 - 2014.
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 
13 #ifndef SPATIAL_PREORDER_HPP
14 #define SPATIAL_PREORDER_HPP
15 
16 #include "../spatial.hpp"
17 #include "spatial_assign.hpp"
18 
19 namespace spatial
20 {
21  namespace details
22  {
23  template <typename NodePtr, typename Rank, typename Query>
24  inline std::pair<NodePtr, dimension_type>
25  preorder_first(NodePtr node, dimension_type dim, Rank rank,
26  const Query& query)
27  {
28  NodePtr init_node = node;
29  dimension_type init_dim = dim;
30  SPATIAL_ASSERT_CHECK(!header(node));
31  SPATIAL_ASSERT_CHECK(node != 0);
32  SPATIAL_ASSERT_CHECK(dim < rank());
33  while (!stop_traversal(node, rank, query))
34  {
35  if (node->left != 0 && left_traversal(node, dim, query))
36  {
37  NodePtr left = node->left;
38  assign(node, dim,
39  preorder_first(left, incr_dim(rank, dim), rank, query));
40  if (left->parent != node) break; // We found the first
41  }
42  if (node->right != 0 && right_traversal(node, dim, query))
43  {
44  node = node->right;
45  dim = incr_dim(rank, dim);
46  continue;
47  }
48  return std::make_pair(init_node->parent,
49  decr_dim(rank, init_dim));
50  }
51  SPATIAL_ASSERT_CHECK(dim < rank());
52  SPATIAL_ASSERT_CHECK(node != 0);
53  return std::make_pair(node, dim);
54  }
55 
56  template <typename NodePtr, typename Rank, typename Query>
57  inline std::pair<NodePtr, dimension_type>
58  preorder_last(NodePtr node, dimension_type dim, Rank rank,
59  const Query& query)
60  {
61  SPATIAL_ASSERT_CHECK(!header(node));
62  SPATIAL_ASSERT_CHECK(node != 0);
63  SPATIAL_ASSERT_CHECK(dim < rank());
64  for (;;)
65  {
66  if (node->right != 0 && right_traversal(node, dim, query))
67  {
68  node = node->right;
69  dim = incr_dim(rank, dim);
70  }
71  else if (node->left != 0 && left_traversal(node, dim, query))
72  {
73  node = node->left;
74  dim = incr_dim(rank, dim);
75  }
76  else break;
77  }
78  while (!stop_traversal(node, rank, query))
79  {
80  NodePtr copy_node = node;
81  dimension_type copy_dim = dim;
82  node = node->parent;
83  dim = decr_dim(rank, dim);
84  if (header(node)) break;
85  if (node->right == copy_node
86  && node->left != 0 && left_traversal(node, dim, query))
87  {
88  node = node->left;
89  dim = copy_dim;
90  for (;;)
91  {
92  if (node->right != 0 && right_traversal(node, dim, query))
93  {
94  node = node->right;
95  dim = incr_dim(rank, dim);
96  }
97  else if (node->left != 0 && left_traversal(node, dim, query))
98  {
99  node = node->left;
100  dim = incr_dim(rank, dim);
101  }
102  else break;
103  }
104  }
105  }
106  SPATIAL_ASSERT_CHECK(dim < rank());
107  SPATIAL_ASSERT_CHECK(node != 0);
108  return std::make_pair(node, dim);
109  }
110 
111  template <typename NodePtr, typename Rank, typename Query>
112  inline std::pair<NodePtr, dimension_type>
113  preorder_increment(NodePtr node, dimension_type dim, Rank rank,
114  const Query& query)
115  {
116  SPATIAL_ASSERT_CHECK(!header(node));
117  SPATIAL_ASSERT_CHECK(node != 0);
118  SPATIAL_ASSERT_CHECK(dim < rank());
119  do
120  {
121  if (node->left != 0 && left_traversal(node, dim, query))
122  {
123  node = node->left;
124  dim = incr_dim(rank, dim);
125  }
126  else if (node->right != 0 && right_traversal(node, dim, query))
127  {
128  node = node->right;
129  dim = incr_dim(rank, dim);
130  }
131  else
132  {
133  NodePtr prev_node = node;
134  node = node->parent;
135  dim = decr_dim(rank, dim);
136  while (!header(node)
137  && (prev_node == node->right
138  || node->right == 0
139  || !right_traversal(node, dim, query)))
140  {
141  prev_node = node;
142  node = node->parent;
143  dim = decr_dim(rank, dim);
144  }
145  if (!header(node))
146  {
147  node = node->right;
148  dim = incr_dim(rank, dim);
149  }
150  else break;
151  }
152  }
153  while (!stop_traversal(node, rank, query));
154  SPATIAL_ASSERT_CHECK(dim < rank());
155  SPATIAL_ASSERT_CHECK(node != 0);
156  return std::make_pair(node, dim);
157  }
158 
159  template <typename NodePtr, typename Rank, typename Query>
160  inline std::pair<NodePtr, dimension_type>
161  preorder_decrement(NodePtr node, dimension_type dim, Rank rank,
162  const Query& query)
163  {
164  if (header(node))
165  { return preorder_last(node->parent, 0, rank, query); }
166  SPATIAL_ASSERT_CHECK(node != 0);
167  SPATIAL_ASSERT_CHECK(dim < rank());
168  NodePtr copy_node = node;
169  dimension_type copy_dim = dim;
170  node = node->parent;
171  dim = decr_dim(rank, dim);
172  while (!header(node))
173  {
174  if (node->right == copy_node
175  && node->left != 0 && left_traversal(node, dim, query))
176  {
177  node = node->left;
178  dim = copy_dim;
179  for (;;)
180  {
181  if (node->right != 0 && right_traversal(node, dim, query))
182  {
183  node = node->right;
184  dim = incr_dim(rank, dim);
185  }
186  else if (node->left != 0 && left_traversal(node, dim, query))
187  {
188  node = node->left;
189  dim = incr_dim(rank, dim);
190  }
191  else break;
192  }
193  }
194  if (stop_traversal(node, rank, query)) break;
195  copy_node = node;
196  copy_dim = dim;
197  node = node->parent;
198  dim = decr_dim(rank, dim);
199  }
200  SPATIAL_ASSERT_CHECK(dim < rank());
201  SPATIAL_ASSERT_CHECK(node != 0);
202  return std::make_pair(node, dim);
203  }
204 
205  } // namespace details
206 } // namespace spatial
207 
208 #endif // SPATIAL_PREORDER_HPP
spatial::details::stop_traversal
bool stop_traversal(typename Container::mode_type::const_node_ptr node, typename Container::rank_type rank, const Equal< Container > &equal)
Return a boolean indicating whether all of x's coordinates are equal to y's coordinates.
Definition: spatial_equal.hpp:69
spatial::details::right_traversal
bool right_traversal(typename Container::mode_type::const_node_ptr node, dimension_type dim, const Equal< Container > &equal)
Definition: spatial_equal.hpp:46
spatial::details::preorder_decrement
std::pair< NodePtr, dimension_type > preorder_decrement(NodePtr node, dimension_type dim, Rank rank, const Query &query)
Definition: spatial_preorder.hpp:161
spatial::details::header
bool header(const Node< Link > *x)
Check if node is a header node.
Definition: spatial_node.hpp:96
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::details::assign
void assign(Type1 &first, Type2 &second, const std::pair< Type1, Type2 > &pair)
Definition: spatial_assign.hpp:26
spatial::details::preorder_last
std::pair< NodePtr, dimension_type > preorder_last(NodePtr node, dimension_type dim, Rank rank, const Query &query)
Definition: spatial_preorder.hpp:58
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::details::decr_dim
dimension_type decr_dim(Rank rank, dimension_type node_dim)
Decrement dimension node_dim, given rank.
Definition: spatial_rank.hpp:79
spatial::details::preorder_first
std::pair< NodePtr, dimension_type > preorder_first(NodePtr node, dimension_type dim, Rank rank, const Query &query)
Definition: spatial_preorder.hpp:25
spatial::details::preorder_increment
const Node< Link > * preorder_increment(const Node< Link > *x)
Reach the next node in preorder transversal.
Definition: spatial_node.hpp:872
spatial::details::incr_dim
dimension_type incr_dim(Rank rank, dimension_type node_dim)
Increment dimension node_dim, given rank.
Definition: spatial_rank.hpp:68
spatial::details::left_traversal
bool left_traversal(typename Container::mode_type::const_node_ptr node, dimension_type dim, const Equal< Container > &equal, relaxed_invariant_tag)
Definition: spatial_equal.hpp:83