ceph/src/boost/boost/geometry/index/detail/rtree/rstar/insert.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree R*-tree insert algorithm implementation
   4 //
   5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
   6 //
   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
  10 //
  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)
  14
  15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
  17
  18 #include <boost/core/ignore_unused.hpp>
  19
  20 #include <boost/geometry/index/detail/algorithms/content.hpp>
  21
  22 namespace boost { namespace geometry { namespace index {
  23
  24 namespace detail { namespace rtree { namespace visitors {
  25
  26 namespace rstar {
  27
  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
  31 {
  32     typedef typename Strategy::comparable_distance_point_point_strategy_type strategy_type;
  33     typedef typename geometry::comparable_distance_result
  34         <
  35             Point1, Point2, strategy_type
  36         >::type result_type;
  37
  38     static inline strategy_type get_strategy(Strategy const& strategy)
  39     {
  40         return strategy.get_comparable_distance_point_point_strategy();
  41     }
  42 };
  43
  44 template <typename Point1, typename Point2>
  45 struct comparable_distance_point_point<Point1, Point2, default_strategy>
  46 {
  47     typedef default_strategy strategy_type;
  48     typedef typename geometry::default_comparable_distance_result
  49         <
  50             Point1, Point2
  51         >::type result_type;
  52
  53     static inline strategy_type get_strategy(default_strategy const& )
  54     {
  55         return strategy_type();
  56     }
  57 };
  58
  59 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
  60 class remove_elements_to_reinsert
  61 {
  62 public:
  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;
  66
  67     typedef typename Options::parameters_type parameters_type;
  68
  69     //typedef typename Allocators::internal_node_pointer internal_node_pointer;
  70     typedef internal_node * internal_node_pointer;
  71
  72     template <typename ResultElements, typename Node>
  73     static inline void apply(ResultElements & result_elements,
  74                              Node & n,
  75                              internal_node_pointer parent,
  76                              size_t current_child_index,
  77                              parameters_type const& parameters,
  78                              Translator const& translator,
  79                              Allocators & allocators)
  80     {
  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
  87             <
  88                 point_type, point_type, strategy_type
  89             > comparable_distance_pp;
  90         typedef typename comparable_distance_pp::result_type comparable_distance_type;
  91
  92         elements_type & elements = rtree::elements(n);
  93
  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());
  96
  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");
 100
 101         // calculate current node's center
 102         point_type node_center;
 103         geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center);
 104
 105         // fill the container of centers' distances of children from current node's center
 106         typedef typename index::detail::rtree::container_from_elements_type<
 107             elements_type,
 108             std::pair<comparable_distance_type, element_type>
 109         >::type sorted_elements_type;
 110
 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)
 114
 115         typename comparable_distance_pp::strategy_type
 116             cdist_strategy = comparable_distance_pp::get_strategy(index::detail::get_strategy(parameters));
 117
 118         for ( typename elements_type::const_iterator it = elements.begin() ;
 119               it != elements.end() ; ++it )
 120         {
 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)
 126         }
 127
 128         // sort elements by distances from center
 129         std::partial_sort(
 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)
 134
 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 )
 140         {
 141             result_elements.push_back(it->second);                                                      // MAY THROW (V, E: copy)
 142         }
 143
 144         BOOST_TRY
 145         {
 146             // copy remaining elements to the current node
 147             elements.clear();
 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 )
 151             {
 152                 elements.push_back(it->second);                                                         // MAY THROW (V, E: copy)
 153             }
 154         }
 155         BOOST_CATCH(...)
 156         {
 157             elements.clear();
 158
 159             for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ;
 160                   it != sorted_elements.end() ; ++it )
 161             {
 162                 destroy_element<Value, Options, Translator, Box, Allocators>::apply(it->second, allocators);
 163             }
 164
 165             BOOST_RETHROW                                                                                 // RETHROW
 166         }
 167         BOOST_CATCH_END
 168
 169         ::boost::ignore_unused(parameters);
 170     }
 171
 172 private:
 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)
 177     {
 178         return d1.first < d2.first;
 179     }
 180
 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)
 185     {
 186         return d1.first > d2.first;
 187     }
 188 };
 189
 190 template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators>
 191 struct level_insert_elements_type
 192 {
 193     typedef typename rtree::elements_type<
 194         typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
 195     >::type type;
 196 };
 197
 198 template <typename Value, typename Options, typename Box, typename Allocators>
 199 struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators>
 200 {
 201     typedef typename rtree::elements_type<
 202         typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
 203     >::type type;
 204 };
 205
 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>
 209 {
 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;
 214
 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<
 217         elements_type,
 218         typename elements_type::value_type
 219     >::type result_elements_type;
 220
 221     typedef typename Options::parameters_type parameters_type;
 222
 223     typedef typename Allocators::node_pointer node_pointer;
 224     typedef typename Allocators::size_type size_type;
 225
 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)
 235     {}
 236
 237     template <typename Node>
 238     inline void handle_possible_reinsert_or_split_of_root(Node &n)
 239     {
 240         BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
 241
 242         result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
 243
 244         // overflow
 245         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
 246         {
 247             // node isn't root node
 248             if ( !base::m_traverse_data.current_is_root() )
 249             {
 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(
 253                     result_elements, n,
 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)
 256             }
 257             // node is root node
 258             else
 259             {
 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)
 262             }
 263         }
 264     }
 265
 266     template <typename Node>
 267     inline void handle_possible_split(Node &n) const
 268     {
 269         // overflow
 270         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
 271         {
 272             base::split(n);                                                                                 // MAY THROW (V, E: alloc, copy, N: alloc)
 273         }
 274     }
 275
 276     template <typename Node>
 277     inline void recalculate_aabb_if_necessary(Node const& n) const
 278     {
 279         if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
 280         {
 281             // calulate node's new box
 282             recalculate_aabb(n);
 283         }
 284     }
 285
 286     template <typename Node>
 287     inline void recalculate_aabb(Node const& n) const
 288     {
 289         base::m_traverse_data.current_element().first =
 290             elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(),
 291                               base::m_translator,
 292                               index::detail::get_strategy(base::m_parameters));
 293     }
 294
 295     inline void recalculate_aabb(leaf const& n) const
 296     {
 297         base::m_traverse_data.current_element().first =
 298             values_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(),
 299                             base::m_translator,
 300                             index::detail::get_strategy(base::m_parameters));
 301     }
 302
 303     size_type result_relative_level;
 304     result_elements_type result_elements;
 305 };
 306
 307 template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
 308 struct level_insert
 309     : public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators>
 310 {
 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;
 315
 316     typedef typename Options::parameters_type parameters_type;
 317
 318     typedef typename Allocators::node_pointer node_pointer;
 319     typedef typename Allocators::size_type size_type;
 320
 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)
 329     {}
 330
 331     inline void operator()(internal_node & n)
 332     {
 333         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
 334
 335         if ( base::m_traverse_data.current_level < base::m_level )
 336         {
 337             // next traversing step
 338             base::traverse(*this, n);                                                                       // MAY THROW (E: alloc, copy, N: alloc)
 339
 340             // further insert
 341             if ( 0 < InsertIndex )
 342             {
 343                 BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
 344
 345                 if ( base::m_traverse_data.current_level == base::m_level - 1 )
 346                 {
 347                     base::handle_possible_reinsert_or_split_of_root(n);                                     // MAY THROW (E: alloc, copy, N: alloc)
 348                 }
 349             }
 350         }
 351         else
 352         {
 353             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
 354
 355             BOOST_TRY
 356             {
 357                 // push new child node
 358                 rtree::elements(n).push_back(base::m_element);                                              // MAY THROW, STRONG (E: alloc, copy)
 359             }
 360             BOOST_CATCH(...)
 361             {
 362                 // NOTE: exception-safety
 363                 // if the insert fails above, the element won't be stored in the tree, so delete it
 364
 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);
 367
 368                 BOOST_RETHROW                                                                                 // RETHROW
 369             }
 370             BOOST_CATCH_END
 371
 372             // first insert
 373             if ( 0 == InsertIndex )
 374             {
 375                 base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
 376             }
 377             // not the first insert
 378             else
 379             {
 380                 base::handle_possible_split(n);                                                             // MAY THROW (E: alloc, N: alloc)
 381             }
 382         }
 383
 384         base::recalculate_aabb_if_necessary(n);
 385     }
 386
 387     inline void operator()(leaf &)
 388     {
 389         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
 390     }
 391 };
 392
 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>
 396 {
 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;
 401
 402     typedef typename Options::parameters_type parameters_type;
 403
 404     typedef typename Allocators::node_pointer node_pointer;
 405     typedef typename Allocators::size_type size_type;
 406
 407     inline level_insert(node_pointer & root,
 408                         size_type & leafs_level,
 409                         Value const& v,
 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)
 415     {}
 416
 417     inline void operator()(internal_node & n)
 418     {
 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");
 421
 422         // next traversing step
 423         base::traverse(*this, n);                                                                       // MAY THROW (V, E: alloc, copy, N: alloc)
 424
 425         BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
 426
 427         if ( base::m_traverse_data.current_level == base::m_level - 1 )
 428         {
 429             base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
 430         }
 431
 432         base::recalculate_aabb_if_necessary(n);
 433     }
 434
 435     inline void operator()(leaf & n)
 436     {
 437         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
 438                                     "unexpected 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)(),
 441                                     "unexpected level");
 442
 443         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
 444
 445         base::handle_possible_split(n);                                                                 // MAY THROW (V: alloc, copy, N: alloc)
 446     }
 447 };
 448
 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>
 452 {
 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;
 457
 458     typedef typename Options::parameters_type parameters_type;
 459
 460     typedef typename Allocators::node_pointer node_pointer;
 461     typedef typename Allocators::size_type size_type;
 462
 463     inline level_insert(node_pointer & root,
 464                         size_type & leafs_level,
 465                         Value const& v,
 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)
 471     {}
 472
 473     inline void operator()(internal_node & n)
 474     {
 475         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
 476                                     "unexpected level");
 477         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
 478                                     "unexpected level");
 479
 480         // next traversing step
 481         base::traverse(*this, n);                                                                       // MAY THROW (V: alloc, copy, N: alloc)
 482
 483         base::recalculate_aabb_if_necessary(n);
 484     }
 485
 486     inline void operator()(leaf & n)
 487     {
 488         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
 489                                     "unexpected 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)(),
 492                                     "unexpected level");
 493
 494         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
 495
 496         base::handle_possible_reinsert_or_split_of_root(n);                                             // MAY THROW (V: alloc, copy, N: alloc)
 497
 498         base::recalculate_aabb_if_necessary(n);
 499     }
 500 };
 501
 502 } // namespace rstar
 503
 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
 511 {
 512     typedef typename Options::parameters_type parameters_type;
 513
 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;
 517
 518     typedef typename Allocators::node_pointer node_pointer;
 519     typedef typename Allocators::size_type size_type;
 520
 521 public:
 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)
 532     {}
 533
 534     inline void operator()(internal_node & n)
 535     {
 536         boost::ignore_unused(n);
 537         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root");
 538
 539         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
 540         if ( m_parameters.get_reinserted_elements() > 0 )
 541         {
 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);
 544
 545             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
 546
 547             if ( !lins_v.result_elements.empty() )
 548             {
 549                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                       // MAY THROW (V, E: alloc, copy, N: alloc)
 550             }
 551         }
 552         else
 553         {
 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);
 556
 557             rtree::apply_visitor(ins_v, *m_root);
 558         }
 559     }
 560
 561     inline void operator()(leaf & n)
 562     {
 563         boost::ignore_unused(n);
 564         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root");
 565
 566         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
 567         if ( m_parameters.get_reinserted_elements() > 0 )
 568         {
 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);
 571
 572             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
 573
 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");
 576         }
 577         else
 578         {
 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);
 581
 582             rtree::apply_visitor(ins_v, *m_root);
 583         }
 584     }
 585
 586 private:
 587     template <typename Elements>
 588     inline void recursive_reinsert(Elements & elements, size_t relative_level)
 589     {
 590         typedef typename Elements::value_type element_type;
 591
 592         // reinsert children starting from the minimum distance
 593         typename Elements::reverse_iterator it = elements.rbegin();
 594         for ( ; it != elements.rend() ; ++it)
 595         {
 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);
 598
 599             BOOST_TRY
 600             {
 601                 rtree::apply_visitor(lins_v, *m_root);                                                          // MAY THROW (V, E: alloc, copy, N: alloc)
 602             }
 603             BOOST_CATCH(...)
 604             {
 605                 ++it;
 606                 for ( ; it != elements.rend() ; ++it)
 607                     rtree::destroy_element<Value, Options, Translator, Box, Allocators>::apply(*it, m_allocators);
 608                 BOOST_RETHROW                                                                                     // RETHROW
 609             }
 610             BOOST_CATCH_END
 611
 612             BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level");
 613
 614             // non-root relative level
 615             if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
 616             {
 617                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                   // MAY THROW (V, E: alloc, copy, N: alloc)
 618             }
 619         }
 620     }
 621
 622     node_pointer & m_root;
 623     size_type & m_leafs_level;
 624     Element const& m_element;
 625
 626     parameters_type const& m_parameters;
 627     Translator const& m_translator;
 628
 629     size_type m_relative_level;
 630
 631     Allocators & m_allocators;
 632 };
 633
 634 }}} // namespace detail::rtree::visitors
 635
 636 }}} // namespace boost::geometry::index
 637
 638 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP