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-2021.
   8 // Modifications copyright (c) 2019-2021 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 <type_traits>
  19
  20 #include <boost/core/ignore_unused.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
  23
  24 #include <boost/geometry/index/detail/algorithms/content.hpp>
  25 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
  26 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
  27 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
  28
  29 namespace boost { namespace geometry { namespace index {
  30
  31 namespace detail { namespace rtree { namespace visitors {
  32
  33 namespace rstar {
  34
  35 // Utility to distinguish between default and non-default index strategy
  36 template <typename Point1, typename Point2, typename Strategy>
  37 struct comparable_distance
  38 {
  39     typedef typename geometry::comparable_distance_result
  40         <
  41             Point1, Point2, Strategy
  42         >::type result_type;
  43
  44     static inline result_type call(Point1 const& p1, Point2 const& p2, Strategy const& s)
  45     {
  46         return geometry::comparable_distance(p1, p2, s);
  47     }
  48 };
  49
  50 template <typename Point1, typename Point2>
  51 struct comparable_distance<Point1, Point2, default_strategy>
  52 {
  53     typedef typename geometry::default_comparable_distance_result
  54         <
  55             Point1, Point2
  56         >::type result_type;
  57
  58     static inline result_type call(Point1 const& p1, Point2 const& p2, default_strategy const& )
  59     {
  60         return geometry::comparable_distance(p1, p2);
  61     }
  62 };
  63
  64 template <typename MembersHolder>
  65 class remove_elements_to_reinsert
  66 {
  67 public:
  68     typedef typename MembersHolder::box_type box_type;
  69     typedef typename MembersHolder::parameters_type parameters_type;
  70     typedef typename MembersHolder::translator_type translator_type;
  71     typedef typename MembersHolder::allocators_type allocators_type;
  72
  73     typedef typename MembersHolder::node node;
  74     typedef typename MembersHolder::internal_node internal_node;
  75     typedef typename MembersHolder::leaf leaf;
  76
  77     //typedef typename Allocators::internal_node_pointer internal_node_pointer;
  78     typedef internal_node * internal_node_pointer;
  79
  80     template <typename ResultElements, typename Node>
  81     static inline void apply(ResultElements & result_elements,
  82                              Node & n,
  83                              internal_node_pointer parent,
  84                              size_t current_child_index,
  85                              parameters_type const& parameters,
  86                              translator_type const& translator,
  87                              allocators_type & allocators)
  88     {
  89         typedef typename rtree::elements_type<Node>::type elements_type;
  90         typedef typename elements_type::value_type element_type;
  91         typedef typename geometry::point_type<box_type>::type point_type;
  92         typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
  93         // TODO: awulkiew - change second point_type to the point type of the Indexable?
  94         typedef rstar::comparable_distance
  95             <
  96                 point_type, point_type, strategy_type
  97             > comparable_distance_pp;
  98         typedef typename comparable_distance_pp::result_type comparable_distance_type;
  99
 100         elements_type & elements = rtree::elements(n);
 101
 102         const size_t elements_count = parameters.get_max_elements() + 1;
 103         const size_t reinserted_elements_count = (::std::min)(parameters.get_reinserted_elements(), elements_count - parameters.get_min_elements());
 104
 105         BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
 106         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
 107         BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
 108
 109         auto const& strategy = index::detail::get_strategy(parameters);
 110
 111         // calculate current node's center
 112         point_type node_center;
 113         geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center,
 114                            strategy);
 115
 116         // fill the container of centers' distances of children from current node's center
 117         typedef typename index::detail::rtree::container_from_elements_type<
 118             elements_type,
 119             std::pair<comparable_distance_type, element_type>
 120         >::type sorted_elements_type;
 121
 122         sorted_elements_type sorted_elements;
 123         // If constructor is used instead of resize() MS implementation leaks here
 124         sorted_elements.reserve(elements_count);                                                         // MAY THROW, STRONG (V, E: alloc, copy)
 125
 126         for ( typename elements_type::const_iterator it = elements.begin() ;
 127               it != elements.end() ; ++it )
 128         {
 129             point_type element_center;
 130             geometry::centroid(rtree::element_indexable(*it, translator), element_center,
 131                                strategy);
 132             sorted_elements.push_back(std::make_pair(
 133                 comparable_distance_pp::call(node_center, element_center, strategy),
 134                 *it));                                                                                  // MAY THROW (V, E: copy)
 135         }
 136
 137         // sort elements by distances from center
 138         std::partial_sort(
 139             sorted_elements.begin(),
 140             sorted_elements.begin() + reinserted_elements_count,
 141             sorted_elements.end(),
 142             distances_dsc<comparable_distance_type, element_type>);                                                // MAY THROW, BASIC (V, E: copy)
 143
 144         // copy elements which will be reinserted
 145         result_elements.clear();
 146         result_elements.reserve(reinserted_elements_count);                                             // MAY THROW, STRONG (V, E: alloc, copy)
 147         for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() ;
 148               it != sorted_elements.begin() + reinserted_elements_count ; ++it )
 149         {
 150             result_elements.push_back(it->second);                                                      // MAY THROW (V, E: copy)
 151         }
 152
 153         BOOST_TRY
 154         {
 155             // copy remaining elements to the current node
 156             elements.clear();
 157             elements.reserve(elements_count - reinserted_elements_count);                                // SHOULDN'T THROW (new_size <= old size)
 158             for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() + reinserted_elements_count;
 159                   it != sorted_elements.end() ; ++it )
 160             {
 161                 elements.push_back(it->second);                                                         // MAY THROW (V, E: copy)
 162             }
 163         }
 164         BOOST_CATCH(...)
 165         {
 166             elements.clear();
 167
 168             for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ;
 169                   it != sorted_elements.end() ; ++it )
 170             {
 171                 destroy_element<MembersHolder>::apply(it->second, allocators);
 172             }
 173
 174             BOOST_RETHROW                                                                                 // RETHROW
 175         }
 176         BOOST_CATCH_END
 177
 178         ::boost::ignore_unused(parameters);
 179     }
 180
 181 private:
 182     template <typename Distance, typename El>
 183     static inline bool distances_asc(
 184         std::pair<Distance, El> const& d1,
 185         std::pair<Distance, El> const& d2)
 186     {
 187         return d1.first < d2.first;
 188     }
 189
 190     template <typename Distance, typename El>
 191     static inline bool distances_dsc(
 192         std::pair<Distance, El> const& d1,
 193         std::pair<Distance, El> const& d2)
 194     {
 195         return d1.first > d2.first;
 196     }
 197 };
 198
 199 template
 200 <
 201     size_t InsertIndex,
 202     typename Element,
 203     typename MembersHolder,
 204     bool IsValue = std::is_same<Element, typename MembersHolder::value_type>::value
 205 >
 206 struct level_insert_elements_type
 207 {
 208     typedef typename rtree::elements_type<
 209         typename rtree::internal_node<
 210             typename MembersHolder::value_type,
 211             typename MembersHolder::parameters_type,
 212             typename MembersHolder::box_type,
 213             typename MembersHolder::allocators_type,
 214             typename MembersHolder::node_tag
 215         >::type
 216     >::type type;
 217 };
 218
 219 template <typename Value, typename MembersHolder>
 220 struct level_insert_elements_type<0, Value, MembersHolder, true>
 221 {
 222     typedef typename rtree::elements_type<
 223         typename rtree::leaf<
 224             typename MembersHolder::value_type,
 225             typename MembersHolder::parameters_type,
 226             typename MembersHolder::box_type,
 227             typename MembersHolder::allocators_type,
 228             typename MembersHolder::node_tag
 229         >::type
 230     >::type type;
 231 };
 232
 233 template <size_t InsertIndex, typename Element, typename MembersHolder>
 234 struct level_insert_base
 235     : public detail::insert<Element, MembersHolder>
 236 {
 237     typedef detail::insert<Element, MembersHolder> base;
 238     typedef typename base::node node;
 239     typedef typename base::internal_node internal_node;
 240     typedef typename base::leaf leaf;
 241
 242     typedef typename level_insert_elements_type<InsertIndex, Element, MembersHolder>::type elements_type;
 243     typedef typename index::detail::rtree::container_from_elements_type<
 244         elements_type,
 245         typename elements_type::value_type
 246     >::type result_elements_type;
 247
 248     typedef typename MembersHolder::box_type box_type;
 249     typedef typename MembersHolder::parameters_type parameters_type;
 250     typedef typename MembersHolder::translator_type translator_type;
 251     typedef typename MembersHolder::allocators_type allocators_type;
 252
 253     typedef typename allocators_type::node_pointer node_pointer;
 254     typedef typename allocators_type::size_type size_type;
 255
 256     inline level_insert_base(node_pointer & root,
 257                              size_type & leafs_level,
 258                              Element const& element,
 259                              parameters_type const& parameters,
 260                              translator_type const& translator,
 261                              allocators_type & allocators,
 262                              size_type relative_level)
 263         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
 264         , result_relative_level(0)
 265     {}
 266
 267     template <typename Node>
 268     inline void handle_possible_reinsert_or_split_of_root(Node &n)
 269     {
 270         BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
 271
 272         result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
 273
 274         // overflow
 275         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
 276         {
 277             // node isn't root node
 278             if ( !base::m_traverse_data.current_is_root() )
 279             {
 280                 // NOTE: exception-safety
 281                 // After an exception result_elements may contain garbage, don't use it
 282                 rstar::remove_elements_to_reinsert<MembersHolder>::apply(
 283                     result_elements, n,
 284                     base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
 285                     base::m_parameters, base::m_translator, base::m_allocators);                            // MAY THROW, BASIC (V, E: alloc, copy)
 286             }
 287             // node is root node
 288             else
 289             {
 290                 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*base::m_root_node), "node should be the root node");
 291                 base::split(n);                                                                             // MAY THROW (V, E: alloc, copy, N: alloc)
 292             }
 293         }
 294     }
 295
 296     template <typename Node>
 297     inline void handle_possible_split(Node &n) const
 298     {
 299         // overflow
 300         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
 301         {
 302             base::split(n);                                                                                 // MAY THROW (V, E: alloc, copy, N: alloc)
 303         }
 304     }
 305
 306     template <typename Node>
 307     inline void recalculate_aabb_if_necessary(Node const& n) const
 308     {
 309         if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
 310         {
 311             // calulate node's new box
 312             recalculate_aabb(n);
 313         }
 314     }
 315
 316     template <typename Node>
 317     inline void recalculate_aabb(Node const& n) const
 318     {
 319         base::m_traverse_data.current_element().first =
 320             elements_box<box_type>(rtree::elements(n).begin(), rtree::elements(n).end(),
 321                                    base::m_translator,
 322                                    index::detail::get_strategy(base::m_parameters));
 323     }
 324
 325     inline void recalculate_aabb(leaf const& n) const
 326     {
 327         base::m_traverse_data.current_element().first =
 328             values_box<box_type>(rtree::elements(n).begin(), rtree::elements(n).end(),
 329                                  base::m_translator,
 330                                  index::detail::get_strategy(base::m_parameters));
 331     }
 332
 333     size_type result_relative_level;
 334     result_elements_type result_elements;
 335 };
 336
 337 template
 338 <
 339     size_t InsertIndex,
 340     typename Element,
 341     typename MembersHolder,
 342     bool IsValue = std::is_same<Element, typename MembersHolder::value_type>::value
 343 >
 344 struct level_insert
 345     : public level_insert_base<InsertIndex, Element, MembersHolder>
 346 {
 347     typedef level_insert_base<InsertIndex, Element, MembersHolder> base;
 348     typedef typename base::node node;
 349     typedef typename base::internal_node internal_node;
 350     typedef typename base::leaf leaf;
 351
 352     typedef typename base::parameters_type parameters_type;
 353     typedef typename base::translator_type translator_type;
 354     typedef typename base::allocators_type allocators_type;
 355
 356     typedef typename base::node_pointer node_pointer;
 357     typedef typename base::size_type size_type;
 358
 359     inline level_insert(node_pointer & root,
 360                         size_type & leafs_level,
 361                         Element const& element,
 362                         parameters_type const& parameters,
 363                         translator_type const& translator,
 364                         allocators_type & allocators,
 365                         size_type relative_level)
 366         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
 367     {}
 368
 369     inline void operator()(internal_node & n)
 370     {
 371         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
 372
 373         if ( base::m_traverse_data.current_level < base::m_level )
 374         {
 375             // next traversing step
 376             base::traverse(*this, n);                                                                       // MAY THROW (E: alloc, copy, N: alloc)
 377
 378             // further insert
 379             if ( 0 < InsertIndex )
 380             {
 381                 BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
 382
 383                 if ( base::m_traverse_data.current_level == base::m_level - 1 )
 384                 {
 385                     base::handle_possible_reinsert_or_split_of_root(n);                                     // MAY THROW (E: alloc, copy, N: alloc)
 386                 }
 387             }
 388         }
 389         else
 390         {
 391             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
 392
 393             BOOST_TRY
 394             {
 395                 // push new child node
 396                 rtree::elements(n).push_back(base::m_element);                                              // MAY THROW, STRONG (E: alloc, copy)
 397             }
 398             BOOST_CATCH(...)
 399             {
 400                 // NOTE: exception-safety
 401                 // if the insert fails above, the element won't be stored in the tree, so delete it
 402
 403                 rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
 404
 405                 BOOST_RETHROW                                                                                 // RETHROW
 406             }
 407             BOOST_CATCH_END
 408
 409             // first insert
 410             if ( 0 == InsertIndex )
 411             {
 412                 base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
 413             }
 414             // not the first insert
 415             else
 416             {
 417                 base::handle_possible_split(n);                                                             // MAY THROW (E: alloc, N: alloc)
 418             }
 419         }
 420
 421         base::recalculate_aabb_if_necessary(n);
 422     }
 423
 424     inline void operator()(leaf &)
 425     {
 426         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
 427     }
 428 };
 429
 430 template <size_t InsertIndex, typename Value, typename MembersHolder>
 431 struct level_insert<InsertIndex, Value, MembersHolder, true>
 432     : public level_insert_base<InsertIndex, typename MembersHolder::value_type, MembersHolder>
 433 {
 434     typedef level_insert_base<InsertIndex, typename MembersHolder::value_type, MembersHolder> base;
 435     typedef typename base::node node;
 436     typedef typename base::internal_node internal_node;
 437     typedef typename base::leaf leaf;
 438
 439     typedef typename MembersHolder::value_type value_type;
 440     typedef typename base::parameters_type parameters_type;
 441     typedef typename base::translator_type translator_type;
 442     typedef typename base::allocators_type allocators_type;
 443
 444     typedef typename base::node_pointer node_pointer;
 445     typedef typename base::size_type size_type;
 446
 447     inline level_insert(node_pointer & root,
 448                         size_type & leafs_level,
 449                         value_type const& v,
 450                         parameters_type const& parameters,
 451                         translator_type const& translator,
 452                         allocators_type & allocators,
 453                         size_type relative_level)
 454         : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
 455     {}
 456
 457     inline void operator()(internal_node & n)
 458     {
 459         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
 460         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
 461
 462         // next traversing step
 463         base::traverse(*this, n);                                                                       // MAY THROW (V, E: alloc, copy, N: alloc)
 464
 465         BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
 466
 467         if ( base::m_traverse_data.current_level == base::m_level - 1 )
 468         {
 469             base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
 470         }
 471
 472         base::recalculate_aabb_if_necessary(n);
 473     }
 474
 475     inline void operator()(leaf & n)
 476     {
 477         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
 478                                     "unexpected level");
 479         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
 480                                     base::m_level == (std::numeric_limits<size_t>::max)(),
 481                                     "unexpected level");
 482
 483         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
 484
 485         base::handle_possible_split(n);                                                                 // MAY THROW (V: alloc, copy, N: alloc)
 486     }
 487 };
 488
 489 template <typename Value, typename MembersHolder>
 490 struct level_insert<0, Value, MembersHolder, true>
 491     : public level_insert_base<0, typename MembersHolder::value_type, MembersHolder>
 492 {
 493     typedef level_insert_base<0, typename MembersHolder::value_type, MembersHolder> base;
 494     typedef typename base::node node;
 495     typedef typename base::internal_node internal_node;
 496     typedef typename base::leaf leaf;
 497
 498     typedef typename MembersHolder::value_type value_type;
 499     typedef typename base::parameters_type parameters_type;
 500     typedef typename base::translator_type translator_type;
 501     typedef typename base::allocators_type allocators_type;
 502
 503     typedef typename base::node_pointer node_pointer;
 504     typedef typename base::size_type size_type;
 505
 506     inline level_insert(node_pointer & root,
 507                         size_type & leafs_level,
 508                         value_type const& v,
 509                         parameters_type const& parameters,
 510                         translator_type const& translator,
 511                         allocators_type & allocators,
 512                         size_type relative_level)
 513         : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
 514     {}
 515
 516     inline void operator()(internal_node & n)
 517     {
 518         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
 519                                     "unexpected level");
 520         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
 521                                     "unexpected level");
 522
 523         // next traversing step
 524         base::traverse(*this, n);                                                                       // MAY THROW (V: alloc, copy, N: alloc)
 525
 526         base::recalculate_aabb_if_necessary(n);
 527     }
 528
 529     inline void operator()(leaf & n)
 530     {
 531         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
 532                                     "unexpected level");
 533         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
 534                                     base::m_level == (std::numeric_limits<size_t>::max)(),
 535                                     "unexpected level");
 536
 537         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
 538
 539         base::handle_possible_reinsert_or_split_of_root(n);                                             // MAY THROW (V: alloc, copy, N: alloc)
 540
 541         base::recalculate_aabb_if_necessary(n);
 542     }
 543 };
 544
 545 } // namespace rstar
 546
 547 // R*-tree insert visitor
 548 // After passing the Element to insert visitor the Element is managed by the tree
 549 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
 550 // because this visitor may delete it
 551 template <typename Element, typename MembersHolder>
 552 class insert<Element, MembersHolder, insert_reinsert_tag>
 553     : public MembersHolder::visitor
 554 {
 555     typedef typename MembersHolder::parameters_type parameters_type;
 556     typedef typename MembersHolder::translator_type translator_type;
 557     typedef typename MembersHolder::allocators_type allocators_type;
 558
 559     typedef typename MembersHolder::node node;
 560     typedef typename MembersHolder::internal_node internal_node;
 561     typedef typename MembersHolder::leaf leaf;
 562
 563     typedef typename allocators_type::node_pointer node_pointer;
 564     typedef typename allocators_type::size_type size_type;
 565
 566 public:
 567     inline insert(node_pointer & root,
 568                   size_type & leafs_level,
 569                   Element const& element,
 570                   parameters_type const& parameters,
 571                   translator_type const& translator,
 572                   allocators_type & allocators,
 573                   size_type relative_level = 0)
 574         : m_root(root), m_leafs_level(leafs_level), m_element(element)
 575         , m_parameters(parameters), m_translator(translator)
 576         , m_relative_level(relative_level), m_allocators(allocators)
 577     {}
 578
 579     inline void operator()(internal_node & n)
 580     {
 581         boost::ignore_unused(n);
 582         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root");
 583
 584         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
 585         if ( m_parameters.get_reinserted_elements() > 0 )
 586         {
 587             rstar::level_insert<0, Element, MembersHolder> lins_v(
 588                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
 589
 590             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
 591
 592             if ( !lins_v.result_elements.empty() )
 593             {
 594                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                       // MAY THROW (V, E: alloc, copy, N: alloc)
 595             }
 596         }
 597         else
 598         {
 599             visitors::insert<Element, MembersHolder, insert_default_tag> ins_v(
 600                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
 601
 602             rtree::apply_visitor(ins_v, *m_root);
 603         }
 604     }
 605
 606     inline void operator()(leaf & n)
 607     {
 608         boost::ignore_unused(n);
 609         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root");
 610
 611         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
 612         if ( m_parameters.get_reinserted_elements() > 0 )
 613         {
 614             rstar::level_insert<0, Element, MembersHolder> lins_v(
 615                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
 616
 617             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
 618
 619             // we're in the root, so root should be split and there should be no elements to reinsert
 620             BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
 621         }
 622         else
 623         {
 624             visitors::insert<Element, MembersHolder, insert_default_tag> ins_v(
 625                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
 626
 627             rtree::apply_visitor(ins_v, *m_root);
 628         }
 629     }
 630
 631 private:
 632     template <typename Elements>
 633     inline void recursive_reinsert(Elements & elements, size_t relative_level)
 634     {
 635         typedef typename Elements::value_type element_type;
 636
 637         // reinsert children starting from the minimum distance
 638         typename Elements::reverse_iterator it = elements.rbegin();
 639         for ( ; it != elements.rend() ; ++it)
 640         {
 641             rstar::level_insert<1, element_type, MembersHolder> lins_v(
 642                 m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
 643
 644             BOOST_TRY
 645             {
 646                 rtree::apply_visitor(lins_v, *m_root);                                                          // MAY THROW (V, E: alloc, copy, N: alloc)
 647             }
 648             BOOST_CATCH(...)
 649             {
 650                 ++it;
 651                 for ( ; it != elements.rend() ; ++it)
 652                     rtree::destroy_element<MembersHolder>::apply(*it, m_allocators);
 653                 BOOST_RETHROW                                                                                     // RETHROW
 654             }
 655             BOOST_CATCH_END
 656
 657             BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level");
 658
 659             // non-root relative level
 660             if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
 661             {
 662                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                   // MAY THROW (V, E: alloc, copy, N: alloc)
 663             }
 664         }
 665     }
 666
 667     node_pointer & m_root;
 668     size_type & m_leafs_level;
 669     Element const& m_element;
 670
 671     parameters_type const& m_parameters;
 672     translator_type const& m_translator;
 673
 674     size_type m_relative_level;
 675
 676     allocators_type & m_allocators;
 677 };
 678
 679 }}} // namespace detail::rtree::visitors
 680
 681 }}} // namespace boost::geometry::index
 682
 683 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP