Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_ordered.hpp
1 // -*- C++ -*-
2 //
3 // Copyright Sylvain Bougerel 2009 - 2013.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file COPYING or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 
13 #ifndef SPATIAL_ORDERED_HPP
14 #define SPATIAL_ORDERED_HPP
15 
16 #include "../traits.hpp"
17 #include "spatial_bidirectional.hpp"
18 #include "spatial_rank.hpp"
19 #include "spatial_except.hpp"
20 
21 namespace spatial
22 {
31  template<typename Ct>
32  class ordered_iterator
33  : public details::Bidirectional_iterator
34  <typename container_traits<Ct>::mode_type,
35  typename container_traits<Ct>::rank_type>
36  {
37  private:
38  typedef details::Bidirectional_iterator
39  <typename container_traits<Ct>::mode_type,
40  typename container_traits<Ct>::rank_type> Base;
41 
42  public:
43  typedef typename container_traits<Ct>::key_compare key_compare;
44 
46  ordered_iterator() { }
47 
56  ordered_iterator(Ct& container,
57  typename container_traits<Ct>::iterator iter)
58  : Base(container.rank(), iter.node, modulo(iter.node, container.rank())),
59  _cmp(container.key_comp())
60  { }
61 
82  ordered_iterator(Ct& container, dimension_type dim,
83  typename container_traits<Ct>::mode_type::node_ptr ptr)
84  : Base(container.rank(), ptr, dim), _cmp(container.key_comp())
85  { except::check_dimension(container.dimension(), dim); }
86 
89  ordered_iterator<Ct>& operator++()
90  { return increment_ordered(*this); }
91 
94  ordered_iterator<Ct> operator++(int)
95  {
96  ordered_iterator<Ct> x(*this);
97  increment_ordered(*this);
98  return x;
99  }
100 
103  ordered_iterator<Ct>& operator--()
104  { return decrement_ordered(*this); }
105 
108  ordered_iterator<Ct> operator--(int)
109  {
110  ordered_iterator<Ct> x(*this);
111  decrement_ordered(*this);
112  return x;
113  }
114 
116  key_compare
117  key_comp() const { return _cmp; }
118 
119  private:
121  key_compare _cmp;
122  };
123 
131  template<typename Ct>
132  class ordered_iterator<const Ct>
133  : public details::Const_bidirectional_iterator
134  <typename container_traits<Ct>::mode_type,
135  typename container_traits<Ct>::rank_type>
136  {
137  private:
138  typedef details::Const_bidirectional_iterator
139  <typename container_traits<Ct>::mode_type,
140  typename container_traits<Ct>::rank_type> Base;
141 
142  public:
144  typedef typename container_traits<Ct>::key_compare key_compare;
145 
147  ordered_iterator() { }
148 
157  ordered_iterator(const Ct& container,
158  typename container_traits<Ct>::const_iterator iter)
159  : Base(container.rank(), iter.node, modulo(iter.node, container.rank())),
160  _cmp(container.key_comp())
161  { }
162 
182  ordered_iterator
183  (const Ct& container, dimension_type dim,
184  typename container_traits<Ct>::mode_type::const_node_ptr ptr)
185  : Base(container.rank(), ptr, dim), _cmp(container.key_comp())
186  { except::check_dimension(container.dimension(), dim); }
187 
189  ordered_iterator(const ordered_iterator<Ct>& iter)
190  : Base(iter.rank(), iter.node, iter.node_dim), _cmp(iter.key_comp())
191  { }
192 
195  ordered_iterator<const Ct>& operator++()
196  { return increment_ordered(*this); }
197 
200  ordered_iterator<const Ct> operator++(int)
201  {
202  ordered_iterator<const Ct> x(*this);
203  increment_ordered(*this);
204  return x;
205  }
206 
209  ordered_iterator<const Ct>& operator--()
210  { return decrement_ordered(*this); }
211 
214  ordered_iterator<const Ct> operator--(int)
215  {
216  ordered_iterator<const Ct> x(*this);
217  decrement_ordered(*this);
218  return x;
219  }
220 
222  key_compare
223  key_comp() const { return _cmp; }
224 
225  private:
227  key_compare _cmp;
228  };
229 
230  namespace details
231  {
254  template <typename Container>
255  ordered_iterator<Container>&
256  increment_ordered(ordered_iterator<Container>& iter);
257 
280  template <typename Container>
281  ordered_iterator<Container>&
282  decrement_ordered(ordered_iterator<Container>& iter);
283 
303  template <typename Container>
304  ordered_iterator<Container>&
305  minimum_ordered(ordered_iterator<Container>& iter);
306 
326  template <typename Container>
327  ordered_iterator<Container>&
328  maximum_ordered(ordered_iterator<Container>& iter);
329  } // namespace details
330 
350  template <typename Container>
351  inline ordered_iterator<Container>
352  ordered_end(Container& container)
353  {
354  return ordered_iterator<Container>
355  // At header (dim = rank - 1)
356  (container, container.dimension() - 1, container.end().node);
357  }
358 
360 
373  template <typename Container>
374  inline ordered_iterator<const Container>
375  ordered_end(const Container& container)
376  {
377  return ordered_iterator<const Container>
378  // At header (dim = rank - 1)
379  (container, container.dimension() - 1, container.end().node);
380  }
381 
382  template <typename Container>
383  inline ordered_iterator<const Container>
384  ordered_cend(const Container& container)
385  { return ordered_end(container); }
387 
405  template <typename Container>
406  inline ordered_iterator<Container>
407  ordered_begin(Container& container)
408  {
409  if (container.empty()) return ordered_end(container);
410  ordered_iterator<Container>
411  it(container, 0, container.end().node->parent);
412  return details::minimum_ordered(it);
413  }
414 
416 
427  template <typename Container>
428  inline ordered_iterator<const Container>
429  ordered_begin(const Container& container)
430  {
431  if (container.empty()) return ordered_end(container);
432  ordered_iterator<const Container>
433  it(container, 0, container.end().node->parent);
434  return details::minimum_ordered(it);
435  }
436 
437  template <typename Container>
438  inline ordered_iterator<const Container>
439  ordered_cbegin(const Container& container)
440  { return ordered_begin(container); }
442 
443  namespace details
444  {
445  template <typename Cmp, typename Rank, typename Key>
446  inline bool
447  order_ref(const Cmp& cmp, const Rank& rank,
448  const Key& a, const Key& b)
449  {
450  for (dimension_type d = 0; d < rank(); ++d)
451  {
452  if (cmp(d, a, b)) return true;
453  if (cmp(d, b, a)) return false;
454  }
455  return (&a < &b);
456  }
457 
460  template <typename Container>
461  inline ordered_iterator<Container>&
462  increment_ordered(ordered_iterator<Container>& iter,
463  relaxed_invariant_tag)
464  {
465  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
466  const typename container_traits<Container>::rank_type
467  rank(iter.rank());
468  const typename container_traits<Container>::key_compare
469  cmp(iter.key_comp());
470  SPATIAL_ASSERT_CHECK(iter.node != 0);
471  SPATIAL_ASSERT_CHECK(!header(iter.node));
472  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
473  // Walk the tree in both directions: one step left, one step right, etc..
474  dimension_type set_dim = 0; // number of values correctly positionned
475  node_ptr best = 0;
476  dimension_type best_dim = 0;
477  node_ptr l_node, r_node; l_node = r_node = iter.node;
478  dimension_type l_dim, r_dim; l_dim = r_dim = iter.node_dim;
479  bool left_ended = false, right_ended = false;
480  do
481  {
482  if (!left_ended)
483  {
484  if (l_node->left != 0
485  && (l_dim > set_dim
486  || !cmp(l_dim, const_key(l_node), const_key(iter.node))))
487  {
488  l_node = l_node->left;
489  l_dim = incr_dim(rank, l_dim);
490  while (l_node->right != 0
491  && (l_dim > set_dim
492  || best == 0 || !cmp(l_dim, const_key(best),
493  const_key(l_node))))
494  { l_node = l_node->right; l_dim = incr_dim(rank, l_dim); }
495  if (order_ref(cmp, rank, const_key(iter.node),
496  const_key(l_node))
497  && (best == 0
498  || order_ref(cmp, rank, const_key(l_node),
499  const_key(best))))
500  { best = l_node; best_dim = l_dim; }
501  }
502  else
503  {
504  node_ptr p = l_node->parent;
505  while (!header(p) && p->left == l_node)
506  {
507  l_node = p;
508  l_dim = decr_dim(rank, l_dim);
509  p = l_node->parent;
510  }
511  l_node = p;
512  l_dim = decr_dim(rank, l_dim);
513  if (!header(l_node))
514  {
515  if (order_ref(cmp, rank, const_key(iter.node),
516  const_key(l_node))
517  && (best == 0
518  || order_ref(cmp, rank, const_key(l_node),
519  const_key(best))))
520  { best = l_node; best_dim = l_dim; }
521  }
522  else left_ended = true;
523  }
524  }
525  if (!right_ended)
526  {
527  if (r_node->right != 0
528  && (r_dim > set_dim
529  || best == 0
530  || !cmp(r_dim, const_key(best), const_key(r_node))))
531  {
532  r_node = r_node->right;
533  r_dim = incr_dim(rank, r_dim);
534  while (r_node->left != 0
535  && (r_dim > set_dim
536  || !cmp(r_dim, const_key(r_node),
537  const_key(iter.node))))
538  { r_node = r_node->left; r_dim = incr_dim(rank, r_dim); }
539  if (order_ref(cmp, rank, const_key(iter.node),
540  const_key(r_node))
541  && (best == 0
542  || order_ref(cmp, rank, const_key(r_node),
543  const_key(best))))
544  { best = r_node; best_dim = r_dim; }
545  continue;
546  }
547  else
548  {
549  node_ptr p = r_node->parent;
550  while (!header(p) && p->right == r_node)
551  {
552  r_node = p;
553  r_dim = decr_dim(rank, r_dim);
554  p = r_node->parent;
555  }
556  r_node = p;
557  r_dim = decr_dim(rank, r_dim);
558  if (!header(r_node))
559  {
560  if (order_ref(cmp, rank, const_key(iter.node),
561  const_key(r_node))
562  && (best == 0
563  || order_ref(cmp, rank, const_key(r_node),
564  const_key(best))))
565  { best = r_node; best_dim = r_dim; }
566  continue;
567  }
568  else right_ended = true;
569  }
570  }
571  if (left_ended) // continue to jump over this!
572  {
573  // stepping is over in both directions...
574  if (++set_dim == rank()) break;
575  right_ended = false;
576  left_ended = false;
577  l_node = r_node = iter.node;
578  l_dim = r_dim = iter.node_dim;
579  }
580  } while(true);
581  if (best != 0)
582  { iter.node = best; iter.node_dim = best_dim; }
583  else { iter.node = r_node; iter.node_dim = r_dim; }
584  SPATIAL_ASSERT_CHECK(r_dim == (rank() - 1));
585  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
586  SPATIAL_ASSERT_CHECK(iter.node != 0);
587  return iter;
588  }
589 
592  template <typename Container>
593  inline ordered_iterator<Container>&
594  increment_ordered(ordered_iterator<Container>& iter,
595  strict_invariant_tag)
596  {
597  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
598  const typename container_traits<Container>::rank_type
599  rank(iter.rank());
600  const typename container_traits<Container>::key_compare
601  cmp(iter.key_comp());
602  SPATIAL_ASSERT_CHECK(iter.node != 0);
603  SPATIAL_ASSERT_CHECK(!header(iter.node));
604  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
605  // Walk the tree in both directions: one step left, one step right, etc..
606  dimension_type set_dim = 0; // number of values correctly positionned
607  node_ptr best = 0;
608  dimension_type best_dim = 0;
609  node_ptr l_node, r_node; l_node = r_node = iter.node;
610  dimension_type l_dim, r_dim; l_dim = r_dim = iter.node_dim;
611  bool left_ended = false, right_ended = false;
612  do
613  {
614  if (!left_ended)
615  {
616  if (l_node->left != 0
617  && (l_dim > set_dim
618  // strict invarient optimization
619  || cmp(l_dim, const_key(iter.node), const_key(l_node))))
620  {
621  l_node = l_node->left;
622  l_dim = incr_dim(rank, l_dim);
623  while (l_node->right != 0
624  && (l_dim > set_dim
625  || best == 0
626  || !cmp(l_dim, const_key(best),
627  const_key(l_node))))
628  { l_node = l_node->right; l_dim = incr_dim(rank, l_dim); }
629  if (order_ref(cmp, rank, const_key(iter.node),
630  const_key(l_node))
631  && (best == 0
632  || order_ref(cmp, rank, const_key(l_node),
633  const_key(best))))
634  { best = l_node; best_dim = l_dim; }
635  }
636  else
637  {
638  node_ptr p = l_node->parent;
639  while (!header(p) && p->left == l_node)
640  {
641  l_node = p;
642  l_dim = decr_dim(rank, l_dim);
643  p = l_node->parent;
644  }
645  l_node = p;
646  l_dim = decr_dim(rank, l_dim);
647  if (!header(l_node))
648  {
649  if (order_ref(cmp, rank, const_key(iter.node),
650  const_key(l_node))
651  && (best == 0
652  || order_ref(cmp, rank, const_key(l_node),
653  const_key(best))))
654  { best = l_node; best_dim = l_dim; }
655  }
656  else left_ended = true;
657  }
658  }
659  if(!right_ended)
660  {
661  if (r_node->right != 0
662  && (r_dim > set_dim
663  || best == 0
664  || !cmp(r_dim, const_key(best), const_key(r_node))))
665  {
666  r_node = r_node->right;
667  r_dim = incr_dim(rank, r_dim);
668  while (r_node->left
669  && (r_dim > set_dim
670  // strict invarient optimization
671  || cmp(r_dim, const_key(iter.node),
672  const_key(r_node))))
673  { r_node = r_node->left; r_dim = incr_dim(rank, r_dim); }
674  if (order_ref(cmp, rank, const_key(iter.node),
675  const_key(r_node))
676  && (best == 0
677  || order_ref(cmp, rank, const_key(r_node),
678  const_key(best))))
679  { best = r_node; best_dim = r_dim; }
680  continue;
681  }
682  else
683  {
684  node_ptr p = r_node->parent;
685  while (!header(p) && p->right == r_node)
686  {
687  r_node = p;
688  r_dim = decr_dim(rank, r_dim);
689  p = r_node->parent;
690  }
691  r_node = p;
692  r_dim = decr_dim(rank, r_dim);
693  if (!header(r_node))
694  {
695  if (order_ref(cmp, rank, const_key(iter.node),
696  const_key(r_node))
697  && (best == 0
698  || order_ref(cmp, rank, const_key(r_node),
699  const_key(best))))
700  { best = r_node; best_dim = r_dim; }
701  continue;
702  }
703  else right_ended = true;
704  }
705  }
706  if (left_ended) // continue to jump over this!
707  {
708  // stepping is over in both directions...
709  if (++set_dim == rank()) break;
710  right_ended = false;
711  left_ended = false;
712  l_node = r_node = iter.node;
713  l_dim = r_dim = iter.node_dim;
714  }
715  } while(true);
716  if (best != 0)
717  { iter.node = best; iter.node_dim = best_dim; }
718  else { iter.node = r_node; iter.node_dim = r_dim; }
719  SPATIAL_ASSERT_CHECK(r_dim == (rank() - 1));
720  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
721  SPATIAL_ASSERT_CHECK(iter.node != 0);
722  return iter;
723  }
724 
725  template <typename Container>
726  inline ordered_iterator<Container>&
727  increment_ordered(ordered_iterator<Container>& iter)
728  {
729  return increment_ordered
730  (iter, typename container_traits<Container>::mode_type
731  ::invariant_category());
732  }
733 
734  // The next largest key on the ordered dimension is likely to be found in
735  // the children of the current best, so, descend into the children of node
736  // first.
737  template <typename Container>
738  inline ordered_iterator<Container>&
739  decrement_ordered(ordered_iterator<Container>& iter,
740  relaxed_invariant_tag)
741  {
742  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
743  const typename container_traits<Container>::rank_type
744  rank(iter.rank());
745  const typename container_traits<Container>::key_compare
746  cmp(iter.key_comp());
747  SPATIAL_ASSERT_CHECK(iter.node != 0);
748  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
749  if (header(iter.node))
750  {
751  iter.node = iter.node->parent;
752  iter.node_dim = 0; // root is always compared on dimension 0
753  return maximum_ordered(iter);
754  }
755  // Walk the tree in both directions: one step left, one step right, etc..
756  dimension_type set_dim = 0; // number of values correctly positionned
757  node_ptr best = 0;
758  dimension_type best_dim = 0;
759  node_ptr l_node, r_node; l_node = r_node = iter.node;
760  dimension_type l_dim, r_dim; l_dim = r_dim = iter.node_dim;
761  bool left_ended = false, right_ended = false;
762  do
763  {
764  if (!left_ended)
765  {
766  if (l_node->left != 0
767  && (l_dim > set_dim
768  || best == 0
769  || !cmp(l_dim, const_key(l_node), const_key(best))))
770  {
771  l_node = l_node->left;
772  l_dim = incr_dim(rank, l_dim);
773  while (l_node->right
774  && (l_dim > set_dim
775  || !cmp(l_dim, const_key(iter.node),
776  const_key(l_node))))
777  { l_node = l_node->right; l_dim = incr_dim(rank, l_dim); }
778  if (order_ref(cmp, rank, const_key(l_node),
779  const_key(iter.node))
780  && (best == 0
781  || order_ref(cmp, rank, const_key(best),
782  const_key(l_node))))
783  { best = l_node; best_dim = l_dim; }
784  }
785  else
786  {
787  node_ptr p = l_node->parent;
788  while (!header(p) && p->left == l_node)
789  {
790  l_node = p;
791  l_dim = decr_dim(rank, l_dim);
792  p = l_node->parent;
793  }
794  l_node = p;
795  l_dim = decr_dim(rank, l_dim);
796  if (!header(l_node))
797  {
798  if (order_ref(cmp, rank, const_key(l_node),
799  const_key(iter.node))
800  && (best == 0
801  || order_ref(cmp, rank, const_key(best),
802  const_key(l_node))))
803  { best = l_node; best_dim = l_dim; }
804  }
805  else left_ended = true;
806  }
807  }
808  if (!right_ended)
809  {
810  if (r_node->right != 0
811  && (r_dim > set_dim
812  || !cmp(r_dim, const_key(iter.node), const_key(r_node))))
813  {
814  r_node = r_node->right;
815  r_dim = incr_dim(rank, r_dim);
816  while (r_node->left
817  && (r_dim > set_dim
818  || best == 0
819  || !cmp(r_dim, const_key(r_node), const_key(best))))
820  { r_node = r_node->left; r_dim = incr_dim(rank, r_dim); }
821  if (order_ref(cmp, rank, const_key(r_node),
822  const_key(iter.node))
823  && (best == 0
824  || order_ref(cmp, rank, const_key(best),
825  const_key(r_node))))
826  { best = r_node; best_dim = r_dim; }
827  continue;
828  }
829  else
830  {
831  node_ptr p = r_node->parent;
832  while (!header(p) && p->right == r_node)
833  {
834  r_node = p;
835  r_dim = decr_dim(rank, r_dim);
836  p = r_node->parent;
837  }
838  r_node = p;
839  r_dim = decr_dim(rank, r_dim);
840  if (!header(r_node))
841  {
842  if (order_ref(cmp, rank, const_key(r_node),
843  const_key(iter.node))
844  && (best == 0
845  || order_ref(cmp, rank, const_key(best),
846  const_key(r_node))))
847  { best = r_node; best_dim = r_dim; }
848  continue;
849  }
850  else right_ended = true;
851  }
852  }
853  if (left_ended) // continue to jump over this!
854  {
855  // stepping is over in both directions...
856  if (++set_dim == rank()) break;
857  right_ended = false;
858  left_ended = false;
859  l_node = r_node = iter.node;
860  l_dim = r_dim = iter.node_dim;
861  }
862  } while(true);
863  if (best != 0)
864  { iter.node = best; iter.node_dim = best_dim; }
865  else { iter.node = r_node; iter.node_dim = r_dim; }
866  SPATIAL_ASSERT_CHECK(r_dim == (rank() - 1));
867  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
868  SPATIAL_ASSERT_CHECK(iter.node != 0);
869  return iter;
870  }
871 
872  // The next largest key on the ordered dimension is likely to be found in
873  // the children of the current best, so, descend into the children of node
874  // first.
875  template <typename Container>
876  inline ordered_iterator<Container>&
877  decrement_ordered(ordered_iterator<Container>& iter,
878  strict_invariant_tag)
879  {
880  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
881  const typename container_traits<Container>::rank_type
882  rank(iter.rank());
883  const typename container_traits<Container>::key_compare
884  cmp(iter.key_comp());
885  SPATIAL_ASSERT_CHECK(iter.node != 0);
886  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
887  if (header(iter.node))
888  {
889  iter.node = iter.node->parent;
890  iter.node_dim = 0; // root is always compared on dimension 0
891  return maximum_ordered(iter);
892  }
893  // Walk the tree in both directions: one step left, one step right, etc..
894  dimension_type set_dim = 0; // number of values correctly positionned
895  node_ptr best = 0;
896  dimension_type best_dim = 0;
897  node_ptr l_node, r_node; l_node = r_node = iter.node;
898  dimension_type l_dim, r_dim; l_dim = r_dim = iter.node_dim;
899  bool left_ended = false, right_ended = false;
900  do
901  {
902  if (!left_ended)
903  {
904  if (l_node->left != 0
905  && (l_dim > set_dim
906  || best == 0
907  // optimization for strict invarient
908  || cmp(l_dim, const_key(best), const_key(l_node))))
909  {
910  l_node = l_node->left;
911  l_dim = incr_dim(rank, l_dim);
912  while (l_node->right
913  && (l_dim > set_dim
914  || !cmp(l_dim, const_key(iter.node),
915  const_key(l_node))))
916  { l_node = l_node->right; l_dim = incr_dim(rank, l_dim); }
917  if (order_ref(cmp, rank, const_key(l_node),
918  const_key(iter.node))
919  && (best == 0
920  || order_ref(cmp, rank, const_key(best),
921  const_key(l_node))))
922  { best = l_node; best_dim = l_dim; }
923  }
924  else
925  {
926  node_ptr p = l_node->parent;
927  while (!header(p) && p->left == l_node)
928  {
929  l_node = p;
930  l_dim = decr_dim(rank, l_dim);
931  p = l_node->parent;
932  }
933  l_node = p;
934  l_dim = decr_dim(rank, l_dim);
935  if (!header(l_node))
936  {
937  if (order_ref(cmp, rank, const_key(l_node),
938  const_key(iter.node))
939  && (best == 0
940  || order_ref(cmp, rank, const_key(best),
941  const_key(l_node))))
942  { best = l_node; best_dim = l_dim; }
943  }
944  else left_ended = true;
945  }
946  }
947  if (!right_ended)
948  {
949  if (r_node->right
950  && (r_dim > set_dim
951  || !cmp(r_dim, const_key(iter.node), const_key(r_node))))
952  {
953  r_node = r_node->right;
954  r_dim = incr_dim(rank, r_dim);
955  while (r_node->left
956  && (r_dim > set_dim
957  || best == 0
958  // optimization for strict invarient
959  || cmp(r_dim, const_key(best), const_key(r_node))))
960  { r_node = r_node->left; r_dim = incr_dim(rank, r_dim); }
961  if (order_ref(cmp, rank, const_key(r_node),
962  const_key(iter.node))
963  && (best == 0
964  || order_ref(cmp, rank, const_key(best),
965  const_key(r_node))))
966  { best = r_node; best_dim = r_dim; }
967  continue;
968  }
969  else
970  {
971  node_ptr p = r_node->parent;
972  while (!header(p) && p->right == r_node)
973  {
974  r_node = p;
975  r_dim = decr_dim(rank, r_dim);
976  p = r_node->parent;
977  }
978  r_node = p;
979  r_dim = decr_dim(rank, r_dim);
980  if (!header(r_node))
981  {
982  if (order_ref(cmp, rank, const_key(r_node),
983  const_key(iter.node))
984  && (best == 0
985  || order_ref(cmp, rank, const_key(best),
986  const_key(r_node))))
987  { best = r_node; best_dim = r_dim; }
988  continue;
989  }
990  else right_ended = true;
991  }
992  }
993  if (left_ended) // continue to jump over this!
994  {
995  // stepping is over in both directions...
996  if (++set_dim == rank()) break;
997  right_ended = false;
998  left_ended = false;
999  l_node = r_node = iter.node;
1000  l_dim = r_dim = iter.node_dim;
1001  }
1002  } while(true);
1003  if (best != 0)
1004  { iter.node = best; iter.node_dim = best_dim; }
1005  else { iter.node = r_node; iter.node_dim = r_dim; }
1006  SPATIAL_ASSERT_CHECK(r_dim == (rank() - 1));
1007  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
1008  SPATIAL_ASSERT_CHECK(iter.node != 0);
1009  return iter;
1010  }
1011 
1012  template <typename Container>
1013  inline ordered_iterator<Container>&
1014  decrement_ordered(ordered_iterator<Container>& iter)
1015  {
1016  return decrement_ordered
1017  (iter, typename container_traits<Container>::mode_type
1018  ::invariant_category());
1019  }
1020 
1021  // Find the minimum from node and stop when reaching the parent. Iterate in
1022  // left-first fashion.
1023  template <typename Container>
1024  inline ordered_iterator<Container>&
1025  minimum_ordered(ordered_iterator<Container>& iter)
1026  {
1027  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
1028  const typename container_traits<Container>::rank_type
1029  rank(iter.rank());
1030  const typename container_traits<Container>::key_compare
1031  cmp(iter.key_comp());
1032  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
1033  SPATIAL_ASSERT_CHECK(!header(iter.node));
1034  SPATIAL_ASSERT_CHECK(iter.node != 0);
1035  node_ptr end = iter.node->parent;
1036  dimension_type set_dim = 0;
1037  while (iter.node->left != 0)
1038  {
1039  iter.node = iter.node->left;
1040  iter.node_dim = incr_dim(rank, iter.node_dim);
1041  }
1042  node_ptr best = iter.node;
1043  dimension_type best_dim = iter.node_dim;
1044  do
1045  {
1046  node_ptr node = iter.node;
1047  dimension_type node_dim = iter.node_dim;
1048  do
1049  {
1050  if (node->right != 0
1051  && (node_dim > set_dim
1052  || !cmp(node_dim, const_key(best), const_key(node))))
1053  {
1054  node = node->right;
1055  node_dim = incr_dim(rank, node_dim);
1056  while (node->left != 0)
1057  { node = node->left; node_dim = incr_dim(rank, node_dim); }
1058  if (order_ref(cmp, rank,
1059  const_key(node), const_key(best)))
1060  { best = node; best_dim = node_dim; }
1061  }
1062  else
1063  {
1064  node_ptr p = node->parent;
1065  while (p != end && p->right == node)
1066  {
1067  node = p;
1068  node_dim = decr_dim(rank, node_dim);
1069  p = node->parent;
1070  }
1071  node = p;
1072  node_dim = decr_dim(rank, node_dim);
1073  if (node != end
1074  && order_ref(cmp, rank,
1075  const_key(node), const_key(best)))
1076  { best = node; best_dim = node_dim; }
1077  }
1078  } while (node != end);
1079  } while (++set_dim < rank());
1080  iter.node = best; iter.node_dim = best_dim;
1081  SPATIAL_ASSERT_CHECK(best_dim < rank());
1082  SPATIAL_ASSERT_CHECK(best != 0);
1083  SPATIAL_ASSERT_CHECK(!header(best));
1084  return iter;
1085  }
1086 
1089  template<typename Container>
1090  inline ordered_iterator<Container>&
1091  maximum_ordered(ordered_iterator<Container>& iter,
1092  relaxed_invariant_tag)
1093  {
1094  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
1095  const typename container_traits<Container>::rank_type
1096  rank(iter.rank());
1097  const typename container_traits<Container>::key_compare
1098  cmp(iter.key_comp());
1099  SPATIAL_ASSERT_CHECK(iter.node != 0);
1100  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
1101  SPATIAL_ASSERT_CHECK(!header(iter.node));
1102  node_ptr end = iter.node->parent;
1103  dimension_type set_dim = 0;
1104  while (iter.node->right != 0)
1105  {
1106  iter.node = iter.node->right;
1107  iter.node_dim = incr_dim(rank, iter.node_dim);
1108  }
1109  node_ptr best = iter.node;
1110  dimension_type best_dim = iter.node_dim;
1111  do
1112  {
1113  node_ptr node = iter.node;
1114  dimension_type node_dim = iter.node_dim;
1115  do
1116  {
1117  if (node->left != 0
1118  && (node_dim > set_dim
1119  || !cmp(node_dim, const_key(node), const_key(best))))
1120  {
1121  node = node->left;
1122  node_dim = incr_dim(rank, node_dim);
1123  while (node->right != 0)
1124  { node = node->right; node_dim = incr_dim(rank, node_dim); }
1125  if (order_ref(cmp, rank,
1126  const_key(best), const_key(node)))
1127  { best = node; best_dim = node_dim; }
1128  }
1129  else
1130  {
1131  node_ptr p = node->parent;
1132  while (p != end && p->left == node)
1133  {
1134  node = p;
1135  node_dim = decr_dim(rank, node_dim);
1136  p = node->parent;
1137  }
1138  node = p;
1139  node_dim = decr_dim(rank, node_dim);
1140  if (node != end
1141  && order_ref(cmp, rank, const_key(best),
1142  const_key(node)))
1143  { best = node; best_dim = node_dim; }
1144  }
1145  } while (node != end);
1146  } while (++set_dim < rank());
1147  iter.node = best; iter.node_dim = best_dim;
1148  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
1149  SPATIAL_ASSERT_CHECK(iter.node != 0);
1150  SPATIAL_ASSERT_CHECK(!header(iter.node));
1151  return iter;
1152  }
1153 
1156  template<typename Container>
1157  inline ordered_iterator<Container>&
1158  maximum_ordered(ordered_iterator<Container>& iter,
1159  strict_invariant_tag)
1160  {
1161  typedef typename ordered_iterator<Container>::node_ptr node_ptr;
1162  const typename container_traits<Container>::rank_type
1163  rank(iter.rank());
1164  const typename container_traits<Container>::key_compare
1165  cmp(iter.key_comp());
1166  SPATIAL_ASSERT_CHECK(iter.node != 0);
1167  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
1168  SPATIAL_ASSERT_CHECK(!header(iter.node));
1169  node_ptr end = iter.node->parent;
1170  dimension_type set_dim = 0;
1171  while (iter.node->right != 0)
1172  {
1173  iter.node = iter.node->right;
1174  iter.node_dim = incr_dim(rank, iter.node_dim);
1175  }
1176  node_ptr best = iter.node;
1177  dimension_type best_dim = iter.node_dim;
1178  do
1179  {
1180  node_ptr node = iter.node;
1181  dimension_type node_dim = iter.node_dim;
1182  do
1183  {
1184  // optimization for strict invariant
1185  if (node->left != 0 && node_dim > set_dim)
1186  {
1187  node = node->left;
1188  node_dim = incr_dim(rank, node_dim);
1189  while (node->right != 0)
1190  { node = node->right; node_dim = incr_dim(rank, node_dim); }
1191  if (order_ref(cmp, rank,
1192  const_key(best), const_key(node)))
1193  { best = node; best_dim = node_dim; }
1194  }
1195  else
1196  {
1197  node_ptr p = node->parent;
1198  while (p != end && p->left == node)
1199  {
1200  node = p;
1201  node_dim = decr_dim(rank, node_dim);
1202  p = node->parent;
1203  }
1204  node = p;
1205  node_dim = decr_dim(rank, node_dim);
1206  if (node != end
1207  && order_ref(cmp, rank,
1208  const_key(best), const_key(node)))
1209  { best = node; best_dim = node_dim; }
1210  }
1211  } while (node != end);
1212  } while (++set_dim < rank());
1213  iter.node = best; iter.node_dim = best_dim;
1214  SPATIAL_ASSERT_CHECK(iter.node_dim < rank());
1215  SPATIAL_ASSERT_CHECK(iter.node != 0);
1216  SPATIAL_ASSERT_CHECK(!header(iter.node));
1217  return iter;
1218  }
1219 
1220  template <typename Container>
1221  inline ordered_iterator<Container>&
1222  maximum_ordered(ordered_iterator<Container>& iter)
1223  {
1224  return maximum_ordered
1225  (iter, typename container_traits<Container>::mode_type
1226  ::invariant_category());
1227  }
1228  } // namespace details
1229 } // namespace spatial
1230 
1231 #endif // SPATIAL_ORDERED_HPP
spatial::ordered_iterator< const Ct >::ordered_iterator
ordered_iterator(const ordered_iterator< Ct > &iter)
Convertion of mutable iterator into a constant iterator is permitted.
Definition: spatial_ordered.hpp:189
spatial::ordered_iterator< const Ct >::ordered_iterator
ordered_iterator()
Build an uninitialized iterator.
Definition: spatial_ordered.hpp:147
spatial::ordered_iterator
All elements returned by this iterator are ordered from the smallest to the largest value of their ke...
Definition: spatial_ordered.hpp:32
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::rank
const rank_type & rank() const
Return the current Rank type used by the iterator.
Definition: spatial_bidirectional.hpp:107
spatial::ordered_cbegin
ordered_iterator< const Container > ordered_cbegin(const Container &container)
Finds the value in container for which its key has the smallest coordinate over the dimension ordered...
Definition: spatial_ordered.hpp:439
spatial::details::invariant_category
Link::invariant_category invariant_category(const Node< Link > *)
For a given node, this function returns the invariant category of the node.
Definition: spatial_node.hpp:229
spatial::details::order_ref
bool order_ref(const Cmp &cmp, const Rank &rank, const Key &a, const Key &b)
Definition: spatial_ordered.hpp:447
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::node
node_ptr node
The pointer to the current node.
Definition: spatial_bidirectional.hpp:122
spatial::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::container_traits::key_compare
Tp::key_compare key_compare
Comparison functor used to compare two instances of key_type.
Definition: traits.hpp:98
spatial::ordered_iterator::ordered_iterator
ordered_iterator()
Uninitialized iterator.
Definition: spatial_ordered.hpp:46
spatial::ordered_iterator::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: spatial_ordered.hpp:117
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::ordered_iterator::ordered_iterator
ordered_iterator(Ct &container, 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: spatial_ordered.hpp:82
spatial::ordered_iterator::operator++
ordered_iterator< Ct > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: spatial_ordered.hpp:94
spatial::ordered_begin
ordered_iterator< Container > ordered_begin(Container &container)
Finds the value in container for which its key has the smallest coordinate over the dimension ordered...
Definition: spatial_ordered.hpp:407
spatial::ordered_iterator< const Ct >::operator--
ordered_iterator< const Ct > & operator--()
Decrements the iterator and returns the decremented value.
Definition: spatial_ordered.hpp:209
spatial::details::maximum_ordered
ordered_iterator< Container > & maximum_ordered(ordered_iterator< Container > &iter)
Move the iterator given in parameter to the maximum value along the iterator's ordered dimension but ...
Definition: spatial_ordered.hpp:1222
spatial::ordered_iterator< const Ct >
All elements returned by this iterator are ordered from the smallest to the largest value of their ke...
Definition: spatial_ordered.hpp:132
spatial::details::const_key
const Kdtree_link< Value, Value >::key_type & const_key(const Node< Kdtree_link< Value, Value > > *node)
This function converts a pointer on a node into a key for a Kdtree_link type.
Definition: spatial_node.hpp:387
spatial::details::minimum_ordered
ordered_iterator< Container > & minimum_ordered(ordered_iterator< Container > &iter)
Move the iterator given in parameter to the minimum value along the iterator's ordered dimension but ...
Definition: spatial_ordered.hpp:1025
spatial::details::Bidirectional_iterator< container_traits< Ct >::mode_type, container_traits< Ct >::rank_type >::node_dim
dimension_type node_dim
The dimension of the current node.
Definition: spatial_bidirectional.hpp:131
spatial::details::header
bool header(const Node< Link > *x)
Check if node is a header node.
Definition: spatial_node.hpp:96
spatial::ordered_iterator< const Ct >::key_compare
container_traits< Ct >::key_compare key_compare
Alias for the key_compare type used by the iterator.
Definition: spatial_ordered.hpp:144
spatial::details::decrement_ordered
ordered_iterator< Container > & decrement_ordered(ordered_iterator< Container > &iter)
Move the pointer given in parameter to the previous element in the ordered iteration of values along ...
Definition: spatial_ordered.hpp:1014
spatial::ordered_iterator::operator++
ordered_iterator< Ct > & operator++()
Increments the iterator and returns the incremented value.
Definition: spatial_ordered.hpp:89
spatial::ordered_end
ordered_iterator< Container > ordered_end(Container &container)
Finds the past-the-end position in container for this constant iterator.
Definition: spatial_ordered.hpp:352
spatial::ordered_iterator< const Ct >::operator++
ordered_iterator< const Ct > & operator++()
Increments the iterator and returns the incremented value.
Definition: spatial_ordered.hpp:195
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::container_traits::mode_type
Tp::mode_type mode_type
The Link Mode type that is associated with the container.
Definition: traits.hpp:82
spatial::ordered_iterator< const Ct >::Base
details::Const_bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: spatial_ordered.hpp:140
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::details::strict_invariant_tag
Definition: spatial_node.hpp:221
spatial::ordered_iterator< const Ct >::ordered_iterator
ordered_iterator(const Ct &container, typename container_traits< Ct >::const_iterator iter)
The standard way to build this iterator: specify a ordered dimension, an iterator on a container...
Definition: spatial_ordered.hpp:157
spatial::container_traits::rank_type
Tp::rank_type rank_type
The type used to represent the rank of the container.
Definition: traits.hpp:111
spatial::ordered_iterator::operator--
ordered_iterator< Ct > & operator--()
Decrements the iterator and returns the decremented value.
Definition: spatial_ordered.hpp:103
spatial::ordered_iterator< const Ct >::operator++
ordered_iterator< const Ct > operator++(int)
Increments the iterator but returns the value of the iterator before the increment.
Definition: spatial_ordered.hpp:200
spatial::details::relaxed_invariant_tag
The category of invariants for a k-d tree node: strict or relaxed.
Definition: spatial_node.hpp:220
spatial::ordered_iterator::ordered_iterator
ordered_iterator(Ct &container, typename container_traits< Ct >::iterator iter)
The standard way to build this iterator: specify a ordered dimension, an iterator on a container...
Definition: spatial_ordered.hpp:56
spatial::ordered_iterator< const Ct >::key_comp
key_compare key_comp() const
Return the key_comparator used by the iterator.
Definition: spatial_ordered.hpp:223
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::details::decr_dim
dimension_type decr_dim(Rank rank, dimension_type node_dim)
Decrement dimension node_dim, given rank.
Definition: spatial_rank.hpp:79
spatial::ordered_cend
ordered_iterator< const Container > ordered_cend(const Container &container)
Finds the past-the-end position in container for this constant iterator.
Definition: spatial_ordered.hpp:384
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::ordered_iterator< const Ct >::_cmp
key_compare _cmp
The related data for the iterator.
Definition: spatial_ordered.hpp:227
spatial::ordered_iterator< const Ct >::operator--
ordered_iterator< const Ct > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: spatial_ordered.hpp:214
spatial::details::Bidirectional_iterator
A common template for bidirectional iterators that work on identical modes of linking.
Definition: spatial_bidirectional.hpp:33
spatial::ordered_iterator::key_compare
container_traits< Ct >::key_compare key_compare
Definition: spatial_ordered.hpp:43
spatial::ordered_iterator::operator--
ordered_iterator< Ct > operator--(int)
Decrements the iterator but returns the value of the iterator before the decrement.
Definition: spatial_ordered.hpp:108
spatial::ordered_iterator::Base
details::Bidirectional_iterator< typename container_traits< Ct >::mode_type, typename container_traits< Ct >::rank_type > Base
Definition: spatial_ordered.hpp:40
spatial::details::increment_ordered
ordered_iterator< Container > & increment_ordered(ordered_iterator< Container > &iter)
Move the pointer given in parameter to the next element in the ordered iteration of values along the ...
Definition: spatial_ordered.hpp:727
spatial::ordered_iterator::_cmp
key_compare _cmp
The related data for the iterator.
Definition: spatial_ordered.hpp:121
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