mdds
Loading...
Searching...
No Matches
rtree.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
3// SPDX-FileCopyrightText: 2018 - 2025 Kohei Yoshida
4//
5// SPDX-License-Identifier: MIT
6
7#pragma once
8
9#include <deque>
10#include <vector>
11#include <cstdlib>
12#include <string>
13#include <unordered_set>
14#include <unordered_map>
15#include <functional>
16
17namespace mdds {
18
19namespace detail { namespace rtree {
20
22{
26 static constexpr size_t dimensions = 2;
27
33 static constexpr size_t min_node_size = 40;
34
39 static constexpr size_t max_node_size = 100;
40
44 static constexpr size_t max_tree_depth = 100;
45
50 static constexpr bool enable_forced_reinsertion = true;
51
57 static constexpr size_t reinsertion_size = 30;
58};
59
76
77enum class node_type
78{
79 unspecified,
80 directory_leaf,
81 directory_nonleaf,
82 value
83};
84
85enum class export_tree_type
86{
91 formatted_node_properties,
92
102 extent_as_obj,
103
108 extent_as_svg
109};
110
111enum class search_type
112{
117 overlap,
118
123 match,
124};
125
126template<typename NodePtrT>
128
129}} // namespace detail::rtree
130
131template<typename KeyT, typename ValueT, typename Traits = detail::rtree::default_rtree_traits>
132class rtree
133{
134 using traits_type = Traits;
135
136 constexpr static size_t max_dist_size = traits_type::max_node_size - traits_type::min_node_size * 2 + 2;
137
138public:
139 using key_type = KeyT;
140 using value_type = ValueT;
141
142 struct point_type
143 {
144 key_type d[traits_type::dimensions];
145
146 point_type();
147 point_type(std::initializer_list<key_type> vs);
148
149 std::string to_string() const;
150
151 bool operator==(const point_type& other) const;
152 };
153
154 struct extent_type
155 {
156 point_type start;
157 point_type end;
158
159 extent_type();
160 extent_type(const point_type& _start, const point_type& _end);
161
162 std::string to_string() const;
163
164 bool is_point() const;
165
166 bool operator==(const extent_type& other) const;
167
177 bool contains(const point_type& pt) const;
178
188 bool contains(const extent_type& bb) const;
189
199 bool intersects(const extent_type& bb) const;
200
205 bool contains_at_boundary(const extent_type& other) const;
206 };
207
208 using node_type = detail::rtree::node_type;
209 using export_tree_type = detail::rtree::export_tree_type;
210 using search_type = detail::rtree::search_type;
211 using integrity_check_properties = detail::rtree::integrity_check_properties;
212
214 {
215 node_type type;
216 extent_type extent;
217 };
218
219private:
220 struct node;
221 struct directory_node;
222
228 struct node_store
229 {
230 node_type type;
232 node_store* parent;
233 node* node_ptr;
234 size_t count;
235
236 bool valid_pointer;
237
238 node_store(const node_store&) = delete;
239 node_store& operator=(const node_store&) = delete;
240
241 node_store();
242 node_store(node_store&& r);
243 node_store(node_type _type, const extent_type& _extent, node* _node_ptr);
244 ~node_store();
245
246 node_store clone() const;
247
248 static node_store create_leaf_directory_node();
249 static node_store create_nonleaf_directory_node();
250 static node_store create_value_node(const extent_type& extent, value_type&& v);
251 static node_store create_value_node(const extent_type& extent, const value_type& v);
252
253 node_store& operator=(node_store&& other);
254
260 bool pack();
261
266 void pack_upward();
267
268 bool is_directory() const;
269 bool is_root() const;
270 bool exceeds_capacity() const;
271
272 void swap(node_store& other);
273
279 void reset_parent_pointers_of_children();
280
286 void reset_parent_pointers();
287
288 directory_node* get_directory_node();
289 const directory_node* get_directory_node() const;
290
291 bool erase_child(const node_store* p);
292 };
293
294 using dir_store_type = std::deque<node_store>;
295
296 struct dir_store_segment
297 {
298 typename dir_store_type::iterator begin;
299 typename dir_store_type::iterator end;
300 size_t size;
301
302 dir_store_segment() : size(0)
303 {}
304
305 dir_store_segment(
306 typename dir_store_type::iterator _begin, typename dir_store_type::iterator _end, size_t _size)
307 : begin(std::move(_begin)), end(std::move(_end)), size(_size)
308 {}
309 };
310
311 struct distribution
312 {
313 dir_store_segment g1;
314 dir_store_segment g2;
315
316 distribution(size_t dist, dir_store_type& nodes)
317 {
318 g1.begin = nodes.begin();
319 g1.end = g1.begin;
320 g1.size = traits_type::min_node_size - 1 + dist;
321 std::advance(g1.end, g1.size);
322
323 g2.begin = g1.end;
324 g2.end = nodes.end();
325 g2.size = nodes.size() - g1.size;
326 }
327 };
328
329 struct node
330 {
331 node();
332 node(const node&) = delete;
333 ~node();
334 };
335
336 struct value_node : public node
337 {
338 value_type value;
339
340 value_node() = delete;
341 value_node(value_type&& _value);
342 value_node(const value_type& _value);
343 ~value_node();
344 };
345
350 struct directory_node : public node
351 {
352 dir_store_type children;
353
354 directory_node(const directory_node&) = delete;
355 directory_node& operator=(const directory_node&) = delete;
356
357 directory_node();
358 ~directory_node();
359
360 bool erase(const node_store* p);
361
362 node_store* get_child_with_minimal_overlap(const extent_type& bb);
363 node_store* get_child_with_minimal_area_enlargement(const extent_type& bb);
364
365 extent_type calc_extent() const;
366 key_type calc_overlap_cost(const extent_type& bb) const;
367 bool has_leaf_directory() const;
368 };
369
370 struct orphan_node_entry
371 {
372 node_store ns;
373 size_t depth;
374 };
375
376 using orphan_node_entries_type = std::deque<orphan_node_entry>;
377
378 struct insertion_point
379 {
380 node_store* ns;
381 size_t depth;
382 };
383
384public:
385 template<typename NS>
387 {
388 friend class rtree;
389
390 protected:
391 using node_store_type = NS;
392
393 struct entry
394 {
395 node_store_type* ns;
396 size_t depth;
397
398 entry(node_store_type* _ns, size_t _depth);
399 };
400
401 using store_type = std::vector<entry>;
402 store_type m_store;
403
404 void add_node_store(node_store_type* ns, size_t depth);
405 };
406
407 class const_iterator;
408 class iterator;
409 class search_results;
410
411 class const_search_results : public search_results_base<const node_store>
412 {
414 using base_type::m_store;
415
416 public:
417 const_iterator cbegin() const;
418 const_iterator cend() const;
419 const_iterator begin() const;
420 const_iterator end() const;
421 };
422
423 class search_results : public search_results_base<node_store>
424 {
425 using base_type = search_results_base<node_store>;
426 using base_type::m_store;
427
428 public:
429 iterator begin();
430 iterator end();
431 };
432
433 template<typename SelfIter, typename StoreIter, typename IterValueT>
434 class iterator_base
435 {
436 public:
437 using store_iterator_type = StoreIter;
438 using self_iterator_type = SelfIter;
439
440 protected:
441 store_iterator_type m_pos;
442
443 iterator_base(store_iterator_type pos);
444
445 public:
446 // iterator traits
447 using value_type = IterValueT;
448 using pointer = value_type*;
449 using reference = value_type&;
450 using difference_type = std::ptrdiff_t;
451 using iterator_category = std::bidirectional_iterator_tag;
452
453 bool operator==(const iterator_base& other) const;
454
455 self_iterator_type& operator++();
456 self_iterator_type operator++(int);
457
458 self_iterator_type& operator--();
459 self_iterator_type operator--(int);
460
461 const extent_type& extent() const;
462 size_t depth() const;
463 };
464
465 class const_iterator
466 : public iterator_base<
467 const_iterator, typename const_search_results::store_type::const_iterator, const rtree::value_type>
468 {
469 using base_type = iterator_base<
470 const_iterator, typename const_search_results::store_type::const_iterator, const rtree::value_type>;
471
472 using store_type = typename const_search_results::store_type;
473 using base_type::m_pos;
474 using typename base_type::store_iterator_type;
475
476 friend class rtree;
477
478 const_iterator(store_iterator_type pos);
479
480 public:
481 using typename base_type::value_type;
482
483 value_type& operator*() const
484 {
485 return static_cast<const value_node*>(m_pos->ns->node_ptr)->value;
486 }
487
488 value_type* operator->() const
489 {
490 return &operator*();
491 }
492 };
493
494 class iterator : public iterator_base<iterator, typename search_results::store_type::iterator, rtree::value_type>
495 {
496 using base_type = iterator_base<iterator, typename search_results::store_type::iterator, 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 iterator(store_iterator_type pos);
505
506 public:
507 using typename base_type::value_type;
508
509 value_type& operator*()
510 {
511 return static_cast<value_node*>(m_pos->ns->node_ptr)->value;
512 }
513
514 value_type* operator->()
515 {
516 return &operator*();
517 }
518 };
519
525 class bulk_loader
526 {
527 dir_store_type m_store;
528
529 public:
530 bulk_loader();
531
532 void insert(const extent_type& extent, value_type&& value);
533 void insert(const extent_type& extent, const value_type& value);
534
535 void insert(const point_type& position, value_type&& value);
536 void insert(const point_type& position, const value_type& value);
537
538 rtree pack();
539
540 private:
541 void pack_level(dir_store_type& store, size_t depth);
542
543 void insert_impl(const extent_type& extent, value_type&& value);
544 void insert_impl(const extent_type& extent, const value_type& value);
545 };
546
547 rtree();
548 rtree(rtree&& other);
549 rtree(const rtree& other);
550
551private:
552 rtree(node_store&& root); // only used internally by bulk_loader.
553
554public:
555 ~rtree();
556
557 rtree& operator=(const rtree& other);
558
559 rtree& operator=(rtree&& other);
560
568 void insert(const extent_type& extent, value_type&& value);
569
577 void insert(const extent_type& extent, const value_type& value);
578
586 void insert(const point_type& position, value_type&& value);
587
595 void insert(const point_type& position, const value_type& value);
596
608 const_search_results search(const point_type& pt, search_type st) const;
609
621 search_results search(const point_type& pt, search_type st);
622
635 const_search_results search(const extent_type& extent, search_type st) const;
636
649 search_results search(const extent_type& extent, search_type st);
650
661
671 void erase(iterator pos);
672
680 const extent_type& extent() const;
681
687 bool empty() const;
688
694 size_t size() const;
695
701 void swap(rtree& other);
702
706 void clear();
707
714 template<typename FuncT>
715 void walk(FuncT func) const;
716
724 void check_integrity(const integrity_check_properties& props) const;
725
734 std::string export_tree(export_tree_type mode) const;
735
736private:
737 void insert_impl(const point_type& start, const point_type& end, value_type&& value);
738 void insert_impl(const point_type& start, const point_type& end, const value_type& value);
739
740 void erase_impl(const node_store* ns, size_t depth);
741
747 detail::rtree::ptr_to_string<const node_store*> build_ptr_to_string_map() const;
748
749 std::string export_tree_formatted() const;
750 std::string export_tree_extent_as_obj() const;
751 std::string export_tree_extent_as_svg() const;
752
753 void insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths);
754 void insert_dir(node_store&& ns, size_t max_depth);
755
763 void split_node(node_store* ns);
764
765 void perform_forced_reinsertion(node_store* ns, std::unordered_set<size_t>& reinserted_depth);
766
773 void sort_dir_store_by_split_dimension(dir_store_type& children);
774
775 void sort_dir_store_by_dimension(size_t dim, dir_store_type& children);
776
777 size_t pick_optimal_distribution(dir_store_type& children) const;
778
779 insertion_point find_leaf_directory_node_for_insertion(const extent_type& bb);
780 node_store* find_nonleaf_directory_node_for_insertion(const extent_type& bb, size_t max_depth);
781
782 template<typename FuncT>
783 void descend_with_func(FuncT func) const;
784
785 using search_condition_type = std::function<bool(const node_store&)>;
786
787 template<typename ResT>
788 void search_descend(
789 size_t depth, const search_condition_type& dir_cond, const search_condition_type& value_cond,
790 typename ResT::node_store_type& ns, ResT& results) const;
791
792 void shrink_tree_upward(node_store* ns, const extent_type& bb_affected);
793
794private:
795 node_store m_root;
796};
797
798} // namespace mdds
799
800#include "rtree_def.inl"
801
802/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition rtree.hpp:468
Definition rtree.hpp:412
Definition rtree.hpp:495
Definition rtree.hpp:387
Definition rtree.hpp:424
void walk(FuncT func) const
void clear()
void insert(const extent_type &extent, value_type &&value)
void erase(iterator pos)
const_search_results search(const extent_type &extent, search_type st) const
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 erase(const_iterator pos)
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:57
static constexpr size_t dimensions
Definition rtree.hpp:26
static constexpr size_t max_tree_depth
Definition rtree.hpp:44
static constexpr size_t max_node_size
Definition rtree.hpp:39
static constexpr size_t min_node_size
Definition rtree.hpp:33
static constexpr bool enable_forced_reinsertion
Definition rtree.hpp:50
bool throw_on_first_error
Definition rtree.hpp:68
bool error_on_min_node_size
Definition rtree.hpp:74
Definition rtree.hpp:127
Definition rtree.hpp:155
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:214
Definition rtree.hpp:143