134 using traits_type = Traits;
136 constexpr static size_t max_dist_size = traits_type::max_node_size - traits_type::min_node_size * 2 + 2;
139 using key_type = KeyT;
140 using value_type = ValueT;
144 key_type d[traits_type::dimensions];
147 point_type(std::initializer_list<key_type> vs);
149 std::string to_string()
const;
151 bool operator==(
const point_type& other)
const;
162 std::string to_string()
const;
164 bool is_point()
const;
166 bool operator==(
const extent_type& other)
const;
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;
221 struct directory_node;
238 node_store(
const node_store&) =
delete;
239 node_store& operator=(
const node_store&) =
delete;
242 node_store(node_store&& r);
243 node_store(node_type _type,
const extent_type& _extent, node* _node_ptr);
246 node_store clone()
const;
248 static node_store create_leaf_directory_node();
249 static node_store create_nonleaf_directory_node();
251 static node_store create_value_node(
const extent_type&
extent,
const value_type& v);
253 node_store& operator=(node_store&& other);
268 bool is_directory()
const;
269 bool is_root()
const;
270 bool exceeds_capacity()
const;
272 void swap(node_store& other);
279 void reset_parent_pointers_of_children();
286 void reset_parent_pointers();
288 directory_node* get_directory_node();
289 const directory_node* get_directory_node()
const;
291 bool erase_child(
const node_store* p);
294 using dir_store_type = std::deque<node_store>;
296 struct dir_store_segment
298 typename dir_store_type::iterator begin;
299 typename dir_store_type::iterator end;
302 dir_store_segment() :
size(0)
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)
313 dir_store_segment g1;
314 dir_store_segment g2;
316 distribution(
size_t dist, dir_store_type& nodes)
318 g1.begin = nodes.begin();
320 g1.size = traits_type::min_node_size - 1 + dist;
321 std::advance(g1.end, g1.size);
324 g2.end = nodes.end();
325 g2.size = nodes.size() - g1.size;
332 node(
const node&) =
delete;
336 struct value_node :
public node
340 value_node() =
delete;
341 value_node(value_type&& _value);
342 value_node(
const value_type& _value);
350 struct directory_node :
public node
352 dir_store_type children;
354 directory_node(
const directory_node&) =
delete;
355 directory_node& operator=(
const directory_node&) =
delete;
360 bool erase(
const node_store* p);
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);
365 extent_type calc_extent()
const;
366 key_type calc_overlap_cost(
const extent_type& bb)
const;
367 bool has_leaf_directory()
const;
370 struct orphan_node_entry
376 using orphan_node_entries_type = std::deque<orphan_node_entry>;
378 struct insertion_point
385 template<
typename NS>
391 using node_store_type = NS;
398 entry(node_store_type* _ns,
size_t _depth);
401 using store_type = std::vector<entry>;
404 void add_node_store(node_store_type* ns,
size_t depth);
414 using base_type::m_store;
426 using base_type::m_store;
433 template<
typename SelfIter,
typename StoreIter,
typename IterValueT>
437 using store_iterator_type = StoreIter;
438 using self_iterator_type = SelfIter;
441 store_iterator_type m_pos;
443 iterator_base(store_iterator_type pos);
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;
453 bool operator==(
const iterator_base& other)
const;
455 self_iterator_type& operator++();
456 self_iterator_type operator++(
int);
458 self_iterator_type& operator--();
459 self_iterator_type operator--(
int);
462 size_t depth()
const;
466 :
public iterator_base<
467 const_iterator, typename const_search_results::store_type::const_iterator, const rtree::value_type>
469 using base_type = iterator_base<
470 const_iterator,
typename const_search_results::store_type::const_iterator,
const rtree::value_type>;
472 using store_type =
typename const_search_results::store_type;
473 using base_type::m_pos;
474 using typename base_type::store_iterator_type;
478 const_iterator(store_iterator_type pos);
481 using typename base_type::value_type;
483 value_type& operator*()
const
485 return static_cast<const value_node*
>(m_pos->ns->node_ptr)->value;
488 value_type* operator->()
const
494 class iterator :
public iterator_base<iterator, typename search_results::store_type::iterator, rtree::value_type>
496 using base_type = iterator_base<iterator, typename search_results::store_type::iterator, rtree::value_type>;
498 using store_type =
typename const_search_results::store_type;
499 using base_type::m_pos;
500 using typename base_type::store_iterator_type;
504 iterator(store_iterator_type pos);
507 using typename base_type::value_type;
509 value_type& operator*()
511 return static_cast<value_node*
>(m_pos->ns->node_ptr)->value;
514 value_type* operator->()
527 dir_store_type m_store;
535 void insert(
const point_type& position, value_type&& value);
536 void insert(
const point_type& position,
const value_type& value);
541 void pack_level(dir_store_type& store,
size_t depth);
548 rtree(rtree&& other);
549 rtree(
const rtree& other);
552 rtree(node_store&& root);
557 rtree& operator=(
const rtree& other);
559 rtree& operator=(rtree&& other);
714 template<
typename FuncT>
740 void erase_impl(
const node_store* ns,
size_t depth);
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;
753 void insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths);
754 void insert_dir(node_store&& ns,
size_t max_depth);
763 void split_node(node_store* ns);
765 void perform_forced_reinsertion(node_store* ns, std::unordered_set<size_t>& reinserted_depth);
773 void sort_dir_store_by_split_dimension(dir_store_type& children);
775 void sort_dir_store_by_dimension(
size_t dim, dir_store_type& children);
777 size_t pick_optimal_distribution(dir_store_type& children)
const;
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);
782 template<
typename FuncT>
783 void descend_with_func(FuncT func)
const;
785 using search_condition_type = std::function<bool(
const node_store&)>;
787 template<
typename ResT>
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;
792 void shrink_tree_upward(node_store* ns,
const extent_type& bb_affected);