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