Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_relaxed_kdtree.hpp
1 // -*- C++ -*-
2 
29 #ifndef SPATIAL_RELAXED_KDTREE_HPP
30 #define SPATIAL_RELAXED_KDTREE_HPP
31 
32 #include <utility> // for std::pair
33 #include <algorithm> // for std::min, std::max, std::equal,
34  // std::lexicographical_compare
35 
36 #include "spatial_ordered.hpp"
37 #include "spatial_mapping.hpp"
38 #include "spatial_equal.hpp"
39 #include "spatial_compress.hpp"
40 #include "spatial_value_compare.hpp"
41 #include "spatial_template_member_swap.hpp"
42 #include "spatial_assert.hpp"
43 #include "spatial_except.hpp"
44 
45 namespace spatial
46 {
61  {
68  template <typename Rank>
69  bool
70  operator()(const Rank&, weight_type left, weight_type right) const
71  {
72  if (left < right)
73  { return ((left + 1) < (right >> 1)); }
74  else
75  { return ((right + 1) < (left >> 1)); }
76  }
77  };
78 
88  {
96  template <typename Rank>
97  bool
98  operator()(const Rank& rank, weight_type left, weight_type right) const
99  {
100  weight_type weight = static_cast<weight_type>(rank());
101  if (weight < 2) weight = 2;
102  if (left < right)
103  { return ((right - left) > weight); }
104  else
105  { return ((left - right) > weight); }
106  }
107  };
108 
120  {
127  template <typename Rank>
128  bool
129  operator()(const Rank&, weight_type left, weight_type right) const
130  {
131  if (left < right)
132  { return ((right - left) > 2); }
133  else
134  { return ((left - right) > 2); }
135  }
136  };
137 
138  namespace details
139  {
146  template <typename Rank, typename Key, typename Value, typename Compare,
147  typename Balancing, typename Alloc>
149  {
150  typedef Relaxed_kdtree<Rank, Key, Value, Compare, Balancing,
151  Alloc> Self;
152 
153  public:
154  // Container intrincsic types
155  typedef Rank rank_type;
156  typedef typename mutate<Key>::type key_type;
157  typedef typename mutate<Value>::type value_type;
159  typedef Compare key_compare;
161  typedef Alloc allocator_type;
162  typedef Balancing balancing_policy;
163 
164  // Container iterator related types
165  typedef Value* pointer;
166  typedef const Value* const_pointer;
167  typedef Value& reference;
168  typedef const Value& const_reference;
169  typedef std::size_t size_type;
170  typedef std::ptrdiff_t difference_type;
171 
172  // Container iterators
173  // Conformant to C++ standard, if Key and Value are the same type then
174  // iterator and const_iterator shall be the same.
177  typedef std::reverse_iterator<iterator> reverse_iterator;
178  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
179 
180  private:
181  typedef typename Alloc::template rebind
183  typedef typename Alloc::template rebind
184  <value_type>::other Value_allocator;
185 
186  // The types used to deal with nodes
187  typedef typename mode_type::node_ptr node_ptr;
189  typedef typename mode_type::link_ptr link_ptr;
191 
192  private:
201  struct Implementation : rank_type
202  {
203  Implementation(const rank_type& rank, const key_compare& compare,
204  const Balancing& balance, const Link_allocator& alloc)
205  : Rank(rank), _compare(balance, compare),
206  _header(alloc, Node<mode_type>()) { initialize(); }
207 
209  : Rank(impl), _compare(impl._compare.base(), impl._compare()),
210  _header(impl._header.base()) { initialize(); }
211 
212  void initialize()
213  {
214  _header().parent = &_header();
215  _header().left = &_header(); // the end marker, *must* not change!
216  _header().right = &_header();
217  _leftmost = &_header(); // the substitute left most pointer
218  }
219 
222  node_ptr _leftmost;
223  } _impl;
224 
225  private:
226  // Internal mutable accessor
227  node_ptr get_header()
228  { return static_cast<node_ptr>(&_impl._header()); }
229 
230  const_node_ptr get_header() const
231  { return static_cast<const_node_ptr>(&_impl._header()); }
232 
233  node_ptr get_leftmost()
234  { return _impl._leftmost; }
235 
236  const_node_ptr get_leftmost() const
237  { return _impl._leftmost; }
238 
239  void set_leftmost(node_ptr x)
240  { _impl._leftmost = x; }
241 
242  node_ptr get_rightmost()
243  { return _impl._header().right; }
244 
245  const_node_ptr get_rightmost() const
246  { return _impl._header().right; }
247 
248  void set_rightmost(node_ptr x)
249  { _impl._header().right = x; }
250 
251  node_ptr get_root()
252  { return _impl._header().parent; }
253 
254  const_node_ptr get_root() const
255  { return _impl._header().parent; }
256 
257  void set_root(node_ptr x)
258  { _impl._header().parent = x; }
259 
260  rank_type& get_rank()
261  { return *static_cast<Rank*>(&_impl); }
262 
263  key_compare& get_compare()
264  { return _impl._compare(); }
265 
266  balancing_policy& get_balancing()
267  { return _impl._compare.base(); }
268 
269  Link_allocator& get_link_allocator()
270  { return _impl._header.base(); }
271 
272  Value_allocator get_value_allocator() const
273  { return _impl._header.base(); }
274 
275  private:
276  // Allocation/Deallocation of nodes
277  struct safe_allocator // RAII for exception-safe memory management
278  {
279  Link_allocator* alloc;
280  link_ptr link;
281  safe_allocator(Link_allocator& a)
282  : alloc(&a), link(0)
283  { link = alloc->allocate(1); } // may throw
284  ~safe_allocator() { if (link) { alloc->deallocate(link, 1); } }
285  link_ptr release() { link_ptr p = link; link=0; return p; }
286  };
287 
288  node_ptr
289  create_node(const value_type& value)
290  {
291  safe_allocator safe(get_link_allocator());
292  // the following may throw. But we have RAII on safe_allocator
293  get_value_allocator().construct(mutate_pointer(&safe.link->value),
294  value);
295  link_ptr node = safe.release();
296  // leave parent uninitialized: its value will change during insertion.
297  node->left = 0;
298  node->right = 0;
299  node->weight = 1;
300  return node; // silently cast into base type node_ptr.
301  }
302 
303  node_ptr
304  clone_node(const_node_ptr node)
305  {
306  node_ptr new_node = create_node(const_value(node));
307  link(new_node)->weight = const_link(node)->weight;
308  return new_node; // silently cast into base type node_ptr.
309  }
310 
314  void
315  destroy_node(node_ptr node)
316  {
317  get_value_allocator().destroy(mutate_pointer(&value(node)));
318  get_link_allocator().deallocate(link(node), 1);
319  }
320 
324  void
326 
327  private:
335  void
336  copy_structure(const Self& other);
337 
346  iterator
347  insert_node(dimension_type node_dim, node_ptr node, node_ptr new_node);
348 
361  node_ptr erase_node(dimension_type dim, node_ptr node);
362 
374  void erase_node_balance(dimension_type dim, node_ptr node);
375 
388  node_ptr balance_node(dimension_type dim, node_ptr node);
389 
390  public:
391  // Iterators standard interface
392  iterator begin()
393  { iterator it; it.node = get_leftmost(); return it; }
394 
395  const_iterator begin() const
396  { const_iterator it; it.node = get_leftmost(); return it; }
397 
398  const_iterator cbegin() const
399  { return begin(); }
400 
401  iterator end()
402  { return iterator(get_header()); }
403 
404  const_iterator end() const
405  { return const_iterator(get_header()); }
406 
407  const_iterator cend() const
408  { return end(); }
409 
410  reverse_iterator rbegin()
411  { return reverse_iterator(end()); }
412 
413  const_reverse_iterator rbegin() const
414  { return const_reverse_iterator(end()); }
415 
416  const_reverse_iterator crbegin() const
417  { return rbegin(); }
418 
419  reverse_iterator rend()
420  { return reverse_iterator(begin()); }
421 
422  const_reverse_iterator rend() const
423  { return const_reverse_iterator(begin()); }
424 
425  const_reverse_iterator crend() const
426  { return rend(); }
427 
428  public:
429  // Functors accessors
433  balancing_policy balancing() const
434  { return _impl._compare.base(); }
435 
440  rank_type rank() const
441  { return *static_cast<const rank_type*>(&_impl); }
442 
447  dimension() const
448  { return rank()(); }
449 
453  key_compare key_comp() const
454  { return _impl._compare(); }
455 
459  value_compare value_comp() const
460  { return value_compare(_impl._compare()); }
461 
465  allocator_type
466  get_allocator() const { return get_value_allocator(); }
467 
471  bool
472  empty() const
473  { return ( get_root() == get_header() ); }
474 
478  size_type
479  size() const
480  {
481  return empty() ? 0
482  : static_cast<const_link_ptr>(get_root())->weight;
483  }
484 
489  size_type
490  count() const
491  { return size(); }
492 
496  size_type
497  max_size() const
498  { return _impl._header.base().max_size(); }
499 
501 
514  iterator
515  find(const key_type& key)
516  {
517  if (empty()) return end();
518  return iterator(first_equal(get_root(), 0, rank(), key_comp(), key)
519  .first);
520  }
521 
522  const_iterator
523  find(const key_type& key) const
524  {
525  if (empty()) return end();
526  return const_iterator(first_equal(get_root(), 0, rank(), key_comp(),
527  key)
528  .first);
529  }
531 
532  public:
534  : _impl(rank_type(), key_compare(), balancing_policy(),
535  Link_allocator()) { }
536 
537  explicit Relaxed_kdtree(const rank_type& rank_)
538  : _impl(rank_, Compare(), Balancing(), Link_allocator())
539  { }
540 
541  Relaxed_kdtree(const rank_type& rank_, const key_compare& compare_)
542  : _impl(rank_, compare_, Balancing(), Link_allocator())
543  { }
544 
545  Relaxed_kdtree(const rank_type& rank_, const key_compare& compare_,
546  const balancing_policy& balancing_)
547  : _impl(rank_, compare_, balancing_, Link_allocator())
548  { }
549 
550  Relaxed_kdtree(const rank_type& rank_, const key_compare& compare_,
551  const balancing_policy& balancing_,
552  const allocator_type& allocator_)
553  : _impl(rank_, compare_, balancing_, allocator_)
554  { }
555 
563  Relaxed_kdtree(const Relaxed_kdtree& other) : _impl(other._impl)
564  { if (!other.empty()) { copy_structure(other); } }
565 
576  operator=(const Relaxed_kdtree& other)
577  {
578  if (&other != this)
579  {
582  ::do_it(get_rank(), other.rank());
584  ::do_it(get_compare(), other.key_comp());
586  ::do_it(get_balancing(), other.balancing());
587  _impl.initialize();
588  if (!other.empty()) { copy_structure(other); }
589  }
590  return *this;
591  }
592 
597  { destroy_all_nodes(); }
598 
599  public:
600  // Mutable functions
608  void
609  swap(Self& other)
610  {
611  if (empty() && other.empty()) return;
613  (get_rank(), other.get_rank());
615  (get_compare(), other.get_compare());
617  (get_balancing(), other.get_balancing());
620  if (_impl._header().parent == &_impl._header())
621  {
622  _impl._header().parent = &other._impl._header();
623  _impl._header().right = &other._impl._header();
624  _impl._leftmost = &other._impl._header();
625  }
626  else if (other._impl._header().parent == &other._impl._header())
627  {
628  other._impl._header().parent = &_impl._header();
629  other._impl._header().right = &_impl._header();
630  other._impl._leftmost = &_impl._header();
631  }
632  std::swap(_impl._header().parent, other._impl._header().parent);
633  std::swap(_impl._header().right, other._impl._header().right);
634  std::swap(_impl._leftmost, other._impl._leftmost);
635  if (_impl._header().parent != &_impl._header())
636  { _impl._header().parent->parent = &_impl._header(); }
637  if (other._impl._header().parent != &other._impl._header())
638  { other._impl._header().parent->parent = &other._impl._header(); }
639  }
640 
644  void
646  {
648  _impl.initialize();
649  }
650 
654  iterator
655  insert(const value_type& value)
656  {
657  node_ptr target_node = create_node(value); // may throw
658  node_ptr node = get_root();
659  if (header(node))
660  {
661  // insert root node in empty tree
662  set_leftmost(target_node);
663  set_rightmost(target_node);
664  set_root(target_node);
665  target_node->parent = node;
666  return iterator(target_node);
667  }
668  else
669  {
670  iterator i = insert_node(0, node, target_node);
671  SPATIAL_ASSERT_INVARIANT(*this);
672  return i;
673  }
674  }
675 
679  template<typename InputIterator>
680  void
681  insert(InputIterator first, InputIterator last)
682  { for (; first != last; ++first) { insert(*first); } }
683 
684  // Deletion
691  void
692  erase(iterator position);
693 
700  size_type
701  erase(const key_type& key);
702  };
703 
707  template <typename Rank, typename Key, typename Value, typename Compare,
708  typename Balancing, typename Alloc>
709  inline void swap
712  { left.swap(right); }
713 
726  template <typename Rank, typename Key, typename Value, typename Compare,
728  typename Balancing, typename Alloc>
729  inline bool
731  <Rank, Key, Value, Compare, Balancing, Alloc>& lhs,
732  const Relaxed_kdtree
733  <Rank, Key, Value, Compare, Balancing, Alloc>& rhs)
734  {
735  return lhs.size() == rhs.size()
736  && std::equal(ordered_begin(lhs), ordered_end(lhs),
737  ordered_begin(rhs));
738  }
739 
740  template <typename Rank, typename Key, typename Value, typename Compare,
741  typename Balancing, typename Alloc>
742  inline bool
744  <Rank, Key, Value, Compare, Balancing, Alloc>& lhs,
745  const Relaxed_kdtree
746  <Rank, Key, Value, Compare, Balancing, Alloc>& rhs)
747  { return !(lhs == rhs); }
749 
762  template <typename Rank, typename Key, typename Value, typename Compare,
764  typename Balancing, typename Alloc>
765  inline bool
767  <Rank, Key, Value, Compare, Balancing, Alloc>& lhs,
768  const Relaxed_kdtree
769  <Rank, Key, Value, Compare, Balancing, Alloc>& rhs)
770  {
771  return std::lexicographical_compare
772  (ordered_begin(lhs), ordered_end(lhs),
773  ordered_begin(rhs), ordered_end(rhs));
774  }
775 
776  template <typename Rank, typename Key, typename Value, typename Compare,
777  typename Balancing, typename Alloc>
778  inline bool
780  <Rank, Key, Value, Compare, Balancing, Alloc>& lhs,
781  const Relaxed_kdtree
782  <Rank, Key, Value, Compare, Balancing, Alloc>& rhs)
783  { return rhs < lhs; }
784 
785  template <typename Rank, typename Key, typename Value, typename Compare,
786  typename Balancing, typename Alloc>
787  inline bool
789  <Rank, Key, Value, Compare, Balancing, Alloc>& lhs,
790  const Relaxed_kdtree
791  <Rank, Key, Value, Compare, Balancing, Alloc>& rhs)
792  { return !(rhs < lhs); }
793 
794  template <typename Rank, typename Key, typename Value, typename Compare,
795  typename Balancing, typename Alloc>
796  inline bool
798  <Rank, Key, Value, Compare, Balancing, Alloc>& lhs,
799  const Relaxed_kdtree
800  <Rank, Key, Value, Compare, Balancing, Alloc>& rhs)
801  { return !(lhs < rhs); }
803 
804  template <typename Rank, typename Key, typename Value, typename Compare,
805  typename Balancing, typename Alloc>
806  inline void
807  Relaxed_kdtree<Rank, Key, Value, Compare, Balancing, Alloc>
808  ::destroy_all_nodes()
809  {
810  node_ptr node = get_root();
811  while (!header(node))
812  {
813  if (node->left != 0) { node = node->left; }
814  else if (node->right != 0) { node = node->right; }
815  else
816  {
817  node_ptr p = node->parent;
818  if (header(p))
819  {
820  set_root(get_header());
821  set_leftmost(get_header());
822  set_rightmost(get_header());
823  }
824  else
825  {
826  if (p->left == node) { p->left = 0; }
827  else { p->right = 0; }
828  }
829  SPATIAL_ASSERT_CHECK(node != 0);
830  SPATIAL_ASSERT_CHECK(p != 0);
831  destroy_node(node);
832  node = p;
833  }
834  }
835  }
836 
837  template <typename Rank, typename Key, typename Value, typename Compare,
838  typename Balancing, typename Alloc>
839  inline void
842  (const Self& other)
843  {
844  SPATIAL_ASSERT_CHECK(!other.empty());
845  SPATIAL_ASSERT_CHECK(empty());
846  const_node_ptr other_node = other.get_root();
847  node_ptr node = clone_node(other_node); // may throw
848  node->parent = get_header();
849  set_root(node);
850  try
851  {
852  while(!header(other_node))
853  {
854  if (other_node->left != 0)
855  {
856  other_node = other_node->left;
857  node_ptr target = clone_node(other_node);
858  target->parent = node;
859  node->left = target;
860  node = node->left;
861  }
862  else if (other_node->right != 0)
863  {
864  other_node = other_node->right;
865  node_ptr target = clone_node(other_node);
866  target->parent = node;
867  node->right = target;
868  node = node->right;
869  }
870  else
871  {
872  const_node_ptr p = other_node->parent;
873  while (!header(p)
874  && (other_node == p->right || p->right == 0))
875  {
876  other_node = p;
877  node = node->parent;
878  p = other_node->parent;
879  }
880  other_node = p;
881  node = node->parent;
882  if (!header(p))
883  {
884  other_node = other_node->right;
885  node_ptr target = clone_node(other_node);
886  target->parent = node;
887  node->right = target;
888  node = node->right;
889  }
890  }
891  }
892  SPATIAL_ASSERT_CHECK(!empty());
893  SPATIAL_ASSERT_CHECK(header(other_node));
894  SPATIAL_ASSERT_CHECK(header(node));
895  }
896  catch (...)
897  { clear(); throw; } // clean-up before re-throw
898  set_leftmost(minimum(get_root()));
899  set_rightmost(maximum(get_root()));
900  }
901 
902  template <typename Rank, typename Key, typename Value, typename Compare,
903  typename Balancing, typename Alloc>
904  inline
908  (dimension_type node_dim, node_ptr node)
909  {
910  const_node_ptr p = node->parent; // Parent is not swapped, node is!
911  bool left_node = (p->left == node);
912  // erase first...
913  erase_node(node_dim, node);
914  node_ptr replacing = header(p) ? p->parent
915  : (left_node ? p->left : p->right);
916  // ...then re-insert.
917  insert_node(node_dim, replacing, node);
918  return header(p) ? p->parent : (left_node ? p->left : p->right);
919  }
920 
921  template <typename Rank, typename Key, typename Value, typename Compare,
922  typename Balancing, typename Alloc>
923  inline
927  (dimension_type node_dim, node_ptr node, node_ptr target_node)
928  {
929  SPATIAL_ASSERT_CHECK(node != 0);
930  SPATIAL_ASSERT_CHECK(!header(node));
931  while (true)
932  {
933  SPATIAL_ASSERT_CHECK
934  ((node->right ? const_link(node->right)->weight : 0)
935  + (node->left ? const_link(node->left)->weight: 0)
936  + 1 == const_link(node)->weight);
937  // Balancing equal values on either side of the tree
938  if (key_comp()(node_dim, const_key(target_node), const_key(node))
939  || (!key_comp()(node_dim,
940  const_key(node), const_key(target_node))
941  && (node->left == 0
942  || (node->right != 0
943  && const_link(node->left)->weight
944  < const_link(node->right)->weight))))
945  {
946  if (node->left == 0)
947  {
948  node->left = target_node;
949  target_node->parent = node;
950  if (get_leftmost() == node)
951  { set_leftmost(target_node); }
952  ++link(node)->weight;
953  break;
954  }
955  else
956  {
957  if(balancing()
958  (rank(),
959  1 + (node->left ? const_link(node->left)->weight : 0),
960  (node->right ? const_link(node->right)->weight : 0)))
961  {
962  node = balance_node(node_dim, node); // recursive!
963  }
964  else
965  {
966  ++link(node)->weight;
967  node = node->left;
968  node_dim = incr_dim(rank(), node_dim);
969  }
970  }
971  }
972  else
973  {
974  if (node->right == 0)
975  {
976  node->right = target_node;
977  target_node->parent = node;
978  if (get_rightmost() == node)
979  { set_rightmost(target_node); }
980  ++link(node)->weight;
981  break;
982  }
983  else
984  {
985  if(balancing()
986  (rank(),
987  (node->left ? const_link(node->left)->weight : 0),
988  1 + (node->right ? const_link(node->right)->weight : 0)))
989  {
990  node = balance_node(node_dim, node); // recursive!
991  }
992  else
993  {
994  ++link(node)->weight;
995  node = node->right;
996  node_dim = incr_dim(rank(), node_dim);
997  }
998  }
999  }
1000  }
1001  SPATIAL_ASSERT_CHECK(target_node != 0);
1002  SPATIAL_ASSERT_CHECK(!header(target_node));
1003  SPATIAL_ASSERT_CHECK(!header(target_node->parent));
1004  SPATIAL_ASSERT_CHECK(target_node->right == 0);
1005  SPATIAL_ASSERT_CHECK(target_node->left == 0);
1006  SPATIAL_ASSERT_CHECK(target_node->parent != 0);
1007  return iterator(target_node);
1008  }
1009 
1010  template <typename Rank, typename Key, typename Value, typename Compare,
1011  typename Balancing, typename Alloc>
1012  inline
1014  ::node_ptr
1017  (dimension_type node_dim, node_ptr node)
1018  {
1019  SPATIAL_ASSERT_CHECK(node != 0);
1020  SPATIAL_ASSERT_CHECK(!header(node));
1021  // never ask to erase a single root node in this function
1022  SPATIAL_ASSERT_CHECK(get_rightmost() != get_leftmost());
1023  node_ptr parent = node->parent;
1024  while (node->right != 0 || node->left != 0)
1025  {
1026  std::pair<node_ptr, dimension_type> candidate;
1027  if (node->left != 0
1028  && (node->right == 0
1029  || const_link(node->right)->weight
1030  < const_link(node->left)->weight))
1031  {
1032  candidate
1033  = maximum_mapping(node->left, incr_dim(rank(), node_dim),
1034  rank(), node_dim, key_comp());
1035  if (get_leftmost() == candidate.first)
1036  { set_leftmost(node); }
1037  if (get_rightmost() == node)
1038  { set_rightmost(candidate.first); }
1039  }
1040  else
1041  {
1042  candidate
1043  = minimum_mapping(node->right,
1044  incr_dim(rank(), node_dim),
1045  rank(), node_dim, key_comp());
1046  if (get_rightmost() == candidate.first)
1047  { set_rightmost(node); }
1048  if (get_leftmost() == node)
1049  { set_leftmost(candidate.first); }
1050  }
1051  swap_node(node, candidate.first);
1052  node = candidate.first;
1053  node_dim = candidate.second;
1054  }
1055  SPATIAL_ASSERT_CHECK(!header(node));
1056  SPATIAL_ASSERT_CHECK(node != 0);
1057  SPATIAL_ASSERT_CHECK(node->right == 0);
1058  SPATIAL_ASSERT_CHECK(node->left == 0);
1059  SPATIAL_ASSERT_CHECK(node->parent != 0);
1060  node_ptr p = node->parent;
1061  if (p->left == node)
1062  {
1063  p->left = 0;
1064  if (get_leftmost() == node) { set_leftmost(p); }
1065  }
1066  else
1067  {
1068  p->right = 0;
1069  if (get_rightmost() == node) { set_rightmost(p); }
1070  }
1071  // decrease count and rebalance parents up to parent
1072  while(node->parent != parent)
1073  {
1074  node = node->parent;
1075  node_dim = decr_dim(rank(), node_dim);
1076  SPATIAL_ASSERT_CHECK(const_link(node)->weight > 1);
1077  --link(node)->weight;
1078  if(balancing()
1079  (rank(),
1080  (node->left ? const_link(node->left)->weight : 0),
1081  (node->right ? const_link(node->right)->weight : 0)))
1082  {
1083  node = balance_node(node_dim, node); // recursive!
1084  }
1085  }
1086  SPATIAL_ASSERT_CHECK(!header(node));
1087  SPATIAL_ASSERT_CHECK(node != 0);
1088  return node;
1089  }
1090 
1091  template <typename Rank, typename Key, typename Value, typename Compare,
1092  typename Balancing, typename Alloc>
1093  inline void
1096  (dimension_type node_dim, node_ptr node)
1097  {
1098  SPATIAL_ASSERT_CHECK(!header(node));
1099  SPATIAL_ASSERT_CHECK(node != 0);
1100  if (node == get_root()
1101  && node->left == 0 && node->right == 0)
1102  {
1103  // if it's a single root tree, erase root quickly
1104  set_root(get_header());
1105  set_leftmost(get_header());
1106  set_rightmost(get_header());
1107  }
1108  else
1109  {
1110  node_ptr p = node->parent;
1111  erase_node(node_dim, node);
1112  node_dim = decr_dim(rank(), node_dim);
1113  while(!header(p))
1114  {
1115  SPATIAL_ASSERT_CHECK(const_link(p)->weight > 1);
1116  --link(p)->weight;
1117  if(balancing()
1118  (rank(),
1119  (node->left ? const_link(node->left)->weight : 0),
1120  (node->right ? const_link(node->right)->weight : 0)))
1121  { p = balance_node(node_dim, p); } // balance node
1122  p = p->parent;
1123  node_dim = decr_dim(rank(), node_dim);
1124  }
1125  }
1126  }
1127 
1128  template <typename Rank, typename Key, typename Value, typename Compare,
1129  typename Balancing, typename Alloc>
1130  inline void
1132  ::erase
1133  (iterator target)
1134  {
1136  node_ptr node = target.node;
1137  dimension_type node_dim = rank()() - 1;
1138  while(!header(node))
1139  {
1140  node_dim = details::incr_dim(rank(), node_dim);
1141  node = node->parent;
1142  }
1143  except::check_iterator(node, get_header());
1144  erase_node_balance(node_dim, target.node);
1145  destroy_node(target.node);
1146  SPATIAL_ASSERT_INVARIANT(*this);
1147  }
1148 
1149  template <typename Rank, typename Key, typename Value, typename Compare,
1150  typename Balancing, typename Alloc>
1151  inline
1153  ::size_type
1155  ::erase
1156  (const key_type& key)
1157  {
1158  details::Equal<Self> equal_query(key_comp(), key);
1159  size_type cnt = 0;
1160  while (!empty())
1161  {
1162  node_ptr node;
1163  dimension_type dim;
1164  details::assign(node, dim,
1165  first_equal(get_root(), 0, rank(), key_comp(), key));
1166  if (node == get_header()) break;
1167  erase_node_balance(dim, node);
1168  destroy_node(node);
1169  ++cnt;
1170  }
1171  SPATIAL_ASSERT_INVARIANT(*this);
1172  return cnt;
1173  }
1174 
1175  } // namespace details
1176 } // namespace spatial
1177 
1178 #endif // SPATIAL_RELAXED_KDTREE_HPP
size_type size() const
Returns the number of elements in the K-d tree.
Relaxed_kdtree & operator=(const Relaxed_kdtree &other)
Assignment of other into the tree, with deep copy.
bool operator<(const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the e...
std::pair< NodePtr, dimension_type > first_equal(NodePtr node, dimension_type dim, Rank rank, KeyCompare key_comp, const Key &key)
A bidirectional iterator traversing all node in the tree in inorder traversal.
A bidirectional iterator traversing all node in the tree in inorder traversal.
Detailed implementation of the kd-tree.
Relaxed_kdtree< Rank, Key, Value, Compare, Balancing, Alloc > Self
std::pair< NodePtr, dimension_type > minimum_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
Move the iterator given in parameter to the minimum value along the iterator's mapping dimension but ...
node_ptr node
The node pointed to by the iterator.
node_ptr clone_node(const_node_ptr node)
node_ptr balance_node(dimension_type dim, node_ptr node)
Attempt to balance the current node.
const_reverse_iterator rend() const
Relaxed_kdtree(const rank_type &rank_, const key_compare &compare_, const balancing_policy &balancing_)
mode_type::const_link_ptr const_link_ptr
~Relaxed_kdtree()
Deallocate all nodes in the destructor.
mode_type::const_node_ptr const_node_ptr
void copy_structure(const Self &other)
Copy the exact sturcture of the sub-tree pointed to by other_node into the current empty tree...
bool operator==(const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch.
std::reverse_iterator< const_iterator > const_reverse_iterator
iterator insert_node(dimension_type node_dim, node_ptr node, node_ptr new_node)
Insert the new node new_node into the tree located at node.
This policy triggers rebalancing for the node when the difference in weight between left or right is ...
const_reverse_iterator crbegin() const
Compress< Link_allocator, Node< mode_type > > _header
The basic node for any tree in the library.
node_ptr erase_node(dimension_type dim, node_ptr node)
Erase the node pointed by node.
bool operator()(const Rank &, weight_type left, weight_type right) const
Rebalancing predicate.
bool operator()(const Rank &, weight_type left, weight_type right) const
Rebalancing predicate.
bool operator<=(const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the e...
size_type count() const
Returns the number of elements in the K-d tree.
ordered_iterator< Container > ordered_begin(Container &container)
Finds the value in container for which its key has the smallest coordinate over the dimension ordered...
void destroy_node(node_ptr node)
Destroy and deallocate node.
bool operator>=(const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the e...
Node< Link > * maximum(Node< Link > *x)
Reach the left most node.
const_reverse_iterator rbegin() const
void swap(Self &other)
Swap the K-d tree content with others.
bool operator()(const Rank &rank, weight_type left, weight_type right) const
Rebalancing predicate.
void clear()
Erase all elements in the K-d tree.
Relaxed_kdtree(const rank_type &rank_, const key_compare &compare_, const balancing_policy &balancing_, const allocator_type &allocator_)
Node * left
A pointer to the left child node of the current node.
const Kdtree_link< Key, Value >::value_type & const_value(const Node< Kdtree_link< Key, Value > > *node)
This function converts a pointer on a node into a value for a Kdtree_link type.
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.
key_compare key_comp() const
Returns the compare function used for the key.
Relaxed_kdtree(const rank_type &rank_, const key_compare &compare_)
bool header(const Node< Link > *x)
Check if node is a header node.
Tp * mutate_pointer(const Tp *p)
A helper functions that mutates pointers.
ValueCompare< value_type, key_compare > value_compare
Node< Link > * minimum(Node< Link > *x)
Reach the left most node.
bool operator!=(const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
The == and != operations is performed by first comparing sizes, and if they match, the elements are compared sequentially using algorithm std::equal, which stops at the first mismatch.
void erase(iterator position)
Deletes the node pointed to by the iterator.
Alloc::template rebind< Relaxed_kdtree_link< Key, Value > >::other Link_allocator
void erase_node_balance(dimension_type dim, node_ptr node)
Erase the node pointed by node and balance tree up to header.
const_iterator find(const key_type &key) const
Find the first node that matches with key and returns an iterator to it found, otherwise it returns a...
iterator insert(const value_type &value)
Insert a single key key in the tree.
bool empty() const
True if the tree is empty.
Value compare functor for container storing pairs of (Key, Mapped) types, such as in spatial::point_m...
balancing_policy balancing() const
Returns the balancing policy for the container.
std::size_t size_type
Defines a positive integral type for counting objects or storing absolute values. ...
Definition: spatial.hpp:66
node_ptr node
The node pointed to by the iterator.
bool operator>(const Kdtree< Rank, Key, Value, Compare, Alloc > &lhs, const Kdtree< Rank, Key, Value, Compare, Alloc > &rhs)
Operations <, >, <= and >= behave as if using algorithm lexicographical_compare, which compares the e...
void insert(InputIterator first, InputIterator last)
Insert a serie of values in the tree at once.
void check_iterator(Ptr1 ptr1, Ptr2 ptr2)
Checks if two iterators are of equal values, if not raises the invalid_iterator exception.
Relaxed_kdtree(const Relaxed_kdtree &other)
Deep copy of other into the new tree.
ordered_iterator< Container > ordered_end(Container &container)
Finds the past-the-end position in container for this constant iterator.
value_compare value_comp() const
Returns the compare function used for the value.
std::size_t weight_type
Defines weight as being a size.
Definition: spatial.hpp:76
spatial::details::Relaxed_kdtree::Implementation _impl
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
Implementation(const rank_type &rank, const key_compare &compare, const Balancing &balance, const Link_allocator &alloc)
Const_node_iterator< mode_type > const_iterator
const Kdtree_link< Key, Value > * const_link(const Node< Kdtree_link< Key, Value > > *node)
This function converts a pointer on a node into a link for a Kdtree_link type.
A policy that balances a node if the difference in weight between left and right is higher than 2 (tw...
void assign(Type1 &first, Type2 &second, const std::pair< Type1, Type2 > &pair)
std::pair< NodePtr, dimension_type > maximum_mapping(NodePtr node, dimension_type dim, Rank rank, dimension_type map, KeyCompare key_comp)
Move the iterator given in parameter to the maximum value along the iterator's mapping dimension but ...
The main namespace used in the library.
Definition: algorithm.hpp:23
Relaxed_kdtree_link< Key, Value > mode_type
void destroy_all_nodes()
Destroy and deallocate all nodes in the container.
dimension_type decr_dim(Rank rank, dimension_type node_dim)
Decrement dimension node_dim, given rank.
const Base & base() const
Accessor to the base class.
void swap_node(Node< Kdtree_link< Key, Value > > *&a, Node< Kdtree_link< Key, Value > > *&b)
Swaps nodes position in the tree.
A policy that balances a node if the difference in weight between left and right is higher than the c...
Value_allocator get_value_allocator() const
Node * right
A pointer to the right child node of the current node.
const_reverse_iterator crend() const
std::reverse_iterator< iterator > reverse_iterator
Kdtree_link< Key, Value > * link(Node< Kdtree_link< Key, Value > > *node)
This function converts a pointer on a node into a link for a Kdtree_link type.
dimension_type dimension() const
Returns the dimension of the container.
node_ptr create_node(const value_type &value)
Alloc::template rebind< value_type >::other Value_allocator
Kdtree_link< Key, Value >::value_type & value(Node< Kdtree_link< Key, Value > > *node)
This function converts a pointer on a node into a value for a Kdtree_link type.
void check_node_iterator(Node *node)
Checks that the node pointed to by an iterator and given as an argument to a function is not null or ...
Node * parent
A pointer to the parent of the current node.
rank_type rank() const
Returns the rank type used internally to get the number of dimensions in the container.
void swap(Kdtree< Rank, Key, Value, Compare, Alloc > &left, Kdtree< Rank, Key, Value, Compare, Alloc > &right)
Swap the content of the tree left and right.
iterator find(const key_type &key)
Find the first node that matches with key and returns an iterator to it found, otherwise it returns a...
allocator_type get_allocator() const
Returns the allocator used by the tree.
dimension_type incr_dim(Rank rank, dimension_type node_dim)
Increment dimension node_dim, given rank.
size_type max_size() const
The maximum number of elements that can be allocated.