mdds
rtree.hpp
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*************************************************************************
3  *
4  * Copyright (c) 2018 Kohei Yoshida
5  *
6  * Permission is hereby granted, free of charge, to any person
7  * obtaining a copy of this software and associated documentation
8  * files (the "Software"), to deal in the Software without
9  * restriction, including without limitation the rights to use,
10  * copy, modify, merge, publish, distribute, sublicense, and/or sell
11  * copies of the Software, and to permit persons to whom the
12  * Software is furnished to do so, subject to the following
13  * conditions:
14  *
15  * The above copyright notice and this permission notice shall be
16  * included in all copies or substantial portions of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25  * OTHER DEALINGS IN THE SOFTWARE.
26  *
27  ************************************************************************/
28 
29 #ifndef INCLUDED_MDDS_RTREE_HPP
30 #define INCLUDED_MDDS_RTREE_HPP
31 
32 #include <deque>
33 #include <vector>
34 #include <cstdlib>
35 #include <string>
36 #include <unordered_set>
37 #include <unordered_map>
38 #include <functional>
39 
40 namespace mdds {
41 
42 namespace detail { namespace rtree {
43 
45 {
49  static constexpr size_t dimensions = 2;
50 
56  static constexpr size_t min_node_size = 40;
57 
62  static constexpr size_t max_node_size = 100;
63 
67  static constexpr size_t max_tree_depth = 100;
68 
73  static constexpr bool enable_forced_reinsertion = true;
74 
80  static constexpr size_t reinsertion_size = 30;
81 };
82 
84 {
91  bool throw_on_first_error = true;
92 
98 };
99 
100 enum class node_type
101 {
102  unspecified,
103  directory_leaf,
104  directory_nonleaf,
105  value
106 };
107 
108 enum class export_tree_type
109 {
114  formatted_node_properties,
115 
125  extent_as_obj,
126 
131  extent_as_svg
132 };
133 
134 enum class search_type
135 {
140  overlap,
141 
146  match,
147 };
148 
149 template<typename _NodePtrT>
151 
152 }} // namespace detail::rtree
153 
154 template<typename _Key, typename _Value, typename _Trait = detail::rtree::default_rtree_trait>
155 class rtree
156 {
157  using trait_type = _Trait;
158 
159  constexpr static size_t max_dist_size = trait_type::max_node_size - trait_type::min_node_size * 2 + 2;
160 
161 public:
162  using key_type = _Key;
163  using value_type = _Value;
164 
165  struct point_type
166  {
167  key_type d[trait_type::dimensions];
168 
169  point_type();
170  point_type(std::initializer_list<key_type> vs);
171 
172  std::string to_string() const;
173 
174  bool operator==(const point_type& other) const;
175  bool operator!=(const point_type& other) const;
176  };
177 
178  struct extent_type
179  {
180  point_type start;
181  point_type end;
182 
183  extent_type();
184  extent_type(const point_type& _start, const point_type& _end);
185 
186  std::string to_string() const;
187 
188  bool is_point() const;
189 
190  bool operator==(const extent_type& other) const;
191  bool operator!=(const extent_type& other) const;
192 
202  bool contains(const point_type& pt) const;
203 
213  bool contains(const extent_type& bb) const;
214 
224  bool intersects(const extent_type& bb) const;
225 
230  bool contains_at_boundary(const extent_type& other) const;
231  };
232 
233  using node_type = detail::rtree::node_type;
234  using export_tree_type = detail::rtree::export_tree_type;
235  using search_type = detail::rtree::search_type;
237 
239  {
240  node_type type;
241  extent_type extent;
242  };
243 
244 private:
245  struct node;
246  struct directory_node;
247 
253  struct node_store
254  {
255  node_type type;
257  node_store* parent;
258  node* node_ptr;
259  size_t count;
260 
261  bool valid_pointer;
262 
263  node_store(const node_store&) = delete;
264  node_store& operator=(const node_store&) = delete;
265 
266  node_store();
267  node_store(node_store&& r);
268  node_store(node_type _type, const extent_type& _extent, node* _node_ptr);
269  ~node_store();
270 
271  node_store clone() const;
272 
273  static node_store create_leaf_directory_node();
274  static node_store create_nonleaf_directory_node();
275  static node_store create_value_node(const extent_type& extent, value_type&& v);
276  static node_store create_value_node(const extent_type& extent, const value_type& v);
277 
278  node_store& operator=(node_store&& other);
279 
285  bool pack();
286 
291  void pack_upward();
292 
293  bool is_directory() const;
294  bool is_root() const;
295  bool exceeds_capacity() const;
296 
297  void swap(node_store& other);
298 
304  void reset_parent_pointers_of_children();
305 
311  void reset_parent_pointers();
312 
313  directory_node* get_directory_node();
314  const directory_node* get_directory_node() const;
315 
316  bool erase_child(const node_store* p);
317  };
318 
319  using dir_store_type = std::deque<node_store>;
320 
321  struct dir_store_segment
322  {
323  typename dir_store_type::iterator begin;
324  typename dir_store_type::iterator end;
325  size_t size;
326 
327  dir_store_segment() : size(0)
328  {}
329 
330  dir_store_segment(
331  typename dir_store_type::iterator _begin, typename dir_store_type::iterator _end, size_t _size)
332  : begin(std::move(_begin)), end(std::move(_end)), size(_size)
333  {}
334  };
335 
336  struct distribution
337  {
338  dir_store_segment g1;
339  dir_store_segment g2;
340 
341  distribution(size_t dist, dir_store_type& nodes)
342  {
343  g1.begin = nodes.begin();
344  g1.end = g1.begin;
345  g1.size = trait_type::min_node_size - 1 + dist;
346  std::advance(g1.end, g1.size);
347 
348  g2.begin = g1.end;
349  g2.end = nodes.end();
350  g2.size = nodes.size() - g1.size;
351  }
352  };
353 
354  struct node
355  {
356  node();
357  node(const node&) = delete;
358  ~node();
359  };
360 
361  struct value_node : public node
362  {
363  value_type value;
364 
365  value_node() = delete;
366  value_node(value_type&& _value);
367  value_node(const value_type& _value);
368  ~value_node();
369  };
370 
375  struct directory_node : public node
376  {
377  dir_store_type children;
378 
379  directory_node(const directory_node&) = delete;
380  directory_node& operator=(const directory_node&) = delete;
381 
382  directory_node();
383  ~directory_node();
384 
385  bool erase(const node_store* p);
386 
387  node_store* get_child_with_minimal_overlap(const extent_type& bb);
388  node_store* get_child_with_minimal_area_enlargement(const extent_type& bb);
389 
390  extent_type calc_extent() const;
391  key_type calc_overlap_cost(const extent_type& bb) const;
392  bool has_leaf_directory() const;
393  };
394 
395  struct orphan_node_entry
396  {
397  node_store ns;
398  size_t depth;
399  };
400 
401  using orphan_node_entries_type = std::deque<orphan_node_entry>;
402 
403  struct insertion_point
404  {
405  node_store* ns;
406  size_t depth;
407  };
408 
409 public:
410  template<typename _NS>
412  {
413  friend class rtree;
414 
415  protected:
416  using node_store_type = _NS;
417 
418  struct entry
419  {
420  node_store_type* ns;
421  size_t depth;
422 
423  entry(node_store_type* _ns, size_t _depth);
424  };
425 
426  using store_type = std::vector<entry>;
427  store_type m_store;
428 
429  void add_node_store(node_store_type* ns, size_t depth);
430  };
431 
432  class const_iterator;
433  class iterator;
434  class search_results;
435 
436  class const_search_results : public search_results_base<const node_store>
437  {
439  using base_type::m_store;
440 
441  public:
442  const_iterator cbegin() const;
443  const_iterator cend() const;
444  const_iterator begin() const;
445  const_iterator end() const;
446  };
447 
448  class search_results : public search_results_base<node_store>
449  {
451  using base_type::m_store;
452 
453  public:
454  iterator begin();
455  iterator end();
456  };
457 
458  template<typename _SelfIter, typename _StoreIter, typename _ValueT>
460  {
461  public:
462  using store_iterator_type = _StoreIter;
463  using self_iterator_type = _SelfIter;
464 
465  protected:
466  store_iterator_type m_pos;
467 
468  iterator_base(store_iterator_type pos);
469 
470  public:
471  // iterator traits
472  using value_type = _ValueT;
473  using pointer = value_type*;
474  using reference = value_type&;
475  using difference_type = std::ptrdiff_t;
476  using iterator_category = std::bidirectional_iterator_tag;
477 
478  bool operator==(const self_iterator_type& other) const;
479  bool operator!=(const self_iterator_type& other) const;
480 
481  self_iterator_type& operator++();
482  self_iterator_type operator++(int);
483 
484  self_iterator_type& operator--();
485  self_iterator_type operator--(int);
486 
487  const extent_type& extent() const;
488  size_t depth() const;
489  };
490 
492  : public iterator_base<
493  const_iterator, typename const_search_results::store_type::const_iterator, const rtree::value_type>
494  {
495  using base_type = iterator_base<
496  const_iterator, typename const_search_results::store_type::const_iterator, const rtree::value_type>;
497 
498  using store_type = typename const_search_results::store_type;
499  using base_type::m_pos;
500  using typename base_type::store_iterator_type;
501 
502  friend class rtree;
503 
504  const_iterator(store_iterator_type pos);
505 
506  public:
507  using typename base_type::value_type;
508 
509  value_type& operator*() const
510  {
511  return static_cast<const value_node*>(m_pos->ns->node_ptr)->value;
512  }
513 
514  value_type* operator->() const
515  {
516  return &operator*();
517  }
518  };
519 
520  class iterator : public iterator_base<iterator, typename search_results::store_type::iterator, rtree::value_type>
521  {
523 
524  using store_type = typename const_search_results::store_type;
525  using base_type::m_pos;
526  using typename base_type::store_iterator_type;
527 
528  friend class rtree;
529 
530  iterator(store_iterator_type pos);
531 
532  public:
533  using typename base_type::value_type;
534 
535  value_type& operator*()
536  {
537  return static_cast<value_node*>(m_pos->ns->node_ptr)->value;
538  }
539 
540  value_type* operator->()
541  {
542  return &operator*();
543  }
544  };
545 
552  {
553  dir_store_type m_store;
554 
555  public:
556  bulk_loader();
557 
558  void insert(const extent_type& extent, value_type&& value);
559  void insert(const extent_type& extent, const value_type& value);
560 
561  void insert(const point_type& position, value_type&& value);
562  void insert(const point_type& position, const value_type& value);
563 
564  rtree pack();
565 
566  private:
567  void pack_level(dir_store_type& store, size_t depth);
568 
569  void insert_impl(const extent_type& extent, value_type&& value);
570  void insert_impl(const extent_type& extent, const value_type& value);
571  };
572 
573  rtree();
574  rtree(rtree&& other);
575  rtree(const rtree& other);
576 
577 private:
578  rtree(node_store&& root); // only used internally by bulk_loader.
579 
580 public:
581  ~rtree();
582 
583  rtree& operator=(const rtree& other);
584 
585  rtree& operator=(rtree&& other);
586 
594  void insert(const extent_type& extent, value_type&& value);
595 
603  void insert(const extent_type& extent, const value_type& value);
604 
612  void insert(const point_type& position, value_type&& value);
613 
621  void insert(const point_type& position, const value_type& value);
622 
634  const_search_results search(const point_type& pt, search_type st) const;
635 
647  search_results search(const point_type& pt, search_type st);
648 
661  const_search_results search(const extent_type& extent, search_type st) const;
662 
675  search_results search(const extent_type& extent, search_type st);
676 
686  void erase(const const_iterator& pos);
687 
697  void erase(const iterator& pos);
698 
706  const extent_type& extent() const;
707 
713  bool empty() const;
714 
720  size_t size() const;
721 
727  void swap(rtree& other);
728 
732  void clear();
733 
740  template<typename _Func>
741  void walk(_Func func) const;
742 
750  void check_integrity(const integrity_check_properties& props) const;
751 
760  std::string export_tree(export_tree_type mode) const;
761 
762 private:
763  void insert_impl(const point_type& start, const point_type& end, value_type&& value);
764  void insert_impl(const point_type& start, const point_type& end, const value_type& value);
765 
766  void erase_impl(const node_store* ns, size_t depth);
767 
773  detail::rtree::ptr_to_string<const node_store*> build_ptr_to_string_map() const;
774 
775  std::string export_tree_formatted() const;
776  std::string export_tree_extent_as_obj() const;
777  std::string export_tree_extent_as_svg() const;
778 
779  void insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths);
780  void insert_dir(node_store&& ns, size_t max_depth);
781 
789  void split_node(node_store* ns);
790 
791  void perform_forced_reinsertion(node_store* ns, std::unordered_set<size_t>& reinserted_depth);
792 
799  void sort_dir_store_by_split_dimension(dir_store_type& children);
800 
801  void sort_dir_store_by_dimension(size_t dim, dir_store_type& children);
802 
803  size_t pick_optimal_distribution(dir_store_type& children) const;
804 
805  insertion_point find_leaf_directory_node_for_insertion(const extent_type& bb);
806  node_store* find_nonleaf_directory_node_for_insertion(const extent_type& bb, size_t max_depth);
807 
808  template<typename _Func>
809  void descend_with_func(_Func func) const;
810 
811  using search_condition_type = std::function<bool(const node_store&)>;
812 
813  template<typename _ResT>
814  void search_descend(
815  size_t depth, const search_condition_type& dir_cond, const search_condition_type& value_cond,
816  typename _ResT::node_store_type& ns, _ResT& results) const;
817 
818  void shrink_tree_upward(node_store* ns, const extent_type& bb_affected);
819 
820 private:
821  node_store m_root;
822 };
823 
824 } // namespace mdds
825 
826 #include "rtree_def.inl"
827 
828 #endif
829 
830 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
static constexpr size_t max_node_size
Definition: rtree.hpp:62
size_t size() const
bool error_on_min_node_size
Definition: rtree.hpp:97
Definition: rtree.hpp:520
bool contains(const point_type &pt) const
Definition: rtree.hpp:459
void clear()
Definition: rtree.hpp:165
static constexpr bool enable_forced_reinsertion
Definition: rtree.hpp:73
const_search_results search(const point_type &pt, search_type st) const
Definition: rtree.hpp:411
void insert(const extent_type &extent, value_type &&value)
Definition: rtree.hpp:238
bool intersects(const extent_type &bb) const
static constexpr size_t min_node_size
Definition: rtree.hpp:56
Definition: rtree.hpp:491
Definition: rtree.hpp:551
Definition: rtree.hpp:155
void erase(const const_iterator &pos)
const extent_type & extent() const
Definition: rtree.hpp:150
bool throw_on_first_error
Definition: rtree.hpp:91
Definition: flat_segment_tree.hpp:46
static constexpr size_t reinsertion_size
Definition: rtree.hpp:80
static constexpr size_t dimensions
Definition: rtree.hpp:49
void walk(_Func func) const
bool contains_at_boundary(const extent_type &other) const
Definition: rtree.hpp:178
Definition: rtree.hpp:436
std::string export_tree(export_tree_type mode) const
static constexpr size_t max_tree_depth
Definition: rtree.hpp:67
Definition: rtree.hpp:448
bool empty() const
void swap(rtree &other)
void check_integrity(const integrity_check_properties &props) const