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/constexpr.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_CONSTEXPR ((std::is_same<Element, value_type>::value)
0332                                     && ! index::detail::is_bounding_geometry
0333                                             <
0334                                                 typename indexable_type<translator_type>::type
0335                                             >::value)
0336         {
0337             geometry::detail::expand_by_epsilon(m_element_bounds);
0338         }
0339 #endif
0340     }
0341
0342     template <typename Visitor>
0343     inline void traverse(Visitor & visitor, internal_node & n)
0344     {
0345         // choose next node
0346         size_t choosen_node_index = rtree::choose_next_node<MembersHolder>
0347             ::apply(n, rtree::element_indexable(m_element, m_translator),
0348                     m_parameters,
0349                     m_leafs_level - m_traverse_data.current_level);
0350
0351         // expand the node to contain value
0352         index::detail::expand(
0353             rtree::elements(n)[choosen_node_index].first,
0354             m_element_bounds,
0355             index::detail::get_strategy(m_parameters));
0356
0357         // next traversing step
0358         traverse_apply_visitor(visitor, n, choosen_node_index);                                                 // MAY THROW (V, E: alloc, copy, N:alloc)
0359     }
0360
0361     // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
0362
0363     template <typename Node>
0364     inline void post_traverse(Node &n)
0365     {
0366         BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
0367                                     &n == &rtree::get<Node>(*m_traverse_data.current_element().second),
0368                                     "if node isn't the root current_child_index should be valid");
0369
0370         // handle overflow
0371         if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
0372         {
0373             // NOTE: If the exception is thrown current node may contain more than MAX elements or be empty.
0374             // Furthermore it may be empty root - internal node.
0375             split(n);                                                                                           // MAY THROW (V, E: alloc, copy, N:alloc)
0376         }
0377     }
0378
0379     template <typename Visitor>
0380     inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
0381     {
0382         // save previous traverse inputs and set new ones
0383         insert_traverse_data<internal_node, internal_node_pointer, size_type>
0384             backup_traverse_data = m_traverse_data;
0385
0386         // calculate new traverse inputs
0387         m_traverse_data.move_to_next_level(&n, choosen_node_index);
0388
0389         // next traversing step
0390         rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);                          // MAY THROW (V, E: alloc, copy, N:alloc)
0391
0392         // restore previous traverse inputs
0393         m_traverse_data = backup_traverse_data;
0394     }
0395
0396     // TODO: consider - split result returned as OutIter is faster than reference to the container. Why?
0397
0398     template <typename Node>
0399     inline void split(Node & n) const
0400     {
0401         typedef rtree::split<MembersHolder> split_algo;
0402
0403         typename split_algo::nodes_container_type additional_nodes;
0404         box_type n_box;
0405
0406         split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators);                // MAY THROW (V, E: alloc, copy, N:alloc)
0407
0408         BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
0409
0410         // TODO add all additional nodes
0411         // For kmeans algorithm:
0412         // elements number may be greater than node max elements count
0413         // split and reinsert must take node with some elements count
0414         // and container of additional elements (std::pair<Box, node*>s or Values)
0415         // and translator + allocators
0416         // where node_elements_count + additional_elements > node_max_elements_count
0417         // What with elements other than std::pair<Box, node*> ?
0418         // Implement template <node_tag> struct node_element_type or something like that
0419
0420         // for exception safety
0421         subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators);
0422
0423 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
0424         // Enlarge bounds of a leaf node.
0425         // It's because Points and Segments are compared WRT machine epsilon
0426         // This ensures that leafs' bounds correspond to the stored elements.
0427         if BOOST_GEOMETRY_CONSTEXPR ((std::is_same<Node, leaf>::value)
0428                                      && ! index::detail::is_bounding_geometry
0429                                             <
0430                                                 typename indexable_type<translator_type>::type
0431                                             >::value)
0432         {
0433             geometry::detail::expand_by_epsilon(n_box);
0434             geometry::detail::expand_by_epsilon(additional_nodes[0].first);
0435         }
0436
0437 #endif
0438
0439         // node is not the root - just add the new node
0440         if ( !m_traverse_data.current_is_root() )
0441         {
0442             // update old node's box
0443             m_traverse_data.current_element().first = n_box;
0444             // add new node to parent's children
0445             m_traverse_data.parent_elements().push_back(additional_nodes[0]);                                     // MAY THROW, STRONG (V, E: alloc, copy)
0446         }
0447         // node is the root - add level
0448         else
0449         {
0450             BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root");
0451
0452             // create new root and add nodes
0453             subtree_destroyer new_root(rtree::create_node<allocators_type, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
0454
0455             BOOST_TRY
0456             {
0457                 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)
0458                 rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);                 // MAY THROW, STRONG (E:alloc, copy)
0459             }
0460             BOOST_CATCH(...)
0461             {
0462                 // clear new root to not delete in the ~subtree_destroyer() potentially stored old root node
0463                 rtree::elements(rtree::get<internal_node>(*new_root)).clear();
0464                 BOOST_RETHROW                                                                                           // RETHROW
0465             }
0466             BOOST_CATCH_END
0467
0468             m_root_node = new_root.get();
0469             ++m_leafs_level;
0470
0471             new_root.release();
0472         }
0473
0474         additional_node_ptr.release();
0475     }
0476
0477     // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
0478
0479     Element const& m_element;
0480     box_type m_element_bounds;
0481     parameters_type const& m_parameters;
0482     translator_type const& m_translator;
0483     size_type const m_relative_level;
0484     size_type const m_level;
0485
0486     node_pointer & m_root_node;
0487     size_type & m_leafs_level;
0488
0489     // traversing input parameters
0490     insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data;
0491
0492     allocators_type & m_allocators;
0493 };
0494
0495 } // namespace detail
0496
0497 // Insert visitor forward declaration
0498 template
0499 <
0500     typename Element,
0501     typename MembersHolder,
0502     typename InsertTag = typename MembersHolder::options_type::insert_tag
0503 >
0504 class insert;
0505
0506 // Default insert visitor used for nodes elements
0507 // After passing the Element to insert visitor the Element is managed by the tree
0508 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
0509 // because this visitor may delete it
0510 template <typename Element, typename MembersHolder>
0511 class insert<Element, MembersHolder, insert_default_tag>
0512     : public detail::insert<Element, MembersHolder>
0513 {
0514 public:
0515     typedef detail::insert<Element, MembersHolder> base;
0516
0517     typedef typename base::parameters_type parameters_type;
0518     typedef typename base::translator_type translator_type;
0519     typedef typename base::allocators_type allocators_type;
0520
0521     typedef typename base::node node;
0522     typedef typename base::internal_node internal_node;
0523     typedef typename base::leaf leaf;
0524
0525     typedef typename base::node_pointer node_pointer;
0526     typedef typename base::size_type size_type;
0527
0528     inline insert(node_pointer & root,
0529                   size_type & leafs_level,
0530                   Element const& element,
0531                   parameters_type const& parameters,
0532                   translator_type const& translator,
0533                   allocators_type & allocators,
0534                   size_type relative_level = 0
0535     )
0536         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
0537     {}
0538
0539     inline void operator()(internal_node & n)
0540     {
0541         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
0542
0543         if ( base::m_traverse_data.current_level < base::m_level )
0544         {
0545             // next traversing step
0546             base::traverse(*this, n);                                                                           // MAY THROW (E: alloc, copy, N: alloc)
0547         }
0548         else
0549         {
0550             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
0551
0552             BOOST_TRY
0553             {
0554                 // push new child node
0555                 rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (E: alloc, copy)
0556             }
0557             BOOST_CATCH(...)
0558             {
0559                 // if the insert fails above, the element won't be stored in the tree
0560
0561                 rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators);
0562
0563                 BOOST_RETHROW                                                                                     // RETHROW
0564             }
0565             BOOST_CATCH_END
0566         }
0567
0568         base::post_traverse(n);                                                                                 // MAY THROW (E: alloc, copy, N: alloc)
0569     }
0570
0571     inline void operator()(leaf &)
0572     {
0573         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
0574     }
0575 };
0576
0577 // Default insert visitor specialized for Values elements
0578 template <typename MembersHolder>
0579 class insert<typename MembersHolder::value_type, MembersHolder, insert_default_tag>
0580     : public detail::insert<typename MembersHolder::value_type, MembersHolder>
0581 {
0582 public:
0583     typedef detail::insert<typename MembersHolder::value_type, MembersHolder> base;
0584
0585     typedef typename base::value_type value_type;
0586     typedef typename base::parameters_type parameters_type;
0587     typedef typename base::translator_type translator_type;
0588     typedef typename base::allocators_type allocators_type;
0589
0590     typedef typename base::node node;
0591     typedef typename base::internal_node internal_node;
0592     typedef typename base::leaf leaf;
0593
0594     typedef typename base::node_pointer node_pointer;
0595     typedef typename base::size_type size_type;
0596
0597     inline insert(node_pointer & root,
0598                   size_type & leafs_level,
0599                   value_type const& value,
0600                   parameters_type const& parameters,
0601                   translator_type const& translator,
0602                   allocators_type & allocators,
0603                   size_type relative_level = 0
0604     )
0605         : base(root, leafs_level, value, parameters, translator, allocators, relative_level)
0606     {}
0607
0608     inline void operator()(internal_node & n)
0609     {
0610         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
0611         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
0612
0613         // next traversing step
0614         base::traverse(*this, n);                                                                                   // MAY THROW (V, E: alloc, copy, N: alloc)
0615
0616         base::post_traverse(n);                                                                                     // MAY THROW (E: alloc, copy, N: alloc)
0617     }
0618
0619     inline void operator()(leaf & n)
0620     {
0621         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
0622         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
0623                                     base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
0624
0625         rtree::elements(n).push_back(base::m_element);                                                              // MAY THROW, STRONG (V: alloc, copy)
0626
0627         base::post_traverse(n);                                                                                     // MAY THROW (V: alloc, copy, N: alloc)
0628     }
0629 };
0630
0631 }}} // namespace detail::rtree::visitors
0632
0633 }}} // namespace boost::geometry::index
0634
0635 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP