Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
ordered_iterator.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 
13 #ifndef SPATIAL_ORDERED_ITERATOR_HPP
14 #define SPATIAL_ORDERED_ITERATOR_HPP
15 
16 #include <utility> // provides ::std::pair<>
17 #include "spatial.hpp"
18 #include "bits/spatial_ordered.hpp"
19 
20 namespace spatial
21 {
28  template <typename Ct>
29  struct ordered_iterator_pair
30  : std::pair<ordered_iterator<Ct>, ordered_iterator<Ct> >
31  {
36  typedef std::pair<ordered_iterator<Ct>, ordered_iterator<Ct> > Base;
37 
39  ordered_iterator_pair() { }
40 
43  ordered_iterator_pair(const ordered_iterator<Ct>& a,
44  const ordered_iterator<Ct>& b) : Base(a, b) { }
45  };
46 
53  template <typename Ct>
54  struct ordered_iterator_pair<const Ct>
55  : std::pair<ordered_iterator<const Ct>, ordered_iterator<const Ct> >
56  {
61  typedef std::pair<ordered_iterator<const Ct>, ordered_iterator<const Ct> >
62  Base;
63 
65  ordered_iterator_pair() { }
66 
69  ordered_iterator_pair(const ordered_iterator<const Ct>& a,
70  const ordered_iterator<const Ct>& b) : Base(a, b)
71  { }
72 
75  ordered_iterator_pair(const ordered_iterator_pair<Ct>& p)
76  : Base(p.first, p.second) { }
77  };
78 
94  template <typename Container>
95  inline ordered_iterator_pair<Container>
96  ordered_range(Container& container)
97  {
98  return ordered_iterator_pair<Container>(ordered_begin(container),
99  ordered_end(container));
100  }
101 
103 
118  template <typename Container>
119  inline ordered_iterator_pair<const Container>
120  ordered_range(const Container& container)
121  {
122  return ordered_iterator_pair<const Container>(ordered_begin(container),
123  ordered_end(container));
124  }
125 
126  template <typename Container>
127  inline ordered_iterator_pair<const Container>
128  ordered_crange(const Container& container)
129  {
130  return ordered_iterator_pair<const Container>(ordered_begin(container),
131  ordered_end(container));
132  }
134 
135  namespace details
136  {
159  template <typename Container>
160  ordered_iterator<Container>&
161  lower_bound_ordered
162  (ordered_iterator<Container>& iter,
163  const typename container_traits<Container>::key_type& bound);
164 
187  template <typename Container>
188  ordered_iterator<Container>&
189  upper_bound_ordered
190  (ordered_iterator<Container>& iter,
191  const typename container_traits<Container>::key_type& bound);
192  } // namespace details
193 
215  template <typename Container>
216  inline ordered_iterator<Container>
217  ordered_lower_bound(Container& container,
218  const typename container_traits<Container>::key_type&
219  bound)
220  {
221  if (container.empty()) return ordered_end(container);
222  ordered_iterator<Container> it
223  (container, 0, container.end().node->parent);
224  return details::lower_bound_ordered(it, bound);
225  }
226 
228 
243  template <typename Container>
244  inline ordered_iterator<const Container>
245  ordered_lower_bound
246  (const Container& container,
247  const typename container_traits<Container>::key_type& bound)
248  {
249  if (container.empty()) return ordered_end(container);
250  ordered_iterator<const Container> it
251  (container, 0, container.end().node->parent);
252  return details::lower_bound_ordered(it, bound);
253  }
254 
255  template <typename Container>
256  inline ordered_iterator<const Container>
257  ordered_clower_bound
258  (const Container& container,
259  const typename container_traits<Container>::key_type& bound)
260  { return ordered_lower_bound(container, bound); }
262 
285  template <typename Container>
286  inline ordered_iterator<Container>
287  ordered_upper_bound
288  (Container& container,
289  const typename container_traits<Container>::key_type& bound)
290  {
291  if (container.empty()) return ordered_end(container);
292  ordered_iterator<Container> it // At root (dim = 0)
293  (container, 0, container.end().node->parent);
294  return details::upper_bound_ordered(it, bound);
295  }
296 
298 
314  template <typename Container>
315  inline ordered_iterator<const Container>
316  ordered_upper_bound
317  (const Container& container,
318  const typename container_traits<Container>::key_type& bound)
319  {
320  if (container.empty()) return ordered_end(container);
321  ordered_iterator<const Container> it // At root (dim = 0)
322  (container, 0, container.end().node->parent);
323  return details::upper_bound_ordered(it, bound);
324  }
325 
326  template <typename Container>
327  inline ordered_iterator<const Container>
328  ordered_cupper_bound
329  (const Container& container,
330  const typename container_traits<Container>::key_type& bound)
331  { return ordered_upper_bound(container, bound); }
333 
334  namespace details
335  {
336  // Used to compare the bound against the node's key
337  template <typename Cmp, typename Key>
338  inline bool
339  order_less(const Cmp& cmp, dimension_type set_dim,
340  const Key& a, const Key& b)
341  {
342  for (dimension_type d = 0; d <= set_dim; ++d)
343  {
344  if (cmp(d, a, b)) return true;
345  if (cmp(d, b, a)) return false;
346  }
347  return false;
348  }
349 
350  // Specialization for iterators pointed to node using the relaxed
351  // invariant.
352  template<typename Container>
353  inline ordered_iterator<Container>&
354  lower_bound_ordered
355  (ordered_iterator<Container>& iter,
356  const typename container_traits<Container>::key_type& bound,
357  relaxed_invariant_tag)
358  {
359  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
360  const typename container_traits<Container>::rank_type
361  rank(iter.rank());
362  const typename container_traits<Container>::key_compare
363  cmp(iter.key_comp());
364  SPATIAL_ASSERT_CHECK(iter.node != 0);
365  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
366  SPATIAL_ASSERT_CHECK(!header(iter.node));
367  node_ptr end = iter.node->parent;
368  dimension_type set_dim = 0;
369  node_ptr best = 0;
370  dimension_type best_dim = 0;
371  node_ptr node;
372  dimension_type node_dim;
373  do
374  {
375  node = iter.node;
376  node_dim = iter.node_dim;
377  while (node->left != 0
378  && (node_dim > set_dim
379  || !cmp(node_dim, const_key(node), bound)))
380  { node = node->left; node_dim = incr_dim(rank, node_dim); }
381  if (!order_less(cmp, set_dim, const_key(node), bound))
382  { best = node; best_dim = node_dim; }
383  do
384  {
385  if (node->right != 0
386  && (node_dim > set_dim || best == 0
387  || !cmp(node_dim, const_key(best), const_key(node))))
388  {
389  node = node->right;
390  node_dim = incr_dim(rank, node_dim);
391  while (node->left != 0
392  && (node_dim > set_dim
393  || !cmp(node_dim, const_key(node), bound)))
394  {
395  node = node->left;
396  node_dim = incr_dim(rank, node_dim);
397  }
398  if (!order_less(cmp, set_dim, const_key(node), bound)
399  && (best == 0
400  || order_ref(cmp, rank,
401  const_key(node), const_key(best))))
402  { best = node; best_dim = node_dim; }
403  }
404  else
405  {
406  node_ptr p = node->parent;
407  while (p != end && p->right == node)
408  {
409  node = p;
410  node_dim = decr_dim(rank, node_dim);
411  p = node->parent;
412  }
413  node = p;
414  node_dim = decr_dim(rank, node_dim);
415  if (node != end
416  && !order_less(cmp, set_dim, const_key(node), bound)
417  && (best == 0 || order_ref(cmp, rank, const_key(node),
418  const_key(best))))
419  { best = node; best_dim = node_dim; }
420  }
421  } while (node != end);
422  } while (++set_dim < rank());
423  if (best != 0) { iter.node = best; iter.node_dim = best_dim; }
424  else { iter.node = node; iter.node_dim = node_dim; }
425  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
426  SPATIAL_ASSERT_CHECK(iter.node != 0);
427  return iter;
428  }
429 
430  // Specialization for iterators pointed to node using the strict
431  // invariant.
432  template<typename Container>
433  inline ordered_iterator<Container>&
434  lower_bound_ordered
435  (ordered_iterator<Container>& iter,
436  const typename container_traits<Container>::key_type& bound,
437  strict_invariant_tag)
438  {
439  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
440  const typename container_traits<Container>::rank_type
441  rank(iter.rank());
442  const typename container_traits<Container>::key_compare
443  cmp(iter.key_comp());
444  SPATIAL_ASSERT_CHECK(iter.node != 0);
445  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
446  SPATIAL_ASSERT_CHECK(!header(iter.node));
447  node_ptr end = iter.node->parent;
448  dimension_type set_dim = 0;
449  node_ptr best = 0;
450  dimension_type best_dim = 0;
451  node_ptr node;
452  dimension_type node_dim;
453  do
454  {
455  node = iter.node;
456  node_dim = iter.node_dim;
457  while (node->left != 0
458  && (node_dim > set_dim
459  // optimization for strict invarient
460  || cmp(node_dim, bound, const_key(node))))
461  { node = node->left; node_dim = incr_dim(rank, node_dim); }
462  if (!order_less(cmp, set_dim, const_key(node), bound))
463  { best = node; best_dim = node_dim; }
464  do
465  {
466  if (node->right != 0
467  && (node_dim > set_dim || best == 0
468  || !cmp(node_dim, const_key(best), const_key(node))))
469  {
470  node = node->right;
471  node_dim = incr_dim(rank, node_dim);
472  while (node->left != 0
473  && (node_dim > set_dim
474  // optimization for strict invarient
475  || cmp(node_dim, bound, const_key(node))))
476  {
477  node = node->left;
478  node_dim = incr_dim(rank, node_dim);
479  }
480  if (!order_less(cmp, set_dim, const_key(node), bound)
481  && (best == 0
482  || order_ref(cmp, rank,
483  const_key(node), const_key(best))))
484  { best = node; best_dim = node_dim; }
485  }
486  else
487  {
488  node_ptr p = node->parent;
489  while (p != end && p->right == node)
490  {
491  node = p;
492  node_dim = decr_dim(rank, node_dim);
493  p = node->parent;
494  }
495  node = p;
496  node_dim = decr_dim(rank, node_dim);
497  if (node != end
498  && !order_less(cmp, set_dim, const_key(node), bound)
499  && (best == 0 || order_ref(cmp, rank, const_key(node),
500  const_key(best))))
501  { best = node; best_dim = node_dim; }
502  }
503  } while (node != end);
504  } while (++set_dim < rank());
505  if (best != 0) { iter.node = best; iter.node_dim = best_dim; }
506  else { iter.node = node; iter.node_dim = node_dim; }
507  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
508  SPATIAL_ASSERT_CHECK(iter.node != 0);
509  return iter;
510  }
511 
512  template <typename Container>
513  inline ordered_iterator<Container>&
514  lower_bound_ordered(ordered_iterator<Container>& iter,
515  const typename container_traits<Container>::key_type&
516  bound)
517  {
518  return lower_bound_ordered
519  (iter, bound, typename container_traits<Container>::mode_type
520  ::invariant_category());
521  }
522 
523  // Walk tree nodes in right-first fashion, bouncing off values that are
524  // higher than key.
525  template <typename Container>
526  inline ordered_iterator<Container>&
527  upper_bound_ordered
528  (ordered_iterator<Container>& iter,
529  const typename container_traits<Container>::key_type& bound,
530  relaxed_invariant_tag)
531  {
532  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
533  const typename container_traits<Container>::rank_type
534  rank(iter.rank());
535  const typename container_traits<Container>::key_compare
536  cmp(iter.key_comp());
537  SPATIAL_ASSERT_CHECK(iter.node != 0);
538  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
539  SPATIAL_ASSERT_CHECK(!header(iter.node));
540  node_ptr end = iter.node->parent;
541  dimension_type set_dim = 0;
542  node_ptr best = 0;
543  dimension_type best_dim = 0;
544  node_ptr node;
545  dimension_type node_dim;
546  do
547  {
548  node = iter.node;
549  node_dim = iter.node_dim;
550  while (node->left != 0
551  && (node_dim > set_dim
552  || !cmp(node_dim, const_key(node), bound)))
553  { node = node->left; node_dim = incr_dim(rank, node_dim); }
554  if (order_less(cmp, set_dim, bound, const_key(node)))
555  { best = node; best_dim = node_dim; }
556  do
557  {
558  if (node->right != 0
559  && (node_dim > set_dim || best == 0
560  || !cmp(node_dim, const_key(best), const_key(node))))
561  {
562  node = node->right;
563  node_dim = incr_dim(rank, node_dim);
564  while (node->left != 0
565  && (node_dim > set_dim
566  || !cmp(node_dim, const_key(node), bound)))
567  {
568  node = node->left;
569  node_dim = incr_dim(rank, node_dim);
570  }
571  if (order_less(cmp, set_dim, bound, const_key(node))
572  && (best == 0
573  || order_ref(cmp, rank,
574  const_key(node), const_key(best))))
575  { best = node; best_dim = node_dim; }
576  }
577  else
578  {
579  node_ptr p = node->parent;
580  while (p != end && p->right == node)
581  {
582  node = p;
583  node_dim = decr_dim(rank, node_dim);
584  p = node->parent;
585  }
586  node = p;
587  node_dim = decr_dim(rank, node_dim);
588  if (node != end
589  && order_less(cmp, set_dim, bound, const_key(node))
590  && (best == 0
591  || order_ref(cmp, rank,
592  const_key(node), const_key(best))))
593  { best = node; best_dim = node_dim; }
594  }
595  } while (node != end);
596  } while (++set_dim < rank());
597  if (best != 0) { iter.node = best; iter.node_dim = best_dim; }
598  else { iter.node = node; iter.node_dim = node_dim; }
599  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
600  SPATIAL_ASSERT_CHECK(iter.node != 0);
601  return iter;
602  }
603 
604  // Walk tree nodes in right-first fashion, bouncing off values that are
605  // higher than key.
606  template <typename Container>
607  inline ordered_iterator<Container>&
608  upper_bound_ordered
609  (ordered_iterator<Container>& iter,
610  const typename container_traits<Container>::key_type& bound,
611  strict_invariant_tag)
612  {
613  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
614  const typename container_traits<Container>::rank_type
615  rank(iter.rank());
616  const typename container_traits<Container>::key_compare
617  cmp(iter.key_comp());
618  SPATIAL_ASSERT_CHECK(iter.node != 0);
619  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
620  SPATIAL_ASSERT_CHECK(!header(iter.node));
621  node_ptr end = iter.node->parent;
622  dimension_type set_dim = 0;
623  node_ptr best = 0;
624  dimension_type best_dim = 0;
625  node_ptr node;
626  dimension_type node_dim;
627  do
628  {
629  node = iter.node;
630  node_dim = iter.node_dim;
631  while (node->left != 0
632  && (node_dim > set_dim
633  // Optimization for strict invarient
634  || cmp(node_dim, bound, const_key(node))))
635  { node = node->left; node_dim = incr_dim(rank, node_dim); }
636  if (order_less(cmp, set_dim, bound, const_key(node)))
637  { best = node; best_dim = node_dim; }
638  do
639  {
640  if (node->right != 0
641  && (node_dim > set_dim || best == 0
642  || !cmp(node_dim, const_key(best), const_key(node))))
643  {
644  node = node->right;
645  node_dim = incr_dim(rank, node_dim);
646  while (node->left != 0
647  && (node_dim > set_dim
648  // Optimization for strict invarient
649  || cmp(node_dim, bound, const_key(node))))
650  {
651  node = node->left;
652  node_dim = incr_dim(rank, node_dim);
653  }
654  if (order_less(cmp, set_dim, bound, const_key(node))
655  && (best == 0
656  || order_ref(cmp, rank,
657  const_key(node), const_key(best))))
658  { best = node; best_dim = node_dim; }
659  }
660  else
661  {
662  node_ptr p = node->parent;
663  while (p != end && p->right == node)
664  {
665  node = p;
666  node_dim = decr_dim(rank, node_dim);
667  p = node->parent;
668  }
669  node = p;
670  node_dim = decr_dim(rank, node_dim);
671  if (node != end
672  && order_less(cmp, set_dim, bound, const_key(node))
673  && (best == 0
674  || order_ref(cmp, rank,
675  const_key(node), const_key(best))))
676  { best = node; best_dim = node_dim; }
677  }
678  } while (node != end);
679  } while (++set_dim < rank());
680  if (best != 0) { iter.node = best; iter.node_dim = best_dim; }
681  else { iter.node = node; iter.node_dim = node_dim; }
682  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
683  SPATIAL_ASSERT_CHECK(iter.node != 0);
684  return iter;
685  }
686 
687  template <typename Container>
688  inline ordered_iterator<Container>&
689  upper_bound_ordered(ordered_iterator<Container>& iter,
690  const typename container_traits<Container>::key_type&
691  bound)
692  {
693  return upper_bound_ordered
694  (iter, bound, typename container_traits<Container>::mode_type
695  ::invariant_category());
696  }
697  } // namespace details
698 } // namespace spatial
699 
700 #endif // SPATIAL_ORDERED_ITERATOR_HPP
spatial::ordered_range
ordered_iterator_pair< Container > ordered_range(Container &container)
Returns a pair of iterator on the first and the last value in the range that can be iterated...
Definition: ordered_iterator.hpp:96
spatial::ordered_cupper_bound
ordered_iterator< const Container > ordered_cupper_bound(const Container &container, const typename container_traits< Container >::key_type &bound)
Finds the value with the largest coordinate along the ordered dimension that is stricly less than bou...
Definition: ordered_iterator.hpp:329
spatial::ordered_iterator
All elements returned by this iterator are ordered from the smallest to the largest value of their ke...
Definition: spatial_ordered.hpp:32
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::rank
const rank_type & rank() const
Return the current Rank type used by the iterator.
Definition: spatial_bidirectional.hpp:107
spatial::details::invariant_category
Link::invariant_category invariant_category(const Node< Link > *)
For a given node, this function returns the invariant category of the node.
Definition: spatial_node.hpp:229
spatial::details::order_ref
bool order_ref(const Cmp &cmp, const Rank &rank, const Key &a, const Key &b)
Definition: spatial_ordered.hpp:447
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::node
node_ptr node
The pointer to the current node.
Definition: spatial_bidirectional.hpp:122
spatial::container_traits::key_compare
Tp::key_compare key_compare
Comparison functor used to compare two instances of key_type.
Definition: traits.hpp:98
spatial::details::upper_bound_ordered
ordered_iterator< Container > & upper_bound_ordered(ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound)
Move the iterator given in parameter to the value with the largest coordinate strictly lower than bou...
Definition: ordered_iterator.hpp:689
spatial::ordered_iterator::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: spatial_ordered.hpp:117
spatial::ordered_iterator_pair::ordered_iterator_pair
ordered_iterator_pair()
Constructs an empty, uninitialized object.
Definition: ordered_iterator.hpp:39
spatial::ordered_begin
ordered_iterator< Container > ordered_begin(Container &container)
Finds the value in container for which its key has the smallest coordinate over the dimension ordered...
Definition: spatial_ordered.hpp:407
spatial::container_traits::key_type
Tp::key_type key_type
The type representing the key managed by the container.
Definition: traits.hpp:48
spatial::ordered_iterator< const Ct >
All elements returned by this iterator are ordered from the smallest to the largest value of their ke...
Definition: spatial_ordered.hpp:132
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::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::node_dim
dimension_type node_dim
The dimension of the current node.
Definition: spatial_bidirectional.hpp:131
spatial::details::header
bool header(const Node< Link > *x)
Check if node is a header node.
Definition: spatial_node.hpp:96
spatial::ordered_iterator_pair
This structure defines a pair of mutable spatial::ordered_iterator.
Definition: ordered_iterator.hpp:29
spatial::ordered_iterator_pair::ordered_iterator_pair
ordered_iterator_pair(const ordered_iterator< Ct > &a, const ordered_iterator< Ct > &b)
Regular constructor that builds a ordered_iterator_pair out of 2 spatial::ordered_iterator.
Definition: ordered_iterator.hpp:43
spatial::details::lower_bound_ordered
ordered_iterator< Container > & lower_bound_ordered(ordered_iterator< Container > &iter, const typename container_traits< Container >::key_type &bound)
Move the iterator given in parameter to the value with the smallest coordinate greater or equal to bo...
Definition: ordered_iterator.hpp:514
spatial::ordered_crange
ordered_iterator_pair< const Container > ordered_crange(const Container &container)
Returns a pair of constant iterator on the first and the last value in the range that can be iterated...
Definition: ordered_iterator.hpp:128
spatial::ordered_end
ordered_iterator< Container > ordered_end(Container &container)
Finds the past-the-end position in container for this constant iterator.
Definition: spatial_ordered.hpp:352
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::node_ptr
container_traits< Ct >::mode_type::node_ptr node_ptr
The type for the node pointed to by the iterator.
Definition: spatial_bidirectional.hpp:48
spatial::container_traits::mode_type
Tp::mode_type mode_type
The Link Mode type that is associated with the container.
Definition: traits.hpp:82
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::ordered_upper_bound
ordered_iterator< Container > ordered_upper_bound(Container &container, const typename container_traits< Container >::key_type &bound)
Finds the value with the largest coordinate along the ordered dimension that is stricly less than bou...
Definition: ordered_iterator.hpp:288
spatial::details::strict_invariant_tag
Definition: spatial_node.hpp:221
spatial::details::order_less
bool order_less(const Cmp &cmp, dimension_type set_dim, const Key &a, const Key &b)
Definition: ordered_iterator.hpp:339
spatial::container_traits::rank_type
Tp::rank_type rank_type
The type used to represent the rank of the container.
Definition: traits.hpp:111
spatial::ordered_iterator_pair< const Ct >::ordered_iterator_pair
ordered_iterator_pair(const ordered_iterator< const Ct > &a, const ordered_iterator< const Ct > &b)
Regular constructor that builds a ordered_iterator_pair out of 2 spatial::ordered_iterator.
Definition: ordered_iterator.hpp:69
spatial::details::relaxed_invariant_tag
The category of invariants for a k-d tree node: strict or relaxed.
Definition: spatial_node.hpp:220
spatial::ordered_iterator_pair::Base
std::pair< ordered_iterator< Ct >, ordered_iterator< Ct > > Base
A pair of iterators that represents a range (that is: a range of elements to iterate, and not an orthogonal range).
Definition: ordered_iterator.hpp:36
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::ordered_iterator_pair< const Ct >::ordered_iterator_pair
ordered_iterator_pair()
Constructs an empty, uninitialized object.
Definition: ordered_iterator.hpp:65
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::ordered_iterator_pair< const Ct >::Base
std::pair< ordered_iterator< const Ct >, ordered_iterator< const Ct > > Base
A pair of iterators that represents a range (that is: a range of elements to iterate, and not an orthogonal range).
Definition: ordered_iterator.hpp:62
spatial::ordered_lower_bound
ordered_iterator< Container > ordered_lower_bound(Container &container, const typename container_traits< Container >::key_type &bound)
Finds the value with the smallest coordinate along the ordered dimension that is greater or equal to ...
Definition: ordered_iterator.hpp:217
spatial::ordered_clower_bound
ordered_iterator< const Container > ordered_clower_bound(const Container &container, const typename container_traits< Container >::key_type &bound)
Finds the value with the smallest coordinate along the ordered dimension that is greater or equal to ...
Definition: ordered_iterator.hpp:258
spatial::ordered_iterator_pair< const Ct >::ordered_iterator_pair
ordered_iterator_pair(const ordered_iterator_pair< Ct > &p)
Convert a mutable ordered iterator pair into a const ordered iterator pair.
Definition: ordered_iterator.hpp:75
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