Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
mapping_iterator.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_MAPPING_ITERATOR_HPP
14 #define SPATIAL_MAPPING_ITERATOR_HPP
15 
16 #include <utility> // std::pair
17 #include "spatial.hpp"
18 #include "traits.hpp"
19 #include "bits/spatial_bidirectional.hpp"
20 #include "bits/spatial_rank.hpp"
21 #include "bits/spatial_except.hpp"
22 #include "bits/spatial_assign.hpp"
23 #include "bits/spatial_mapping.hpp"
24 
25 namespace spatial
26 {
27  namespace details
28  {
41  template <typename Container>
42  struct Mapping : Container::key_compare
43  {
45  Mapping() { }
46 
54  Mapping
55  (const typename Container::key_compare& c, dimension_type m)
56  : Container::key_compare(c), mapping_dim(m)
57  { }
58 
59  typename Container::key_compare key_comp() const
60  { return static_cast<typename Container::key_compare>(*this); }
61 
75  dimension_type mapping_dim;
76  };
77  }
78 
92  template<typename Ct>
93  class mapping_iterator
94  : public details::Bidirectional_iterator
95  <typename container_traits<Ct>::mode_type,
96  typename container_traits<Ct>::rank_type>
97  {
98  private:
99  typedef details::Bidirectional_iterator
100  <typename container_traits<Ct>::mode_type,
101  typename container_traits<Ct>::rank_type> Base;
102 
103  public:
104  using Base::node;
105  using Base::node_dim;
106  using Base::rank;
107 
108  typedef typename container_traits<Ct>::key_compare key_compare;
109 
111  mapping_iterator() { }
112 
123  mapping_iterator(Ct& container, dimension_type mapping_dim,
124  typename container_traits<Ct>::iterator iter)
125  : Base(container.rank(), iter.node, modulo(iter.node, container.rank())),
126  _data(container.key_comp(), mapping_dim)
127  { except::check_dimension(container.dimension(), mapping_dim); }
128 
151  mapping_iterator(Ct& container, dimension_type mapping_dim,
152  dimension_type dim,
153  typename container_traits<Ct>::mode_type::node_ptr ptr)
154  : Base(container.rank(), ptr, dim),
155  _data(container.key_comp(), mapping_dim)
156  { except::check_dimension(container.dimension(), mapping_dim); }
157 
160  mapping_iterator<Ct>& operator++()
161  {
162  details::assign(node, node_dim,
163  increment_mapping(node, node_dim, rank(),
164  _data.mapping_dim, key_comp()));
165  return *this;
166  }
167 
170  mapping_iterator<Ct> operator++(int)
171  {
172  mapping_iterator<Ct> x(*this);
173  details::assign(node, node_dim,
174  increment_mapping(node, node_dim, rank(),
175  _data.mapping_dim, key_comp()));
176  return x;
177  }
178 
181  mapping_iterator<Ct>& operator--()
182  {
183  details::assign(node, node_dim,
184  decrement_mapping(node, node_dim, rank(),
185  _data.mapping_dim, key_comp()));
186  return *this;
187  }
188 
191  mapping_iterator<Ct> operator--(int)
192  {
193  mapping_iterator<Ct> x(*this);
194  details::assign(node, node_dim,
195  decrement_mapping(node, node_dim, rank(),
196  _data.mapping_dim, key_comp()));
197  return x;
198  }
199 
201  key_compare
202  key_comp() const { return _data.key_comp(); }
203 
220  dimension_type
222  mapping_dimension() const { return _data.mapping_dim; }
223  dimension_type&
224  mapping_dimension() { return _data.mapping_dim; }
226 
227  private:
229  details::Mapping<Ct> _data;
230  };
231 
247  template<typename Ct>
248  class mapping_iterator<const Ct>
249  : public details::Const_bidirectional_iterator
250  <typename container_traits<Ct>::mode_type,
251  typename container_traits<Ct>::rank_type>
252  {
253  private:
254  typedef details::Const_bidirectional_iterator
255  <typename container_traits<Ct>::mode_type,
256  typename container_traits<Ct>::rank_type> Base;
257 
258  public:
259  using Base::node;
260  using Base::node_dim;
261  using Base::rank;
262 
264  typedef typename container_traits<Ct>::key_compare key_compare;
265 
267  mapping_iterator() { }
268 
279  mapping_iterator(const Ct& container, dimension_type mapping_dim,
280  typename container_traits<Ct>::const_iterator iter)
281  : Base(container.rank(), iter.node, modulo(iter.node, container.rank())),
282  _data(container.key_comp(), mapping_dim)
283  { except::check_dimension(container.dimension(), mapping_dim); }
284 
310  mapping_iterator
311  (const Ct& container, dimension_type mapping_dim, dimension_type dim,
312  typename container_traits<Ct>::mode_type::const_node_ptr ptr)
313  : Base(container.rank(), ptr, dim),
314  _data(container.key_comp(), mapping_dim)
315  { except::check_dimension(container.dimension(), mapping_dim); }
316 
318  mapping_iterator(const mapping_iterator<Ct>& iter)
319  : Base(iter.rank(), iter.node, iter.node_dim),
320  _data(iter.key_comp(), iter.mapping_dimension()) { }
321 
324  mapping_iterator<const Ct>& operator++()
325  {
326  details::assign(node, node_dim,
327  increment_mapping(node, node_dim, rank(),
328  _data.mapping_dim, key_comp()));
329  return *this;
330  }
331 
334  mapping_iterator<const Ct> operator++(int)
335  {
336  mapping_iterator<const Ct> x(*this);
337  details::assign(node, node_dim,
338  increment_mapping(node, node_dim, rank(),
339  _data.mapping_dim, key_comp()));
340  return x;
341  }
342 
345  mapping_iterator<const Ct>& operator--()
346  {
347  details::assign(node, node_dim,
348  decrement_mapping(node, node_dim, rank(),
349  _data.mapping_dim, key_comp()));
350  return *this;
351  }
352 
355  mapping_iterator<const Ct> operator--(int)
356  {
357  mapping_iterator<const Ct> x(*this);
358  details::assign(node, node_dim,
359  decrement_mapping(node, node_dim, rank(),
360  _data.mapping_dim, key_comp()));
361  return x;
362  }
363 
365  key_compare
366  key_comp() const { return _data.key_comp(); }
367 
384  dimension_type
386  mapping_dimension() const { return _data.mapping_dim; }
387  dimension_type&
388  mapping_dimension() { return _data.mapping_dim; }
390 
391  private:
393  details::Mapping<Ct> _data;
394  };
395 
400  template <typename Container>
401  inline dimension_type
402  mapping_dimension(const mapping_iterator<Container>& it)
403  { return it.mapping_dimension(); }
404 
410  template <typename Container>
411  inline void
412  mapping_dimension(mapping_iterator<Container>& it,
413  dimension_type mapping_dim)
414  {
415  except::check_dimension(it.dimension(), mapping_dim);
416  it.mapping_dimension() = mapping_dim;
417  }
418 
441  template <typename Container>
443  inline mapping_iterator<Container>
444  mapping_end(Container& container, dimension_type mapping_dim)
445  {
446  except::check_dimension(container.dimension(), mapping_dim);
447  return mapping_iterator<Container>
448  (container, mapping_dim, container.dimension() - 1,
449  container.end().node); // At header (dim = rank - 1)
450  }
451 
452  template <typename Container>
453  inline mapping_iterator<const Container>
454  mapping_cend(const Container& container, dimension_type mapping_dim)
455  { return mapping_end(container, mapping_dim); }
457 
478  template <typename Container>
480  inline mapping_iterator<Container>
481  mapping_begin(Container& container, dimension_type mapping_dim)
482  {
483  if (container.empty()) return mapping_end(container, mapping_dim);
484  except::check_dimension(container.dimension(), mapping_dim);
485  typename mapping_iterator<Container>::node_ptr node
486  = container.end().node->parent;
487  dimension_type dim;
488  details::assign(node, dim,
489  minimum_mapping(node, 0,
490  container.rank(), mapping_dim,
491  container.key_comp()));
492  return mapping_iterator<Container>(container, mapping_dim, dim, node);
493  }
494 
495  template <typename Container>
496  inline mapping_iterator<const Container>
497  mapping_cbegin(const Container& container, dimension_type mapping_dim)
498  { return mapping_begin(container, mapping_dim); }
500 
507  template <typename Ct>
508  struct mapping_iterator_pair
509  : std::pair<mapping_iterator<Ct>, mapping_iterator<Ct> >
510  {
515  typedef std::pair<mapping_iterator<Ct>, mapping_iterator<Ct> > Base;
516 
518  mapping_iterator_pair() { }
519 
522  mapping_iterator_pair(const mapping_iterator<Ct>& a,
523  const mapping_iterator<Ct>& b) : Base(a, b) { }
524  };
525 
532  template <typename Ct>
533  struct mapping_iterator_pair<const Ct>
534  : std::pair<mapping_iterator<const Ct>, mapping_iterator<const Ct> >
535  {
540  typedef std::pair<mapping_iterator<const Ct>, mapping_iterator<const Ct> >
541  Base;
542 
544  mapping_iterator_pair() { }
545 
548  mapping_iterator_pair(const mapping_iterator<const Ct>& a,
549  const mapping_iterator<const Ct>& b) : Base(a, b)
550  { }
551 
554  mapping_iterator_pair(const mapping_iterator_pair<Ct>& p)
555  : Base(p.first, p.second) { }
556  };
557 
594  template <typename Container>
595  inline mapping_iterator_pair<Container>
596  mapping_range(Container& container, dimension_type mapping_dim)
597  {
598  return mapping_iterator_pair<Container>
599  (mapping_begin(container, mapping_dim),
600  mapping_end(container, mapping_dim));
601  }
602 
604 
634  template <typename Container>
635  inline mapping_iterator_pair<const Container>
636  mapping_range(const Container& container, dimension_type mapping_dim)
637  {
638  return mapping_iterator_pair<const Container>
639  (mapping_begin(container, mapping_dim),
640  mapping_end(container, mapping_dim));
641  }
642 
643  template <typename Container>
644  inline mapping_iterator_pair<const Container>
645  mapping_crange(const Container& container, dimension_type mapping_dim)
646  {
647  return mapping_iterator_pair<const Container>
648  (mapping_begin(container, mapping_dim),
649  mapping_end(container, mapping_dim));
650  }
652 
677  template <typename Container>
679  inline mapping_iterator<Container>
680  mapping_lower_bound(Container& container, dimension_type mapping_dim,
681  const typename container_traits<Container>::key_type&
682  bound)
683  {
684  if (container.empty()) return mapping_end(container, mapping_dim);
685  except::check_dimension(container.dimension(), mapping_dim);
686  typename mapping_iterator<Container>::node_ptr node
687  = container.end().node->parent;
688  dimension_type dim;
689  details::assign(node, dim,
690  lower_bound_mapping(node, 0, container.rank(), mapping_dim,
691  container.key_comp(), bound));
692  return mapping_iterator<Container>(container, mapping_dim, dim, node);
693  }
694 
695  template <typename Container>
696  inline mapping_iterator<const Container>
697  mapping_clower_bound
698  (const Container& container, dimension_type mapping_dim,
699  const typename container_traits<Container>::key_type& bound)
700  { return mapping_lower_bound(container, mapping_dim, bound); }
702 
727  template <typename Container>
729  inline mapping_iterator<Container>
730  mapping_upper_bound
731  (Container& container, dimension_type mapping_dim,
732  const typename container_traits<Container>::key_type& bound)
733  {
734  if (container.empty()) return mapping_end(container, mapping_dim);
735  except::check_dimension(container.dimension(), mapping_dim);
736  typename mapping_iterator<Container>::node_ptr node
737  = container.end().node->parent;
738  dimension_type dim;
739  details::assign(node, dim,
740  upper_bound_mapping(node, 0, container.rank(), mapping_dim,
741  container.key_comp(), bound));
742  return mapping_iterator<Container>(container, mapping_dim, dim, node);
743  }
744 
745  template <typename Container>
746  inline mapping_iterator<const Container>
747  mapping_cupper_bound
748  (const Container& container, dimension_type mapping_dim,
749  const typename container_traits<Container>::key_type& bound)
750  { return mapping_upper_bound(container, mapping_dim, bound); }
752 
753  namespace details
754  {
759  template <typename KeyCompare, typename Key>
761  inline bool
762  left_compare_mapping
763  (KeyCompare key_comp, dimension_type map, const Key& x, const Key& y,
764  strict_invariant_tag)
765  { return key_comp(map, x, y); }
766 
767  template <typename KeyCompare, typename Key>
768  inline bool
769  left_compare_mapping
770  (KeyCompare key_comp, dimension_type map, const Key& x, const Key& y,
771  relaxed_invariant_tag)
772  { return !key_comp(map, y, x); }
774 
800  template <typename NodePtr, typename Rank, typename KeyCompare>
801  inline std::pair<NodePtr, dimension_type>
802  increment_mapping
803  (NodePtr node, dimension_type dim, Rank rank, dimension_type map,
804  KeyCompare key_comp)
805  {
806  SPATIAL_ASSERT_CHECK(dim < rank());
807  SPATIAL_ASSERT_CHECK(!header(node));
808  NodePtr orig = node;
809  dimension_type orig_dim = dim;
810  NodePtr best = 0;
811  dimension_type best_dim = 0;
812  // Look forward to find an equal or greater next best
813  // If an equal next best is found, then no need to look further
814  for (;;)
815  {
816  if (node->right != 0
817  && (dim != map || best == 0
818  || key_comp(map, const_key(node), const_key(best))))
819  {
820  node = node->right; dim = incr_dim(rank, dim);
821  while (node->left != 0
822  && (dim != map
823  || left_compare_mapping
824  (key_comp, map, const_key(orig), const_key(node),
825  invariant_category(node))))
826  { node = node->left; dim = incr_dim(rank, dim); }
827  }
828  else
829  {
830  NodePtr prev_node = node;
831  node = node->parent; dim = decr_dim(rank, dim);
832  while (!header(node)
833  && prev_node == node->right)
834  {
835  prev_node = node;
836  node = node->parent; dim = decr_dim(rank, dim);
837  }
838  if (header(node)) break;
839  }
840  if (key_comp(map, const_key(orig), const_key(node)))
841  {
842  if (best == 0 || key_comp(map, const_key(node), const_key(best)))
843  { best = node; best_dim = dim; }
844  }
845  else if (!key_comp(map, const_key(node), const_key(orig)))
846  {
847  SPATIAL_ASSERT_CHECK(dim < rank());
848  SPATIAL_ASSERT_CHECK(!header(node));
849  return std::make_pair(node, dim);
850  }
851  }
852  SPATIAL_ASSERT_CHECK(dim == rank() - 1);
853  SPATIAL_ASSERT_CHECK(header(node));
854  // Maybe there is a better best looking backward...
855  node = orig;
856  dim = orig_dim;
857  for (;;)
858  {
859  if (node->left != 0
860  && (dim != map
861  || key_comp(map, const_key(orig), const_key(node))))
862  {
863  node = node->left; dim = incr_dim(rank, dim);
864  while (node->right != 0
865  && (dim != map || best == 0
866  || key_comp(map, const_key(node), const_key(best))))
867  { node = node->right; dim = incr_dim(rank, dim); }
868  }
869  else
870  {
871  NodePtr prev_node = node;
872  node = node->parent; dim = decr_dim(rank, dim);
873  while (!header(node)
874  && prev_node == node->left)
875  {
876  prev_node = node;
877  node = node->parent; dim = decr_dim(rank, dim);
878  }
879  if (header(node)) break;
880  }
881  if (key_comp(map, const_key(orig), const_key(node))
882  && (best == 0
883  || !key_comp(map, const_key(best), const_key(node))))
884  { best = node; best_dim = dim; }
885  }
886  if (best != 0)
887  { node = best; dim = best_dim; }
888  SPATIAL_ASSERT_CHECK(dim < rank());
889  SPATIAL_ASSERT_CHECK((best == 0 && header(node))
890  || (best != 0 && !header(node)));
891  return std::make_pair(node, dim);
892  }
893 
922  template <typename NodePtr, typename Rank, typename KeyCompare>
923  inline std::pair<NodePtr, dimension_type>
924  decrement_mapping
925  (NodePtr node, dimension_type dim, Rank rank, dimension_type map,
926  KeyCompare key_comp)
927  {
928  SPATIAL_ASSERT_CHECK(dim < rank());
929  if (header(node))
930  return maximum_mapping(node->parent, 0, rank, map, key_comp);
931  NodePtr orig = node;
932  dimension_type orig_dim = dim;
933  NodePtr best = 0;
934  dimension_type best_dim = 0;
935  // Look backward to find an equal or greater next best
936  // If an equal next best is found, then no need to look further
937  for (;;)
938  {
939  if (node->left != 0
940  && (dim != map || best == 0
941  || key_comp(map, const_key(best), const_key(node))))
942  {
943  node = node->left; dim = incr_dim(rank, dim);
944  while (node->right != 0
945  && (dim != map
946  || !key_comp(map, const_key(orig), const_key(node))))
947  { node = node->right; dim = incr_dim(rank, dim); }
948  }
949  else
950  {
951  NodePtr prev_node = node;
952  node = node->parent; dim = decr_dim(rank, dim);
953  while (!header(node)
954  && prev_node == node->left)
955  {
956  prev_node = node;
957  node = node->parent; dim = decr_dim(rank, dim);
958  }
959  if (header(node)) break;
960  }
961  if (key_comp(map, const_key(node), const_key(orig)))
962  {
963  if (best == 0 || key_comp(map, const_key(best), const_key(node)))
964  { best = node; best_dim = dim; }
965  }
966  else if (!key_comp(map, const_key(orig), const_key(node)))
967  {
968  SPATIAL_ASSERT_CHECK(dim < rank());
969  SPATIAL_ASSERT_CHECK(!header(node));
970  return std::make_pair(node, dim);
971  }
972  }
973  SPATIAL_ASSERT_CHECK(dim == rank() - 1);
974  SPATIAL_ASSERT_CHECK(header(node));
975  // Maybe there is a better best looking forward...
976  node = orig;
977  dim = orig_dim;
978  for (;;)
979  {
980  if (node->right != 0
981  && (dim != map
982  || key_comp(map, const_key(node), const_key(orig))))
983  {
984  node = node->right; dim = incr_dim(rank, dim);
985  while (node->left != 0
986  && (dim != map || best == 0
987  || key_comp(map, const_key(best), const_key(node))))
988  { node = node->left; dim = incr_dim(rank, dim); }
989  }
990  else
991  {
992  NodePtr prev_node = node;
993  node = node->parent; dim = decr_dim(rank, dim);
994  while (!header(node)
995  && prev_node == node->right)
996  {
997  prev_node = node;
998  node = node->parent; dim = decr_dim(rank, dim);
999  }
1000  if (header(node)) break;
1001  }
1002  if (key_comp(map, const_key(node), const_key(orig))
1003  && (best == 0
1004  || !key_comp(map, const_key(node), const_key(best))))
1005  { best = node; best_dim = dim; }
1006  }
1007  if (best != 0)
1008  { node = best; dim = best_dim; }
1009  SPATIAL_ASSERT_CHECK(dim < rank());
1010  SPATIAL_ASSERT_CHECK((best == 0 && header(node))
1011  || (best != 0 && !header(node)));
1012  return std::make_pair(node, dim);
1013  }
1014 
1043  template <typename NodePtr, typename Rank, typename KeyCompare,
1044  typename KeyType>
1045  inline std::pair<NodePtr, dimension_type>
1046  lower_bound_mapping
1047  (NodePtr node, dimension_type dim, Rank rank, dimension_type map,
1048  KeyCompare key_comp, const KeyType& bound)
1049  {
1050  SPATIAL_ASSERT_CHECK(map < rank());
1051  SPATIAL_ASSERT_CHECK(dim < rank());
1052  SPATIAL_ASSERT_CHECK(!header(node));
1053  while (node->left != 0
1054  && (dim != map
1055  || left_compare_mapping(key_comp, map, bound, const_key(node),
1056  invariant_category(node))))
1057  { node = node->left; dim = incr_dim(rank, dim); }
1058  NodePtr best = 0;
1059  dimension_type best_dim;
1060  if (!key_comp(map, const_key(node), bound))
1061  { best = node; best_dim = dim; }
1062  for (;;)
1063  {
1064  if (node->right != 0 && (dim != map || best == 0))
1065  {
1066  node = node->right;
1067  dim = incr_dim(rank, dim);
1068  while (node->left != 0
1069  && (dim != map
1070  || left_compare_mapping(key_comp, map, bound,
1071  const_key(node),
1072  invariant_category(node))))
1073  { node = node->left; dim = incr_dim(rank, dim); }
1074  }
1075  else
1076  {
1077  NodePtr prev_node = node;
1078  node = node->parent;
1079  dim = decr_dim(rank, dim);
1080  while (!header(node)
1081  && prev_node == node->right)
1082  {
1083  prev_node = node;
1084  node = node->parent; dim = decr_dim(rank, dim);
1085  }
1086  if (header(node)) break;
1087  }
1088  if (!key_comp(map, const_key(node), bound)
1089  && (best == 0 || key_comp(map, const_key(node), const_key(best))))
1090  { best = node; best_dim = dim; }
1091  }
1092  SPATIAL_ASSERT_CHECK(dim == rank() - 1);
1093  SPATIAL_ASSERT_CHECK(best != node);
1094  SPATIAL_ASSERT_CHECK(header(node));
1095  if (best == 0)
1096  { best = node; best_dim = dim; }
1097  return std::make_pair(best, best_dim);
1098  }
1099 
1128  template <typename NodePtr, typename Rank, typename KeyCompare,
1129  typename KeyType>
1130  inline std::pair<NodePtr, dimension_type>
1131  upper_bound_mapping
1132  (NodePtr node, dimension_type dim, Rank rank, dimension_type map,
1133  KeyCompare key_comp, const KeyType& bound)
1134  {
1135  SPATIAL_ASSERT_CHECK(map < rank());
1136  SPATIAL_ASSERT_CHECK(dim < rank());
1137  SPATIAL_ASSERT_CHECK(!header(node));
1138  while (node->left != 0
1139  && (dim != map
1140  || key_comp(map, bound, const_key(node))))
1141  { node = node->left; dim = incr_dim(rank, dim); }
1142  NodePtr best = 0;
1143  dimension_type best_dim;
1144  if (key_comp(map, bound, const_key(node)))
1145  { best = node; best_dim = dim; }
1146  for (;;)
1147  {
1148  if (node->right != 0 && (dim != map || best == 0))
1149  {
1150  node = node->right;
1151  dim = incr_dim(rank, dim);
1152  while (node->left != 0
1153  && (dim != map
1154  || key_comp(map, bound, const_key(node))))
1155  { node = node->left; dim = incr_dim(rank, dim); }
1156  }
1157  else
1158  {
1159  NodePtr prev_node = node;
1160  node = node->parent;
1161  dim = decr_dim(rank, dim);
1162  while (!header(node)
1163  && prev_node == node->right)
1164  {
1165  prev_node = node;
1166  node = node->parent; dim = decr_dim(rank, dim);
1167  }
1168  if (header(node)) break;
1169  }
1170  if (key_comp(map, bound, const_key(node))
1171  && (best == 0 || key_comp(map, const_key(node), const_key(best))))
1172  { best = node; best_dim = dim; }
1173  }
1174  SPATIAL_ASSERT_CHECK(dim == rank() - 1);
1175  SPATIAL_ASSERT_CHECK(best != node);
1176  SPATIAL_ASSERT_CHECK(header(node));
1177  if (best == 0)
1178  { best = node; best_dim = dim; }
1179  return std::make_pair(best, best_dim);
1180  }
1181 
1182  } // namespace details
1183 }
1184 
1185 #endif // SPATIAL_MAPPING_ITERATOR_HPP
spatial::mapping_iterator< const Ct >::_data
details::Mapping< Ct > _data
The related data for the iterator.
Definition: mapping_iterator.hpp:393
spatial::mapping_iterator::_data
details::Mapping< Ct > _data
The related data for the iterator.
Definition: mapping_iterator.hpp:229
spatial::mapping_iterator::mapping_dimension
dimension_type mapping_dimension() const
Accessor to the mapping dimension used by the iterator.
Definition: mapping_iterator.hpp:222
spatial::mapping_clower_bound
mapping_iterator< const Container > mapping_clower_bound(const Container &container, dimension_type mapping_dim, const typename container_traits< Container >::key_type &bound)
Finds the value with the smallest coordinate along the mapping dimension that is greater or equal to ...
Definition: mapping_iterator.hpp:698
spatial::mapping_iterator::mapping_iterator
mapping_iterator(Ct &container, dimension_type mapping_dim, dimension_type dim, typename container_traits< Ct >::mode_type::node_ptr ptr)
When the information of the dimension for the current node being pointed to by the iterator is known...
Definition: mapping_iterator.hpp:151
spatial::mapping_range
mapping_iterator_pair< Container > mapping_range(Container &container, dimension_type mapping_dim)
Returns a pair of iterator on the first and the last value in the range that can be iterated...
Definition: mapping_iterator.hpp:596
spatial::mapping_iterator::key_compare
container_traits< Ct >::key_compare key_compare
Definition: mapping_iterator.hpp:108
spatial::mapping_iterator< const Ct >::mapping_iterator
mapping_iterator(const Ct &container, dimension_type mapping_dim, typename container_traits< Ct >::const_iterator iter)
The standard way to build this iterator: specify a mapping dimension, an iterator on a container...
Definition: mapping_iterator.hpp:279
spatial::mapping_upper_bound
mapping_iterator< Container > mapping_upper_bound(Container &container, dimension_type mapping_dim, const typename container_traits< Container >::key_type &bound)
Finds the value with the largest coordinate along the mapping dimension that is stricly less than bou...
Definition: mapping_iterator.hpp:731
spatial::mapping_iterator_pair
This structure defines a pair of mutable mapping iterator.
Definition: mapping_iterator.hpp:508
spatial::details::Bidirectional_iterator::rank
const rank_type & rank() const
Return the current Rank type used by the iterator.
Definition: spatial_bidirectional.hpp:107
spatial::details::Mapping::mapping_dim
dimension_type mapping_dim
The current dimension of iteration.
Definition: mapping_iterator.hpp:75
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::decrement_mapping
std::pair< NodePtr, dimension_type > decrement_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
Move the pointer given in parameter to the previous element in the ordered iteration of values along ...
Definition: mapping_iterator.hpp:925
spatial::details::Bidirectional_iterator::node
node_ptr node
The pointer to the current node.
Definition: spatial_bidirectional.hpp:122
spatial::mapping_iterator::operator--
mapping_iterator< Ct > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: mapping_iterator.hpp:191
spatial::except::check_dimension
void check_dimension(dimension_type rank, dimension_type dimension)
Checks that dimension is not greater or equal to rank.
Definition: spatial_except.hpp:50
spatial::mapping_iterator
This iterator walks through all items in the container in order from the lowest to the highest value ...
Definition: mapping_iterator.hpp:93
spatial::mapping_cupper_bound
mapping_iterator< const Container > mapping_cupper_bound(const Container &container, dimension_type mapping_dim, const typename container_traits< Container >::key_type &bound)
Finds the value with the largest coordinate along the mapping dimension that is stricly less than bou...
Definition: mapping_iterator.hpp:748
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::dimension
dimension_type dimension() const
Return the number of dimensions stored by the Rank of the iterator.
Definition: spatial_bidirectional.hpp:112
spatial::mapping_iterator_pair::Base
std::pair< mapping_iterator< Ct >, mapping_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: mapping_iterator.hpp:515
spatial::mapping_iterator_pair< const Ct >::Base
std::pair< mapping_iterator< const Ct >, mapping_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: mapping_iterator.hpp:541
spatial::mapping_crange
mapping_iterator_pair< const Container > mapping_crange(const Container &container, dimension_type mapping_dim)
Returns a pair of constant iterator on the first and the last value in the range that can be iterated...
Definition: mapping_iterator.hpp:645
spatial::mapping_iterator< const Ct >::mapping_dimension
dimension_type mapping_dimension() const
Accessor to the mapping dimension used by the iterator.
Definition: mapping_iterator.hpp:386
spatial::mapping_end
mapping_iterator< Container > mapping_end(Container &container, dimension_type mapping_dim)
Finds the past-the-end position in container for this constant iterator.
Definition: mapping_iterator.hpp:444
spatial::mapping_iterator::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: mapping_iterator.hpp:202
spatial::container_traits::key_type
Tp::key_type key_type
The type representing the key managed by the container.
Definition: traits.hpp:48
spatial::mapping_iterator< const Ct >::operator--
mapping_iterator< const Ct > & operator--()
Decrements the iterator and returns the decremented value.
Definition: mapping_iterator.hpp:345
spatial::mapping_iterator< const Ct >::key_compare
container_traits< Ct >::key_compare key_compare
Alias for the key_compare type used by the iterator.
Definition: mapping_iterator.hpp:264
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::mapping_iterator< const Ct >::mapping_iterator
mapping_iterator()
Build an uninitialized iterator.
Definition: mapping_iterator.hpp:267
spatial::details::Bidirectional_iterator::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::mapping_iterator< const Ct >::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: mapping_iterator.hpp:366
spatial::details::Mapping::key_comp
Container::key_compare key_comp() const
Definition: mapping_iterator.hpp:59
spatial::details::lower_bound_mapping
std::pair< NodePtr, dimension_type > lower_bound_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp, const KeyType &bound)
Move the iterator given in parameter to the value with the smallest coordinate greater or equal to bo...
Definition: mapping_iterator.hpp:1047
spatial::mapping_iterator_pair< const Ct >::mapping_iterator_pair
mapping_iterator_pair(const mapping_iterator_pair< Ct > &p)
Convert a mutable mapping iterator pair into a const mapping iterator pair.
Definition: mapping_iterator.hpp:554
spatial::mapping_iterator< const Ct >::Base
details::Const_bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: mapping_iterator.hpp:256
spatial::mapping_cbegin
mapping_iterator< const Container > mapping_cbegin(const Container &container, dimension_type mapping_dim)
Finds the value in container for which its key has the smallest coordinate over the dimension mapping...
Definition: mapping_iterator.hpp:497
spatial::mapping_lower_bound
mapping_iterator< Container > mapping_lower_bound(Container &container, dimension_type mapping_dim, const typename container_traits< Container >::key_type &bound)
Finds the value with the smallest coordinate along the mapping dimension that is greater or equal to ...
Definition: mapping_iterator.hpp:680
spatial::mapping_iterator::operator++
mapping_iterator< Ct > & operator++()
Increments the iterator and returns the incremented value.
Definition: mapping_iterator.hpp:160
spatial::mapping_iterator< const Ct >::operator++
mapping_iterator< const Ct > & operator++()
Increments the iterator and returns the incremented value.
Definition: mapping_iterator.hpp:324
spatial::mapping_iterator::operator--
mapping_iterator< Ct > & operator--()
Decrements the iterator and returns the decremented value.
Definition: mapping_iterator.hpp:181
spatial::container_traits
The traits type for all containers in the spatial namespace.
Definition: traits.hpp:42
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::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::mapping_iterator_pair< const Ct >::mapping_iterator_pair
mapping_iterator_pair()
Empty constructor.
Definition: mapping_iterator.hpp:544
spatial::mapping_iterator< const Ct >::operator--
mapping_iterator< const Ct > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: mapping_iterator.hpp:355
spatial::details::strict_invariant_tag
Definition: spatial_node.hpp:221
spatial::mapping_iterator< const Ct >::mapping_dimension
dimension_type & mapping_dimension()
Accessor to the mapping dimension used by the iterator.
Definition: mapping_iterator.hpp:388
spatial::mapping_iterator_pair< const Ct >::mapping_iterator_pair
mapping_iterator_pair(const mapping_iterator< const Ct > &a, const mapping_iterator< const Ct > &b)
Regular constructor that builds a mapping_iterator_pair out of 2 mapping_iterators.
Definition: mapping_iterator.hpp:548
spatial::details::relaxed_invariant_tag
The category of invariants for a k-d tree node: strict or relaxed.
Definition: spatial_node.hpp:220
spatial::details::assign
void assign(Type1 &first, Type2 &second, const std::pair< Type1, Type2 > &pair)
Definition: spatial_assign.hpp:26
spatial::mapping_iterator::Base
details::Bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: mapping_iterator.hpp:101
spatial::details::maximum_mapping
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 ...
Definition: spatial_mapping.hpp:130
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::details::upper_bound_mapping
std::pair< NodePtr, dimension_type > upper_bound_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp, const KeyType &bound)
Move the iterator given in parameter to the value with the largest coordinate strictly lower than bou...
Definition: mapping_iterator.hpp:1132
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::mapping_iterator_pair::mapping_iterator_pair
mapping_iterator_pair(const mapping_iterator< Ct > &a, const mapping_iterator< Ct > &b)
Regular constructor that builds a mapping_iterator_pair out of 2 mapping_iterators.
Definition: mapping_iterator.hpp:522
spatial::mapping_iterator< const Ct >::mapping_iterator
mapping_iterator(const mapping_iterator< Ct > &iter)
Convertion of mutable iterator into a constant iterator is permitted.
Definition: mapping_iterator.hpp:318
spatial::mapping_iterator::mapping_iterator
mapping_iterator(Ct &container, dimension_type mapping_dim, typename container_traits< Ct >::iterator iter)
The standard way to build this iterator: specify a mapping dimension, an iterator on a container...
Definition: mapping_iterator.hpp:123
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::increment_mapping
std::pair< NodePtr, dimension_type > increment_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
Move the pointer given in parameter to the next element in the ordered iteration of values along the ...
Definition: mapping_iterator.hpp:803
spatial::details::Bidirectional_iterator
A common template for bidirectional iterators that work on identical modes of linking.
Definition: spatial_bidirectional.hpp:33
spatial::details::left_compare_mapping
bool left_compare_mapping(KeyCompare key_comp, dimension_type map, const Key &x, const Key &y, strict_invariant_tag)
This function provides a common interface for the two k-d tree invariants.
Definition: mapping_iterator.hpp:763
spatial::details::Mapping::Mapping
Mapping()
Build an uninitialized mapping data object.
Definition: mapping_iterator.hpp:45
spatial::details::Mapping
Extra information needed by the iterator to perform its work.
Definition: mapping_iterator.hpp:42
spatial::mapping_iterator_pair::mapping_iterator_pair
mapping_iterator_pair()
Empty constructor.
Definition: mapping_iterator.hpp:518
spatial::mapping_iterator< const Ct >::operator++
mapping_iterator< const Ct > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: mapping_iterator.hpp:334
spatial::mapping_begin
mapping_iterator< Container > mapping_begin(Container &container, dimension_type mapping_dim)
Finds the value in container for which its key has the smallest coordinate over the dimension mapping...
Definition: mapping_iterator.hpp:481
spatial::mapping_iterator::mapping_iterator
mapping_iterator()
Uninitialized iterator.
Definition: mapping_iterator.hpp:111
spatial::mapping_iterator< const Ct >
This iterator walks through all items in the container in order from the lowest to the highest value ...
Definition: mapping_iterator.hpp:248
spatial::mapping_iterator::operator++
mapping_iterator< Ct > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: mapping_iterator.hpp:170
spatial::mapping_dimension
dimension_type mapping_dimension(const mapping_iterator< Container > &it)
Return the mapping dimension of the iterator.
Definition: mapping_iterator.hpp:402
spatial::mapping_iterator::mapping_dimension
dimension_type & mapping_dimension()
Accessor to the mapping dimension used by the iterator.
Definition: mapping_iterator.hpp:224
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::mapping_cend
mapping_iterator< const Container > mapping_cend(const Container &container, dimension_type mapping_dim)
Finds the past-the-end position in container for this constant iterator.
Definition: mapping_iterator.hpp:454