29 #ifndef INCLUDED_MDDS_RTREE_HPP
30 #define INCLUDED_MDDS_RTREE_HPP
36 #include <unordered_set>
37 #include <unordered_map>
42 namespace detail {
namespace rtree {
100 enum class node_type { unspecified, directory_leaf, directory_nonleaf, value };
102 enum class export_tree_type
108 formatted_node_properties,
128 enum class search_type
143 template<
typename _NodePtrT>
148 template<
typename _Key,
typename _Value,
typename _Trait = detail::rtree::default_rtree_trait>
151 using trait_type = _Trait;
153 constexpr
static size_t max_dist_size = trait_type::max_node_size - trait_type::min_node_size * 2 + 2;
156 using key_type = _Key;
157 using value_type = _Value;
161 key_type d[trait_type::dimensions];
164 point_type(std::initializer_list<key_type> vs);
166 std::string to_string()
const;
168 bool operator== (
const point_type& other)
const;
169 bool operator!= (
const point_type& other)
const;
180 std::string to_string()
const;
182 bool is_point()
const;
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;
241 struct directory_node;
258 node_store(
const node_store&) =
delete;
259 node_store& operator= (
const node_store&) =
delete;
262 node_store(node_store&& r);
263 node_store(node_type _type,
const extent_type& _extent, node* _node_ptr);
266 node_store clone()
const;
268 static node_store create_leaf_directory_node();
269 static node_store create_nonleaf_directory_node();
271 static node_store create_value_node(
const extent_type&
extent,
const value_type& v);
273 node_store& operator= (node_store&& other);
288 bool is_directory()
const;
289 bool is_root()
const;
290 bool exceeds_capacity()
const;
292 void swap(node_store& other);
299 void reset_parent_pointers_of_children();
306 void reset_parent_pointers();
308 directory_node* get_directory_node();
309 const directory_node* get_directory_node()
const;
311 bool erase_child(
const node_store* p);
314 using dir_store_type = std::deque<node_store>;
316 struct dir_store_segment
318 typename dir_store_type::iterator begin;
319 typename dir_store_type::iterator end;
322 dir_store_segment() :
size(0) {}
325 typename dir_store_type::iterator _begin,
326 typename dir_store_type::iterator _end,
328 begin(std::move(_begin)),
329 end(std::move(_end)),
335 dir_store_segment g1;
336 dir_store_segment g2;
338 distribution(
size_t dist, dir_store_type& nodes)
340 g1.begin = nodes.begin();
342 g1.size = trait_type::min_node_size - 1 + dist;
343 std::advance(g1.end, g1.size);
346 g2.end = nodes.end();
347 g2.size = nodes.size() - g1.size;
354 node(
const node&) =
delete;
358 struct value_node :
public node
362 value_node() =
delete;
363 value_node(value_type&& _value);
364 value_node(
const value_type& _value);
372 struct directory_node :
public node
374 dir_store_type children;
376 directory_node(
const directory_node&) =
delete;
377 directory_node& operator=(
const directory_node&) =
delete;
382 bool erase(
const node_store* p);
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);
387 extent_type calc_extent()
const;
388 key_type calc_overlap_cost(
const extent_type& bb)
const;
389 bool has_leaf_directory()
const;
392 struct orphan_node_entry
398 using orphan_node_entries_type = std::deque<orphan_node_entry>;
400 struct insertion_point
408 template<
typename _NS>
413 using node_store_type = _NS;
420 entry(node_store_type* _ns,
size_t _depth);
423 using store_type = std::vector<entry>;
426 void add_node_store(node_store_type* ns,
size_t depth);
436 using base_type::m_store;
447 using base_type::m_store;
453 template<
typename _SelfIter,
typename _StoreIter,
typename _ValueT>
457 using store_iterator_type = _StoreIter;
458 using self_iterator_type = _SelfIter;
461 store_iterator_type m_pos;
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;
473 bool operator== (
const self_iterator_type& other)
const;
474 bool operator!= (
const self_iterator_type& other)
const;
476 self_iterator_type& operator++();
477 self_iterator_type operator++(
int);
479 self_iterator_type& operator--();
480 self_iterator_type operator--(
int);
483 size_t depth()
const;
488 typename const_search_results::store_type::const_iterator,
489 const rtree::value_type>
493 typename const_search_results::store_type::const_iterator,
494 const rtree::value_type>;
496 using store_type =
typename const_search_results::store_type;
497 using typename base_type::store_iterator_type;
498 using base_type::m_pos;
504 using typename base_type::value_type;
506 value_type& operator*()
const
508 return static_cast<const value_node*
>(m_pos->ns->node_ptr)->value;
511 value_type* operator->()
const
519 typename search_results::store_type::iterator,
524 typename search_results::store_type::iterator,
527 using store_type =
typename const_search_results::store_type;
528 using typename base_type::store_iterator_type;
529 using base_type::m_pos;
535 using typename base_type::value_type;
537 value_type& operator*()
539 return static_cast<value_node*
>(m_pos->ns->node_ptr)->value;
542 value_type* operator->()
555 dir_store_type m_store;
563 void insert(
const point_type& position, value_type&& value);
564 void insert(
const point_type& position,
const value_type& value);
569 void pack_level(dir_store_type& store,
size_t depth);
580 rtree(node_store&& root);
742 template<
typename _Func>
769 void erase_impl(
const node_store* ns,
size_t depth);
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;
782 void insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths);
783 void insert_dir(node_store&& ns,
size_t max_depth);
792 void split_node(node_store* ns);
794 void perform_forced_reinsertion(node_store* ns, std::unordered_set<size_t>& reinserted_depth);
802 void sort_dir_store_by_split_dimension(dir_store_type& children);
804 void sort_dir_store_by_dimension(
size_t dim, dir_store_type& children);
806 size_t pick_optimal_distribution(dir_store_type& children)
const;
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);
811 template<
typename _Func>
812 void descend_with_func(_Func func)
const;
814 using search_condition_type = std::function<bool(
const node_store&)>;
816 template<
typename _ResT>
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;
821 void shrink_tree_upward(node_store* ns,
const extent_type& bb_affected);
829 #include "rtree_def.inl"
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 erase(const iterator &pos)
const extent_type & extent() 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)
const_search_results search(const extent_type &extent, search_type st) const
std::string export_tree(export_tree_type mode) 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
Definition: rtree.hpp:416