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 { unspecified, directory_leaf, directory_nonleaf, value };
101 
102 enum class export_tree_type
103 {
108  formatted_node_properties,
109 
119  extent_as_obj,
120 
125  extent_as_svg
126 };
127 
128 enum class search_type
129 {
134  overlap,
135 
140  match,
141 };
142 
143 template<typename _NodePtrT>
145 
146 }}
147 
148 template<typename _Key, typename _Value, typename _Trait = detail::rtree::default_rtree_trait>
149 class rtree
150 {
151  using trait_type = _Trait;
152 
153  constexpr static size_t max_dist_size = trait_type::max_node_size - trait_type::min_node_size * 2 + 2;
154 
155 public:
156  using key_type = _Key;
157  using value_type = _Value;
158 
159  struct point_type
160  {
161  key_type d[trait_type::dimensions];
162 
163  point_type();
164  point_type(std::initializer_list<key_type> vs);
165 
166  std::string to_string() const;
167 
168  bool operator== (const point_type& other) const;
169  bool operator!= (const point_type& other) const;
170  };
171 
172  struct extent_type
173  {
174  point_type start;
175  point_type end;
176 
177  extent_type();
178  extent_type(const point_type& _start, const point_type& _end);
179 
180  std::string to_string() const;
181 
182  bool is_point() const;
183 
184  bool operator== (const extent_type& other) const;
185  bool operator!= (const extent_type& other) const;
186 
196  bool contains(const point_type& pt) const;
197 
207  bool contains(const extent_type& bb) const;
208 
218  bool intersects(const extent_type& bb) const;
219 
224  bool contains_at_boundary(const extent_type& other) const;
225  };
226 
227  using node_type = detail::rtree::node_type;
228  using export_tree_type = detail::rtree::export_tree_type;
229  using search_type = detail::rtree::search_type;
231 
233  {
234  node_type type;
235  extent_type extent;
236  };
237 
238 private:
239 
240  struct node;
241  struct directory_node;
242 
248  struct node_store
249  {
250  node_type type;
252  node_store* parent;
253  node* node_ptr;
254  size_t count;
255 
256  bool valid_pointer;
257 
258  node_store(const node_store&) = delete;
259  node_store& operator= (const node_store&) = delete;
260 
261  node_store();
262  node_store(node_store&& r);
263  node_store(node_type _type, const extent_type& _extent, node* _node_ptr);
264  ~node_store();
265 
266  node_store clone() const;
267 
268  static node_store create_leaf_directory_node();
269  static node_store create_nonleaf_directory_node();
270  static node_store create_value_node(const extent_type& extent, value_type&& v);
271  static node_store create_value_node(const extent_type& extent, const value_type& v);
272 
273  node_store& operator= (node_store&& other);
274 
280  bool pack();
281 
286  void pack_upward();
287 
288  bool is_directory() const;
289  bool is_root() const;
290  bool exceeds_capacity() const;
291 
292  void swap(node_store& other);
293 
299  void reset_parent_pointers_of_children();
300 
306  void reset_parent_pointers();
307 
308  directory_node* get_directory_node();
309  const directory_node* get_directory_node() const;
310 
311  bool erase_child(const node_store* p);
312  };
313 
314  using dir_store_type = std::deque<node_store>;
315 
316  struct dir_store_segment
317  {
318  typename dir_store_type::iterator begin;
319  typename dir_store_type::iterator end;
320  size_t size;
321 
322  dir_store_segment() : size(0) {}
323 
324  dir_store_segment(
325  typename dir_store_type::iterator _begin,
326  typename dir_store_type::iterator _end,
327  size_t _size) :
328  begin(std::move(_begin)),
329  end(std::move(_end)),
330  size(_size) {}
331  };
332 
333  struct distribution
334  {
335  dir_store_segment g1;
336  dir_store_segment g2;
337 
338  distribution(size_t dist, dir_store_type& nodes)
339  {
340  g1.begin = nodes.begin();
341  g1.end = g1.begin;
342  g1.size = trait_type::min_node_size - 1 + dist;
343  std::advance(g1.end, g1.size);
344 
345  g2.begin = g1.end;
346  g2.end = nodes.end();
347  g2.size = nodes.size() - g1.size;
348  }
349  };
350 
351  struct node
352  {
353  node();
354  node(const node&) = delete;
355  ~node();
356  };
357 
358  struct value_node : public node
359  {
360  value_type value;
361 
362  value_node() = delete;
363  value_node(value_type&& _value);
364  value_node(const value_type& _value);
365  ~value_node();
366  };
367 
372  struct directory_node : public node
373  {
374  dir_store_type children;
375 
376  directory_node(const directory_node&) = delete;
377  directory_node& operator=(const directory_node&) = delete;
378 
379  directory_node();
380  ~directory_node();
381 
382  bool erase(const node_store* p);
383 
384  node_store* get_child_with_minimal_overlap(const extent_type& bb);
385  node_store* get_child_with_minimal_area_enlargement(const extent_type& bb);
386 
387  extent_type calc_extent() const;
388  key_type calc_overlap_cost(const extent_type& bb) const;
389  bool has_leaf_directory() const;
390  };
391 
392  struct orphan_node_entry
393  {
394  node_store ns;
395  size_t depth;
396  };
397 
398  using orphan_node_entries_type = std::deque<orphan_node_entry>;
399 
400  struct insertion_point
401  {
402  node_store* ns;
403  size_t depth;
404  };
405 
406 public:
407 
408  template<typename _NS>
410  {
411  friend class rtree;
412  protected:
413  using node_store_type = _NS;
414 
415  struct entry
416  {
417  node_store_type* ns;
418  size_t depth;
419 
420  entry(node_store_type* _ns, size_t _depth);
421  };
422 
423  using store_type = std::vector<entry>;
424  store_type m_store;
425 
426  void add_node_store(node_store_type* ns, size_t depth);
427  };
428 
429  class const_iterator;
430  class iterator;
431  class search_results;
432 
433  class const_search_results : public search_results_base<const node_store>
434  {
436  using base_type::m_store;
437  public:
438  const_iterator cbegin() const;
439  const_iterator cend() const;
440  const_iterator begin() const;
441  const_iterator end() const;
442  };
443 
444  class search_results : public search_results_base<node_store>
445  {
447  using base_type::m_store;
448  public:
449  iterator begin();
450  iterator end();
451  };
452 
453  template<typename _SelfIter, typename _StoreIter, typename _ValueT>
455  {
456  public:
457  using store_iterator_type = _StoreIter;
458  using self_iterator_type = _SelfIter;
459 
460  protected:
461  store_iterator_type m_pos;
462 
463  iterator_base(store_iterator_type pos);
464 
465  public:
466  // iterator traits
467  using value_type = _ValueT;
468  using pointer = value_type*;
469  using reference = value_type&;
470  using difference_type = std::ptrdiff_t;
471  using iterator_category = std::bidirectional_iterator_tag;
472 
473  bool operator== (const self_iterator_type& other) const;
474  bool operator!= (const self_iterator_type& other) const;
475 
476  self_iterator_type& operator++();
477  self_iterator_type operator++(int);
478 
479  self_iterator_type& operator--();
480  self_iterator_type operator--(int);
481 
482  const extent_type& extent() const;
483  size_t depth() const;
484  };
485 
487  const_iterator,
488  typename const_search_results::store_type::const_iterator,
489  const rtree::value_type>
490  {
491  using base_type = iterator_base<
493  typename const_search_results::store_type::const_iterator,
494  const rtree::value_type>;
495 
496  using store_type = typename const_search_results::store_type;
497  using typename base_type::store_iterator_type;
498  using base_type::m_pos;
499 
500  friend class rtree;
501 
502  const_iterator(store_iterator_type pos);
503  public:
504  using typename base_type::value_type;
505 
506  value_type& operator*() const
507  {
508  return static_cast<const value_node*>(m_pos->ns->node_ptr)->value;
509  }
510 
511  value_type* operator->() const
512  {
513  return &operator*();
514  }
515  };
516 
517  class iterator : public iterator_base<
518  iterator,
519  typename search_results::store_type::iterator,
520  rtree::value_type>
521  {
522  using base_type = iterator_base<
523  iterator,
524  typename search_results::store_type::iterator,
525  rtree::value_type>;
526 
527  using store_type = typename const_search_results::store_type;
528  using typename base_type::store_iterator_type;
529  using base_type::m_pos;
530 
531  friend class rtree;
532 
533  iterator(store_iterator_type pos);
534  public:
535  using typename base_type::value_type;
536 
537  value_type& operator*()
538  {
539  return static_cast<value_node*>(m_pos->ns->node_ptr)->value;
540  }
541 
542  value_type* operator->()
543  {
544  return &operator*();
545  }
546  };
547 
554  {
555  dir_store_type m_store;
556 
557  public:
558  bulk_loader();
559 
560  void insert(const extent_type& extent, value_type&& value);
561  void insert(const extent_type& extent, const value_type& value);
562 
563  void insert(const point_type& position, value_type&& value);
564  void insert(const point_type& position, const value_type& value);
565 
566  rtree pack();
567 
568  private:
569  void pack_level(dir_store_type& store, size_t depth);
570 
571  void insert_impl(const extent_type& extent, value_type&& value);
572  void insert_impl(const extent_type& extent, const value_type& value);
573  };
574 
575  rtree();
576  rtree(rtree&& other);
577  rtree(const rtree& other);
578 
579 private:
580  rtree(node_store&& root); // only used internally by bulk_loader.
581 
582 public:
583  ~rtree();
584 
585  rtree& operator= (const rtree& other);
586 
587  rtree& operator= (rtree&& other);
588 
596  void insert(const extent_type& extent, value_type&& value);
597 
605  void insert(const extent_type& extent, const value_type& value);
606 
614  void insert(const point_type& position, value_type&& value);
615 
623  void insert(const point_type& position, const value_type& value);
624 
636  const_search_results search(const point_type& pt, search_type st) const;
637 
649  search_results search(const point_type& pt, search_type st);
650 
663  const_search_results search(const extent_type& extent, search_type st) const;
664 
677  search_results search(const extent_type& extent, search_type st);
678 
688  void erase(const const_iterator& pos);
689 
699  void erase(const iterator& pos);
700 
708  const extent_type& extent() const;
709 
715  bool empty() const;
716 
722  size_t size() const;
723 
729  void swap(rtree& other);
730 
734  void clear();
735 
742  template<typename _Func>
743  void walk(_Func func) const;
744 
752  void check_integrity(const integrity_check_properties& props) const;
753 
762  std::string export_tree(export_tree_type mode) const;
763 
764 private:
765 
766  void insert_impl(const point_type& start, const point_type& end, value_type&& value);
767  void insert_impl(const point_type& start, const point_type& end, const value_type& value);
768 
769  void erase_impl(const node_store* ns, size_t depth);
770 
776  detail::rtree::ptr_to_string<const node_store*> build_ptr_to_string_map() const;
777 
778  std::string export_tree_formatted() const;
779  std::string export_tree_extent_as_obj() const;
780  std::string export_tree_extent_as_svg() const;
781 
782  void insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths);
783  void insert_dir(node_store&& ns, size_t max_depth);
784 
792  void split_node(node_store* ns);
793 
794  void perform_forced_reinsertion(node_store* ns, std::unordered_set<size_t>& reinserted_depth);
795 
802  void sort_dir_store_by_split_dimension(dir_store_type& children);
803 
804  void sort_dir_store_by_dimension(size_t dim, dir_store_type& children);
805 
806  size_t pick_optimal_distribution(dir_store_type& children) const;
807 
808  insertion_point find_leaf_directory_node_for_insertion(const extent_type& bb);
809  node_store* find_nonleaf_directory_node_for_insertion(const extent_type& bb, size_t max_depth);
810 
811  template<typename _Func>
812  void descend_with_func(_Func func) const;
813 
814  using search_condition_type = std::function<bool(const node_store&)>;
815 
816  template<typename _ResT>
817  void search_descend(
818  size_t depth, const search_condition_type& dir_cond, const search_condition_type& value_cond,
819  typename _ResT::node_store_type& ns, _ResT& results) const;
820 
821  void shrink_tree_upward(node_store* ns, const extent_type& bb_affected);
822 
823 private:
824  node_store m_root;
825 };
826 
827 } // namespace mdds
828 
829 #include "rtree_def.inl"
830 
831 #endif
832 
833 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: rtree.hpp:554
Definition: rtree.hpp:490
Definition: rtree.hpp:434
Definition: rtree.hpp:455
Definition: rtree.hpp:521
Definition: rtree.hpp:410
Definition: rtree.hpp:445
Definition: rtree.hpp:150
search_results search(const point_type &pt, search_type st)
void walk(_Func func) const
void swap(rtree &other)
void erase(const iterator &pos)
const extent_type & extent() const
bool empty() const
void insert(const extent_type &extent, const value_type &value)
void insert(const point_type &position, const value_type &value)
void check_integrity(const integrity_check_properties &props) const
search_results search(const extent_type &extent, search_type st)
void erase(const const_iterator &pos)
void insert(const extent_type &extent, value_type &&value)
void clear()
const_search_results search(const extent_type &extent, search_type st) const
std::string export_tree(export_tree_type mode) const
size_t size() const
void insert(const point_type &position, value_type &&value)
const_search_results search(const point_type &pt, search_type st) const
static constexpr size_t reinsertion_size
Definition: rtree.hpp:80
static constexpr size_t max_tree_depth
Definition: rtree.hpp:67
static constexpr size_t min_node_size
Definition: rtree.hpp:56
static constexpr bool enable_forced_reinsertion
Definition: rtree.hpp:73
static constexpr size_t max_node_size
Definition: rtree.hpp:62
static constexpr size_t dimensions
Definition: rtree.hpp:49
bool throw_on_first_error
Definition: rtree.hpp:91
bool error_on_min_node_size
Definition: rtree.hpp:97
Definition: rtree.hpp:144
Definition: rtree.hpp:173
bool contains_at_boundary(const extent_type &other) const
bool contains(const point_type &pt) const
bool intersects(const extent_type &bb) const
bool contains(const extent_type &bb) const
Definition: rtree.hpp:233
Definition: rtree.hpp:160