rtree/rstar/insert.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree R*-tree insert algorithm implementation
0004 //
0005 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2023.
0008 // Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
0018
0019 #include <type_traits>
0020
0021 #include <boost/core/ignore_unused.hpp>
0022
0023 #include <boost/geometry/algorithms/centroid.hpp>
0024 #include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
0025
0026 #include <boost/geometry/index/detail/algorithms/content.hpp>
0027 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
0028 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0029 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
0030
0031 namespace boost { namespace geometry { namespace index {
0032
0033 namespace detail { namespace rtree { namespace visitors {
0034
0035 namespace rstar {
0036
0037 // Utility to distinguish between default and non-default index strategy
0038 template <typename Point1, typename Point2, typename Strategy>
0039 struct comparable_distance
0040 {
0041     typedef typename geometry::comparable_distance_result
0042         <
0043             Point1, Point2, Strategy
0044         >::type result_type;
0045
0046     static inline result_type call(Point1 const& p1, Point2 const& p2, Strategy const& s)
0047     {
0048         return geometry::comparable_distance(p1, p2, s);
0049     }
0050 };
0051
0052 template <typename Point1, typename Point2>
0053 struct comparable_distance<Point1, Point2, default_strategy>
0054 {
0055     typedef typename geometry::default_comparable_distance_result
0056         <
0057             Point1, Point2
0058         >::type result_type;
0059
0060     static inline result_type call(Point1 const& p1, Point2 const& p2, default_strategy const& )
0061     {
0062         return geometry::comparable_distance(p1, p2);
0063     }
0064 };
0065
0066 template <typename MembersHolder>
0067 class remove_elements_to_reinsert
0068 {
0069 public:
0070     typedef typename MembersHolder::box_type box_type;
0071     typedef typename MembersHolder::parameters_type parameters_type;
0072     typedef typename MembersHolder::translator_type translator_type;
0073     typedef typename MembersHolder::allocators_type allocators_type;
0074
0075     typedef typename MembersHolder::node node;
0076     typedef typename MembersHolder::internal_node internal_node;
0077     typedef typename MembersHolder::leaf leaf;
0078
0079     //typedef typename Allocators::internal_node_pointer internal_node_pointer;
0080     typedef internal_node * internal_node_pointer;
0081
0082     template <typename ResultElements, typename Node>
0083     static inline void apply(ResultElements & result_elements,
0084                              Node & n,
0085                              internal_node_pointer parent,
0086                              size_t current_child_index,
0087                              parameters_type const& parameters,
0088                              translator_type const& translator,
0089                              allocators_type & allocators)
0090     {
0091         typedef typename rtree::elements_type<Node>::type elements_type;
0092         typedef typename elements_type::value_type element_type;
0093         typedef typename geometry::point_type<box_type>::type point_type;
0094         typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
0095         // TODO: awulkiew - change second point_type to the point type of the Indexable?
0096         typedef rstar::comparable_distance
0097             <
0098                 point_type, point_type, strategy_type
0099             > comparable_distance_pp;
0100         typedef typename comparable_distance_pp::result_type comparable_distance_type;
0101
0102         elements_type & elements = rtree::elements(n);
0103
0104         const size_t elements_count = parameters.get_max_elements() + 1;
0105         const size_t reinserted_elements_count = (::std::min)(parameters.get_reinserted_elements(), elements_count - parameters.get_min_elements());
0106
0107         BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
0108         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
0109         BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
0110
0111         auto const& strategy = index::detail::get_strategy(parameters);
0112
0113         // calculate current node's center
0114         point_type node_center;
0115         geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center,
0116                            strategy);
0117
0118         // fill the container of centers' distances of children from current node's center
0119         typedef typename index::detail::rtree::container_from_elements_type<
0120             elements_type,
0121             std::pair<comparable_distance_type, element_type>
0122         >::type sorted_elements_type;
0123
0124         sorted_elements_type sorted_elements;
0125         // If constructor is used instead of resize() MS implementation leaks here
0126         sorted_elements.reserve(elements_count);                                                         // MAY THROW, STRONG (V, E: alloc, copy)
0127
0128         for ( typename elements_type::const_iterator it = elements.begin() ;
0129               it != elements.end() ; ++it )
0130         {
0131             point_type element_center;
0132             geometry::centroid(rtree::element_indexable(*it, translator), element_center,
0133                                strategy);
0134             sorted_elements.push_back(std::make_pair(
0135                 comparable_distance_pp::call(node_center, element_center, strategy),
0136                 *it));                                                                                  // MAY THROW (V, E: copy)
0137         }
0138
0139         // sort elements by distances from center
0140         std::partial_sort(
0141             sorted_elements.begin(),
0142             sorted_elements.begin() + reinserted_elements_count,
0143             sorted_elements.end(),
0144             distances_dsc<comparable_distance_type, element_type>);                                                // MAY THROW, BASIC (V, E: copy)
0145
0146         // copy elements which will be reinserted
0147         result_elements.clear();
0148         result_elements.reserve(reinserted_elements_count);                                             // MAY THROW, STRONG (V, E: alloc, copy)
0149         for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() ;
0150               it != sorted_elements.begin() + reinserted_elements_count ; ++it )
0151         {
0152             result_elements.push_back(it->second);                                                      // MAY THROW (V, E: copy)
0153         }
0154
0155         BOOST_TRY
0156         {
0157             // copy remaining elements to the current node
0158             elements.clear();
0159             elements.reserve(elements_count - reinserted_elements_count);                                // SHOULDN'T THROW (new_size <= old size)
0160             for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() + reinserted_elements_count;
0161                   it != sorted_elements.end() ; ++it )
0162             {
0163                 elements.push_back(it->second);                                                         // MAY THROW (V, E: copy)
0164             }
0165         }
0166         BOOST_CATCH(...)
0167         {
0168             elements.clear();
0169
0170             for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ;
0171                   it != sorted_elements.end() ; ++it )
0172             {
0173                 destroy_element<MembersHolder>::apply(it->second, allocators);
0174             }
0175
0176             BOOST_RETHROW                                                                                 // RETHROW
0177         }
0178         BOOST_CATCH_END
0179
0180         ::boost::ignore_unused(parameters);
0181     }
0182
0183 private:
0184     template <typename Distance, typename El>
0185     static inline bool distances_asc(
0186         std::pair<Distance, El> const& d1,
0187         std::pair<Distance, El> const& d2)
0188     {
0189         return d1.first < d2.first;
0190     }
0191
0192     template <typename Distance, typename El>
0193     static inline bool distances_dsc(
0194         std::pair<Distance, El> const& d1,
0195         std::pair<Distance, El> const& d2)
0196     {
0197         return d1.first > d2.first;
0198     }
0199 };
0200
0201 template
0202 <
0203     size_t InsertIndex,
0204     typename Element,
0205     typename MembersHolder,
0206     bool IsValue = std::is_same<Element, typename MembersHolder::value_type>::value
0207 >
0208 struct level_insert_elements_type
0209 {
0210     typedef typename rtree::elements_type<
0211         typename rtree::internal_node<
0212             typename MembersHolder::value_type,
0213             typename MembersHolder::parameters_type,
0214             typename MembersHolder::box_type,
0215             typename MembersHolder::allocators_type,
0216             typename MembersHolder::node_tag
0217         >::type
0218     >::type type;
0219 };
0220
0221 template <typename Value, typename MembersHolder>
0222 struct level_insert_elements_type<0, Value, MembersHolder, true>
0223 {
0224     typedef typename rtree::elements_type<
0225         typename rtree::leaf<
0226             typename MembersHolder::value_type,
0227             typename MembersHolder::parameters_type,
0228             typename MembersHolder::box_type,
0229             typename MembersHolder::allocators_type,
0230             typename MembersHolder::node_tag
0231         >::type
0232     >::type type;
0233 };
0234
0235 template <size_t InsertIndex, typename Element, typename MembersHolder>
0236 struct level_insert_base
0237     : public detail::insert<Element, MembersHolder>
0238 {
0239     typedef detail::insert<Element, MembersHolder> base;
0240     typedef typename base::node node;
0241     typedef typename base::internal_node internal_node;
0242     typedef typename base::leaf leaf;
0243
0244     typedef typename level_insert_elements_type<InsertIndex, Element, MembersHolder>::type elements_type;
0245     typedef typename index::detail::rtree::container_from_elements_type<
0246         elements_type,
0247         typename elements_type::value_type
0248     >::type result_elements_type;
0249
0250     typedef typename MembersHolder::box_type box_type;
0251     typedef typename MembersHolder::parameters_type parameters_type;
0252     typedef typename MembersHolder::translator_type translator_type;
0253     typedef typename MembersHolder::allocators_type allocators_type;
0254
0255     typedef typename allocators_type::node_pointer node_pointer;
0256     typedef typename allocators_type::size_type size_type;
0257
0258     inline level_insert_base(node_pointer & root,
0259                              size_type & leafs_level,
0260                              Element const& element,
0261                              parameters_type const& parameters,
0262                              translator_type const& translator,
0263                              allocators_type & allocators,
0264                              size_type relative_level)
0265         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
0266         , result_relative_level(0)
0267     {}
0268
0269     template <typename Node>
0270     inline void handle_possible_reinsert_or_split_of_root(Node &n)
0271     {
0272         BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
0273
0274         result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
0275
0276         // overflow
0277         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
0278         {
0279             // node isn't root node
0280             if ( !base::m_traverse_data.current_is_root() )
0281             {
0282                 // NOTE: exception-safety
0283                 // After an exception result_elements may contain garbage, don't use it
0284                 rstar::remove_elements_to_reinsert<MembersHolder>::apply(
0285                     result_elements, n,
0286                     base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
0287                     base::m_parameters, base::m_translator, base::m_allocators);                            // MAY THROW, BASIC (V, E: alloc, copy)
0288             }
0289             // node is root node
0290             else
0291             {
0292                 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*base::m_root_node), "node should be the root node");
0293                 base::split(n);                                                                             // MAY THROW (V, E: alloc, copy, N: alloc)
0294             }
0295         }
0296     }
0297
0298     template <typename Node>
0299     inline void handle_possible_split(Node &n) const
0300     {
0301         // overflow
0302         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
0303         {
0304             base::split(n);                                                                                 // MAY THROW (V, E: alloc, copy, N: alloc)
0305         }
0306     }
0307
0308     template <typename Node>
0309     inline void recalculate_aabb_if_necessary(Node const& n) const
0310     {
0311         if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
0312         {
0313             // calulate node's new box
0314             recalculate_aabb(n);
0315         }
0316     }
0317
0318     template <typename Node>
0319     inline void recalculate_aabb(Node const& n) const
0320     {
0321         base::m_traverse_data.current_element().first =
0322             elements_box<box_type>(rtree::elements(n).begin(), rtree::elements(n).end(),
0323                                    base::m_translator,
0324                                    index::detail::get_strategy(base::m_parameters));
0325     }
0326
0327     inline void recalculate_aabb(leaf const& n) const
0328     {
0329         base::m_traverse_data.current_element().first =
0330             values_box<box_type>(rtree::elements(n).begin(), rtree::elements(n).end(),
0331                                  base::m_translator,
0332                                  index::detail::get_strategy(base::m_parameters));
0333     }
0334
0335     size_type result_relative_level;
0336     result_elements_type result_elements;
0337 };
0338
0339 template
0340 <
0341     size_t InsertIndex,
0342     typename Element,
0343     typename MembersHolder,
0344     bool IsValue = std::is_same<Element, typename MembersHolder::value_type>::value
0345 >
0346 struct level_insert
0347     : public level_insert_base<InsertIndex, Element, MembersHolder>
0348 {
0349     typedef level_insert_base<InsertIndex, Element, MembersHolder> base;
0350     typedef typename base::node node;
0351     typedef typename base::internal_node internal_node;
0352     typedef typename base::leaf leaf;
0353
0354     typedef typename base::parameters_type parameters_type;
0355     typedef typename base::translator_type translator_type;
0356     typedef typename base::allocators_type allocators_type;
0357
0358     typedef typename base::node_pointer node_pointer;
0359     typedef typename base::size_type size_type;
0360
0361     inline level_insert(node_pointer & root,
0362                         size_type & leafs_level,
0363                         Element const& element,
0364                         parameters_type const& parameters,
0365                         translator_type const& translator,
0366                         allocators_type & allocators,
0367                         size_type relative_level)
0368         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
0369     {}
0370
0371     inline void operator()(internal_node & n)
0372     {
0373         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
0374
0375         if ( base::m_traverse_data.current_level < base::m_level )
0376         {
0377             // next traversing step
0378             base::traverse(*this, n);                                                                       // MAY THROW (E: alloc, copy, N: alloc)
0379
0380             // further insert
0381             if ( 0 < InsertIndex )
0382             {
0383                 BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
0384
0385                 if ( base::m_traverse_data.current_level == base::m_level - 1 )
0386                 {
0387                     base::handle_possible_reinsert_or_split_of_root(n);                                     // MAY THROW (E: alloc, copy, N: alloc)
0388                 }
0389             }
0390         }
0391         else
0392         {
0393             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
0394
0395             BOOST_TRY
0396             {
0397                 // push new child node
0398                 rtree::elements(n).push_back(base::m_element);                                              // MAY THROW, STRONG (E: alloc, copy)
0399             }
0400             BOOST_CATCH(...)
0401             {
0402                 // NOTE: exception-safety
0403                 // if the insert fails above, the element won't be stored in the tree, so delete it
0404
0405                 rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
0406
0407                 BOOST_RETHROW                                                                                 // RETHROW
0408             }
0409             BOOST_CATCH_END
0410
0411             // first insert
0412             if ( 0 == InsertIndex )
0413             {
0414                 base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
0415             }
0416             // not the first insert
0417             else
0418             {
0419                 base::handle_possible_split(n);                                                             // MAY THROW (E: alloc, N: alloc)
0420             }
0421         }
0422
0423         base::recalculate_aabb_if_necessary(n);
0424     }
0425
0426     inline void operator()(leaf &)
0427     {
0428         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
0429     }
0430 };
0431
0432 template <size_t InsertIndex, typename Value, typename MembersHolder>
0433 struct level_insert<InsertIndex, Value, MembersHolder, true>
0434     : public level_insert_base<InsertIndex, typename MembersHolder::value_type, MembersHolder>
0435 {
0436     typedef level_insert_base<InsertIndex, typename MembersHolder::value_type, MembersHolder> base;
0437     typedef typename base::node node;
0438     typedef typename base::internal_node internal_node;
0439     typedef typename base::leaf leaf;
0440
0441     typedef typename MembersHolder::value_type value_type;
0442     typedef typename base::parameters_type parameters_type;
0443     typedef typename base::translator_type translator_type;
0444     typedef typename base::allocators_type allocators_type;
0445
0446     typedef typename base::node_pointer node_pointer;
0447     typedef typename base::size_type size_type;
0448
0449     inline level_insert(node_pointer & root,
0450                         size_type & leafs_level,
0451                         value_type const& v,
0452                         parameters_type const& parameters,
0453                         translator_type const& translator,
0454                         allocators_type & allocators,
0455                         size_type relative_level)
0456         : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
0457     {}
0458
0459     inline void operator()(internal_node & n)
0460     {
0461         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
0462         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
0463
0464         // next traversing step
0465         base::traverse(*this, n);                                                                       // MAY THROW (V, E: alloc, copy, N: alloc)
0466
0467         BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
0468
0469         if ( base::m_traverse_data.current_level == base::m_level - 1 )
0470         {
0471             base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
0472         }
0473
0474         base::recalculate_aabb_if_necessary(n);
0475     }
0476
0477     inline void operator()(leaf & n)
0478     {
0479         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
0480                                     "unexpected level");
0481         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
0482                                     base::m_level == (std::numeric_limits<size_t>::max)(),
0483                                     "unexpected level");
0484
0485         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
0486
0487         base::handle_possible_split(n);                                                                 // MAY THROW (V: alloc, copy, N: alloc)
0488     }
0489 };
0490
0491 template <typename Value, typename MembersHolder>
0492 struct level_insert<0, Value, MembersHolder, true>
0493     : public level_insert_base<0, typename MembersHolder::value_type, MembersHolder>
0494 {
0495     typedef level_insert_base<0, typename MembersHolder::value_type, MembersHolder> base;
0496     typedef typename base::node node;
0497     typedef typename base::internal_node internal_node;
0498     typedef typename base::leaf leaf;
0499
0500     typedef typename MembersHolder::value_type value_type;
0501     typedef typename base::parameters_type parameters_type;
0502     typedef typename base::translator_type translator_type;
0503     typedef typename base::allocators_type allocators_type;
0504
0505     typedef typename base::node_pointer node_pointer;
0506     typedef typename base::size_type size_type;
0507
0508     inline level_insert(node_pointer & root,
0509                         size_type & leafs_level,
0510                         value_type const& v,
0511                         parameters_type const& parameters,
0512                         translator_type const& translator,
0513                         allocators_type & allocators,
0514                         size_type relative_level)
0515         : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
0516     {}
0517
0518     inline void operator()(internal_node & n)
0519     {
0520         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
0521                                     "unexpected level");
0522         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
0523                                     "unexpected level");
0524
0525         // next traversing step
0526         base::traverse(*this, n);                                                                       // MAY THROW (V: alloc, copy, N: alloc)
0527
0528         base::recalculate_aabb_if_necessary(n);
0529     }
0530
0531     inline void operator()(leaf & n)
0532     {
0533         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
0534                                     "unexpected level");
0535         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
0536                                     base::m_level == (std::numeric_limits<size_t>::max)(),
0537                                     "unexpected level");
0538
0539         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
0540
0541         base::handle_possible_reinsert_or_split_of_root(n);                                             // MAY THROW (V: alloc, copy, N: alloc)
0542
0543         base::recalculate_aabb_if_necessary(n);
0544     }
0545 };
0546
0547 } // namespace rstar
0548
0549 // R*-tree insert visitor
0550 // After passing the Element to insert visitor the Element is managed by the tree
0551 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
0552 // because this visitor may delete it
0553 template <typename Element, typename MembersHolder>
0554 class insert<Element, MembersHolder, insert_reinsert_tag>
0555     : public MembersHolder::visitor
0556 {
0557     typedef typename MembersHolder::parameters_type parameters_type;
0558     typedef typename MembersHolder::translator_type translator_type;
0559     typedef typename MembersHolder::allocators_type allocators_type;
0560
0561     typedef typename MembersHolder::node node;
0562     typedef typename MembersHolder::internal_node internal_node;
0563     typedef typename MembersHolder::leaf leaf;
0564
0565     typedef typename allocators_type::node_pointer node_pointer;
0566     typedef typename allocators_type::size_type size_type;
0567
0568 public:
0569     inline insert(node_pointer & root,
0570                   size_type & leafs_level,
0571                   Element const& element,
0572                   parameters_type const& parameters,
0573                   translator_type const& translator,
0574                   allocators_type & allocators,
0575                   size_type relative_level = 0)
0576         : m_root(root), m_leafs_level(leafs_level), m_element(element)
0577         , m_parameters(parameters), m_translator(translator)
0578         , m_relative_level(relative_level), m_allocators(allocators)
0579     {}
0580
0581     inline void operator()(internal_node & n)
0582     {
0583         boost::ignore_unused(n);
0584         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root");
0585
0586         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
0587         if ( m_parameters.get_reinserted_elements() > 0 )
0588         {
0589             rstar::level_insert<0, Element, MembersHolder> lins_v(
0590                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
0591
0592             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
0593
0594             if ( !lins_v.result_elements.empty() )
0595             {
0596                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                       // MAY THROW (V, E: alloc, copy, N: alloc)
0597             }
0598         }
0599         else
0600         {
0601             visitors::insert<Element, MembersHolder, insert_default_tag> ins_v(
0602                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
0603
0604             rtree::apply_visitor(ins_v, *m_root);
0605         }
0606     }
0607
0608     inline void operator()(leaf & n)
0609     {
0610         boost::ignore_unused(n);
0611         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root");
0612
0613         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
0614         if ( m_parameters.get_reinserted_elements() > 0 )
0615         {
0616             rstar::level_insert<0, Element, MembersHolder> lins_v(
0617                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
0618
0619             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
0620
0621             // we're in the root, so root should be split and there should be no elements to reinsert
0622             BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
0623         }
0624         else
0625         {
0626             visitors::insert<Element, MembersHolder, insert_default_tag> ins_v(
0627                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
0628
0629             rtree::apply_visitor(ins_v, *m_root);
0630         }
0631     }
0632
0633 private:
0634     template <typename Elements>
0635     inline void recursive_reinsert(Elements & elements, size_t relative_level)
0636     {
0637         typedef typename Elements::value_type element_type;
0638
0639         // reinsert children starting from the minimum distance
0640         typename Elements::reverse_iterator it = elements.rbegin();
0641         for ( ; it != elements.rend() ; ++it)
0642         {
0643             rstar::level_insert<1, element_type, MembersHolder> lins_v(
0644                 m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
0645
0646             BOOST_TRY
0647             {
0648                 rtree::apply_visitor(lins_v, *m_root);                                                          // MAY THROW (V, E: alloc, copy, N: alloc)
0649             }
0650             BOOST_CATCH(...)
0651             {
0652                 ++it;
0653                 for ( ; it != elements.rend() ; ++it)
0654                     rtree::destroy_element<MembersHolder>::apply(*it, m_allocators);
0655                 BOOST_RETHROW                                                                                     // RETHROW
0656             }
0657             BOOST_CATCH_END
0658
0659             BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level");
0660
0661             // non-root relative level
0662             if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
0663             {
0664                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                   // MAY THROW (V, E: alloc, copy, N: alloc)
0665             }
0666         }
0667     }
0668
0669     node_pointer & m_root;
0670     size_type & m_leafs_level;
0671     Element const& m_element;
0672
0673     parameters_type const& m_parameters;
0674     translator_type const& m_translator;
0675
0676     size_type m_relative_level;
0677
0678     allocators_type & m_allocators;
0679 };
0680
0681 }}} // namespace detail::rtree::visitors
0682
0683 }}} // namespace boost::geometry::index
0684
0685 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP