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