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

   1 // Boost.Geometry Index
   2 //
   3 // R-tree inserting visitor implementation
   4 //
   5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // This file was modified by Oracle on 2019.
   8 // Modifications copyright (c) 2019 Oracle and/or its affiliates.
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10 //
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
  17
  18 #include <boost/type_traits/is_same.hpp>
  19
  20 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
  21 #include <boost/geometry/util/condition.hpp>
  22
  23 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
  24 #include <boost/geometry/index/detail/algorithms/content.hpp>
  25
  26 #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
  27
  28 namespace boost { namespace geometry { namespace index {
  29
  30 namespace detail { namespace rtree {
  31
  32 // Default choose_next_node
  33 template
  34 <
  35     typename MembersHolder,
  36     typename ChooseNextNodeTag = typename MembersHolder::options_type::choose_next_node_tag
  37 >
  38 class choose_next_node;
  39
  40 template <typename MembersHolder>
  41 class choose_next_node<MembersHolder, choose_by_content_diff_tag>
  42 {
  43 public:
  44     typedef typename MembersHolder::box_type box_type;
  45     typedef typename MembersHolder::parameters_type parameters_type;
  46
  47     typedef typename MembersHolder::node node;
  48     typedef typename MembersHolder::internal_node internal_node;
  49     typedef typename MembersHolder::leaf leaf;
  50
  51     typedef typename rtree::elements_type<internal_node>::type children_type;
  52
  53     typedef typename index::detail::default_content_result<box_type>::type content_type;
  54
  55     template <typename Indexable>
  56     static inline size_t apply(internal_node & n,
  57                                Indexable const& indexable,
  58                                parameters_type const& parameters,
  59                                size_t /*node_relative_level*/)
  60     {
  61         children_type & children = rtree::elements(n);
  62
  63         BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty");
  64
  65         size_t children_count = children.size();
  66
  67         // choose index with smallest content change or smallest content
  68         size_t choosen_index = 0;
  69         content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
  70         content_type smallest_content = (std::numeric_limits<content_type>::max)();
  71
  72         // caculate areas and areas of all nodes' boxes
  73         for ( size_t i = 0 ; i < children_count ; ++i )
  74         {
  75             typedef typename children_type::value_type child_type;
  76             child_type const& ch_i = children[i];
  77
  78             // expanded child node's box
  79             box_type box_exp(ch_i.first);
  80             index::detail::expand(box_exp, indexable,
  81                                   index::detail::get_strategy(parameters));
  82
  83             // areas difference
  84             content_type content = index::detail::content(box_exp);
  85             content_type content_diff = content - index::detail::content(ch_i.first);
  86
  87             // update the result
  88             if ( content_diff < smallest_content_diff ||
  89                 ( content_diff == smallest_content_diff && content < smallest_content ) )
  90             {
  91                 smallest_content_diff = content_diff;
  92                 smallest_content = content;
  93                 choosen_index = i;
  94             }
  95         }
  96
  97         return choosen_index;
  98     }
  99 };
 100
 101 // ----------------------------------------------------------------------- //
 102
 103 // Not implemented here
 104 template
 105 <
 106     typename MembersHolder,
 107     typename RedistributeTag = typename MembersHolder::options_type::redistribute_tag
 108 >
 109 struct redistribute_elements
 110 {
 111     BOOST_MPL_ASSERT_MSG(
 112         (false),
 113         NOT_IMPLEMENTED_FOR_THIS_REDISTRIBUTE_TAG_TYPE,
 114         (redistribute_elements));
 115 };
 116
 117 // ----------------------------------------------------------------------- //
 118
 119 // Split algorithm
 120 template
 121 <
 122     typename MembersHolder,
 123     typename SplitTag = typename MembersHolder::options_type::split_tag
 124 >
 125 class split
 126 {
 127     BOOST_MPL_ASSERT_MSG(
 128         (false),
 129         NOT_IMPLEMENTED_FOR_THIS_SPLIT_TAG_TYPE,
 130         (split));
 131 };
 132
 133 // Default split algorithm
 134 template <typename MembersHolder>
 135 class split<MembersHolder, split_default_tag>
 136 {
 137 protected:
 138     typedef typename MembersHolder::parameters_type parameters_type;
 139     typedef typename MembersHolder::box_type box_type;
 140     typedef typename MembersHolder::translator_type translator_type;
 141     typedef typename MembersHolder::allocators_type allocators_type;
 142     typedef typename MembersHolder::size_type size_type;
 143
 144     typedef typename MembersHolder::node node;
 145     typedef typename MembersHolder::internal_node internal_node;
 146     typedef typename MembersHolder::leaf leaf;
 147
 148     typedef typename MembersHolder::node_pointer node_pointer;
 149
 150 public:
 151     typedef index::detail::varray<
 152         typename rtree::elements_type<internal_node>::type::value_type,
 153         1
 154     > nodes_container_type;
 155
 156     template <typename Node>
 157     static inline void apply(nodes_container_type & additional_nodes,
 158                              Node & n,
 159                              box_type & n_box,
 160                              parameters_type const& parameters,
 161                              translator_type const& translator,
 162                              allocators_type & allocators)
 163     {
 164         // TODO - consider creating nodes always with sufficient memory allocated
 165
 166         // create additional node, use auto destroyer for automatic destruction on exception
 167         node_pointer n2_ptr = rtree::create_node<allocators_type, Node>::apply(allocators);                  // MAY THROW, STRONG (N: alloc)
 168         // create reference to the newly created node
 169         Node & n2 = rtree::get<Node>(*n2_ptr);
 170
 171         BOOST_TRY
 172         {
 173             // NOTE: thread-safety
 174             // After throwing an exception by redistribute_elements the original node may be not changed or
 175             // both nodes may be empty. In both cases the tree won't be valid r-tree.
 176             // The alternative is to create 2 (or more) additional nodes here and store backup info
 177             // in the original node, then, if exception was thrown, the node would always have more than max
 178             // elements.
 179             // The alternative is to use moving semantics in the implementations of redistribute_elements,
 180             // it will be possible to throw from boost::move() in the case of e.g. static size nodes.
 181
 182             // redistribute elements
 183             box_type box2;
 184             redistribute_elements<MembersHolder>
 185                 ::apply(n, n2, n_box, box2, parameters, translator, allocators);                                   // MAY THROW (V, E: alloc, copy, copy)
 186
 187             // check numbers of elements
 188             BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
 189                 rtree::elements(n).size() <= parameters.get_max_elements(),
 190                 "unexpected number of elements");
 191             BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
 192                 rtree::elements(n2).size() <= parameters.get_max_elements(),
 193                 "unexpected number of elements");
 194
 195             // return the list of newly created nodes (this algorithm returns one)
 196             additional_nodes.push_back(rtree::make_ptr_pair(box2, n2_ptr));                                  // MAY THROW, STRONG (alloc, copy)
 197         }
 198         BOOST_CATCH(...)
 199         {
 200             // NOTE: This code is here to prevent leaving the rtree in a state
 201             //  after an exception is thrown in which pushing new element could
 202             //  result in assert or putting it outside the memory of node elements.
 203             typename rtree::elements_type<Node>::type & elements = rtree::elements(n);
 204             size_type const max_size = parameters.get_max_elements();
 205             if (elements.size() > max_size)
 206             {
 207                 rtree::destroy_element<MembersHolder>::apply(elements[max_size], allocators);
 208                 elements.pop_back();
 209             }
 210
 211             rtree::visitors::destroy<MembersHolder>::apply(n2_ptr, allocators);
 212
 213             BOOST_RETHROW
 214         }
 215         BOOST_CATCH_END
 216     }
 217 };
 218
 219 // ----------------------------------------------------------------------- //
 220
 221 namespace visitors { namespace detail {
 222
 223 template <typename InternalNode, typename InternalNodePtr, typename SizeType>
 224 struct insert_traverse_data
 225 {
 226     typedef typename rtree::elements_type<InternalNode>::type elements_type;
 227     typedef typename elements_type::value_type element_type;
 228     typedef typename elements_type::size_type elements_size_type;
 229     typedef SizeType size_type;
 230
 231     insert_traverse_data()
 232         : parent(0), current_child_index(0), current_level(0)
 233     {}
 234
 235     void move_to_next_level(InternalNodePtr new_parent,
 236                             elements_size_type new_child_index)
 237     {
 238         parent = new_parent;
 239         current_child_index = new_child_index;
 240         ++current_level;
 241     }
 242
 243     bool current_is_root() const
 244     {
 245         return 0 == parent;
 246     }
 247
 248     elements_type & parent_elements() const
 249     {
 250         BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
 251         return rtree::elements(*parent);
 252     }
 253
 254     element_type & current_element() const
 255     {
 256         BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
 257         return rtree::elements(*parent)[current_child_index];
 258     }
 259
 260     InternalNodePtr parent;
 261     elements_size_type current_child_index;
 262     size_type current_level;
 263 };
 264
 265 // Default insert visitor
 266 template <typename Element, typename MembersHolder>
 267 class insert
 268     : MembersHolder::visitor
 269 {
 270 protected:
 271     typedef typename MembersHolder::box_type box_type;
 272     typedef typename MembersHolder::value_type value_type;
 273     typedef typename MembersHolder::parameters_type parameters_type;
 274     typedef typename MembersHolder::translator_type translator_type;
 275     typedef typename MembersHolder::allocators_type allocators_type;
 276
 277     typedef typename MembersHolder::node node;
 278     typedef typename MembersHolder::internal_node internal_node;
 279     typedef typename MembersHolder::leaf leaf;
 280
 281     typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
 282     typedef typename allocators_type::node_pointer node_pointer;
 283     typedef typename allocators_type::size_type size_type;
 284
 285     //typedef typename allocators_type::internal_node_pointer internal_node_pointer;
 286     typedef internal_node * internal_node_pointer;
 287
 288     inline insert(node_pointer & root,
 289                   size_type & leafs_level,
 290                   Element const& element,
 291                   parameters_type const& parameters,
 292                   translator_type const& translator,
 293                   allocators_type & allocators,
 294                   size_type relative_level = 0
 295     )
 296         : m_element(element)
 297         , m_parameters(parameters)
 298         , m_translator(translator)
 299         , m_relative_level(relative_level)
 300         , m_level(leafs_level - relative_level)
 301         , m_root_node(root)
 302         , m_leafs_level(leafs_level)
 303         , m_traverse_data()
 304         , m_allocators(allocators)
 305     {
 306         BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
 307         BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
 308         BOOST_GEOMETRY_INDEX_ASSERT(0 != m_root_node, "there is no root node");
 309         // TODO
 310         // assert - check if Box is correct
 311
 312         // When a value is inserted, during the tree traversal bounds of nodes
 313         // on a path from the root to a leaf must be expanded. So prepare
 314         // a bounding object at the beginning to not do it later for each node.
 315         // NOTE: This is actually only needed because conditionally the bounding
 316         //       object may be expanded below. Otherwise the indexable could be
 317         //       directly used instead
 318         index::detail::bounds(rtree::element_indexable(m_element, m_translator),
 319                               m_element_bounds,
 320                               index::detail::get_strategy(m_parameters));
 321
 322 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
 323         // Enlarge it in case if it's not bounding geometry type.
 324         // It's because Points and Segments are compared WRT machine epsilon
 325         // This ensures that leafs bounds correspond to the stored elements
 326         if (BOOST_GEOMETRY_CONDITION((
 327                 boost::is_same<Element, value_type>::value
 328              && ! index::detail::is_bounding_geometry
 329                     <
 330                         typename indexable_type<translator_type>::type
 331                     >::value )) )
 332         {
 333             geometry::detail::expand_by_epsilon(m_element_bounds);
 334         }
 335 #endif
 336     }
 337
 338     template <typename Visitor>
 339     inline void traverse(Visitor & visitor, internal_node & n)
 340     {
 341         // choose next node
 342         size_t choosen_node_index = rtree::choose_next_node<MembersHolder>
 343             ::apply(n, rtree::element_indexable(m_element, m_translator),
 344                     m_parameters,
 345                     m_leafs_level - m_traverse_data.current_level);
 346
 347         // expand the node to contain value
 348         index::detail::expand(
 349             rtree::elements(n)[choosen_node_index].first,
 350             m_element_bounds,
 351             index::detail::get_strategy(m_parameters));
 352
 353         // next traversing step
 354         traverse_apply_visitor(visitor, n, choosen_node_index);                                                 // MAY THROW (V, E: alloc, copy, N:alloc)
 355     }
 356
 357     // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
 358
 359     template <typename Node>
 360     inline void post_traverse(Node &n)
 361     {
 362         BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
 363                                     &n == &rtree::get<Node>(*m_traverse_data.current_element().second),
 364                                     "if node isn't the root current_child_index should be valid");
 365
 366         // handle overflow
 367         if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
 368         {
 369             // NOTE: If the exception is thrown current node may contain more than MAX elements or be empty.
 370             // Furthermore it may be empty root - internal node.
 371             split(n);                                                                                           // MAY THROW (V, E: alloc, copy, N:alloc)
 372         }
 373     }
 374
 375     template <typename Visitor>
 376     inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
 377     {
 378         // save previous traverse inputs and set new ones
 379         insert_traverse_data<internal_node, internal_node_pointer, size_type>
 380             backup_traverse_data = m_traverse_data;
 381
 382         // calculate new traverse inputs
 383         m_traverse_data.move_to_next_level(&n, choosen_node_index);
 384
 385         // next traversing step
 386         rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);                          // MAY THROW (V, E: alloc, copy, N:alloc)
 387
 388         // restore previous traverse inputs
 389         m_traverse_data = backup_traverse_data;
 390     }
 391
 392     // TODO: consider - split result returned as OutIter is faster than reference to the container. Why?
 393
 394     template <typename Node>
 395     inline void split(Node & n) const
 396     {
 397         typedef rtree::split<MembersHolder> split_algo;
 398
 399         typename split_algo::nodes_container_type additional_nodes;
 400         box_type n_box;
 401
 402         split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators);                // MAY THROW (V, E: alloc, copy, N:alloc)
 403
 404         BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
 405
 406         // TODO add all additional nodes
 407         // For kmeans algorithm:
 408         // elements number may be greater than node max elements count
 409         // split and reinsert must take node with some elements count
 410         // and container of additional elements (std::pair<Box, node*>s or Values)
 411         // and translator + allocators
 412         // where node_elements_count + additional_elements > node_max_elements_count
 413         // What with elements other than std::pair<Box, node*> ?
 414         // Implement template <node_tag> struct node_element_type or something like that
 415
 416         // for exception safety
 417         subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators);
 418
 419 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
 420         // Enlarge bounds of a leaf node.
 421         // It's because Points and Segments are compared WRT machine epsilon
 422         // This ensures that leafs' bounds correspond to the stored elements.
 423         if (BOOST_GEOMETRY_CONDITION((
 424                 boost::is_same<Node, leaf>::value
 425              && ! index::detail::is_bounding_geometry
 426                     <
 427                         typename indexable_type<translator_type>::type
 428                     >::value )))
 429         {
 430             geometry::detail::expand_by_epsilon(n_box);
 431             geometry::detail::expand_by_epsilon(additional_nodes[0].first);
 432         }
 433 #endif
 434
 435         // node is not the root - just add the new node
 436         if ( !m_traverse_data.current_is_root() )
 437         {
 438             // update old node's box
 439             m_traverse_data.current_element().first = n_box;
 440             // add new node to parent's children
 441             m_traverse_data.parent_elements().push_back(additional_nodes[0]);                                     // MAY THROW, STRONG (V, E: alloc, copy)
 442         }
 443         // node is the root - add level
 444         else
 445         {
 446             BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root");
 447
 448             // create new root and add nodes
 449             subtree_destroyer new_root(rtree::create_node<allocators_type, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
 450
 451             BOOST_TRY
 452             {
 453                 rtree::elements(rtree::get<internal_node>(*new_root)).push_back(rtree::make_ptr_pair(n_box, m_root_node));  // MAY THROW, STRONG (E:alloc, copy)
 454                 rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);                 // MAY THROW, STRONG (E:alloc, copy)
 455             }
 456             BOOST_CATCH(...)
 457             {
 458                 // clear new root to not delete in the ~subtree_destroyer() potentially stored old root node
 459                 rtree::elements(rtree::get<internal_node>(*new_root)).clear();
 460                 BOOST_RETHROW                                                                                           // RETHROW
 461             }
 462             BOOST_CATCH_END
 463
 464             m_root_node = new_root.get();
 465             ++m_leafs_level;
 466
 467             new_root.release();
 468         }
 469
 470         additional_node_ptr.release();
 471     }
 472
 473     // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
 474
 475     Element const& m_element;
 476     box_type m_element_bounds;
 477     parameters_type const& m_parameters;
 478     translator_type const& m_translator;
 479     size_type const m_relative_level;
 480     size_type const m_level;
 481
 482     node_pointer & m_root_node;
 483     size_type & m_leafs_level;
 484
 485     // traversing input parameters
 486     insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data;
 487
 488     allocators_type & m_allocators;
 489 };
 490
 491 } // namespace detail
 492
 493 // Insert visitor forward declaration
 494 template
 495 <
 496     typename Element,
 497     typename MembersHolder,
 498     typename InsertTag = typename MembersHolder::options_type::insert_tag
 499 >
 500 class insert;
 501
 502 // Default insert visitor used for nodes elements
 503 // After passing the Element to insert visitor the Element is managed by the tree
 504 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
 505 // because this visitor may delete it
 506 template <typename Element, typename MembersHolder>
 507 class insert<Element, MembersHolder, insert_default_tag>
 508     : public detail::insert<Element, MembersHolder>
 509 {
 510 public:
 511     typedef detail::insert<Element, MembersHolder> base;
 512
 513     typedef typename base::parameters_type parameters_type;
 514     typedef typename base::translator_type translator_type;
 515     typedef typename base::allocators_type allocators_type;
 516
 517     typedef typename base::node node;
 518     typedef typename base::internal_node internal_node;
 519     typedef typename base::leaf leaf;
 520
 521     typedef typename base::node_pointer node_pointer;
 522     typedef typename base::size_type size_type;
 523
 524     inline insert(node_pointer & root,
 525                   size_type & leafs_level,
 526                   Element const& element,
 527                   parameters_type const& parameters,
 528                   translator_type const& translator,
 529                   allocators_type & allocators,
 530                   size_type relative_level = 0
 531     )
 532         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
 533     {}
 534
 535     inline void operator()(internal_node & n)
 536     {
 537         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
 538
 539         if ( base::m_traverse_data.current_level < base::m_level )
 540         {
 541             // next traversing step
 542             base::traverse(*this, n);                                                                           // MAY THROW (E: alloc, copy, N: alloc)
 543         }
 544         else
 545         {
 546             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
 547
 548             BOOST_TRY
 549             {
 550                 // push new child node
 551                 rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (E: alloc, copy)
 552             }
 553             BOOST_CATCH(...)
 554             {
 555                 // if the insert fails above, the element won't be stored in the tree
 556
 557                 rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
 558
 559                 BOOST_RETHROW                                                                                     // RETHROW
 560             }
 561             BOOST_CATCH_END
 562         }
 563
 564         base::post_traverse(n);                                                                                 // MAY THROW (E: alloc, copy, N: alloc)
 565     }
 566
 567     inline void operator()(leaf &)
 568     {
 569         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
 570     }
 571 };
 572
 573 // Default insert visitor specialized for Values elements
 574 template <typename MembersHolder>
 575 class insert<typename MembersHolder::value_type, MembersHolder, insert_default_tag>
 576     : public detail::insert<typename MembersHolder::value_type, MembersHolder>
 577 {
 578 public:
 579     typedef detail::insert<typename MembersHolder::value_type, MembersHolder> base;
 580
 581     typedef typename base::value_type value_type;
 582     typedef typename base::parameters_type parameters_type;
 583     typedef typename base::translator_type translator_type;
 584     typedef typename base::allocators_type allocators_type;
 585
 586     typedef typename base::node node;
 587     typedef typename base::internal_node internal_node;
 588     typedef typename base::leaf leaf;
 589
 590     typedef typename base::node_pointer node_pointer;
 591     typedef typename base::size_type size_type;
 592
 593     inline insert(node_pointer & root,
 594                   size_type & leafs_level,
 595                   value_type const& value,
 596                   parameters_type const& parameters,
 597                   translator_type const& translator,
 598                   allocators_type & allocators,
 599                   size_type relative_level = 0
 600     )
 601         : base(root, leafs_level, value, parameters, translator, allocators, relative_level)
 602     {}
 603
 604     inline void operator()(internal_node & n)
 605     {
 606         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
 607         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
 608
 609         // next traversing step
 610         base::traverse(*this, n);                                                                                   // MAY THROW (V, E: alloc, copy, N: alloc)
 611
 612         base::post_traverse(n);                                                                                     // MAY THROW (E: alloc, copy, N: alloc)
 613     }
 614
 615     inline void operator()(leaf & n)
 616     {
 617         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
 618         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
 619                                     base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
 620
 621         rtree::elements(n).push_back(base::m_element);                                                              // MAY THROW, STRONG (V: alloc, copy)
 622
 623         base::post_traverse(n);                                                                                     // MAY THROW (V: alloc, copy, N: alloc)
 624     }
 625 };
 626
 627 }}} // namespace detail::rtree::visitors
 628
 629 }}} // namespace boost::geometry::index
 630
 631 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP