Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_region.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 
15 #ifndef SPATIAL_REGION_HPP
16 #define SPATIAL_REGION_HPP
17 
18 #include <utility> // std::pair<> and std::make_pair()
19 #include "../traits.hpp"
20 #include "spatial_bidirectional.hpp"
21 #include "spatial_rank.hpp"
22 #include "spatial_except.hpp"
23 
24 namespace spatial
25 {
45  template <typename Key, typename Compare>
46  class bounds
47  : private Compare // empty member optimization
48  {
49  public:
53  bounds()
54  : Compare(), _lower(), _upper() { }
55 
60  bounds(const Compare& compare, const Key& lower, const Key& upper)
61  : Compare(compare), _lower(lower), _upper(upper)
62  { }
63 
68  relative_order
69  operator()(dimension_type dim, dimension_type, const Key& key) const
70  {
71  return (Compare::operator()(dim, key, _lower)
72  ? below
73  : (Compare::operator()(dim, key, _upper)
74  ? matching
75  : above));
76  }
77 
78  private:
82  Key _lower;
83 
87  Key _upper;
88  };
89 
108  template <typename Tp>
109  bounds<typename container_traits<Tp>::key_type,
110  typename container_traits<Tp>::key_compare>
111  make_bounds
112  (const Tp& container,
113  const typename container_traits<Tp>::key_type& lower,
114  const typename container_traits<Tp>::key_type& upper)
115  {
116  except::check_bounds(container, lower, upper);
117  return bounds
118  <typename container_traits<Tp>::key_type,
119  typename container_traits<Tp>::key_compare>
120  (container.key_comp(), lower, upper);
121  }
122 
137  template <typename Ct, typename Predicate
138  = bounds<typename container_traits<Ct>::key_type,
139  typename container_traits<Ct>::key_compare> >
140  class region_iterator
141  : public details::Bidirectional_iterator
142  <typename container_traits<Ct>::mode_type,
143  typename container_traits<Ct>::rank_type>
144  {
145  private:
146  typedef typename details::Bidirectional_iterator
147  <typename container_traits<Ct>::mode_type,
148  typename container_traits<Ct>::rank_type> Base;
149 
150  public:
152  region_iterator() { }
153 
168  region_iterator(Ct& container, const Predicate& pred,
169  typename container_traits<Ct>::iterator iter)
170  : Base(container.rank(), iter.node, modulo(iter.node, container.rank())),
171  _pred(pred) { }
172 
190  region_iterator
191  (Ct& container, const Predicate& pred, dimension_type dim,
192  typename container_traits<Ct>::mode_type::node_ptr ptr)
193  : Base(container.rank(), ptr, dim), _pred(pred) { }
194 
197  region_iterator<Ct, Predicate>& operator++()
198  { return increment_region(*this); }
199 
202  region_iterator<Ct, Predicate> operator++(int)
203  {
204  region_iterator<Ct, Predicate> x(*this);
205  increment_region(*this);
206  return x;
207  }
208 
211  region_iterator<Ct, Predicate>& operator--()
212  { return decrement_region(*this); }
213 
216  region_iterator<Ct, Predicate> operator--(int)
217  {
218  region_iterator<Ct, Predicate> x(*this);
219  decrement_region(*this);
220  return x;
221  }
222 
224  Predicate predicate() const { return _pred; }
225 
226  private:
228  Predicate _pred;
229  };
230 
245  template <typename Ct, typename Predicate>
246  class region_iterator<const Ct, Predicate>
247  : public details::Const_bidirectional_iterator
248  <typename container_traits<Ct>::mode_type,
249  typename container_traits<Ct>::rank_type>
250  {
251  private:
252  typedef details::Const_bidirectional_iterator
253  <typename container_traits<Ct>::mode_type,
254  typename container_traits<Ct>::rank_type> Base;
255 
256  public:
258  region_iterator() { }
259 
274  region_iterator(const Ct& container, const Predicate& pred,
275  typename container_traits<Ct>::const_iterator iter)
276  : Base(container.rank(), iter.node, modulo(iter.node, container.rank())),
277  _pred(pred) { }
278 
297  region_iterator
298  (const Ct& container, const Predicate& pred, dimension_type dim,
299  typename container_traits<Ct>::mode_type::const_node_ptr ptr)
300  : Base(container.rank(), ptr, dim), _pred(pred) { }
301 
303  region_iterator(const region_iterator<Ct, Predicate>& iter)
304  : Base(iter.rank(), iter.node, iter.node_dim), _pred(iter.predicate()) { }
305 
308  region_iterator<const Ct, Predicate>& operator++()
309  { return increment_region(*this); }
310 
313  region_iterator<const Ct, Predicate> operator++(int)
314  {
315  region_iterator<const Ct, Predicate> x(*this);
316  increment_region(*this);
317  return x;
318  }
319 
322  region_iterator<const Ct, Predicate>& operator--()
323  { return decrement_region(*this); }
324 
327  region_iterator<const Ct, Predicate> operator--(int)
328  {
329  region_iterator<const Ct, Predicate> x(*this);
330  decrement_region(*this);
331  return x;
332  }
333 
335  Predicate predicate() const { return _pred; }
336 
337  private:
339  Predicate _pred;
340  };
341 
342  namespace details
343  {
353  template <typename Ct, typename Predicate>
354  region_iterator<Ct, Predicate>&
355  increment_region(region_iterator<Ct, Predicate>& iter);
356 
369  template <typename Ct, typename Predicate>
370  region_iterator<Ct, Predicate>&
371  decrement_region(region_iterator<Ct, Predicate>& iter);
372 
383  template <typename Ct, typename Predicate>
384  region_iterator<Ct, Predicate>&
385  minimum_region(region_iterator<Ct, Predicate>& iter);
386 
397  template <typename Ct, typename Predicate>
398  region_iterator<Ct, Predicate>&
399  maximum_region(region_iterator<Ct, Predicate>& iter);
400 
401  } // namespace details
402 
403  template <typename Ct, typename Predicate>
404  inline region_iterator<Ct, Predicate>
405  region_end(Ct& container, const Predicate& pred)
406  {
407  return region_iterator<Ct, Predicate>
408  (container, pred, container.dimension() - 1,
409  container.end().node); // At header, dim = rank - 1
410  }
411 
412  template <typename Ct, typename Predicate>
413  inline region_iterator<const Ct, Predicate>
414  region_end(const Ct& container, const Predicate& pred)
415  {
416  return region_iterator<const Ct, Predicate>
417  (container, pred, container.dimension() - 1,
418  container.end().node); // At header, dim = rank - 1
419  }
420 
421  template <typename Ct, typename Predicate>
422  inline region_iterator<const Ct, Predicate>
423  region_cend(const Ct& container, const Predicate& pred)
424  { return region_end(container, pred); }
425 
426  template <typename Ct>
427  inline region_iterator<Ct>
428  region_end(Ct& container,
429  const typename container_traits<Ct>::key_type& lower,
430  const typename container_traits<Ct>::key_type& upper)
431  { return region_end(container, make_bounds(container, lower, upper)); }
432 
433  template <typename Ct>
434  inline region_iterator<const Ct>
435  region_end(const Ct& container,
436  const typename container_traits<Ct>::key_type& lower,
437  const typename container_traits<Ct>::key_type& upper)
438  { return region_end(container, make_bounds(container, lower, upper)); }
439 
440  template <typename Ct>
441  inline region_iterator<const Ct>
442  region_cend(const Ct& container,
443  const typename container_traits<Ct>::key_type& lower,
444  const typename container_traits<Ct>::key_type& upper)
445  { return region_cend(container, make_bounds(container, lower, upper)); }
446 
447  template <typename Ct, typename Predicate>
448  inline region_iterator<Ct, Predicate>
449  region_begin(Ct& container, const Predicate& pred)
450  {
451  if (container.empty()) return region_end(container, pred);
452  region_iterator<Ct, Predicate>
453  it(container, pred, 0, container.end().node->parent); // At root, dim = 0
454  return details::minimum_region(it);
455  }
456 
457  template <typename Ct, typename Predicate>
458  inline region_iterator<const Ct, Predicate>
459  region_begin(const Ct& container, const Predicate& pred)
460  {
461  if (container.empty()) return region_end(container, pred);
462  region_iterator<const Ct, Predicate>
463  it(container, pred, 0, container.end().node->parent); // At root, dim = 0
464  return details::minimum_region(it);
465  }
466 
467  template <typename Ct, typename Predicate>
468  inline region_iterator<const Ct, Predicate>
469  region_cbegin(const Ct& container, const Predicate& pred)
470  { return region_begin(container, pred); }
471 
472  template <typename Ct>
473  inline region_iterator<Ct>
474  region_begin(Ct& container,
475  const typename container_traits<Ct>::key_type& lower,
476  const typename container_traits<Ct>::key_type& upper)
477  { return region_begin(container, make_bounds(container, lower, upper)); }
478 
479  template <typename Ct>
480  inline region_iterator<const Ct>
481  region_begin(const Ct& container,
482  const typename container_traits<Ct>::key_type& lower,
483  const typename container_traits<Ct>::key_type& upper)
484  { return region_begin(container, make_bounds(container, lower, upper)); }
485 
486  template <typename Ct>
487  inline region_iterator<const Ct>
488  region_cbegin(const Ct& container,
489  const typename container_traits<Ct>::key_type& lower,
490  const typename container_traits<Ct>::key_type& upper)
491  { return region_cbegin(container, make_bounds(container, lower, upper)); }
492 
499  template <typename Ct, typename Predicate
500  = bounds<typename container_traits<Ct>::key_type,
501  typename container_traits<Ct>::key_compare> >
502  struct region_iterator_pair
503  : std::pair<region_iterator<Ct, Predicate>,
504  region_iterator<Ct, Predicate> >
505  {
510  typedef std::pair<region_iterator<Ct, Predicate>,
511  region_iterator<Ct, Predicate> > Base;
512 
514  region_iterator_pair() { }
515 
518  region_iterator_pair(const region_iterator<Ct, Predicate>& a,
519  const region_iterator<Ct, Predicate>& b)
520  : Base(a, b) { }
521  };
522 
529  template <typename Ct, typename Predicate>
530  struct region_iterator_pair<const Ct, Predicate>
531  : std::pair<region_iterator<const Ct, Predicate>,
532  region_iterator<const Ct, Predicate> >
533  {
538  typedef std::pair<region_iterator<const Ct, Predicate>,
539  region_iterator<const Ct, Predicate> > Base;
540 
542  region_iterator_pair() { }
543 
546  region_iterator_pair(const region_iterator<const Ct, Predicate>& a,
547  const region_iterator<const Ct, Predicate>& b)
548  : Base(a, b) { }
549 
552  region_iterator_pair(const region_iterator_pair<Ct, Predicate>& p)
553  : Base(p.first, p.second) { }
554  };
555 
567  template <typename Ct, typename Predicate>
569  inline region_iterator_pair<Ct, Predicate>
570  region_range(Ct& container, const Predicate& pred)
571  {
572  return region_iterator_pair<Ct, Predicate>
573  (region_begin(container, pred), region_end(container, pred));
574  }
575 
579  template <typename Ct, typename Predicate>
580  inline region_iterator_pair<const Ct, Predicate>
581  region_range(const Ct& container, const Predicate& pred)
582  {
583  return region_iterator_pair<const Ct, Predicate>
584  (region_begin(container, pred), region_end(container, pred));
585  }
586 
590  template <typename Ct, typename Predicate>
591  inline region_iterator_pair<const Ct, Predicate>
592  region_crange(const Ct& container, const Predicate& pred)
593  {
594  return region_iterator_pair<const Ct, Predicate>
595  (region_begin(container, pred), region_end(container, pred));
596  }
598 
599  template <typename Ct>
600  inline region_iterator_pair<Ct>
601  region_range(Ct& container,
602  const typename container_traits<Ct>::key_type& lower,
603  const typename container_traits<Ct>::key_type& upper)
604  { return region_range(container, make_bounds(container, lower, upper)); }
605 
606  template <typename Ct>
607  inline region_iterator_pair<const Ct>
608  region_range(const Ct& container,
609  const typename container_traits<Ct>::key_type& lower,
610  const typename container_traits<Ct>::key_type& upper)
611  { return region_range(container, make_bounds(container, lower, upper)); }
612 
613  template <typename Ct>
614  inline region_iterator_pair<const Ct>
615  region_crange(const Ct& container,
616  const typename container_traits<Ct>::key_type& lower,
617  const typename container_traits<Ct>::key_type& upper)
618  { return region_crange(container, make_bounds(container, lower, upper)); }
619 
620  namespace details
621  {
636  template <typename Rank, typename Key, typename Predicate>
637  inline bool
638  match_all(const Rank& rank, const Key& key, const Predicate& predicate)
639  {
640  for (dimension_type i = 0; i < rank(); ++i)
641  { if (predicate(i, rank(), key) != matching) { return false; } }
642  return true;
643  }
644 
645  template <typename Container, typename Predicate>
646  inline region_iterator<Container, Predicate>&
647  increment_region(region_iterator<Container, Predicate>& iter)
648  {
649  const typename container_traits<Container>::rank_type rank(iter.rank());
650  const Predicate pred(iter.predicate());
651  SPATIAL_ASSERT_CHECK(!header(iter.node));
652  SPATIAL_ASSERT_CHECK(iter.node != 0);
653  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
654  do
655  {
656  if (iter.node->right != 0
657  && pred(iter.node_dim, rank(), const_key(iter.node)) != above)
658  {
659  iter.node = iter.node->right;
660  iter.node_dim = incr_dim(rank, iter.node_dim);
661  while (iter.node->left != 0
662  && pred(iter.node_dim, rank(),
663  const_key(iter.node)) != below)
664  {
665  iter.node = iter.node->left;
666  iter.node_dim = incr_dim(rank, iter.node_dim);
667  }
668  }
669  else
670  {
671  typename region_iterator<Container, Predicate>::node_ptr p
672  = iter.node->parent;
673  while (!header(p) && iter.node == p->right)
674  {
675  iter.node = p;
676  iter.node_dim = decr_dim(rank, iter.node_dim);
677  p = iter.node->parent;
678  }
679  iter.node = p;
680  iter.node_dim = decr_dim(rank, iter.node_dim);
681  }
682  }
683  while (!header(iter.node)
684  && match_all(rank, const_key(iter.node), pred) == false);
685  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
686  SPATIAL_ASSERT_CHECK(iter.node != 0);
687  return iter;
688  }
689 
690  template <typename Container, typename Predicate>
691  inline region_iterator<Container, Predicate>&
692  decrement_region(region_iterator<Container, Predicate>& iter)
693  {
694  const typename container_traits<Container>::rank_type rank(iter.rank());
695  const Predicate pred(iter.predicate());
696  SPATIAL_ASSERT_CHECK(iter.node != 0);
697  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
698  if (header(iter.node))
699  {
700  iter.node = iter.node->parent;
701  iter.node_dim = 0; // root is always compared on dimension 0
702  return maximum_region(iter);
703  }
704  do
705  {
706  if (iter.node->left != 0
707  && pred(iter.node_dim, rank(), const_key(iter.node)) != below)
708  {
709  iter.node = iter.node->left;
710  iter.node_dim = incr_dim(rank, iter.node_dim);
711  while (iter.node->right != 0
712  && pred(iter.node_dim, rank(),
713  const_key(iter.node)) != above)
714  {
715  iter.node = iter.node->right;
716  iter.node_dim = incr_dim(rank, iter.node_dim);
717  }
718  }
719  else
720  {
721  typename region_iterator<Container, Predicate>::node_ptr p
722  = iter.node->parent;
723  while (!header(p) && iter.node == p->left)
724  {
725  iter.node = p;
726  iter.node_dim = decr_dim(rank, iter.node_dim);
727  p = iter.node->parent;
728  }
729  iter.node = p;
730  iter.node_dim = decr_dim(rank, iter.node_dim);
731  }
732  }
733  while (!header(iter.node)
734  && match_all(rank, const_key(iter.node), pred) == false);
735  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
736  SPATIAL_ASSERT_CHECK(iter.node != 0);
737  return iter;
738  }
739 
740  template <typename Container, typename Predicate>
741  inline region_iterator<Container, Predicate>&
742  minimum_region(region_iterator<Container, Predicate>& iter)
743  {
744  const typename container_traits<Container>::rank_type rank(iter.rank());
745  const Predicate pred(iter.predicate());
746  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
747  SPATIAL_ASSERT_CHECK(!header(iter.node));
748  SPATIAL_ASSERT_CHECK(iter.node != 0);
749  typename region_iterator<Container, Predicate>::node_ptr end
750  = iter.node->parent;
751  // Quick positioning according to in-order transversal.
752  while(iter.node->right != 0
753  && pred(iter.node_dim, rank(), const_key(iter.node)) == below)
754  {
755  iter.node = iter.node->right;
756  iter.node_dim = incr_dim(rank, iter.node_dim);
757  }
758  while(iter.node->left != 0
759  && pred(iter.node_dim, rank(), const_key(iter.node)) != below)
760  {
761  iter.node = iter.node->left;
762  iter.node_dim = incr_dim(rank, iter.node_dim);
763  }
764  // Start algorithm.
765  do
766  {
767  if (match_all(rank, const_key(iter.node), pred) == true) { break; }
768  if (iter.node->right != 0
769  && pred(iter.node_dim, rank(),
770  const_key(iter.node)) != above)
771  {
772  iter.node = iter.node->right;
773  iter.node_dim = incr_dim(rank, iter.node_dim);
774  while (iter.node->left != 0
775  && pred(iter.node_dim, rank(),
776  const_key(iter.node)) != below)
777  {
778  iter.node = iter.node->left;
779  iter.node_dim = incr_dim(rank, iter.node_dim);
780  }
781  }
782  else
783  {
784  typename region_iterator<Container, Predicate>::node_ptr p
785  = iter.node->parent;
786  while (p != end && iter.node == p->right)
787  {
788  iter.node = p;
789  iter.node_dim = decr_dim(rank, iter.node_dim);
790  p = iter.node->parent;
791  }
792  iter.node = p;
793  iter.node_dim = decr_dim(rank, iter.node_dim);
794  }
795  }
796  while (iter.node != end);
797  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
798  SPATIAL_ASSERT_CHECK(iter.node != 0);
799  return iter;
800  }
801 
802  template <typename Container, typename Predicate>
803  inline region_iterator<Container, Predicate>&
804  maximum_region(region_iterator<Container, Predicate>& iter)
805  {
806  const typename container_traits<Container>::rank_type rank(iter.rank());
807  const Predicate pred(iter.predicate());
808  SPATIAL_ASSERT_CHECK(iter.node != 0);
809  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
810  SPATIAL_ASSERT_CHECK(!header(iter.node));
811  typename region_iterator<Container, Predicate>::node_ptr end
812  = iter.node->parent;
813  // Quick positioning according to in-order transversal.
814  while (iter.node->left != 0
815  && pred(iter.node_dim, rank(), const_key(iter.node)) == above)
816  {
817  iter.node = iter.node->left;
818  iter.node_dim = incr_dim(rank, iter.node_dim);
819  }
820  while (iter.node->right != 0
821  && pred(iter.node_dim, rank(), const_key(iter.node)) != above)
822  {
823  iter.node = iter.node->right;
824  iter.node_dim = incr_dim(rank, iter.node_dim);
825  }
826  // Start algorithm.
827  do
828  {
829  if (match_all(rank, const_key(iter.node), pred) == true) { break; }
830  if (iter.node->left != 0
831  && pred(iter.node_dim, rank(), const_key(iter.node)) != below)
832  {
833  iter.node = iter.node->left;
834  iter.node_dim = incr_dim(rank, iter.node_dim);
835  while (iter.node->right != 0
836  && pred(iter.node_dim, rank(),
837  const_key(iter.node)) != above)
838  {
839  iter.node = iter.node->right;
840  iter.node_dim = incr_dim(rank, iter.node_dim);
841  }
842  }
843  else
844  {
845  typename region_iterator<Container, Predicate>::node_ptr p
846  = iter.node->parent;
847  while (p != end && iter.node == p->left)
848  {
849  iter.node = p;
850  iter.node_dim = decr_dim(rank, iter.node_dim);
851  p = iter.node->parent;
852  }
853  iter.node = p;
854  iter.node_dim = decr_dim(rank, iter.node_dim);
855  }
856  }
857  while (iter.node != end);
858  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
859  SPATIAL_ASSERT_CHECK(iter.node != 0);
860  return iter;
861  }
862 
863  } // namespace details
864 } // namespace spatial
865 
866 #endif // SPATIAL_REGION_HPP
spatial::bounds::operator()
relative_order operator()(dimension_type dim, dimension_type, const Key &key) const
The operator that returns true if the key is within the boundaries, false if it isn't.
Definition: spatial_region.hpp:69
spatial::region_iterator< const Ct, Predicate >::region_iterator
region_iterator(const Ct &container, const Predicate &pred, typename container_traits< Ct >::const_iterator iter)
Build a region iterator from a container's iterator type.
Definition: spatial_region.hpp:274
spatial::details::decrement_region
region_iterator< Ct, Predicate > & decrement_region(region_iterator< Ct, Predicate > &iter)
From iter, returns the previous matching iterator in the region delimited by Predicate, using in-order transversal.
spatial::region_iterator_pair< const Ct, Predicate >
This structure defines a pair of constant region iterator.
Definition: spatial_region.hpp:530
spatial::bounds::_upper
Key _upper
The upper bound for the orthogonal region.
Definition: spatial_region.hpp:87
spatial::region_iterator_pair< const Ct, Predicate >::region_iterator_pair
region_iterator_pair(const region_iterator_pair< Ct, Predicate > &p)
Convert a mutable region iterator pair into a const region iterator pair.
Definition: spatial_region.hpp:552
spatial::region_iterator
This type provides both an iterator and a constant iterator to iterate through all elements of a tree...
Definition: spatial_region.hpp:140
spatial::region_iterator< const Ct, Predicate >::operator--
region_iterator< const Ct, Predicate > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: spatial_region.hpp:327
spatial::except::check_bounds
void check_bounds(const Tp &container, const typename container_traits< Tp >::key_type &lower, const typename container_traits< Tp >::key_type &upper)
Checks if all coordinates of lower are strictly less than these of higher along the same dimensions...
Definition: spatial_except.hpp:150
spatial::region_iterator_pair::region_iterator_pair
region_iterator_pair()
Empty constructor.
Definition: spatial_region.hpp:514
spatial::details::maximum_region
region_iterator< Ct, Predicate > & maximum_region(region_iterator< Ct, Predicate > &iter)
In the children of the node pointed to by iter, find the last matching iterator in the region delimit...
spatial::region_iterator< const Ct, Predicate >::region_iterator
region_iterator(const region_iterator< Ct, Predicate > &iter)
Convertion of an iterator into a const_iterator is permitted.
Definition: spatial_region.hpp:303
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::region_iterator< const Ct, Predicate >::_pred
Predicate _pred
The related data for the iterator.
Definition: spatial_region.hpp:339
spatial::region_iterator< const Ct, Predicate >
This type provides both an iterator and a constant iterator to iterate through all elements of a tree...
Definition: spatial_region.hpp:246
spatial::details::minimum_region
region_iterator< Ct, Predicate > & minimum_region(region_iterator< Ct, Predicate > &iter)
In the children of the node pointed to by iter, find the first matching iterator in the region delimi...
spatial::bounds::bounds
bounds()
The default constructor leaves everything un-initialized.
Definition: spatial_region.hpp:53
spatial::region_cend
region_iterator< const Ct, Predicate > region_cend(const Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:423
spatial::region_iterator_pair
This structure defines a pair of mutable region iterator.
Definition: spatial_region.hpp:502
spatial::bounds::bounds
bounds(const Compare &compare, const Key &lower, const Key &upper)
Set the lower and upper boundary for the orthogonal region search.
Definition: spatial_region.hpp:60
spatial::container_traits::key_type
Tp::key_type key_type
The type representing the key managed by the container.
Definition: traits.hpp:48
spatial::region_iterator_pair< const Ct, Predicate >::Base
std::pair< region_iterator< const Ct, Predicate >, region_iterator< const Ct, Predicate > > Base
A pair of iterators that represents a range (that is: a range of elements to iterate, and not an orthogonal range).
Definition: spatial_region.hpp:539
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::region_iterator_pair< const Ct, Predicate >::region_iterator_pair
region_iterator_pair()
Empty constructor.
Definition: spatial_region.hpp:542
spatial::region_iterator_pair::region_iterator_pair
region_iterator_pair(const region_iterator< Ct, Predicate > &a, const region_iterator< Ct, Predicate > &b)
Regular constructor that builds a region_iterator_pair out of 2 region_iterators. ...
Definition: spatial_region.hpp:518
spatial::details::header
bool header(const Node< Link > *x)
Check if node is a header node.
Definition: spatial_node.hpp:96
spatial::region_iterator< const Ct, Predicate >::operator++
region_iterator< const Ct, Predicate > & operator++()
Increments the iterator and returns the incremented value.
Definition: spatial_region.hpp:308
spatial::region_iterator< const Ct, Predicate >::predicate
Predicate predicate() const
Return the key_comparator used by the iterator.
Definition: spatial_region.hpp:335
spatial::region_iterator_pair::Base
std::pair< region_iterator< Ct, Predicate >, region_iterator< Ct, Predicate > > Base
A pair of iterators that represents a range (that is: a range of elements to iterate, and not an orthogonal range).
Definition: spatial_region.hpp:511
spatial::region_begin
region_iterator< Ct, Predicate > region_begin(Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:449
spatial::region_range
region_iterator_pair< Ct, Predicate > region_range(Ct &container, const Predicate &pred)
Returns a spatial::region_iterator_pair where first points to the first element matching the predicat...
Definition: spatial_region.hpp:570
spatial::region_iterator_pair< const Ct, Predicate >::region_iterator_pair
region_iterator_pair(const region_iterator< const Ct, Predicate > &a, const region_iterator< const Ct, Predicate > &b)
Regular constructor that builds a region_iterator_pair out of 2 region_iterators. ...
Definition: spatial_region.hpp:546
spatial::container_traits
The traits type for all containers in the spatial namespace.
Definition: traits.hpp:42
spatial::region_iterator::predicate
Predicate predicate() const
Return the key_comparator used by the iterator.
Definition: spatial_region.hpp:224
spatial::region_cbegin
region_iterator< const Ct, Predicate > region_cbegin(const Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:469
spatial::relative_order
relative_order
Defines values for relative ordering.
Definition: spatial.hpp:81
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::region_end
region_iterator< Ct, Predicate > region_end(Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:405
spatial::region_iterator< const Ct, Predicate >::operator++
region_iterator< const Ct, Predicate > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: spatial_region.hpp:313
spatial::region_iterator::operator--
region_iterator< Ct, Predicate > & operator--()
Decrements the iterator and returns the decremented value.
Definition: spatial_region.hpp:211
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::region_iterator< const Ct, Predicate >::Base
details::Const_bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: spatial_region.hpp:254
spatial::region_iterator::region_iterator
region_iterator(Ct &container, const Predicate &pred, typename container_traits< Ct >::iterator iter)
Build a region iterator from a container's iterator type.
Definition: spatial_region.hpp:168
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::region_crange
region_iterator_pair< const Ct, Predicate > region_crange(const Ct &container, const Predicate &pred)
This overload works only on constant containers and will return a set of constant iterators...
Definition: spatial_region.hpp:592
spatial::region_iterator::region_iterator
region_iterator()
Uninitialized iterator.
Definition: spatial_region.hpp:152
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::region_iterator< const Ct, Predicate >::operator--
region_iterator< const Ct, Predicate > & operator--()
Decrements the iterator and returns the decremented value.
Definition: spatial_region.hpp:322
spatial::region_iterator::operator++
region_iterator< Ct, Predicate > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: spatial_region.hpp:202
spatial::region_iterator::operator++
region_iterator< Ct, Predicate > & operator++()
Increments the iterator and returns the incremented value.
Definition: spatial_region.hpp:197
spatial::details::Const_bidirectional_iterator
A common template for constant bidirectional iterators that work on identical modes of linking...
Definition: spatial_bidirectional.hpp:145
spatial::details::Bidirectional_iterator
A common template for bidirectional iterators that work on identical modes of linking.
Definition: spatial_bidirectional.hpp:33
spatial::region_iterator::Base
details::Bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: spatial_region.hpp:148
spatial::region_iterator::_pred
Predicate _pred
The related data for the iterator.
Definition: spatial_region.hpp:228
spatial::details::match_all
bool match_all(const Rank &rank, const Key &key, const Predicate &predicate)
Return a boolean indicating whether all of key's coordinates are within range or not.
Definition: spatial_region.hpp:638
spatial::region_iterator< const Ct, Predicate >::region_iterator
region_iterator()
Constructs an empty, uninitialized object.
Definition: spatial_region.hpp:258
spatial::details::increment_region
region_iterator< Ct, Predicate > & increment_region(region_iterator< Ct, Predicate > &iter)
From iter, returns the next matching iterator in the region delimited by Predicate, using in-order transversal.
spatial::region_iterator::operator--
region_iterator< Ct, Predicate > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: spatial_region.hpp:216
spatial::bounds
A model of Region Predicate that defines an orthogonal region and checks if a value of type Key is co...
Definition: spatial_region.hpp:46
spatial::bounds::_lower
Key _lower
The lower bound for the orthogonal region.
Definition: spatial_region.hpp:82
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::make_bounds
bounds< typename container_traits< Tp >::key_type, typename container_traits< Tp >::key_compare > make_bounds(const Tp &container, const typename container_traits< Tp >::key_type &lower, const typename container_traits< Tp >::key_type &upper)
A bounds factory that takes in a container, 2 arguments lower and upper, and returns a fully construc...
Definition: spatial_region.hpp:112