1 // Boost.Geometry Index
3 // R-tree R*-tree insert algorithm implementation
5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
7 // This file was modified by Oracle on 2019.
8 // Modifications copyright (c) 2019 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
18 #include <boost/core/ignore_unused.hpp>
20 #include <boost/geometry/index/detail/algorithms/content.hpp>
22 namespace boost { namespace geometry { namespace index {
24 namespace detail { namespace rtree { namespace visitors {
28 // Utility to distinguish between default and non-default index strategy
29 template <typename Point1, typename Point2, typename Strategy>
30 struct comparable_distance_point_point
32 typedef typename Strategy::comparable_distance_point_point_strategy_type strategy_type;
33 typedef typename geometry::comparable_distance_result
35 Point1, Point2, strategy_type
38 static inline strategy_type get_strategy(Strategy const& strategy)
40 return strategy.get_comparable_distance_point_point_strategy();
44 template <typename Point1, typename Point2>
45 struct comparable_distance_point_point<Point1, Point2, default_strategy>
47 typedef default_strategy strategy_type;
48 typedef typename geometry::default_comparable_distance_result
53 static inline strategy_type get_strategy(default_strategy const& )
55 return strategy_type();
59 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
60 class remove_elements_to_reinsert
63 typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
64 typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
65 typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
67 typedef typename Options::parameters_type parameters_type;
69 //typedef typename Allocators::internal_node_pointer internal_node_pointer;
70 typedef internal_node * internal_node_pointer;
72 template <typename ResultElements, typename Node>
73 static inline void apply(ResultElements & result_elements,
75 internal_node_pointer parent,
76 size_t current_child_index,
77 parameters_type const& parameters,
78 Translator const& translator,
79 Allocators & allocators)
81 typedef typename rtree::elements_type<Node>::type elements_type;
82 typedef typename elements_type::value_type element_type;
83 typedef typename geometry::point_type<Box>::type point_type;
84 typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
85 // TODO: awulkiew - change second point_type to the point type of the Indexable?
86 typedef rstar::comparable_distance_point_point
88 point_type, point_type, strategy_type
89 > comparable_distance_pp;
90 typedef typename comparable_distance_pp::result_type comparable_distance_type;
92 elements_type & elements = rtree::elements(n);
94 const size_t elements_count = parameters.get_max_elements() + 1;
95 const size_t reinserted_elements_count = (::std::min)(parameters.get_reinserted_elements(), elements_count - parameters.get_min_elements());
97 BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
98 BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
99 BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
101 // calculate current node's center
102 point_type node_center;
103 geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center);
105 // fill the container of centers' distances of children from current node's center
106 typedef typename index::detail::rtree::container_from_elements_type<
108 std::pair<comparable_distance_type, element_type>
109 >::type sorted_elements_type;
111 sorted_elements_type sorted_elements;
112 // If constructor is used instead of resize() MS implementation leaks here
113 sorted_elements.reserve(elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
115 typename comparable_distance_pp::strategy_type
116 cdist_strategy = comparable_distance_pp::get_strategy(index::detail::get_strategy(parameters));
118 for ( typename elements_type::const_iterator it = elements.begin() ;
119 it != elements.end() ; ++it )
121 point_type element_center;
122 geometry::centroid( rtree::element_indexable(*it, translator), element_center);
123 sorted_elements.push_back(std::make_pair(
124 geometry::comparable_distance(node_center, element_center, cdist_strategy),
125 *it)); // MAY THROW (V, E: copy)
128 // sort elements by distances from center
130 sorted_elements.begin(),
131 sorted_elements.begin() + reinserted_elements_count,
132 sorted_elements.end(),
133 distances_dsc<comparable_distance_type, element_type>); // MAY THROW, BASIC (V, E: copy)
135 // copy elements which will be reinserted
136 result_elements.clear();
137 result_elements.reserve(reinserted_elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
138 for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() ;
139 it != sorted_elements.begin() + reinserted_elements_count ; ++it )
141 result_elements.push_back(it->second); // MAY THROW (V, E: copy)
146 // copy remaining elements to the current node
148 elements.reserve(elements_count - reinserted_elements_count); // SHOULDN'T THROW (new_size <= old size)
149 for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() + reinserted_elements_count;
150 it != sorted_elements.end() ; ++it )
152 elements.push_back(it->second); // MAY THROW (V, E: copy)
159 for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ;
160 it != sorted_elements.end() ; ++it )
162 destroy_element<Value, Options, Translator, Box, Allocators>::apply(it->second, allocators);
165 BOOST_RETHROW // RETHROW
169 ::boost::ignore_unused(parameters);
173 template <typename Distance, typename El>
174 static inline bool distances_asc(
175 std::pair<Distance, El> const& d1,
176 std::pair<Distance, El> const& d2)
178 return d1.first < d2.first;
181 template <typename Distance, typename El>
182 static inline bool distances_dsc(
183 std::pair<Distance, El> const& d1,
184 std::pair<Distance, El> const& d2)
186 return d1.first > d2.first;
190 template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators>
191 struct level_insert_elements_type
193 typedef typename rtree::elements_type<
194 typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
198 template <typename Value, typename Options, typename Box, typename Allocators>
199 struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators>
201 typedef typename rtree::elements_type<
202 typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
206 template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
207 struct level_insert_base
208 : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
210 typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
211 typedef typename base::node node;
212 typedef typename base::internal_node internal_node;
213 typedef typename base::leaf leaf;
215 typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type;
216 typedef typename index::detail::rtree::container_from_elements_type<
218 typename elements_type::value_type
219 >::type result_elements_type;
221 typedef typename Options::parameters_type parameters_type;
223 typedef typename Allocators::node_pointer node_pointer;
224 typedef typename Allocators::size_type size_type;
226 inline level_insert_base(node_pointer & root,
227 size_type & leafs_level,
228 Element const& element,
229 parameters_type const& parameters,
230 Translator const& translator,
231 Allocators & allocators,
232 size_type relative_level)
233 : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
234 , result_relative_level(0)
237 template <typename Node>
238 inline void handle_possible_reinsert_or_split_of_root(Node &n)
240 BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
242 result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
245 if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
247 // node isn't root node
248 if ( !base::m_traverse_data.current_is_root() )
250 // NOTE: exception-safety
251 // After an exception result_elements may contain garbage, don't use it
252 rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
254 base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
255 base::m_parameters, base::m_translator, base::m_allocators); // MAY THROW, BASIC (V, E: alloc, copy)
260 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*base::m_root_node), "node should be the root node");
261 base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc)
266 template <typename Node>
267 inline void handle_possible_split(Node &n) const
270 if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
272 base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc)
276 template <typename Node>
277 inline void recalculate_aabb_if_necessary(Node const& n) const
279 if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
281 // calulate node's new box
286 template <typename Node>
287 inline void recalculate_aabb(Node const& n) const
289 base::m_traverse_data.current_element().first =
290 elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(),
292 index::detail::get_strategy(base::m_parameters));
295 inline void recalculate_aabb(leaf const& n) const
297 base::m_traverse_data.current_element().first =
298 values_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(),
300 index::detail::get_strategy(base::m_parameters));
303 size_type result_relative_level;
304 result_elements_type result_elements;
307 template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
309 : public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators>
311 typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
312 typedef typename base::node node;
313 typedef typename base::internal_node internal_node;
314 typedef typename base::leaf leaf;
316 typedef typename Options::parameters_type parameters_type;
318 typedef typename Allocators::node_pointer node_pointer;
319 typedef typename Allocators::size_type size_type;
321 inline level_insert(node_pointer & root,
322 size_type & leafs_level,
323 Element const& element,
324 parameters_type const& parameters,
325 Translator const& translator,
326 Allocators & allocators,
327 size_type relative_level)
328 : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
331 inline void operator()(internal_node & n)
333 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
335 if ( base::m_traverse_data.current_level < base::m_level )
337 // next traversing step
338 base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc)
341 if ( 0 < InsertIndex )
343 BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
345 if ( base::m_traverse_data.current_level == base::m_level - 1 )
347 base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
353 BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
357 // push new child node
358 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy)
362 // NOTE: exception-safety
363 // if the insert fails above, the element won't be stored in the tree, so delete it
365 rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
366 rtree::apply_visitor(del_v, *base::m_element.second);
368 BOOST_RETHROW // RETHROW
373 if ( 0 == InsertIndex )
375 base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
377 // not the first insert
380 base::handle_possible_split(n); // MAY THROW (E: alloc, N: alloc)
384 base::recalculate_aabb_if_necessary(n);
387 inline void operator()(leaf &)
389 BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
393 template <size_t InsertIndex, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
394 struct level_insert<InsertIndex, Value, Value, Options, Translator, Box, Allocators>
395 : public level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators>
397 typedef level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators> base;
398 typedef typename base::node node;
399 typedef typename base::internal_node internal_node;
400 typedef typename base::leaf leaf;
402 typedef typename Options::parameters_type parameters_type;
404 typedef typename Allocators::node_pointer node_pointer;
405 typedef typename Allocators::size_type size_type;
407 inline level_insert(node_pointer & root,
408 size_type & leafs_level,
410 parameters_type const& parameters,
411 Translator const& translator,
412 Allocators & allocators,
413 size_type relative_level)
414 : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
417 inline void operator()(internal_node & n)
419 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
420 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
422 // next traversing step
423 base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc)
425 BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
427 if ( base::m_traverse_data.current_level == base::m_level - 1 )
429 base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
432 base::recalculate_aabb_if_necessary(n);
435 inline void operator()(leaf & n)
437 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
439 BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
440 base::m_level == (std::numeric_limits<size_t>::max)(),
443 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
445 base::handle_possible_split(n); // MAY THROW (V: alloc, copy, N: alloc)
449 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
450 struct level_insert<0, Value, Value, Options, Translator, Box, Allocators>
451 : public level_insert_base<0, Value, Value, Options, Translator, Box, Allocators>
453 typedef level_insert_base<0, Value, Value, Options, Translator, Box, Allocators> base;
454 typedef typename base::node node;
455 typedef typename base::internal_node internal_node;
456 typedef typename base::leaf leaf;
458 typedef typename Options::parameters_type parameters_type;
460 typedef typename Allocators::node_pointer node_pointer;
461 typedef typename Allocators::size_type size_type;
463 inline level_insert(node_pointer & root,
464 size_type & leafs_level,
466 parameters_type const& parameters,
467 Translator const& translator,
468 Allocators & allocators,
469 size_type relative_level)
470 : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
473 inline void operator()(internal_node & n)
475 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
477 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
480 // next traversing step
481 base::traverse(*this, n); // MAY THROW (V: alloc, copy, N: alloc)
483 base::recalculate_aabb_if_necessary(n);
486 inline void operator()(leaf & n)
488 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
490 BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
491 base::m_level == (std::numeric_limits<size_t>::max)(),
494 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
496 base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (V: alloc, copy, N: alloc)
498 base::recalculate_aabb_if_necessary(n);
504 // R*-tree insert visitor
505 // After passing the Element to insert visitor the Element is managed by the tree
506 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
507 // because this visitor may delete it
508 template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
509 class insert<Element, Value, Options, Translator, Box, Allocators, insert_reinsert_tag>
510 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
512 typedef typename Options::parameters_type parameters_type;
514 typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
515 typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
516 typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
518 typedef typename Allocators::node_pointer node_pointer;
519 typedef typename Allocators::size_type size_type;
522 inline insert(node_pointer & root,
523 size_type & leafs_level,
524 Element const& element,
525 parameters_type const& parameters,
526 Translator const& translator,
527 Allocators & allocators,
528 size_type relative_level = 0)
529 : m_root(root), m_leafs_level(leafs_level), m_element(element)
530 , m_parameters(parameters), m_translator(translator)
531 , m_relative_level(relative_level), m_allocators(allocators)
534 inline void operator()(internal_node & n)
536 boost::ignore_unused(n);
537 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root");
539 // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
540 if ( m_parameters.get_reinserted_elements() > 0 )
542 rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
543 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
545 rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
547 if ( !lins_v.result_elements.empty() )
549 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
554 visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v(
555 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
557 rtree::apply_visitor(ins_v, *m_root);
561 inline void operator()(leaf & n)
563 boost::ignore_unused(n);
564 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root");
566 // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
567 if ( m_parameters.get_reinserted_elements() > 0 )
569 rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
570 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
572 rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
574 // we're in the root, so root should be split and there should be no elements to reinsert
575 BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
579 visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v(
580 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
582 rtree::apply_visitor(ins_v, *m_root);
587 template <typename Elements>
588 inline void recursive_reinsert(Elements & elements, size_t relative_level)
590 typedef typename Elements::value_type element_type;
592 // reinsert children starting from the minimum distance
593 typename Elements::reverse_iterator it = elements.rbegin();
594 for ( ; it != elements.rend() ; ++it)
596 rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v(
597 m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
601 rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
606 for ( ; it != elements.rend() ; ++it)
607 rtree::destroy_element<Value, Options, Translator, Box, Allocators>::apply(*it, m_allocators);
608 BOOST_RETHROW // RETHROW
612 BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level");
614 // non-root relative level
615 if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
617 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
622 node_pointer & m_root;
623 size_type & m_leafs_level;
624 Element const& m_element;
626 parameters_type const& m_parameters;
627 Translator const& m_translator;
629 size_type m_relative_level;
631 Allocators & m_allocators;
634 }}} // namespace detail::rtree::visitors
636 }}} // namespace boost::geometry::index
638 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP