Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_neighbor.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_NEIGHBOR_HPP
14 #define SPATIAL_NEIGHBOR_HPP
15 
16 #include <limits> // numeric_limits min() and max()
17 
18 #include "spatial_import_tuple.hpp"
19 #include "../metric.hpp"
20 #include "../traits.hpp"
21 #include "spatial_bidirectional.hpp"
22 
23 namespace spatial
24 {
25  namespace details
26  {
41  template<typename Ct, typename Metric>
42  struct Neighbor_data : container_traits<Ct>::key_compare
43  {
45  Neighbor_data() { }
46 
57  Neighbor_data
58  (const typename container_traits<Ct>::key_compare& container,
59  const Metric& metric,
60  const typename container_traits<Ct>::key_type& key,
61  typename Metric::distance_type distance)
62  : container_traits<Ct>::key_compare(container), _target(metric, key),
63  _distance(distance) { }
64 
69  Compress<Metric, typename container_traits<Ct>::key_type> _target;
70 
75  typename Metric::distance_type _distance;
76  };
77  } // namespace details
78 
111  template <typename Ct, typename Metric =
112  euclidian<typename details::mutate<Ct>::type,
113  double,
114  typename details::with_builtin_difference<Ct>::type> >
115  class neighbor_iterator
116  : public details::Bidirectional_iterator
117  <typename container_traits<Ct>::mode_type,
118  typename container_traits<Ct>::rank_type>
119  {
120  private:
121  typedef typename details::Bidirectional_iterator
122  <typename container_traits<Ct>::mode_type,
123  typename container_traits<Ct>::rank_type> Base;
124 
125  public:
126  using Base::node;
127  using Base::node_dim;
128  using Base::rank;
129 
131  typedef typename container_traits<Ct>::key_compare key_compare;
132 
134  typedef Metric metric_type;
135 
137  typedef typename Metric::distance_type distance_type;
138 
140  typedef typename container_traits<Ct>::key_type key_type;
141 
143  neighbor_iterator() { }
144 
156  neighbor_iterator
157  (Ct& container_, const Metric& metric_,
158  const typename container_traits<Ct>::key_type& target_,
159  const typename container_traits<Ct>::iterator& iter_,
160  typename Metric::distance_type distance_)
161  : Base(container_.rank(), iter_.node,
162  modulo(iter_.node, container_.rank())),
163  _data(container_.key_comp(), metric_, target_, distance_) { }
164 
189  neighbor_iterator
190  (Ct& container_, const Metric& metric_,
191  const typename container_traits<Ct>::key_type& target_,
192  dimension_type node_dim_,
193  typename container_traits<Ct>::mode_type::node_ptr node_,
194  typename Metric::distance_type distance_)
195  : Base(container_.rank(), node_, node_dim_),
196  _data(container_.key_comp(), metric_, target_, distance_) { }
197 
222  neighbor_iterator
223  (const typename container_traits<Ct>::rank_type& rank_,
224  const typename container_traits<Ct>::key_compare& key_comp_,
225  const Metric& metric_,
226  const typename container_traits<Ct>::key_type& target_,
227  dimension_type node_dim_,
228  typename container_traits<Ct>::mode_type::node_ptr node_,
229  typename Metric::distance_type distance_)
230  : Base(rank_, node_, node_dim_),
231  _data(key_comp_, metric_, target_, distance_) { }
232 
235  neighbor_iterator<Ct, Metric>& operator++()
236  {
237  import::tie(node, node_dim, distance())
238  = increment_neighbor(node, node_dim, rank(), key_comp(),
239  metric(), target_key(), distance());
240  return *this;
241  }
242 
245  neighbor_iterator<Ct, Metric> operator++(int)
246  {
247  neighbor_iterator<Ct, Metric> x(*this);
248  import::tie(node, node_dim, distance())
249  = increment_neighbor(node, node_dim, rank(), key_comp(),
250  metric(), target_key(), distance());
251  return x;
252  }
253 
256  neighbor_iterator<Ct, Metric>& operator--()
257  {
258  import::tie(node, node_dim, distance())
259  = decrement_neighbor(node, node_dim, rank(), key_comp(),
260  metric(), target_key(), distance());
261  return *this;
262  }
263 
266  neighbor_iterator<Ct, Metric> operator--(int)
267  {
268  neighbor_iterator<Ct, Metric> x(*this);
269  import::tie(node, node_dim, distance())
270  = decrement_neighbor(node, node_dim, rank(), key_comp(),
271  metric(), target_key(), distance());
272  return x;
273  }
274 
276  key_compare
277  key_comp() const { return static_cast<const key_compare&>(_data); }
278 
280  metric_type
281  metric() const { return _data._target.base(); }
282 
284  const distance_type&
285  distance() const { return _data._distance; }
286 
288  distance_type&
289  distance() { return _data._distance; }
290 
292  const key_type&
293  target_key() const { return _data._target(); }
294 
296  key_type&
297  target_key() { return _data._target(); }
298 
299  private:
301  details::Neighbor_data<Ct, Metric> _data;
302  };
303 
339  template<typename Ct, typename Metric>
340  class neighbor_iterator<const Ct, Metric>
341  : public details::Const_bidirectional_iterator
342  <typename container_traits<Ct>::mode_type,
343  typename container_traits<Ct>::rank_type>
344  {
345  private:
346  typedef typename details::Const_bidirectional_iterator
347  <typename container_traits<Ct>::mode_type,
348  typename container_traits<Ct>::rank_type> Base;
349 
350  public:
351  using Base::node;
352  using Base::node_dim;
353  using Base::rank;
354 
356  typedef typename container_traits<Ct>::key_compare key_compare;
357 
359  typedef Metric metric_type;
360 
362  typedef typename Metric::distance_type distance_type;
363 
365  typedef typename container_traits<Ct>::key_type key_type;
366 
368  neighbor_iterator() { }
369 
381  neighbor_iterator
382  (const Ct& container_, const Metric& metric_,
383  const typename container_traits<Ct>::key_type& target_,
384  typename container_traits<Ct>::const_iterator iter_,
385  typename Metric::distance_type distance_)
386  : Base(container_.rank(), iter_.node,
387  modulo(iter_.node, container_.rank())),
388  _data(container_.key_comp(), metric_, target_, distance_) { }
389 
414  neighbor_iterator
415  (const Ct& container_, const Metric& metric_,
416  const typename container_traits<Ct>::key_type& target_,
417  dimension_type node_dim_,
418  typename container_traits<Ct>::mode_type::const_node_ptr node_,
419  typename Metric::distance_type distance_)
420  : Base(container_.rank(), node_, node_dim_),
421  _data(container_.key_comp(), metric_, target_, distance_) { }
422 
443  neighbor_iterator
444  (const typename container_traits<Ct>::rank_type& rank_,
445  const typename container_traits<Ct>::key_compare& key_comp_,
446  const Metric& metric_,
447  const typename container_traits<Ct>::key_type& target_,
448  dimension_type node_dim_,
449  typename container_traits<Ct>::mode_type::const_node_ptr node_,
450  typename Metric::distance_type distance_)
451  : Base(rank_, node_, node_dim_),
452  _data(key_comp_, metric_, target_, distance_) { }
453 
455  neighbor_iterator(const neighbor_iterator<Ct, Metric>& iter)
456  : Base(iter.rank(), iter.node, iter.node_dim),
457  _data(iter.key_comp(), iter.metric(),
458  iter.target_key(), iter.distance()) { }
459 
462  neighbor_iterator<const Ct, Metric>& operator++()
463  {
464  import::tie(node, node_dim, distance())
465  = increment_neighbor(node, node_dim, rank(), key_comp(),
466  metric(), target_key(), distance());
467  return *this;
468  }
469 
472  neighbor_iterator<const Ct, Metric> operator++(int)
473  {
474  neighbor_iterator<const Ct, Metric> x(*this);
475  import::tie(node, node_dim, distance())
476  = increment_neighbor(node, node_dim, rank(), key_comp(),
477  metric(), target_key(), distance());
478  return x;
479  }
480 
483  neighbor_iterator<const Ct, Metric>& operator--()
484  {
485  import::tie(node, node_dim, distance())
486  = decrement_neighbor(node, node_dim, rank(), key_comp(),
487  metric(), target_key(), distance());
488  return *this;
489  }
490 
493  neighbor_iterator<const Ct, Metric> operator--(int)
494  {
495  neighbor_iterator<const Ct, Metric> x(*this);
496  import::tie(node, node_dim, distance())
497  = decrement_neighbor(node, node_dim, rank(), key_comp(),
498  metric(), target_key(), distance());
499  return x;
500  }
501 
503  key_compare
504  key_comp() const { return static_cast<const key_compare&>(_data); }
505 
507  metric_type
508  metric() const { return _data._target.base(); }
509 
511  distance_type
512  distance() const { return _data._distance; }
513 
515  distance_type&
516  distance() { return _data._distance; }
517 
519  const key_type&
520  target_key() const { return _data._target(); }
521 
523  key_type&
524  target_key() { return _data._target(); }
525 
526  private:
528  details::Neighbor_data<Ct, Metric> _data;
529  };
530 
536  template <typename Ct, typename Metric>
538  inline typename Metric::distance_type
539  distance(const neighbor_iterator<Ct, Metric>& iter)
540  { return iter.distance(); }
541 
542  template <typename Ct, typename Metric>
543  inline void
544  distance(neighbor_iterator<Ct, Metric>& iter,
545  const typename Metric::distance_type& distance)
546  { iter.distance() = distance; }
548 
553  template <typename Ct, typename Metric>
554  inline const typename container_traits<Ct>::key_type&
555  target_key(const neighbor_iterator<Ct, Metric>& iter)
556  { return iter.target_key(); }
557 
565  template <typename Ct, typename Metric
566  = euclidian<typename details::mutate<Ct>::type,
567  double, typename details::with_builtin_difference<Ct>
568  ::type> >
569  struct neighbor_iterator_pair
570  : std::pair<neighbor_iterator<Ct, Metric>,
571  neighbor_iterator<Ct, Metric> >
572  {
577  typedef std::pair<neighbor_iterator<Ct, Metric>,
578  neighbor_iterator<Ct, Metric> > Base;
579 
581  neighbor_iterator_pair() { }
582 
585  neighbor_iterator_pair(const neighbor_iterator<Ct, Metric>& a,
586  const neighbor_iterator<Ct, Metric>& b)
587  : Base(a, b) { }
588  };
589 
597  template <typename Ct, typename Metric>
598  struct neighbor_iterator_pair<const Ct, Metric>
599  : std::pair<neighbor_iterator<const Ct, Metric>,
600  neighbor_iterator<const Ct, Metric> >
601  {
606  typedef std::pair<neighbor_iterator<const Ct, Metric>,
607  neighbor_iterator<const Ct, Metric> > Base;
608 
610  neighbor_iterator_pair() { }
611 
614  neighbor_iterator_pair(const neighbor_iterator<const Ct, Metric>& a,
615  const neighbor_iterator<const Ct, Metric>& b)
616  : Base(a, b)
617  { }
618 
621  neighbor_iterator_pair(const neighbor_iterator_pair<Ct, Metric>& p)
622  : Base(p.first, p.second) { }
623  };
624 
631  template <typename Ct, typename Metric>
633  inline neighbor_iterator<Ct, Metric>
634  neighbor_end(Ct& container, const Metric& metric,
635  const typename container_traits<Ct>::key_type& target)
636  {
637  return neighbor_iterator<Ct, Metric>
638  (container, metric, target, container.dimension() - 1,
639  container.end().node, typename Metric::distance_type());
640  }
641 
642  template <typename Ct, typename Metric>
643  inline neighbor_iterator<const Ct, Metric>
644  neighbor_end(const Ct& container, const Metric& metric,
645  const typename container_traits<Ct>::key_type& target)
646  {
647  return neighbor_iterator<const Ct, Metric>
648  (container, metric, target, container.dimension() - 1,
649  container.end().node, typename Metric::distance_type());
650  }
651 
652  template <typename Ct, typename Metric>
653  inline neighbor_iterator<const Ct, Metric>
654  neighbor_cend(const Ct& container, const Metric& metric,
655  const typename container_traits<Ct>::key_type& target)
656  {
657  return neighbor_end(container, metric, target,
658  typename Metric::distance_type());
659  }
661 
669  template <typename Ct>
671  inline typename enable_if<details::is_compare_builtin<Ct>,
672  neighbor_iterator<Ct> >::type
673  neighbor_end(Ct& container,
674  const typename container_traits<Ct>::key_type& target)
675  {
676  return neighbor_end
677  (container,
678  euclidian<Ct, double,
679  typename details::with_builtin_difference<Ct>::type>
680  (details::with_builtin_difference<Ct>()(container)),
681  target);
682  }
683 
684  template <typename Ct>
685  inline typename enable_if<details::is_compare_builtin<Ct>,
686  neighbor_iterator<const Ct> >::type
687  neighbor_end(const Ct& container,
688  const typename container_traits<Ct>::key_type& target)
689  {
690  return neighbor_end
691  (container,
692  euclidian<Ct, double,
693  typename details::with_builtin_difference<Ct>::type>
694  (details::with_builtin_difference<Ct>()(container)),
695  target);
696  }
697 
698  template <typename Ct>
699  inline typename enable_if<details::is_compare_builtin<Ct>,
700  neighbor_iterator<const Ct> >::type
701  neighbor_cend(const Ct& container,
702  const typename container_traits<Ct>::key_type& target)
703  {
704  return neighbor_end
705  (container,
706  euclidian<Ct, double,
707  typename details::with_builtin_difference<Ct>::type>
708  (details::with_builtin_difference<Ct>()(container)),
709  target);
710  }
712 
720  template <typename Ct, typename Metric>
722  inline neighbor_iterator<Ct, Metric>
723  neighbor_begin(Ct& container, const Metric& metric,
724  const typename container_traits<Ct>::key_type& target)
725  {
726  if (container.empty()) return neighbor_end(container, metric, target);
727  typename Ct::mode_type::node_ptr node = container.end().node->parent;
728  dimension_type dim = 0;
729  typename Metric::distance_type dist;
730  import::tie(node, dim, dist)
731  = first_neighbor(node, dim, container.rank(), container.key_comp(),
732  metric, target);
733  return neighbor_iterator<Ct, Metric>(container, metric, target,
734  dim, node, dist);
735  }
736 
737  template <typename Ct, typename Metric>
738  inline neighbor_iterator<const Ct, Metric>
739  neighbor_begin(const Ct& container, const Metric& metric,
740  const typename container_traits<Ct>::key_type& target)
741  {
742  if (container.empty()) return neighbor_end(container, metric, target);
743  typename Ct::mode_type::const_node_ptr node = container.end().node->parent;
744  dimension_type dim = 0;
745  typename Metric::distance_type dist;
746  import::tie(node, dim, dist)
747  = first_neighbor(node, dim, container.rank(), container.key_comp(),
748  metric, target);
749  return neighbor_iterator<const Ct, Metric>(container, metric, target,
750  dim, node, dist);
751  }
752 
753  template <typename Ct, typename Metric>
754  inline neighbor_iterator<const Ct, Metric>
755  neighbor_cbegin(const Ct& container, const Metric& metric,
756  const typename container_traits<Ct>::key_type& target)
757  { return neighbor_begin(container, metric, target); }
759 
768  template <typename Ct>
770  inline typename enable_if<details::is_compare_builtin<Ct>,
771  neighbor_iterator<Ct> >::type
772  neighbor_begin(Ct& container,
773  const typename container_traits<Ct>::key_type& target)
774  {
775  return neighbor_begin
776  (container,
777  euclidian<Ct, double,
778  typename details::with_builtin_difference<Ct>::type>
779  (details::with_builtin_difference<Ct>()(container)),
780  target);
781  }
782 
783  template <typename Ct>
784  inline typename enable_if<details::is_compare_builtin<Ct>,
785  neighbor_iterator<const Ct> >::type
786  neighbor_begin(const Ct& container,
787  const typename container_traits<Ct>::key_type& target)
788  {
789  return neighbor_begin
790  (container,
791  euclidian<Ct, double,
792  typename details::with_builtin_difference<Ct>::type>
793  (details::with_builtin_difference<Ct>()(container)),
794  target);
795  }
796 
797  template <typename Ct>
798  inline typename enable_if<details::is_compare_builtin<Ct>,
799  neighbor_iterator<const Ct> >::type
800  neighbor_cbegin(const Ct& container,
801  const typename container_traits<Ct>::key_type& target)
802  {
803  return neighbor_begin
804  (container,
805  euclidian<Ct, double,
806  typename details::with_builtin_difference<Ct>::type>
807  (details::with_builtin_difference<Ct>()(container)),
808  target);
809  }
811 
822  template <typename Ct, typename Metric>
824  inline neighbor_iterator<Ct, Metric>
825  neighbor_lower_bound(Ct& container, const Metric& metric,
826  const typename container_traits<Ct>::key_type& target,
827  typename Metric::distance_type bound)
828  {
829  if (container.empty()) return neighbor_end(container, metric, target);
830  typename Ct::mode_type::node_ptr node = container.end().node->parent;
831  dimension_type dim = 0;
832  typename Metric::distance_type dist;
833  import::tie(node, dim, dist)
834  = lower_bound_neighbor(node, dim, container.rank(), container.key_comp(),
835  metric, target, bound);
836  return neighbor_iterator<Ct, Metric>(container, metric, target,
837  dim, node, dist);
838  }
839 
840  template <typename Ct, typename Metric>
841  inline neighbor_iterator<const Ct, Metric>
842  neighbor_lower_bound(const Ct& container, const Metric& metric,
843  const typename container_traits<Ct>::key_type& target,
844  typename Metric::distance_type bound)
845  {
846  if (container.empty()) return neighbor_end(container, metric, target);
847  typename Ct::mode_type::const_node_ptr node = container.end().node->parent;
848  dimension_type dim = 0;
849  typename Metric::distance_type dist;
850  import::tie(node, dim, dist)
851  = lower_bound_neighbor(node, dim, container.rank(), container.key_comp(),
852  metric, target, bound);
853  return neighbor_iterator<const Ct, Metric>(container, metric, target,
854  dim, node, dist);
855  }
856 
857  template <typename Ct, typename Metric>
858  inline neighbor_iterator<const Ct, Metric>
859  neighbor_clower_bound(const Ct& container, const Metric& metric,
860  const typename container_traits<Ct>::key_type& target,
861  typename Metric::distance_type bound)
862  { return neighbor_lower_bound(container, metric, target, bound); }
864 
876  template <typename Ct>
878  inline typename enable_if<details::is_compare_builtin<Ct>,
879  neighbor_iterator<Ct> >::type
880  neighbor_lower_bound(Ct& container,
881  const typename container_traits<Ct>::key_type& target,
882  double bound)
883  {
884  return neighbor_lower_bound
885  (container,
886  euclidian<Ct, double,
887  typename details::with_builtin_difference<Ct>::type>
888  (details::with_builtin_difference<Ct>()(container)),
889  target, bound);
890  }
891 
892  template <typename Ct>
893  inline typename enable_if<details::is_compare_builtin<Ct>,
894  neighbor_iterator<const Ct> >::type
895  neighbor_lower_bound(const Ct& container,
896  const typename container_traits<Ct>::key_type& target,
897  double bound)
898  {
899  return neighbor_lower_bound
900  (container,
901  euclidian<Ct, double,
902  typename details::with_builtin_difference<Ct>::type>
903  (details::with_builtin_difference<Ct>()(container)),
904  target, bound);
905  }
906 
907  template <typename Ct>
908  inline typename enable_if<details::is_compare_builtin<Ct>,
909  neighbor_iterator<const Ct> >::type
910  neighbor_clower_bound(const Ct& container,
911  const typename container_traits<Ct>::key_type& target,
912  double bound)
913  {
914  return neighbor_lower_bound
915  (container,
916  euclidian<Ct, double,
917  typename details::with_builtin_difference<Ct>::type>
918  (details::with_builtin_difference<Ct>()(container)),
919  target, bound);
920  }
922 
933  template <typename Ct, typename Metric>
935  inline neighbor_iterator<Ct, Metric>
936  neighbor_upper_bound(Ct& container, const Metric& metric,
937  const typename container_traits<Ct>::key_type& target,
938  typename Metric::distance_type bound)
939  {
940  if (container.empty()) return neighbor_end(container, metric, target);
941  typename Ct::mode_type::node_ptr node = container.end().node->parent;
942  dimension_type dim = 0;
943  typename Metric::distance_type dist;
944  import::tie(node, dim, dist)
945  = upper_bound_neighbor(node, dim, container.rank(), container.key_comp(),
946  metric, target, bound);
947  return neighbor_iterator<Ct, Metric>(container, metric, target, dim,
948  node, dist);
949  }
950 
951  template <typename Ct, typename Metric>
952  inline neighbor_iterator<const Ct, Metric>
953  neighbor_upper_bound(const Ct& container, const Metric& metric,
954  const typename container_traits<Ct>::key_type& target,
955  typename Metric::distance_type bound)
956  {
957  if (container.empty()) return neighbor_end(container, metric, target);
958  typename Ct::mode_type::const_node_ptr node = container.end().node->parent;
959  dimension_type dim = 0;
960  typename Metric::distance_type dist;
961  import::tie(node, dim, dist)
962  = upper_bound_neighbor(node, dim, container.rank(), container.key_comp(),
963  metric, target, bound);
964  return neighbor_iterator<const Ct, Metric>(container, metric, target,
965  dim, node, dist);
966  }
967 
968  template <typename Ct, typename Metric>
969  inline neighbor_iterator<const Ct, Metric>
970  neighbor_cupper_bound(const Ct& container, const Metric& metric,
971  const typename container_traits<Ct>::key_type& target,
972  typename Metric::distance_type bound)
973  { return neighbor_upper_bound(container, metric, target, bound); }
975 
987  template <typename Ct>
989  inline typename enable_if<details::is_compare_builtin<Ct>,
990  neighbor_iterator<Ct> >::type
991  neighbor_upper_bound(Ct& container,
992  const typename container_traits<Ct>::key_type& target,
993  double bound)
994  {
995  return neighbor_upper_bound
996  (container,
997  euclidian<Ct, double,
998  typename details::with_builtin_difference<Ct>::type>
999  (details::with_builtin_difference<Ct>()(container)),
1000  target, bound);
1001  }
1002 
1003  template <typename Ct>
1004  inline typename enable_if<details::is_compare_builtin<Ct>,
1005  neighbor_iterator<const Ct> >::type
1006  neighbor_upper_bound(const Ct& container,
1007  const typename container_traits<Ct>::key_type& target,
1008  double bound)
1009  {
1010  return neighbor_upper_bound
1011  (container,
1012  euclidian<Ct, double,
1013  typename details::with_builtin_difference<Ct>::type>
1014  (details::with_builtin_difference<Ct>()(container)),
1015  target, bound);
1016  }
1017 
1018  template <typename Ct>
1019  inline typename enable_if<details::is_compare_builtin<Ct>,
1020  neighbor_iterator<const Ct> >::type
1021  neighbor_cupper_bound(const Ct& container,
1022  const typename container_traits<Ct>::key_type& target,
1023  double bound)
1024  {
1025  return neighbor_upper_bound
1026  (container,
1027  euclidian<Ct, double,
1028  typename details::with_builtin_difference<Ct>::type>
1029  (details::with_builtin_difference<Ct>()(container)),
1030  target, bound);
1031  }
1033 
1043  template <typename Ct, typename Metric>
1045  inline neighbor_iterator_pair<Ct, Metric>
1046  neighbor_range(Ct& container, const Metric& metric,
1047  const typename container_traits<Ct>::key_type& target)
1048  {
1049  return neighbor_iterator_pair<Ct, Metric>
1050  (neighbor_begin(container, metric, target),
1051  neighbor_end(container, metric, target));
1052  }
1053 
1054  template <typename Ct, typename Metric>
1055  inline neighbor_iterator_pair<const Ct, Metric>
1056  neighbor_range(const Ct& container, const Metric& metric,
1057  const typename container_traits<Ct>::key_type& target)
1058  {
1059  return neighbor_iterator_pair<const Ct, Metric>
1060  (neighbor_begin(container, metric, target),
1061  neighbor_end(container, metric, target));
1062  }
1063 
1064  template <typename Ct, typename Metric>
1065  inline neighbor_iterator_pair<const Ct, Metric>
1066  neighbor_crange(const Ct& container, const Metric& metric,
1067  const typename container_traits<Ct>::key_type& target)
1068  {
1069  return neighbor_iterator_pair<const Ct, Metric>
1070  (neighbor_begin(container, metric, target),
1071  neighbor_end(container, metric, target));
1072  }
1074 
1085  template <typename Ct>
1087  inline typename enable_if<details::is_compare_builtin<Ct>,
1088  neighbor_iterator_pair<Ct> >::type
1089  neighbor_range(Ct& container,
1090  const typename container_traits<Ct>::key_type& target)
1091  {
1092  return neighbor_iterator_pair<Ct>
1093  (neighbor_begin(container, target), neighbor_end(container, target));
1094  }
1095 
1096  template <typename Ct>
1097  inline typename enable_if<details::is_compare_builtin<Ct>,
1098  neighbor_iterator_pair<const Ct> >::type
1099  neighbor_range(const Ct& container,
1100  const typename container_traits<Ct>::key_type& target)
1101  {
1102  return neighbor_iterator_pair<const Ct>
1103  (neighbor_begin(container, target), neighbor_end(container, target));
1104  }
1105 
1106  template <typename Ct>
1107  inline typename enable_if<details::is_compare_builtin<Ct>,
1108  neighbor_iterator_pair<const Ct> >::type
1109  neighbor_crange(const Ct& container,
1110  const typename container_traits<Ct>::key_type& target)
1111  {
1112  return neighbor_iterator_pair<const Ct>
1113  (neighbor_begin(container, target), neighbor_end(container, target));
1114  }
1116 
1117  namespace details
1118  {
1119  template <typename NodePtr, typename Rank, typename KeyCompare,
1120  typename Key, typename Metric>
1121  inline import::tuple<NodePtr, dimension_type,
1122  typename Metric::distance_type>
1123  last_neighbor_sub(NodePtr node, dimension_type dim, Rank rank,
1124  KeyCompare key_comp, const Metric& met, const Key& target,
1125  typename Metric::distance_type best_dist)
1126  {
1127  SPATIAL_ASSERT_CHECK(dim < rank());
1128  SPATIAL_ASSERT_CHECK(!header(node));
1129  SPATIAL_ASSERT_CHECK(node != 0);
1130  // Finding the maximum is, for lack of a better algorithm, equivalent to a
1131  // O(n) search. An alternative has been explored: being able to find if a
1132  // node is in a cell that is smaller than the current 'far_node' node
1133  // found. However, with the data at hand, computing the cell turned out
1134  // to be more expensive than doing a simple iteration over all nodes in
1135  // the tree. Maybe, one day we'll find a better algorithm that also has
1136  // no impact on the memory footprint of the tree (although I doubt these 2
1137  // conditions will ever be met. Probably there will be a tradeoff.)
1138  //
1139  // Seeks the last node in near-pre-order.
1140  NodePtr best = node->parent;
1141  dimension_type best_dim = 0;
1142  for (;;)
1143  {
1144  typename Metric::distance_type test_dist
1145  = met.distance_to_key(rank(), target, const_key(node));
1146  if (test_dist >= best_dist)
1147  {
1148  best = node;
1149  best_dim = dim;
1150  best_dist = test_dist;
1151  }
1152  NodePtr near, far;
1153  import::tie(near, far) = key_comp(dim, const_key(node), target)
1154  ? import::make_tuple(node->right, node->left)
1155  : import::make_tuple(node->left, node->right);
1156  if (far != 0)
1157  {
1158  dimension_type child_dim = incr_dim(rank, dim);
1159  if (near != 0)
1160  {
1161  import::tuple<NodePtr, dimension_type,
1162  typename Metric::distance_type>
1163  triplet = last_neighbor_sub(near, child_dim, rank,
1164  key_comp, met, target,
1165  best_dist);
1166  if (import::get<0>(triplet) != node)
1167  { import::tie(best, best_dim, best_dist) = triplet; }
1168  }
1169  node = far; dim = child_dim;
1170  }
1171  else if (near != 0)
1172  { node = near; dim = incr_dim(rank, dim); }
1173  else
1174  { return import::make_tuple(best, best_dim, best_dist); }
1175  }
1176  }
1177 
1178  template <typename NodePtr, typename Rank, typename KeyCompare,
1179  typename Key, typename Metric>
1180  inline import::tuple<NodePtr, dimension_type,
1181  typename Metric::distance_type>
1182  last_neighbor(NodePtr node, dimension_type dim, Rank rank,
1183  KeyCompare key_comp, const Metric& met, const Key& target)
1184  {
1185  return last_neighbor_sub(node, dim, rank, key_comp, met, target,
1186  typename Metric::distance_type());
1187  }
1188 
1189  template <typename NodePtr, typename Rank, typename KeyCompare,
1190  typename Key, typename Metric>
1191  inline import::tuple<NodePtr, dimension_type,
1192  typename Metric::distance_type>
1193  first_neighbor_sub(NodePtr node, dimension_type dim, Rank rank,
1194  const KeyCompare& key_comp, const Metric& met,
1195  const Key& target,
1196  typename Metric::distance_type best_dist)
1197  {
1198  SPATIAL_ASSERT_CHECK(dim < rank());
1199  SPATIAL_ASSERT_CHECK(node != 0);
1200  SPATIAL_ASSERT_CHECK(!header(node));
1201  // Finds the nearest in near-pre-order fashion. Uses semi-recursiveness.
1202  NodePtr best = node->parent;
1203  dimension_type best_dim = 0;
1204  for (;;)
1205  {
1206  typename Metric::distance_type test_dist
1207  = met.distance_to_key(rank(), target, const_key(node));
1208  if (test_dist < best_dist)
1209  {
1210  best = node;
1211  best_dim = dim;
1212  best_dist = test_dist;
1213  }
1214  NodePtr near, far;
1215  import::tie(near, far) = key_comp(dim, const_key(node), target)
1216  ? import::make_tuple(node->right, node->left)
1217  : import::make_tuple(node->left, node->right);
1218  if (far != 0 && (met.distance_to_plane
1219  (rank(), dim, target, const_key(node)) < best_dist))
1220  {
1221  dimension_type child_dim = incr_dim(rank, dim);
1222  if (near != 0)
1223  {
1224  import::tuple<NodePtr, dimension_type,
1225  typename Metric::distance_type>
1226  triplet = first_neighbor_sub(near, child_dim, rank,
1227  key_comp, met, target,
1228  best_dist);
1229  if (import::get<0>(triplet) != node)
1230  {
1231  // If I can't go right after exploring left, I'm done
1232  if (!(met.distance_to_plane
1233  (rank(), dim, target, const_key(node))
1234  < import::get<2>(triplet)))
1235  { return triplet; }
1236  import::tie(best, best_dim, best_dist) = triplet;
1237  }
1238  }
1239  node = far; dim = child_dim;
1240  }
1241  else if (near != 0)
1242  { node = near; dim = incr_dim(rank, dim); }
1243  else
1244  { return import::make_tuple(best, best_dim, best_dist); }
1245  }
1246  }
1247 
1248  template <typename NodePtr, typename Rank, typename KeyCompare,
1249  typename Key, typename Metric>
1250  inline import::tuple<NodePtr, dimension_type,
1251  typename Metric::distance_type>
1252  first_neighbor(NodePtr node, dimension_type dim, Rank rank,
1253  const KeyCompare& key_comp, const Metric& met, const Key& target)
1254  {
1255  return first_neighbor_sub
1256  (node, dim, rank, key_comp, met, target,
1257  (std::numeric_limits<typename Metric::distance_type>::max)());
1258  }
1259 
1260  template <typename NodePtr, typename Rank, typename KeyCompare,
1261  typename Key, typename Metric>
1262  inline import::tuple<NodePtr, dimension_type,
1263  typename Metric::distance_type>
1264  lower_bound_neighbor_sub(NodePtr node, dimension_type dim, Rank rank,
1265  KeyCompare key_comp, const Metric& met,
1266  const Key& target,
1267  typename Metric::distance_type bound,
1268  typename Metric::distance_type best_dist)
1269  {
1270  // Finds lower bound in left-pre-order fashion. Uses semi-recursiveness.
1271  SPATIAL_ASSERT_CHECK(dim < rank());
1272  SPATIAL_ASSERT_CHECK(node != 0);
1273  SPATIAL_ASSERT_CHECK(!header(node));
1274  NodePtr best = node->parent;
1275  dimension_type best_dim = decr_dim(rank, dim);
1276  for (;;)
1277  {
1278  typename Metric::distance_type test_dist
1279  = met.distance_to_key(rank(), target, const_key(node));
1280  if (test_dist > bound)
1281  {
1282  if (test_dist < best_dist)
1283  {
1284  best = node;
1285  best_dim = dim;
1286  best_dist = test_dist;
1287  }
1288  }
1289  else if (test_dist == bound)
1290  { return import::make_tuple(node, dim, test_dist); }
1291  NodePtr near, far;
1292  import::tie(near, far) = key_comp(dim, const_key(node), target)
1293  ? import::make_tuple(node->right, node->left)
1294  : import::make_tuple(node->left, node->right);
1295  if (far != 0 && (met.distance_to_plane
1296  (rank(), dim, target, const_key(node)) < best_dist))
1297  {
1298  dimension_type child_dim = incr_dim(rank, dim);
1299  if (near != 0)
1300  {
1301  import::tuple<NodePtr, dimension_type,
1302  typename Metric::distance_type>
1303  triplet = lower_bound_neighbor_sub(near, child_dim, rank,
1304  key_comp, met, target,
1305  bound, best_dist);
1306  if (import::get<0>(triplet) != node)
1307  {
1308  if (import::get<2>(triplet) == bound
1309  // If I can't go right after exploring left, I'm done
1310  || !(met.distance_to_plane
1311  (rank(), dim, target, const_key(node))
1312  < import::get<2>(triplet)))
1313  { return triplet; }
1314  import::tie(best, best_dim, best_dist) = triplet;
1315  }
1316  }
1317  node = far; dim = child_dim;
1318  }
1319  else if (near != 0)
1320  { node = near; dim = incr_dim(rank, dim); }
1321  else
1322  { return import::make_tuple(best, best_dim, best_dist); }
1323  }
1324  }
1325 
1326  template <typename NodePtr, typename Rank, typename KeyCompare,
1327  typename Key, typename Metric>
1328  inline import::tuple<NodePtr, dimension_type,
1329  typename Metric::distance_type>
1330  lower_bound_neighbor(NodePtr node, dimension_type dim, Rank rank,
1331  KeyCompare key_comp, const Metric& met,
1332  const Key& target,
1333  typename Metric::distance_type bound)
1334  {
1335  return lower_bound_neighbor_sub
1336  (node, dim, rank, key_comp, met, target, bound,
1337  (std::numeric_limits<typename Metric::distance_type>::max)());
1338  }
1339 
1340  template <typename NodePtr, typename Rank, typename KeyCompare,
1341  typename Key, typename Metric>
1342  inline import::tuple<NodePtr, dimension_type,
1343  typename Metric::distance_type>
1344  upper_bound_neighbor_sub(NodePtr node, dimension_type dim, Rank rank,
1345  KeyCompare key_comp, Metric met, const Key& target,
1346  typename Metric::distance_type bound,
1347  typename Metric::distance_type best_dist)
1348  {
1349  SPATIAL_ASSERT_CHECK(dim < rank());
1350  SPATIAL_ASSERT_CHECK(node != 0);
1351  SPATIAL_ASSERT_CHECK(!header(node));
1352  // Finds upper bound in left-pre-order fashion. Uses semi-recursiveness.
1353  NodePtr best = node->parent;
1354  dimension_type best_dim = decr_dim(rank, dim);
1355  for (;;)
1356  {
1357  typename Metric::distance_type test_dist
1358  = met.distance_to_key(rank(), target, const_key(node));
1359  if (test_dist > bound && test_dist < best_dist)
1360  {
1361  best = node;
1362  best_dim = dim;
1363  best_dist = test_dist;
1364  }
1365  NodePtr near, far;
1366  import::tie(near, far) = key_comp(dim, const_key(node), target)
1367  ? import::make_tuple(node->right, node->left)
1368  : import::make_tuple(node->left, node->right);
1369  if (far != 0 && (met.distance_to_plane
1370  (rank(), dim, target, const_key(node)) < best_dist))
1371  {
1372  dimension_type child_dim = incr_dim(rank, dim);
1373  if (near != 0)
1374  {
1375  import::tuple<NodePtr, dimension_type,
1376  typename Metric::distance_type>
1377  triplet = upper_bound_neighbor_sub(near, child_dim, rank,
1378  key_comp, met, target,
1379  bound, best_dist);
1380  if (import::get<0>(triplet) != node)
1381  {
1382  // If I can't go right after exploring left, I'm done
1383  if (!(met.distance_to_plane
1384  (rank(), dim, target, const_key(node))
1385  < import::get<2>(triplet)))
1386  { return triplet; }
1387  import::tie(best, best_dim, best_dist) = triplet;
1388  }
1389  }
1390  node = far; dim = child_dim;
1391  }
1392  else if (near != 0)
1393  { node = near; dim = incr_dim(rank, dim); }
1394  else
1395  { return import::make_tuple(best, best_dim, best_dist); }
1396  }
1397  }
1398 
1399  template <typename NodePtr, typename Rank, typename KeyCompare,
1400  typename Key, typename Metric>
1401  inline import::tuple<NodePtr, dimension_type,
1402  typename Metric::distance_type>
1403  upper_bound_neighbor(NodePtr node, dimension_type dim, Rank rank,
1404  KeyCompare key_comp, const Metric& met,
1405  const Key& target,
1406  typename Metric::distance_type bound)
1407  {
1408  return upper_bound_neighbor_sub
1409  (node, dim, rank, key_comp, met, target, bound,
1410  (std::numeric_limits<typename Metric::distance_type>::max)());
1411  }
1412 
1413  template <typename NodePtr, typename Rank, typename KeyCompare,
1414  typename Key, typename Metric>
1415  inline import::tuple<NodePtr, dimension_type,
1416  typename Metric::distance_type>
1417  increment_neighbor(NodePtr node, dimension_type dim, Rank rank,
1418  KeyCompare key_comp, const Metric& met,
1419  const Key& target,
1420  typename Metric::distance_type node_dist)
1421  {
1422  SPATIAL_ASSERT_CHECK(dim < rank());
1423  SPATIAL_ASSERT_CHECK(!header(node));
1424  SPATIAL_ASSERT_CHECK(node != 0);
1425  NodePtr orig = node;
1426  dimension_type orig_dim = dim;
1427  NodePtr best = 0;
1428  dimension_type best_dim = dim;
1429  typename Metric::distance_type best_dist = node_dist;
1430  // Looks forward to find an equal or greater next best. If an equal next
1431  // best is found, then no need to look further. 'Forward' and 'backward'
1432  // refer to tree walking in near-pre-order.
1433  for(;;)
1434  {
1435  NodePtr near, far;
1436  import::tie(near, far) = key_comp(dim, const_key(node), target)
1437  ? import::make_tuple(node->right, node->left)
1438  : import::make_tuple(node->left, node->right);
1439  if (near != 0)
1440  { node = near; dim = incr_dim(rank, dim); }
1441  else if (far != 0
1442  && (best == 0
1443  || met.distance_to_plane
1444  (rank(), dim, target, const_key(node)) < best_dist))
1445  { node = far; dim = incr_dim(rank, dim); }
1446  else
1447  {
1448  NodePtr prev_node = node;
1449  node = node->parent; dim = decr_dim(rank, dim);
1450  while (!header(node)
1451  && (prev_node
1452  == (far = key_comp(dim, const_key(node), target)
1453  ? node->left : node->right)
1454  || far == 0
1455  || !(best == 0
1456  || (met.distance_to_plane
1457  (rank(), dim, target, const_key(node))
1458  < best_dist))))
1459  {
1460  prev_node = node;
1461  node = node->parent; dim = decr_dim(rank, dim);
1462  }
1463  if (!header(node))
1464  { node = far; dim = incr_dim(rank, dim); }
1465  else break;
1466  }
1467  // Test node here and stops as soon as it finds an equal
1468  typename Metric::distance_type test_dist
1469  = met.distance_to_key(rank(), target, const_key(node));
1470  if (test_dist == node_dist)
1471  {
1472  SPATIAL_ASSERT_CHECK(dim < rank());
1473  SPATIAL_ASSERT_CHECK(best == 0 || test_dist < best_dist);
1474  return import::make_tuple(node, dim, test_dist);
1475  }
1476  else if (test_dist > node_dist
1477  && (best == 0 || test_dist < best_dist))
1478  {
1479  best = node;
1480  best_dim = dim;
1481  best_dist = test_dist;
1482  }
1483  }
1484  // Here, current best_dist > node_dist or best == 0, maybe there is a
1485  // better best at the back (iterate backwards to header)
1486  NodePtr prev_node = orig;
1487  dimension_type prev_dim = orig_dim;
1488  node = orig->parent;
1489  dim = decr_dim(rank, orig_dim);
1490  while(!header(node))
1491  {
1492  NodePtr near, far;
1493  import::tie(near, far) = key_comp(dim, const_key(node), target)
1494  ? import::make_tuple(node->right, node->left)
1495  : import::make_tuple(node->left, node->right);
1496  if (far == prev_node && near != 0)
1497  {
1498  node = near;
1499  dim = prev_dim;
1500  for (;;)
1501  {
1502  import::tie(near, far) = key_comp(dim, const_key(node), target)
1503  ? import::make_tuple(node->right, node->left)
1504  : import::make_tuple(node->left, node->right);
1505  if (far != 0
1506  && (best == 0
1507  || (met.distance_to_plane(rank(), dim, target,
1508  const_key(node))
1509  < best_dist)))
1510  { node = far; dim = incr_dim(rank, dim); }
1511  else if (near != 0)
1512  { node = near; dim = incr_dim(rank, dim); }
1513  else break;
1514  }
1515  }
1516  // Test node here for new best
1517  typename Metric::distance_type test_dist
1518  = met.distance_to_key(rank(), target, const_key(node));
1519  if (test_dist > node_dist && (best == 0 || test_dist <= best_dist))
1520  {
1521  best = node;
1522  best_dim = dim;
1523  best_dist = test_dist;
1524  }
1525  prev_node = node;
1526  prev_dim = dim;
1527  node = node->parent;
1528  dim = decr_dim(rank, dim);
1529  }
1530  SPATIAL_ASSERT_CHECK(dim < rank());
1531  SPATIAL_ASSERT_CHECK(node != 0);
1532  if (best != 0) { node = best; dim = best_dim; }
1533  return import::make_tuple(node, dim, best_dist);
1534  }
1535 
1536  template <typename NodePtr, typename Rank, typename KeyCompare,
1537  typename Key, typename Metric>
1538  inline import::tuple<NodePtr, dimension_type,
1539  typename Metric::distance_type>
1540  decrement_neighbor(NodePtr node, dimension_type dim, Rank rank,
1541  KeyCompare key_comp, const Metric& met,
1542  const Key& target,
1543  typename Metric::distance_type node_dist)
1544  {
1545  if (header(node))
1546  { return last_neighbor(node->parent, 0, rank, key_comp, met, target); }
1547  SPATIAL_ASSERT_CHECK(dim < rank());
1548  SPATIAL_ASSERT_CHECK(node != 0);
1549  NodePtr orig = node;
1550  dimension_type orig_dim = dim;
1551  NodePtr best = 0;
1552  dimension_type best_dim = dim;
1553  typename Metric::distance_type best_dist = node_dist;
1554  // Looks backaward to find an equal or lower next best. If an equal next
1555  // best is found, then no need to look further. 'Forward' and 'backward'
1556  // refer to tree walking in near-pre-order.
1557  NodePtr prev_node = node;
1558  dimension_type prev_dim = dim;
1559  node = node->parent;
1560  dim = decr_dim(rank, dim);
1561  while (!header(node))
1562  {
1563  NodePtr near, far;
1564  import::tie(near, far) = key_comp(dim, const_key(node), target)
1565  ? import::make_tuple(node->right, node->left)
1566  : import::make_tuple(node->left, node->right);
1567  if (prev_node == far && near != 0)
1568  {
1569  node = near;
1570  dim = prev_dim;
1571  for (;;)
1572  {
1573  import::tie(near, far) = key_comp(dim, const_key(node), target)
1574  ? import::make_tuple(node->right, node->left)
1575  : import::make_tuple(node->left, node->right);
1576  if (far != 0
1577  && (met.distance_to_plane(rank(), dim, target,
1578  const_key(node))
1579  <= node_dist))
1580  { node = far; dim = incr_dim(rank, dim); }
1581  else if (near != 0)
1582  { node = near; dim = incr_dim(rank, dim); }
1583  else break;
1584  }
1585  }
1586  // Test node here and stops as soon as it finds an equal
1587  typename Metric::distance_type test_dist
1588  = met.distance_to_key(rank(), target, const_key(node));
1589  if (test_dist == node_dist)
1590  {
1591  SPATIAL_ASSERT_CHECK(dim < rank());
1592  SPATIAL_ASSERT_CHECK(best == 0 || test_dist > best_dist);
1593  return import::make_tuple(node, dim, test_dist);
1594  }
1595  else if (test_dist < node_dist
1596  && (best == 0 || test_dist > best_dist))
1597  {
1598  best = node;
1599  best_dim = dim;
1600  best_dist = test_dist;
1601  }
1602  prev_node = node;
1603  prev_dim = dim;
1604  node = node->parent;
1605  dim = decr_dim(rank, dim);
1606  }
1607  // Here, current best_dist < node_dist or best == 0, maybe there is a
1608  // better best at the front (iterate forward to header)
1609  node = orig;
1610  dim = orig_dim;
1611  for(;;)
1612  {
1613  NodePtr near, far;
1614  import::tie(near, far) = key_comp(dim, const_key(node), target)
1615  ? import::make_tuple(node->right, node->left)
1616  : import::make_tuple(node->left, node->right);
1617  if (near != 0)
1618  { node = near; dim = incr_dim(rank, dim); }
1619  else if (far != 0
1620  && (met.distance_to_plane(rank(), dim, target,
1621  const_key(node))
1622  < node_dist))
1623  { node = far; dim = incr_dim(rank, dim); }
1624  else
1625  {
1626  prev_node = node;
1627  node = node->parent; dim = decr_dim(rank, dim);
1628  while (!header(node)
1629  && (prev_node
1630  == (far = key_comp(dim, const_key(node), target)
1631  ? node->left : node->right)
1632  || far == 0
1633  || !(met.distance_to_plane(rank(), dim, target,
1634  const_key(node))
1635  < node_dist)))
1636  {
1637  prev_node = node;
1638  node = node->parent; dim = decr_dim(rank, dim);
1639  }
1640  if (!header(node))
1641  { node = far; dim = incr_dim(rank, dim); }
1642  else break;
1643  }
1644  typename Metric::distance_type test_dist
1645  = met.distance_to_key(rank(), target, const_key(node));
1646  if (test_dist < node_dist && (best == 0 || test_dist >= best_dist))
1647  {
1648  best = node;
1649  best_dim = dim;
1650  best_dist = test_dist;
1651  }
1652  }
1653  SPATIAL_ASSERT_CHECK(dim < rank());
1654  SPATIAL_ASSERT_CHECK(node != 0);
1655  if (best != 0) { node = best; dim = best_dim; }
1656  return import::make_tuple(node, dim, best_dist);
1657  }
1658 
1659  } // namespace details
1660 } // namespace spatial
1661 
1662 #endif // SPATIAL_NEIGHBOR_HPP
spatial::neighbor_iterator_pair::neighbor_iterator_pair
neighbor_iterator_pair()
Empty constructor.
Definition: spatial_neighbor.hpp:581
spatial::neighbor_iterator< const Ct, Metric >::target_key
key_type & target_key()
Read/write accessor to the target of the iterator.
Definition: spatial_neighbor.hpp:524
spatial::neighbor_iterator_pair< const Ct, Metric >::neighbor_iterator_pair
neighbor_iterator_pair()
Empty constructor.
Definition: spatial_neighbor.hpp:610
spatial::neighbor_iterator_pair::Base
std::pair< neighbor_iterator< Ct, Metric >, neighbor_iterator< Ct, Metric > > Base
A pair of iterators that represents a range (that is: a range of elements to iterate, and not an orthogonal range).
Definition: spatial_neighbor.hpp:578
spatial::distance
Metric::distance_type distance(const neighbor_iterator< Ct, Metric > &iter)
Read/write accessor for neighbor iterators that retrieve the valid calculated distance from the targe...
Definition: spatial_neighbor.hpp:539
spatial::details::last_neighbor
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > last_neighbor(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target)
Definition: spatial_neighbor.hpp:1182
spatial::neighbor_iterator_pair< const Ct, Metric >
This structure defines a pair of constant neighbor iterator.
Definition: spatial_neighbor.hpp:598
spatial::neighbor_iterator< const Ct, Metric >::key_type
container_traits< Ct >::key_type key_type
The key type that is used as a target for the nearest neighbor search.
Definition: spatial_neighbor.hpp:365
spatial::details::increment_neighbor
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > increment_neighbor(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type node_dist)
Definition: spatial_neighbor.hpp:1417
spatial::neighbor_iterator_pair< const Ct, Metric >::neighbor_iterator_pair
neighbor_iterator_pair(const neighbor_iterator_pair< Ct, Metric > &p)
Convert a mutable neighbor iterator pair into a const neighbor iterator pair.
Definition: spatial_neighbor.hpp:621
spatial::neighbor_iterator< const Ct, Metric >::Base
details::Const_bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: spatial_neighbor.hpp:348
spatial::neighbor_clower_bound
neighbor_iterator< const Ct, Metric > neighbor_clower_bound(const Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target, typename Metric::distance_type bound)
Build a neighbor_iterator pointing to the neighbor closest to target but for which distance to target...
Definition: spatial_neighbor.hpp:859
spatial::neighbor_iterator< const Ct, Metric >::operator++
neighbor_iterator< const Ct, Metric > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: spatial_neighbor.hpp:472
spatial::target_key
const container_traits< Ct >::key_type & target_key(const neighbor_iterator< Ct, Metric > &iter)
A quick accessor for neighbor iterators that retrive the key that is the target for the nearest neigh...
Definition: spatial_neighbor.hpp:555
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::neighbor_iterator::_data
details::Neighbor_data< Ct, Metric > _data
The related data for the iterator.
Definition: spatial_neighbor.hpp:301
spatial::neighbor_iterator< const Ct, Metric >::operator--
neighbor_iterator< const Ct, Metric > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: spatial_neighbor.hpp:493
spatial::details::Bidirectional_iterator::node
node_ptr node
The pointer to the current node.
Definition: spatial_bidirectional.hpp:122
spatial::neighbor_iterator::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: spatial_neighbor.hpp:277
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::neighbor_iterator< const Ct, Metric >::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: spatial_neighbor.hpp:504
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::neighbor_iterator::Base
details::Bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: spatial_neighbor.hpp:123
spatial::details::last_neighbor_sub
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > last_neighbor_sub(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type best_dist)
Definition: spatial_neighbor.hpp:1123
spatial::neighbor_iterator::metric_type
Metric metric_type
The metric type used by the iterator.
Definition: spatial_neighbor.hpp:134
spatial::neighbor_iterator::distance
const distance_type & distance() const
Read-only accessor to the last valid distance of the iterator.
Definition: spatial_neighbor.hpp:285
spatial::neighbor_iterator< const Ct, Metric >::key_compare
container_traits< Ct >::key_compare key_compare
Key comparator type transferred from the container.
Definition: spatial_neighbor.hpp:356
spatial::neighbor_iterator< const Ct, Metric >::_data
details::Neighbor_data< Ct, Metric > _data
The related data for the iterator.
Definition: spatial_neighbor.hpp:528
spatial::neighbor_iterator< const Ct, Metric >::operator--
neighbor_iterator< const Ct, Metric > & operator--()
Decrements the iterator and returns the decremented value.
Definition: spatial_neighbor.hpp:483
spatial::neighbor_iterator< const Ct, Metric >::neighbor_iterator
neighbor_iterator(const neighbor_iterator< Ct, Metric > &iter)
Convertion of mutable iterator into a constant iterator.
Definition: spatial_neighbor.hpp:455
spatial::neighbor_range
neighbor_iterator_pair< Ct, Metric > neighbor_range(Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target)
Returns a neighbor_iterator_pair representing the range of values from the closest to the furthest in...
Definition: spatial_neighbor.hpp:1046
spatial::neighbor_iterator::distance_type
Metric::distance_type distance_type
The distance type that is read from metric_type.
Definition: spatial_neighbor.hpp:137
spatial::neighbor_iterator::key_compare
container_traits< Ct >::key_compare key_compare
Key comparator type transferred from the container.
Definition: spatial_neighbor.hpp:131
spatial::neighbor_cend
neighbor_iterator< const Ct, Metric > neighbor_cend(const Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target)
Build a past-the-end neighbor iterator with a user-defined Metric.
Definition: spatial_neighbor.hpp:654
spatial::container_traits< Ct >::key_type
Ct::key_type key_type
The type representing the key managed by the container.
Definition: traits.hpp:48
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::neighbor_iterator::operator--
neighbor_iterator< Ct, Metric > & operator--()
Decrements the iterator and returns the decremented value.
Definition: spatial_neighbor.hpp:256
spatial::neighbor_iterator< const Ct, Metric >::metric
metric_type metric() const
Return the metric used by the iterator.
Definition: spatial_neighbor.hpp:508
spatial::details::Bidirectional_iterator::node_dim
dimension_type node_dim
The dimension of the current node.
Definition: spatial_bidirectional.hpp:131
spatial::details::Neighbor_data::_distance
Metric::distance_type _distance
The last valid computed value of the distance.
Definition: spatial_neighbor.hpp:75
spatial::details::header
bool header(const Node< Link > *x)
Check if node is a header node.
Definition: spatial_node.hpp:96
spatial::neighbor_iterator_pair::neighbor_iterator_pair
neighbor_iterator_pair(const neighbor_iterator< Ct, Metric > &a, const neighbor_iterator< Ct, Metric > &b)
Regular constructor that builds a neighbor_iterator_pair out of 2 neighbor_iterators.
Definition: spatial_neighbor.hpp:585
spatial::details::Neighbor_data::Neighbor_data
Neighbor_data()
Build an unintialized neighbor data object.
Definition: spatial_neighbor.hpp:45
spatial::neighbor_lower_bound
neighbor_iterator< Ct, Metric > neighbor_lower_bound(Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target, typename Metric::distance_type bound)
Build a neighbor_iterator pointing to the neighbor closest to target but for which distance to target...
Definition: spatial_neighbor.hpp:825
spatial::neighbor_end
neighbor_iterator< Ct, Metric > neighbor_end(Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target)
Build a past-the-end neighbor iterator with a user-defined Metric.
Definition: spatial_neighbor.hpp:634
spatial::neighbor_iterator
A spatial iterator for a container Ct that goes through the nearest to the furthest element from a ta...
Definition: spatial_neighbor.hpp:115
spatial::neighbor_iterator::target_key
key_type & target_key()
Read/write accessor to the target of the iterator.
Definition: spatial_neighbor.hpp:297
spatial::neighbor_iterator::operator++
neighbor_iterator< Ct, Metric > & operator++()
Increments the iterator and returns the incremented value.
Definition: spatial_neighbor.hpp:235
spatial::neighbor_crange
neighbor_iterator_pair< const Ct, Metric > neighbor_crange(const Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target)
Returns a neighbor_iterator_pair representing the range of values from the closest to the furthest in...
Definition: spatial_neighbor.hpp:1066
spatial::container_traits
The traits type for all containers in the spatial namespace.
Definition: traits.hpp:42
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::neighbor_cbegin
neighbor_iterator< const Ct, Metric > neighbor_cbegin(const Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target)
Build a neighbor_iterator pointing to the nearest neighbor of target using a user-defined Metric...
Definition: spatial_neighbor.hpp:755
spatial::neighbor_iterator::operator++
neighbor_iterator< Ct, Metric > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: spatial_neighbor.hpp:245
spatial::details::first_neighbor_sub
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > first_neighbor_sub(NodePtr node, dimension_type dim, Rank rank, const KeyCompare &key_comp, const Metric &met, const Key &target, typename Metric::distance_type best_dist)
Definition: spatial_neighbor.hpp:1193
spatial::neighbor_iterator< const Ct, Metric >::target_key
const key_type & target_key() const
Read-only accessor to the target of the iterator.
Definition: spatial_neighbor.hpp:520
spatial::neighbor_iterator< const Ct, Metric >::metric_type
Metric metric_type
The metric type used by the iterator.
Definition: spatial_neighbor.hpp:359
spatial::neighbor_iterator::neighbor_iterator
neighbor_iterator()
Uninitialized iterator.
Definition: spatial_neighbor.hpp:143
spatial::neighbor_iterator_pair
This structure defines a pair of neighbor iterator.
Definition: spatial_neighbor.hpp:569
spatial::euclidian
Defines a metric working on the Euclidian space where distances are expressed in one of C++'s floatin...
Definition: metric.hpp:42
spatial::neighbor_iterator< const Ct, Metric >::operator++
neighbor_iterator< const Ct, Metric > & operator++()
Increments the iterator and returns the incremented value.
Definition: spatial_neighbor.hpp:462
spatial::neighbor_iterator< const Ct, Metric >
A spatial iterator for a container Ct that goes through the nearest to the furthest element from a ta...
Definition: spatial_neighbor.hpp:340
spatial::neighbor_iterator_pair< const Ct, Metric >::neighbor_iterator_pair
neighbor_iterator_pair(const neighbor_iterator< const Ct, Metric > &a, const neighbor_iterator< const Ct, Metric > &b)
Regular constructor that builds a neighbor_iterator_pair out of 2 neighbor_iterators.
Definition: spatial_neighbor.hpp:614
spatial::details::Compress
Uses the empty base class optimization in order to compress a potentially empty base class with a mem...
Definition: spatial_compress.hpp:46
spatial::details::Neighbor_data
Extra information needed by the iterator to perform its work.
Definition: spatial_neighbor.hpp:42
spatial::details::Neighbor_data::_target
Compress< Metric, typename container_traits< Ct >::key_type > _target
The target of the iteration; element of the container are iterate from the closest to the element fur...
Definition: spatial_neighbor.hpp:69
spatial::neighbor_upper_bound
neighbor_iterator< Ct, Metric > neighbor_upper_bound(Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target, typename Metric::distance_type bound)
Build a neighbor_iterator pointing to the neighbor closest to target but for which distance to target...
Definition: spatial_neighbor.hpp:936
spatial::neighbor_iterator< const Ct, Metric >::distance
distance_type distance() const
Read-only accessor to the last valid distance of the iterator.
Definition: spatial_neighbor.hpp:512
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::neighbor_iterator::key_type
container_traits< Ct >::key_type key_type
The key type that is used as a target for the nearest neighbor search.
Definition: spatial_neighbor.hpp:140
spatial::details::first_neighbor
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > first_neighbor(NodePtr node, dimension_type dim, Rank rank, const KeyCompare &key_comp, const Metric &met, const Key &target)
Definition: spatial_neighbor.hpp:1252
spatial::neighbor_iterator< const Ct, Metric >::distance
distance_type & distance()
Read/write accessor to the last valid distance of the iterator.
Definition: spatial_neighbor.hpp:516
spatial::neighbor_iterator::operator--
neighbor_iterator< Ct, Metric > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: spatial_neighbor.hpp:266
spatial::neighbor_iterator< const Ct, Metric >::neighbor_iterator
neighbor_iterator()
Constructs an empty, uninitialized object.
Definition: spatial_neighbor.hpp:368
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::neighbor_iterator::target_key
const key_type & target_key() const
Read-only accessor to the target of the iterator.
Definition: spatial_neighbor.hpp:293
spatial::details::lower_bound_neighbor_sub
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > lower_bound_neighbor_sub(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type bound, typename Metric::distance_type best_dist)
Definition: spatial_neighbor.hpp:1264
spatial::neighbor_iterator< const Ct, Metric >::distance_type
Metric::distance_type distance_type
The distance type that is read from metric_type.
Definition: spatial_neighbor.hpp:362
spatial::details::upper_bound_neighbor_sub
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > upper_bound_neighbor_sub(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, Metric met, const Key &target, typename Metric::distance_type bound, typename Metric::distance_type best_dist)
Definition: spatial_neighbor.hpp:1344
spatial::neighbor_iterator::distance
distance_type & distance()
Read/write accessor to the last valid distance of the iterator.
Definition: spatial_neighbor.hpp:289
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::neighbor_begin
neighbor_iterator< Ct, Metric > neighbor_begin(Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target)
Build a neighbor_iterator pointing to the nearest neighbor of target using a user-defined Metric...
Definition: spatial_neighbor.hpp:723
spatial::details::lower_bound_neighbor
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > lower_bound_neighbor(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type bound)
Definition: spatial_neighbor.hpp:1330
spatial::neighbor_cupper_bound
neighbor_iterator< const Ct, Metric > neighbor_cupper_bound(const Ct &container, const Metric &metric, const typename container_traits< Ct >::key_type &target, typename Metric::distance_type bound)
Build a neighbor_iterator pointing to the neighbor closest to target but for which distance to target...
Definition: spatial_neighbor.hpp:970
spatial::details::upper_bound_neighbor
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > upper_bound_neighbor(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type bound)
Definition: spatial_neighbor.hpp:1403
spatial::details::Bidirectional_iterator
A common template for bidirectional iterators that work on identical modes of linking.
Definition: spatial_bidirectional.hpp:33
spatial::details::with_builtin_difference
The generic helper class to determine if a container uses a built-in compare type.
Definition: spatial_builtin.hpp:70
spatial::details::decrement_neighbor
import::tuple< NodePtr, dimension_type, typename Metric::distance_type > decrement_neighbor(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Metric &met, const Key &target, typename Metric::distance_type node_dist)
Definition: spatial_neighbor.hpp:1540
spatial::neighbor_iterator::metric
metric_type metric() const
Return the metric used by the iterator.
Definition: spatial_neighbor.hpp:281
spatial::neighbor_iterator_pair< const Ct, Metric >::Base
std::pair< neighbor_iterator< const Ct, Metric >, neighbor_iterator< const Ct, Metric > > Base
A pair of iterators that represents a range (that is: a range of elements to iterate, and not an orthogonal range).
Definition: spatial_neighbor.hpp:607
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