rtree/visitors/insert.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree inserting visitor implementation
0004 //
0005 // Copyright (c) 2011-2023 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2023.
0008 // Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
0018
0019 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
0020 #include <type_traits>
0021 #endif
0022
0023 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
0024 #include <boost/geometry/core/static_assert.hpp>
0025
0026 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
0027 #include <boost/geometry/index/detail/algorithms/content.hpp>
0028 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0029 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0030 #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
0031 #include <boost/geometry/index/detail/rtree/options.hpp>
0032
0033 #include <boost/geometry/util/condition.hpp>
0034
0035 namespace boost { namespace geometry { namespace index {
0036
0037 namespace detail { namespace rtree {
0038
0039 // Default choose_next_node
0040 template
0041 <
0042     typename MembersHolder,
0043     typename ChooseNextNodeTag = typename MembersHolder::options_type::choose_next_node_tag
0044 >
0045 class choose_next_node;
0046
0047 template <typename MembersHolder>
0048 class choose_next_node<MembersHolder, choose_by_content_diff_tag>
0049 {
0050 public:
0051     typedef typename MembersHolder::box_type box_type;
0052     typedef typename MembersHolder::parameters_type parameters_type;
0053
0054     typedef typename MembersHolder::node node;
0055     typedef typename MembersHolder::internal_node internal_node;
0056     typedef typename MembersHolder::leaf leaf;
0057
0058     typedef typename rtree::elements_type<internal_node>::type children_type;
0059
0060     typedef typename index::detail::default_content_result<box_type>::type content_type;
0061
0062     template <typename Indexable>
0063     static inline size_t apply(internal_node & n,
0064                                Indexable const& indexable,
0065                                parameters_type const& parameters,
0066                                size_t /*node_relative_level*/)
0067     {
0068         children_type & children = rtree::elements(n);
0069
0070         BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty");
0071
0072         size_t children_count = children.size();
0073
0074         // choose index with smallest content change or smallest content
0075         size_t choosen_index = 0;
0076         content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
0077         content_type smallest_content = (std::numeric_limits<content_type>::max)();
0078
0079         // caculate areas and areas of all nodes' boxes
0080         for ( size_t i = 0 ; i < children_count ; ++i )
0081         {
0082             typedef typename children_type::value_type child_type;
0083             child_type const& ch_i = children[i];
0084
0085             // expanded child node's box
0086             box_type box_exp(ch_i.first);
0087             index::detail::expand(box_exp, indexable,
0088                                   index::detail::get_strategy(parameters));
0089
0090             // areas difference
0091             content_type content = index::detail::content(box_exp);
0092             content_type content_diff = content - index::detail::content(ch_i.first);
0093
0094             // update the result
0095             if ( content_diff < smallest_content_diff ||
0096                 ( content_diff == smallest_content_diff && content < smallest_content ) )
0097             {
0098                 smallest_content_diff = content_diff;
0099                 smallest_content = content;
0100                 choosen_index = i;
0101             }
0102         }
0103
0104         return choosen_index;
0105     }
0106 };
0107
0108 // ----------------------------------------------------------------------- //
0109
0110 // Not implemented here
0111 template
0112 <
0113     typename MembersHolder,
0114     typename RedistributeTag = typename MembersHolder::options_type::redistribute_tag
0115 >
0116 struct redistribute_elements
0117 {
0118     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0119         "Not implemented for this RedistributeTag type.",
0120         MembersHolder, RedistributeTag);
0121 };
0122
0123 // ----------------------------------------------------------------------- //
0124
0125 // Split algorithm
0126 template
0127 <
0128     typename MembersHolder,
0129     typename SplitTag = typename MembersHolder::options_type::split_tag
0130 >
0131 class split
0132 {
0133     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0134         "Not implemented for this SplitTag type.",
0135         MembersHolder, SplitTag);
0136 };
0137
0138 // Default split algorithm
0139 template <typename MembersHolder>
0140 class split<MembersHolder, split_default_tag>
0141 {
0142 protected:
0143     typedef typename MembersHolder::parameters_type parameters_type;
0144     typedef typename MembersHolder::box_type box_type;
0145     typedef typename MembersHolder::translator_type translator_type;
0146     typedef typename MembersHolder::allocators_type allocators_type;
0147     typedef typename MembersHolder::size_type size_type;
0148
0149     typedef typename MembersHolder::node node;
0150     typedef typename MembersHolder::internal_node internal_node;
0151     typedef typename MembersHolder::leaf leaf;
0152
0153     typedef typename MembersHolder::node_pointer node_pointer;
0154
0155 public:
0156     typedef index::detail::varray<
0157         typename rtree::elements_type<internal_node>::type::value_type,
0158         1
0159     > nodes_container_type;
0160
0161     template <typename Node>
0162     static inline void apply(nodes_container_type & additional_nodes,
0163                              Node & n,
0164                              box_type & n_box,
0165                              parameters_type const& parameters,
0166                              translator_type const& translator,
0167                              allocators_type & allocators)
0168     {
0169         // TODO - consider creating nodes always with sufficient memory allocated
0170
0171         // create additional node, use auto destroyer for automatic destruction on exception
0172         node_pointer n2_ptr = rtree::create_node<allocators_type, Node>::apply(allocators);                  // MAY THROW, STRONG (N: alloc)
0173         // create reference to the newly created node
0174         Node & n2 = rtree::get<Node>(*n2_ptr);
0175
0176         BOOST_TRY
0177         {
0178             // NOTE: thread-safety
0179             // After throwing an exception by redistribute_elements the original node may be not changed or
0180             // both nodes may be empty. In both cases the tree won't be valid r-tree.
0181             // The alternative is to create 2 (or more) additional nodes here and store backup info
0182             // in the original node, then, if exception was thrown, the node would always have more than max
0183             // elements.
0184             // The alternative is to use moving semantics in the implementations of redistribute_elements,
0185             // it will be possible to throw from std::move() in the case of e.g. static size nodes.
0186
0187             // redistribute elements
0188             box_type box2;
0189             redistribute_elements<MembersHolder>
0190                 ::apply(n, n2, n_box, box2, parameters, translator, allocators);                                   // MAY THROW (V, E: alloc, copy, copy)
0191
0192             // check numbers of elements
0193             BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
0194                 rtree::elements(n).size() <= parameters.get_max_elements(),
0195                 "unexpected number of elements");
0196             BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
0197                 rtree::elements(n2).size() <= parameters.get_max_elements(),
0198                 "unexpected number of elements");
0199
0200             // return the list of newly created nodes (this algorithm returns one)
0201             additional_nodes.push_back(rtree::make_ptr_pair(box2, n2_ptr));                                  // MAY THROW, STRONG (alloc, copy)
0202         }
0203         BOOST_CATCH(...)
0204         {
0205             // NOTE: This code is here to prevent leaving the rtree in a state
0206             //  after an exception is thrown in which pushing new element could
0207             //  result in assert or putting it outside the memory of node elements.
0208             typename rtree::elements_type<Node>::type & elements = rtree::elements(n);
0209             size_type const max_size = parameters.get_max_elements();
0210             if (elements.size() > max_size)
0211             {
0212                 rtree::destroy_element<MembersHolder>::apply(elements[max_size], allocators);
0213                 elements.pop_back();
0214             }
0215
0216             rtree::visitors::destroy<MembersHolder>::apply(n2_ptr, allocators);
0217
0218             BOOST_RETHROW
0219         }
0220         BOOST_CATCH_END
0221     }
0222 };
0223
0224 // ----------------------------------------------------------------------- //
0225
0226 namespace visitors { namespace detail {
0227
0228 template <typename InternalNode, typename InternalNodePtr, typename SizeType>
0229 struct insert_traverse_data
0230 {
0231     typedef typename rtree::elements_type<InternalNode>::type elements_type;
0232     typedef typename elements_type::value_type element_type;
0233     typedef typename elements_type::size_type elements_size_type;
0234     typedef SizeType size_type;
0235
0236     insert_traverse_data()
0237         : parent(0), current_child_index(0), current_level(0)
0238     {}
0239
0240     void move_to_next_level(InternalNodePtr new_parent,
0241                             elements_size_type new_child_index)
0242     {
0243         parent = new_parent;
0244         current_child_index = new_child_index;
0245         ++current_level;
0246     }
0247
0248     bool current_is_root() const
0249     {
0250         return 0 == parent;
0251     }
0252
0253     elements_type & parent_elements() const
0254     {
0255         BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
0256         return rtree::elements(*parent);
0257     }
0258
0259     element_type & current_element() const
0260     {
0261         BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
0262         return rtree::elements(*parent)[current_child_index];
0263     }
0264
0265     InternalNodePtr parent;
0266     elements_size_type current_child_index;
0267     size_type current_level;
0268 };
0269
0270 // Default insert visitor
0271 template <typename Element, typename MembersHolder>
0272 class insert
0273     : public MembersHolder::visitor
0274 {
0275 protected:
0276     typedef typename MembersHolder::box_type box_type;
0277     typedef typename MembersHolder::value_type value_type;
0278     typedef typename MembersHolder::parameters_type parameters_type;
0279     typedef typename MembersHolder::translator_type translator_type;
0280     typedef typename MembersHolder::allocators_type allocators_type;
0281
0282     typedef typename MembersHolder::node node;
0283     typedef typename MembersHolder::internal_node internal_node;
0284     typedef typename MembersHolder::leaf leaf;
0285
0286     typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
0287     typedef typename allocators_type::node_pointer node_pointer;
0288     typedef typename allocators_type::size_type size_type;
0289
0290     //typedef typename allocators_type::internal_node_pointer internal_node_pointer;
0291     typedef internal_node * internal_node_pointer;
0292
0293     inline insert(node_pointer & root,
0294                   size_type & leafs_level,
0295                   Element const& element,
0296                   parameters_type const& parameters,
0297                   translator_type const& translator,
0298                   allocators_type & allocators,
0299                   size_type relative_level = 0
0300     )
0301         : m_element(element)
0302         , m_parameters(parameters)
0303         , m_translator(translator)
0304         , m_relative_level(relative_level)
0305         , m_level(leafs_level - relative_level)
0306         , m_root_node(root)
0307         , m_leafs_level(leafs_level)
0308         , m_traverse_data()
0309         , m_allocators(allocators)
0310     {
0311         BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
0312         BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
0313         BOOST_GEOMETRY_INDEX_ASSERT(0 != m_root_node, "there is no root node");
0314         // TODO
0315         // assert - check if Box is correct
0316
0317         // When a value is inserted, during the tree traversal bounds of nodes
0318         // on a path from the root to a leaf must be expanded. So prepare
0319         // a bounding object at the beginning to not do it later for each node.
0320         // NOTE: This is actually only needed because conditionally the bounding
0321         //       object may be expanded below. Otherwise the indexable could be
0322         //       directly used instead
0323         index::detail::bounds(rtree::element_indexable(m_element, m_translator),
0324                               m_element_bounds,
0325                               index::detail::get_strategy(m_parameters));
0326
0327 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
0328         // Enlarge it in case if it's not bounding geometry type.
0329         // It's because Points and Segments are compared WRT machine epsilon
0330         // This ensures that leafs bounds correspond to the stored elements
0331         if (BOOST_GEOMETRY_CONDITION((
0332                 std::is_same<Element, value_type>::value
0333              && ! index::detail::is_bounding_geometry
0334                     <
0335                         typename indexable_type<translator_type>::type
0336                     >::value )) )
0337         {
0338             geometry::detail::expand_by_epsilon(m_element_bounds);
0339         }
0340 #endif
0341     }
0342
0343     template <typename Visitor>
0344     inline void traverse(Visitor & visitor, internal_node & n)
0345     {
0346         // choose next node
0347         size_t choosen_node_index = rtree::choose_next_node<MembersHolder>
0348             ::apply(n, rtree::element_indexable(m_element, m_translator),
0349                     m_parameters,
0350                     m_leafs_level - m_traverse_data.current_level);
0351
0352         // expand the node to contain value
0353         index::detail::expand(
0354             rtree::elements(n)[choosen_node_index].first,
0355             m_element_bounds,
0356             index::detail::get_strategy(m_parameters));
0357
0358         // next traversing step
0359         traverse_apply_visitor(visitor, n, choosen_node_index);                                                 // MAY THROW (V, E: alloc, copy, N:alloc)
0360     }
0361
0362     // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
0363
0364     template <typename Node>
0365     inline void post_traverse(Node &n)
0366     {
0367         BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
0368                                     &n == &rtree::get<Node>(*m_traverse_data.current_element().second),
0369                                     "if node isn't the root current_child_index should be valid");
0370
0371         // handle overflow
0372         if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
0373         {
0374             // NOTE: If the exception is thrown current node may contain more than MAX elements or be empty.
0375             // Furthermore it may be empty root - internal node.
0376             split(n);                                                                                           // MAY THROW (V, E: alloc, copy, N:alloc)
0377         }
0378     }
0379
0380     template <typename Visitor>
0381     inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
0382     {
0383         // save previous traverse inputs and set new ones
0384         insert_traverse_data<internal_node, internal_node_pointer, size_type>
0385             backup_traverse_data = m_traverse_data;
0386
0387         // calculate new traverse inputs
0388         m_traverse_data.move_to_next_level(&n, choosen_node_index);
0389
0390         // next traversing step
0391         rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);                          // MAY THROW (V, E: alloc, copy, N:alloc)
0392
0393         // restore previous traverse inputs
0394         m_traverse_data = backup_traverse_data;
0395     }
0396
0397     // TODO: consider - split result returned as OutIter is faster than reference to the container. Why?
0398
0399     template <typename Node>
0400     inline void split(Node & n) const
0401     {
0402         typedef rtree::split<MembersHolder> split_algo;
0403
0404         typename split_algo::nodes_container_type additional_nodes;
0405         box_type n_box;
0406
0407         split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators);                // MAY THROW (V, E: alloc, copy, N:alloc)
0408
0409         BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
0410
0411         // TODO add all additional nodes
0412         // For kmeans algorithm:
0413         // elements number may be greater than node max elements count
0414         // split and reinsert must take node with some elements count
0415         // and container of additional elements (std::pair<Box, node*>s or Values)
0416         // and translator + allocators
0417         // where node_elements_count + additional_elements > node_max_elements_count
0418         // What with elements other than std::pair<Box, node*> ?
0419         // Implement template <node_tag> struct node_element_type or something like that
0420
0421         // for exception safety
0422         subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators);
0423
0424 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
0425         // Enlarge bounds of a leaf node.
0426         // It's because Points and Segments are compared WRT machine epsilon
0427         // This ensures that leafs' bounds correspond to the stored elements.
0428         if (BOOST_GEOMETRY_CONDITION((
0429                 std::is_same<Node, leaf>::value
0430              && ! index::detail::is_bounding_geometry
0431                     <
0432                         typename indexable_type<translator_type>::type
0433                     >::value )))
0434         {
0435             geometry::detail::expand_by_epsilon(n_box);
0436             geometry::detail::expand_by_epsilon(additional_nodes[0].first);
0437         }
0438 #endif
0439
0440         // node is not the root - just add the new node
0441         if ( !m_traverse_data.current_is_root() )
0442         {
0443             // update old node's box
0444             m_traverse_data.current_element().first = n_box;
0445             // add new node to parent's children
0446             m_traverse_data.parent_elements().push_back(additional_nodes[0]);                                     // MAY THROW, STRONG (V, E: alloc, copy)
0447         }
0448         // node is the root - add level
0449         else
0450         {
0451             BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root");
0452
0453             // create new root and add nodes
0454             subtree_destroyer new_root(rtree::create_node<allocators_type, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
0455
0456             BOOST_TRY
0457             {
0458                 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)
0459                 rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);                 // MAY THROW, STRONG (E:alloc, copy)
0460             }
0461             BOOST_CATCH(...)
0462             {
0463                 // clear new root to not delete in the ~subtree_destroyer() potentially stored old root node
0464                 rtree::elements(rtree::get<internal_node>(*new_root)).clear();
0465                 BOOST_RETHROW                                                                                           // RETHROW
0466             }
0467             BOOST_CATCH_END
0468
0469             m_root_node = new_root.get();
0470             ++m_leafs_level;
0471
0472             new_root.release();
0473         }
0474
0475         additional_node_ptr.release();
0476     }
0477
0478     // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
0479
0480     Element const& m_element;
0481     box_type m_element_bounds;
0482     parameters_type const& m_parameters;
0483     translator_type const& m_translator;
0484     size_type const m_relative_level;
0485     size_type const m_level;
0486
0487     node_pointer & m_root_node;
0488     size_type & m_leafs_level;
0489
0490     // traversing input parameters
0491     insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data;
0492
0493     allocators_type & m_allocators;
0494 };
0495
0496 } // namespace detail
0497
0498 // Insert visitor forward declaration
0499 template
0500 <
0501     typename Element,
0502     typename MembersHolder,
0503     typename InsertTag = typename MembersHolder::options_type::insert_tag
0504 >
0505 class insert;
0506
0507 // Default insert visitor used for nodes elements
0508 // After passing the Element to insert visitor the Element is managed by the tree
0509 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
0510 // because this visitor may delete it
0511 template <typename Element, typename MembersHolder>
0512 class insert<Element, MembersHolder, insert_default_tag>
0513     : public detail::insert<Element, MembersHolder>
0514 {
0515 public:
0516     typedef detail::insert<Element, MembersHolder> base;
0517
0518     typedef typename base::parameters_type parameters_type;
0519     typedef typename base::translator_type translator_type;
0520     typedef typename base::allocators_type allocators_type;
0521
0522     typedef typename base::node node;
0523     typedef typename base::internal_node internal_node;
0524     typedef typename base::leaf leaf;
0525
0526     typedef typename base::node_pointer node_pointer;
0527     typedef typename base::size_type size_type;
0528
0529     inline insert(node_pointer & root,
0530                   size_type & leafs_level,
0531                   Element const& element,
0532                   parameters_type const& parameters,
0533                   translator_type const& translator,
0534                   allocators_type & allocators,
0535                   size_type relative_level = 0
0536     )
0537         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
0538     {}
0539
0540     inline void operator()(internal_node & n)
0541     {
0542         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
0543
0544         if ( base::m_traverse_data.current_level < base::m_level )
0545         {
0546             // next traversing step
0547             base::traverse(*this, n);                                                                           // MAY THROW (E: alloc, copy, N: alloc)
0548         }
0549         else
0550         {
0551             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
0552
0553             BOOST_TRY
0554             {
0555                 // push new child node
0556                 rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (E: alloc, copy)
0557             }
0558             BOOST_CATCH(...)
0559             {
0560                 // if the insert fails above, the element won't be stored in the tree
0561
0562                 rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
0563
0564                 BOOST_RETHROW                                                                                     // RETHROW
0565             }
0566             BOOST_CATCH_END
0567         }
0568
0569         base::post_traverse(n);                                                                                 // MAY THROW (E: alloc, copy, N: alloc)
0570     }
0571
0572     inline void operator()(leaf &)
0573     {
0574         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
0575     }
0576 };
0577
0578 // Default insert visitor specialized for Values elements
0579 template <typename MembersHolder>
0580 class insert<typename MembersHolder::value_type, MembersHolder, insert_default_tag>
0581     : public detail::insert<typename MembersHolder::value_type, MembersHolder>
0582 {
0583 public:
0584     typedef detail::insert<typename MembersHolder::value_type, MembersHolder> base;
0585
0586     typedef typename base::value_type value_type;
0587     typedef typename base::parameters_type parameters_type;
0588     typedef typename base::translator_type translator_type;
0589     typedef typename base::allocators_type allocators_type;
0590
0591     typedef typename base::node node;
0592     typedef typename base::internal_node internal_node;
0593     typedef typename base::leaf leaf;
0594
0595     typedef typename base::node_pointer node_pointer;
0596     typedef typename base::size_type size_type;
0597
0598     inline insert(node_pointer & root,
0599                   size_type & leafs_level,
0600                   value_type const& value,
0601                   parameters_type const& parameters,
0602                   translator_type const& translator,
0603                   allocators_type & allocators,
0604                   size_type relative_level = 0
0605     )
0606         : base(root, leafs_level, value, parameters, translator, allocators, relative_level)
0607     {}
0608
0609     inline void operator()(internal_node & n)
0610     {
0611         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
0612         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
0613
0614         // next traversing step
0615         base::traverse(*this, n);                                                                                   // MAY THROW (V, E: alloc, copy, N: alloc)
0616
0617         base::post_traverse(n);                                                                                     // MAY THROW (E: alloc, copy, N: alloc)
0618     }
0619
0620     inline void operator()(leaf & n)
0621     {
0622         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
0623         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
0624                                     base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
0625
0626         rtree::elements(n).push_back(base::m_element);                                                              // MAY THROW, STRONG (V: alloc, copy)
0627
0628         base::post_traverse(n);                                                                                     // MAY THROW (V: alloc, copy, N: alloc)
0629     }
0630 };
0631
0632 }}} // namespace detail::rtree::visitors
0633
0634 }}} // namespace boost::geometry::index
0635
0636 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP