Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_assert.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 
19 #ifdef SPATIAL_ENABLE_ASSERT
20 # ifndef SPATIAL_ASSERT_HPP_ONCE
21 # define SPATIAL_ASSERT_HPP_ONCE
22 # include <cstdlib>
23 # include <iostream>
24 namespace spatial
25 {
30  namespace assert
31  {
50  inline void assert_fail
51  (const char* msg, const char* filename, unsigned int line) throw()
52  {
53  try
54  {
55  std::cerr << std::endl
56  << "Assertion failed (" << filename << ":" << line
57  << "): '" << msg << "'" << std::endl;
58  }
59  catch (...) { }
60  abort();
61  }
62  }
63 
64  namespace details
65  {
66  // Prototype declaration for the assertions.
67  template <typename Key, typename Value> struct Kdtree_link;
68  template <typename Key, typename Value> struct Relaxed_kdtree_link;
69  template <typename Link> struct Node;
70  template <typename Rank, typename Key, typename Value, typename Compare,
71  typename Alloc>
72  class Kdtree;
73  template <typename Rank, typename Key, typename Value, typename Compare,
74  typename Balancing, typename Alloc>
75  class Relaxed_kdtree;
76 
77  template <typename Value>
78  inline const typename Kdtree_link<Value, Value>::key_type&
79  const_key(const Node<Kdtree_link<Value, Value> >* node);
80  template <typename Key, typename Value>
81  inline const typename Kdtree_link<Key, Value>::key_type&
82  const_key(const Node<Kdtree_link<Key, Value> >* node);
83  template <typename Key, typename Value>
84  inline const Kdtree_link<Key, Value>*
85  const_link(const Node<Kdtree_link<Key, Value> >* node);
86 
87  template <typename Value>
88  inline const typename Relaxed_kdtree_link<Value, Value>::key_type&
89  const_key(const Node<Relaxed_kdtree_link<Value, Value> >* node);
90  template <typename Key, typename Value>
91  inline const typename Relaxed_kdtree_link<Key, Value>::key_type&
92  const_key(const Node<Relaxed_kdtree_link<Key, Value> >* node);
93  template <typename Key, typename Value>
94  inline const Relaxed_kdtree_link<Key, Value>*
95  const_link(const Node<Relaxed_kdtree_link<Key, Value> >* node);
96  }
97 
98  namespace assert
99  {
108  template <typename Compare, typename Key, typename Value>
110  inline bool
111  assert_invariant_node
112  (const Compare& cmp, dimension_type rank, dimension_type depth,
113  const details::Node<details::Kdtree_link<Key, Value> >* node)
114  {
115  dimension_type next_depth = depth + 1;
116  const details::Node<details::Kdtree_link<Key, Value> >
117  *left = node->left, *right = node->right;
118  while (!header(node->parent))
119  {
120  if (node->parent->left == node)
121  {
122  if (!cmp((depth - 1) % rank, const_key(node),
123  const_key(node->parent)))
124  return false;
125  }
126  else
127  {
128  if (cmp((depth - 1) % rank, const_key(node),
129  const_key(node->parent)))
130  return false;
131  }
132  --depth;
133  node = node->parent;
134  }
135  return
136  ((!left || assert_invariant_node(cmp, rank, next_depth, left))
137  && (!right || assert_invariant_node(cmp, rank, next_depth, right)));
138  }
139 
140  template <typename Compare, typename Key, typename Value>
141  inline bool
142  assert_invariant_node
143  (const Compare& cmp, dimension_type rank, dimension_type depth,
144  const details::Node<details::Relaxed_kdtree_link<Key, Value> >* node)
145  {
146  dimension_type next_depth = depth + 1;
147  const details::Node<details::Relaxed_kdtree_link<Key, Value> >
148  *left = node->left, *right = node->right;
149  while (!header(node->parent))
150  {
151  if (node->parent->left == node)
152  {
153  if (cmp((depth - 1) % rank, const_key(node->parent),
154  const_key(node)))
155  return false;
156  }
157  else
158  {
159  if (cmp((depth - 1) % rank, const_key(node),
160  const_key(node->parent)))
161  return false;
162  }
163  --depth;
164  node = node->parent;
165  }
166  return
167  ((!left || assert_invariant_node(cmp, rank, next_depth, left))
168  && (!right || assert_invariant_node(cmp, rank, next_depth, right)));
169  }
171 
177  template <typename Container>
178  inline bool
179  assert_invariant(const Container& container)
180  {
181  typename Container::const_iterator::node_ptr node
182  = container.end().node->parent; // get root node
183  if (container.size() == 0 && node != node->parent)
184  return false;
185  else if (!header(node))
186  return assert_invariant_node
187  (container.key_comp(), container.dimension(), 0, node);
188  else return true;
189  }
190 
199  template <typename Compare, typename Key, typename Value>
201  inline std::ostream&
202  assert_inspect_node
203  (const Compare& cmp, dimension_type rank, std::ostream& o,
204  const details::Node<details::Kdtree_link<Key, Value> >* node,
205  std::size_t depth)
206  {
207  for (std::size_t i = 0; i < depth; ++i) o << ".";
208  if (header(node->parent)) o << "T";
209  else if (node->parent->left == node) o << "L";
210  else if (node->parent->right == node) o << "R";
211  else o << "E";
212  const details::Node<details::Kdtree_link<Key, Value> >
213  *test = node;
214  std::size_t test_depth = depth;
215  while (!header(test->parent))
216  {
217  if (test->parent->left == test)
218  {
219  if (!cmp((test_depth - 1) % rank, const_key(test),
220  const_key(test->parent)))
221  { o << "!"; break; }
222  }
223  else
224  {
225  if (cmp((test_depth - 1) % rank, const_key(test),
226  const_key(test->parent)))
227  { o << "!"; break; }
228  }
229  --test_depth;
230  test = test->parent;
231  }
232  o << "<node:" << node << ">{parent:" << node->parent
233  << " left:" << node->left << " right:" << node->right
234  << std::flush
235  << " key:" << details::const_key(node) << "}"
236  << std::endl;
237  if (node->left)
238  assert_inspect_node(cmp, rank, o, node->left, depth + 1);
239  if (node->right)
240  assert_inspect_node(cmp, rank, o, node->right, depth + 1);
241  return o;
242  }
243 
244  template <typename Compare, typename Key, typename Value>
245  inline std::ostream&
246  assert_inspect_node
247  (const Compare& cmp, dimension_type rank, std::ostream& o,
248  const details::Node<details::Relaxed_kdtree_link<Key, Value> >* node,
249  std::size_t depth)
250  {
251  if (node->left)
252  assert_inspect_node(cmp, rank, o, node->left, depth + 1);
253  for (std::size_t i = 0; i < depth; ++i) o << ".";
254  if (header(node->parent)) o << "T";
255  else if (node->parent->left == node) o << "L";
256  else if (node->parent->right == node) o << "R";
257  else o << "E";
258  const details::Node<details::Relaxed_kdtree_link<Key, Value> >
259  *test = node;
260  std::size_t test_depth = depth;
261  while (!header(test->parent))
262  {
263  if (test->parent->left == test)
264  {
265  if (cmp((test_depth - 1) % rank, const_key(test->parent),
266  const_key(test)))
267  { o << "!"; break; }
268  }
269  else
270  {
271  if (cmp((test_depth - 1) % rank, const_key(test),
272  const_key(test->parent)))
273  { o << "!"; break; }
274  }
275  --test_depth;
276  test = test->parent;
277  }
278  o << "<node:" << node << ">{parent:" << node->parent
279  << " left:" << node->left << " right:" << node->right
280  << " weight:" << details::const_link(node)->weight
281  << std::flush
282  << " key:" << details::const_key(node) << "}"
283  << std::endl;
284  if (node->right)
285  assert_inspect_node(cmp, rank, o, node->right, depth + 1);
286  return o;
287  }
289 
311  template <typename Rank, typename Key, typename Value, typename Compare,
313  typename Alloc>
314  inline void assert_inspect
315  (const char* msg, const char* filename, unsigned int line,
316  const details::Kdtree<Rank, Key, Value, Compare, Alloc>& tree) throw()
317  {
318  try
319  {
320  std::cerr << std::endl
321  << "Assertion failed (" << filename << ":" << line
322  << "): '" << msg << "' does not satisfy invariant"
323  << std::endl;
324  std::cerr << "<Kdtree:" << &tree << ">{" << std::endl;
325  std::cerr << "header:<node:" << tree.end().node
326  << ">{parent:" << tree.end().node->parent
327  << " left:" << tree.end().node->left
328  << " right:" << tree.end().node->right
329  << "}" << std::endl;
330  std::cerr << "leftmost:" << tree.begin().node
331  << " size:" << tree.size()
332  << " items:[" << std::endl;
333  if (tree.end().node->parent != tree.end().node)
334  assert_inspect_node(tree.key_comp(), tree.dimension(), std::cerr,
335  tree.end().node->parent, 0);
336  std::cerr << "]}" << std::endl;
337  }
338  catch (...) { }
339  abort();
340  }
341 
342  template <typename Rank, typename Key, typename Value, typename Compare,
343  typename Balancing, typename Alloc>
344  inline void assert_inspect
345  (const char* msg, const char* filename, unsigned int line,
346  const details::Relaxed_kdtree<Rank, Key, Value, Compare, Balancing, Alloc>&
347  tree) throw()
348  {
349  try
350  {
351  std::cerr << std::endl
352  << "Assertion failed (" << filename << ":" << line
353  << "): '" << msg << "' does not satisfy invariant"
354  << std::endl;
355  std::cerr << "<Relaxed_kdtree:" << &tree << ">{" << std::endl;
356  std::cerr << "header:<node:" << tree.end().node
357  << ">{parent:" << tree.end().node->parent
358  << " left:" << tree.end().node->left
359  << " right:" << tree.end().node->right
360  << "}" << std::endl;
361  std::cerr << "leftmost:" << tree.begin().node
362  << " size:" << tree.size()
363  << " items:[" << std::endl;
364  if (tree.end().node->parent != tree.end().node)
365  assert_inspect_node(tree.key_comp(), tree.dimension(), std::cerr,
366  tree.end().node->parent, 0);
367  std::cerr << "]}" << std::endl;
368  }
369  catch (...) { }
370  abort();
371  }
373  } // namespace assert
374 } // namespace spatial
375 # endif
376 #endif
377 
378 #ifdef SPATIAL_ASSERT_CHECK
379 # undef SPATIAL_ASSERT_CHECK
380 #endif
381 
382 #ifndef SPATIAL_ENABLE_ASSERT
383 
403 # define SPATIAL_ASSERT_CHECK(expr)
404 
426 # define SPATIAL_ASSERT_INVARIANT(container)
427 #else
428 # define SPATIAL_ASSERT_CHECK(expr) \
429  ((expr) \
430  ? static_cast<void>(0) \
431  : ::spatial::assert::assert_fail(#expr, __FILE__, __LINE__))
432 # define SPATIAL_ASSERT_INVARIANT(container) \
433  ((::spatial::assert::assert_invariant(container)) \
434  ? static_cast<void>(0) \
435  : ::spatial::assert::assert_inspect(#container, __FILE__, __LINE__, container))
436 #endif
spatial::details::const_key
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.
Definition: spatial_node.hpp:387
spatial::details::header
bool header(const Node< Link > *x)
Check if node is a header node.
Definition: spatial_node.hpp:96
spatial::depth
std::size_t depth(const Iterator &iterator)
Returns the depth of a node's iterator.
Definition: algorithm.hpp:84
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::details::const_link
const Kdtree_link< Key, Value > * const_link(const Node< Kdtree_link< Key, Value > > *node)
This function converts a pointer on a node into a link for a Kdtree_link type.
Definition: spatial_node.hpp:369
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23