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