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
40namespace mdds {
41
42namespace 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{
92
98};
99
100enum class node_type
101{
102 unspecified,
103 directory_leaf,
104 directory_nonleaf,
105 value
106};
107
108enum class export_tree_type
109{
114 formatted_node_properties,
115
125 extent_as_obj,
126
131 extent_as_svg
132};
133
134enum class search_type
135{
140 overlap,
141
146 match,
147};
148
149template<typename _NodePtrT>
151
152}} // namespace detail::rtree
153
154template<typename KeyT, typename ValueT, typename Traits = detail::rtree::default_rtree_traits>
155class rtree
156{
157 using traits_type = Traits;
158
159 constexpr static size_t max_dist_size = traits_type::max_node_size - traits_type::min_node_size * 2 + 2;
160
161public:
162 using key_type = KeyT;
163 using value_type = ValueT;
164
166 {
167 key_type d[traits_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
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
244private:
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 = traits_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
409public:
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
577private:
578 rtree(node_store&& root); // only used internally by bulk_loader.
579
580public:
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 FuncT>
741 void walk(FuncT func) const;
742
751
760 std::string export_tree(export_tree_type mode) const;
761
762private:
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 FuncT>
809 void descend_with_func(FuncT 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
820private:
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: */
Definition: rtree.hpp:552
Definition: rtree.hpp:494
Definition: rtree.hpp:437
Definition: rtree.hpp:460
Definition: rtree.hpp:521
Definition: rtree.hpp:412
Definition: rtree.hpp:449
Definition: rtree.hpp:156
void walk(FuncT func) const
void clear()
void insert(const extent_type &extent, value_type &&value)
void erase(const iterator &pos)
const_search_results search(const extent_type &extent, search_type st) const
void erase(const const_iterator &pos)
search_results search(const extent_type &extent, search_type st)
std::string export_tree(export_tree_type mode) const
size_t size() const
void swap(rtree &other)
void check_integrity(const integrity_check_properties &props) const
search_results search(const point_type &pt, search_type st)
void insert(const point_type &position, const value_type &value)
void insert(const point_type &position, value_type &&value)
const extent_type & extent() const
void insert(const extent_type &extent, const value_type &value)
bool empty() const
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 dimensions
Definition: rtree.hpp:49
static constexpr size_t max_tree_depth
Definition: rtree.hpp:67
static constexpr size_t max_node_size
Definition: rtree.hpp:62
static constexpr size_t min_node_size
Definition: rtree.hpp:56
static constexpr bool enable_forced_reinsertion
Definition: rtree.hpp:73
bool throw_on_first_error
Definition: rtree.hpp:91
bool error_on_min_node_size
Definition: rtree.hpp:97
Definition: rtree.hpp:150
Definition: rtree.hpp:179
bool contains(const point_type &pt) const
bool intersects(const extent_type &bb) const
bool contains(const extent_type &bb) const
bool contains_at_boundary(const extent_type &other) const
Definition: rtree.hpp:239
Definition: rtree.hpp:166