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