29#ifndef INCLUDED_MDDS_RTREE_HPP
30#define INCLUDED_MDDS_RTREE_HPP
36#include <unordered_set>
37#include <unordered_map>
42namespace detail {
namespace rtree {
108enum class export_tree_type
114 formatted_node_properties,
134enum class search_type
149template<
typename _NodePtrT>
154template<
typename KeyT,
typename ValueT,
typename Traits = detail::rtree::default_rtree_traits>
157 using traits_type = Traits;
159 constexpr static size_t max_dist_size = traits_type::max_node_size - traits_type::min_node_size * 2 + 2;
162 using key_type = KeyT;
163 using value_type = ValueT;
167 key_type d[traits_type::dimensions];
170 point_type(std::initializer_list<key_type> vs);
172 std::string to_string()
const;
174 bool operator==(
const point_type& other)
const;
175 bool operator!=(
const point_type& other)
const;
186 std::string to_string()
const;
188 bool is_point()
const;
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;
246 struct directory_node;
263 node_store(
const node_store&) =
delete;
264 node_store& operator=(
const node_store&) =
delete;
267 node_store(node_store&& r);
268 node_store(node_type _type,
const extent_type& _extent, node* _node_ptr);
271 node_store clone()
const;
273 static node_store create_leaf_directory_node();
274 static node_store create_nonleaf_directory_node();
276 static node_store create_value_node(
const extent_type&
extent,
const value_type& v);
278 node_store& operator=(node_store&& other);
293 bool is_directory()
const;
294 bool is_root()
const;
295 bool exceeds_capacity()
const;
297 void swap(node_store& other);
304 void reset_parent_pointers_of_children();
311 void reset_parent_pointers();
313 directory_node* get_directory_node();
314 const directory_node* get_directory_node()
const;
316 bool erase_child(
const node_store* p);
319 using dir_store_type = std::deque<node_store>;
321 struct dir_store_segment
323 typename dir_store_type::iterator begin;
324 typename dir_store_type::iterator end;
327 dir_store_segment() :
size(0)
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)
338 dir_store_segment g1;
339 dir_store_segment g2;
341 distribution(
size_t dist, dir_store_type& nodes)
343 g1.begin = nodes.begin();
345 g1.size = traits_type::min_node_size - 1 + dist;
346 std::advance(g1.end, g1.size);
349 g2.end = nodes.end();
350 g2.size = nodes.size() - g1.size;
357 node(
const node&) =
delete;
361 struct value_node :
public node
365 value_node() =
delete;
366 value_node(value_type&& _value);
367 value_node(
const value_type& _value);
375 struct directory_node :
public node
377 dir_store_type children;
379 directory_node(
const directory_node&) =
delete;
380 directory_node& operator=(
const directory_node&) =
delete;
385 bool erase(
const node_store* p);
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);
390 extent_type calc_extent()
const;
391 key_type calc_overlap_cost(
const extent_type& bb)
const;
392 bool has_leaf_directory()
const;
395 struct orphan_node_entry
401 using orphan_node_entries_type = std::deque<orphan_node_entry>;
403 struct insertion_point
410 template<
typename NS>
416 using node_store_type = NS;
423 entry(node_store_type* _ns,
size_t _depth);
426 using store_type = std::vector<entry>;
429 void add_node_store(node_store_type* ns,
size_t depth);
439 using base_type::m_store;
451 using base_type::m_store;
458 template<
typename _SelfIter,
typename _StoreIter,
typename _ValueT>
462 using store_iterator_type = _StoreIter;
463 using self_iterator_type = _SelfIter;
466 store_iterator_type m_pos;
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;
478 bool operator==(
const self_iterator_type& other)
const;
479 bool operator!=(
const self_iterator_type& other)
const;
481 self_iterator_type& operator++();
482 self_iterator_type operator++(
int);
484 self_iterator_type& operator--();
485 self_iterator_type operator--(
int);
488 size_t depth()
const;
493 const_iterator, typename const_search_results::store_type::const_iterator, const rtree::value_type>
496 const_iterator,
typename const_search_results::store_type::const_iterator,
const 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;
507 using typename base_type::value_type;
509 value_type& operator*()
const
511 return static_cast<const value_node*
>(m_pos->ns->node_ptr)->value;
514 value_type* operator->()
const
524 using store_type =
typename const_search_results::store_type;
525 using base_type::m_pos;
526 using typename base_type::store_iterator_type;
533 using typename base_type::value_type;
535 value_type& operator*()
537 return static_cast<value_node*
>(m_pos->ns->node_ptr)->value;
540 value_type* operator->()
553 dir_store_type m_store;
561 void insert(
const point_type& position, value_type&& value);
562 void insert(
const point_type& position,
const value_type& value);
567 void pack_level(dir_store_type& store,
size_t depth);
578 rtree(node_store&& root);
740 template<
typename FuncT>
766 void erase_impl(
const node_store* ns,
size_t depth);
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;
779 void insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths);
780 void insert_dir(node_store&& ns,
size_t max_depth);
789 void split_node(node_store* ns);
791 void perform_forced_reinsertion(node_store* ns, std::unordered_set<size_t>& reinserted_depth);
799 void sort_dir_store_by_split_dimension(dir_store_type& children);
801 void sort_dir_store_by_dimension(
size_t dim, dir_store_type& children);
803 size_t pick_optimal_distribution(dir_store_type& children)
const;
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);
808 template<
typename FuncT>
809 void descend_with_func(FuncT func)
const;
811 using search_condition_type = std::function<bool(
const node_store&)>;
813 template<
typename _ResT>
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;
818 void shrink_tree_upward(node_store* ns,
const extent_type& bb_affected);
826#include "rtree_def.inl"
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 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
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)
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
Definition: rtree.hpp:419