Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // R-tree R*-tree insert algorithm implementation
Chris@16: //
Chris@101: // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/algorithms/content.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index {
Chris@16: 
Chris@16: namespace detail { namespace rtree { namespace visitors {
Chris@16: 
Chris@16: namespace rstar {
Chris@16: 
Chris@16: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: class remove_elements_to_reinsert
Chris@16: {
Chris@16: public:
Chris@16:     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
Chris@16:     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
Chris@16:     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
Chris@16: 
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     //typedef typename Allocators::internal_node_pointer internal_node_pointer;
Chris@16:     typedef internal_node * internal_node_pointer;
Chris@16: 
Chris@16:     template <typename ResultElements, typename Node>
Chris@16:     static inline void apply(ResultElements & result_elements,
Chris@16:                              Node & n,
Chris@16:                              internal_node_pointer parent,
Chris@16:                              size_t current_child_index,
Chris@16:                              parameters_type const& parameters,
Chris@16:                              Translator const& translator,
Chris@16:                              Allocators & allocators)
Chris@16:     {
Chris@16:         typedef typename rtree::elements_type<Node>::type elements_type;
Chris@16:         typedef typename elements_type::value_type element_type;
Chris@16:         typedef typename geometry::point_type<Box>::type point_type;
Chris@16:         // TODO: awulkiew - change second point_type to the point type of the Indexable?
Chris@101:         typedef typename
Chris@101:             geometry::default_comparable_distance_result<point_type>::type
Chris@101:                 comparable_distance_type;
Chris@16: 
Chris@16:         elements_type & elements = rtree::elements(n);
Chris@16: 
Chris@16:         const size_t elements_count = parameters.get_max_elements() + 1;
Chris@16:         const size_t reinserted_elements_count = (::std::min)(parameters.get_reinserted_elements(), elements_count - parameters.get_min_elements());
Chris@16: 
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
Chris@16: 
Chris@16:         // calculate current node's center
Chris@16:         point_type node_center;
Chris@16:         geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center);
Chris@16: 
Chris@16:         // fill the container of centers' distances of children from current node's center
Chris@16:         typedef typename index::detail::rtree::container_from_elements_type<
Chris@16:             elements_type,
Chris@101:             std::pair<comparable_distance_type, element_type>
Chris@16:         >::type sorted_elements_type;
Chris@101: 
Chris@16:         sorted_elements_type sorted_elements;
Chris@16:         // If constructor is used instead of resize() MS implementation leaks here
Chris@16:         sorted_elements.reserve(elements_count);                                                         // MAY THROW, STRONG (V, E: alloc, copy)
Chris@16:         
Chris@16:         for ( typename elements_type::const_iterator it = elements.begin() ;
Chris@16:               it != elements.end() ; ++it )
Chris@16:         {
Chris@16:             point_type element_center;
Chris@16:             geometry::centroid( rtree::element_indexable(*it, translator), element_center);
Chris@16:             sorted_elements.push_back(std::make_pair(
Chris@16:                 geometry::comparable_distance(node_center, element_center),
Chris@16:                 *it));                                                                                  // MAY THROW (V, E: copy)
Chris@16:         }
Chris@16: 
Chris@16:         // sort elements by distances from center
Chris@16:         std::partial_sort(
Chris@16:             sorted_elements.begin(),
Chris@16:             sorted_elements.begin() + reinserted_elements_count,
Chris@16:             sorted_elements.end(),
Chris@101:             distances_dsc<comparable_distance_type, element_type>);                                                // MAY THROW, BASIC (V, E: copy)
Chris@16: 
Chris@16:         // copy elements which will be reinserted
Chris@16:         result_elements.clear();
Chris@16:         result_elements.reserve(reinserted_elements_count);                                             // MAY THROW, STRONG (V, E: alloc, copy)
Chris@16:         for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() ;
Chris@16:               it != sorted_elements.begin() + reinserted_elements_count ; ++it )
Chris@16:         {
Chris@16:             result_elements.push_back(it->second);                                                      // MAY THROW (V, E: copy)
Chris@16:         }
Chris@16: 
Chris@16:         BOOST_TRY
Chris@16:         {
Chris@16:             // copy remaining elements to the current node
Chris@16:             elements.clear();
Chris@16:             elements.reserve(elements_count - reinserted_elements_count);                                // SHOULDN'T THROW (new_size <= old size)
Chris@16:             for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() + reinserted_elements_count;
Chris@16:                   it != sorted_elements.end() ; ++it )
Chris@16:             {
Chris@16:                 elements.push_back(it->second);                                                         // MAY THROW (V, E: copy)
Chris@16:             }
Chris@16:         }
Chris@16:         BOOST_CATCH(...)
Chris@16:         {
Chris@16:             elements.clear();
Chris@16: 
Chris@16:             for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ;
Chris@16:                   it != sorted_elements.end() ; ++it )
Chris@16:             {
Chris@16:                 destroy_element<Value, Options, Translator, Box, Allocators>::apply(it->second, allocators);
Chris@16:             }
Chris@16: 
Chris@16:             BOOST_RETHROW                                                                                 // RETHROW
Chris@16:         }
Chris@16:         BOOST_CATCH_END
Chris@16: 
Chris@16:         ::boost::ignore_unused_variable_warning(parameters);
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     template <typename Distance, typename El>
Chris@16:     static inline bool distances_asc(
Chris@16:         std::pair<Distance, El> const& d1,
Chris@16:         std::pair<Distance, El> const& d2)
Chris@16:     {
Chris@16:         return d1.first < d2.first;
Chris@16:     }
Chris@16:     
Chris@16:     template <typename Distance, typename El>
Chris@16:     static inline bool distances_dsc(
Chris@16:         std::pair<Distance, El> const& d1,
Chris@16:         std::pair<Distance, El> const& d2)
Chris@16:     {
Chris@16:         return d1.first > d2.first;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators>
Chris@16: struct level_insert_elements_type
Chris@16: {
Chris@16:     typedef typename rtree::elements_type<
Chris@16:         typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
Chris@16:     >::type type;
Chris@16: };
Chris@16: 
Chris@16: template <typename Value, typename Options, typename Box, typename Allocators>
Chris@16: struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators>
Chris@16: {
Chris@16:     typedef typename rtree::elements_type<
Chris@16:         typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
Chris@16:     >::type type;
Chris@16: };
Chris@16: 
Chris@16: template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct level_insert_base
Chris@16:     : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
Chris@16: {
Chris@16:     typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
Chris@16:     typedef typename base::node node;
Chris@16:     typedef typename base::internal_node internal_node;
Chris@16:     typedef typename base::leaf leaf;
Chris@16: 
Chris@16:     typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type;
Chris@16:     typedef typename index::detail::rtree::container_from_elements_type<
Chris@16:         elements_type,
Chris@16:         typename elements_type::value_type
Chris@16:     >::type result_elements_type;
Chris@16: 
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename Allocators::node_pointer node_pointer;
Chris@101:     typedef typename Allocators::size_type size_type;
Chris@16: 
Chris@16:     inline level_insert_base(node_pointer & root,
Chris@101:                              size_type & leafs_level,
Chris@16:                              Element const& element,
Chris@16:                              parameters_type const& parameters,
Chris@16:                              Translator const& translator,
Chris@16:                              Allocators & allocators,
Chris@101:                              size_type relative_level)
Chris@16:         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
Chris@16:         , result_relative_level(0)
Chris@16:     {}
Chris@16: 
Chris@16:     template <typename Node>
Chris@16:     inline void handle_possible_reinsert_or_split_of_root(Node &n)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
Chris@16: 
Chris@16:         result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
Chris@16: 
Chris@16:         // overflow
Chris@16:         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
Chris@16:         {
Chris@16:             // node isn't root node
Chris@16:             if ( !base::m_traverse_data.current_is_root() )
Chris@16:             {
Chris@16:                 // NOTE: exception-safety
Chris@16:                 // After an exception result_elements may contain garbage, don't use it
Chris@16:                 rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
Chris@16:                     result_elements, n,
Chris@16:                     base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
Chris@16:                     base::m_parameters, base::m_translator, base::m_allocators);                            // MAY THROW, BASIC (V, E: alloc, copy)
Chris@16:             }
Chris@16:             // node is root node
Chris@16:             else
Chris@16:             {
Chris@16:                 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*base::m_root_node), "node should be the root node");
Chris@16:                 base::split(n);                                                                             // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Node>
Chris@16:     inline void handle_possible_split(Node &n) const
Chris@16:     {
Chris@16:         // overflow
Chris@16:         if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
Chris@16:         {
Chris@16:             base::split(n);                                                                                 // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Node>
Chris@16:     inline void recalculate_aabb_if_necessary(Node &n) const
Chris@16:     {
Chris@16:         if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
Chris@16:         {
Chris@16:             // calulate node's new box
Chris@16:             base::m_traverse_data.current_element().first =
Chris@16:                 elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@101:     size_type result_relative_level;
Chris@16:     result_elements_type result_elements;
Chris@16: };
Chris@16: 
Chris@16: template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct level_insert
Chris@16:     : public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators>
Chris@16: {
Chris@16:     typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
Chris@16:     typedef typename base::node node;
Chris@16:     typedef typename base::internal_node internal_node;
Chris@16:     typedef typename base::leaf leaf;
Chris@16: 
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename Allocators::node_pointer node_pointer;
Chris@101:     typedef typename Allocators::size_type size_type;
Chris@16: 
Chris@16:     inline level_insert(node_pointer & root,
Chris@101:                         size_type & leafs_level,
Chris@16:                         Element const& element,
Chris@16:                         parameters_type const& parameters,
Chris@16:                         Translator const& translator,
Chris@16:                         Allocators & allocators,
Chris@101:                         size_type relative_level)
Chris@16:         : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
Chris@16:     {}
Chris@16: 
Chris@16:     inline void operator()(internal_node & n)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
Chris@16: 
Chris@16:         if ( base::m_traverse_data.current_level < base::m_level )
Chris@16:         {
Chris@16:             // next traversing step
Chris@16:             base::traverse(*this, n);                                                                       // MAY THROW (E: alloc, copy, N: alloc)
Chris@16: 
Chris@16:             // further insert
Chris@16:             if ( 0 < InsertIndex )
Chris@16:             {
Chris@16:                 BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
Chris@16: 
Chris@16:                 if ( base::m_traverse_data.current_level == base::m_level - 1 )
Chris@16:                 {
Chris@16:                     base::handle_possible_reinsert_or_split_of_root(n);                                     // MAY THROW (E: alloc, copy, N: alloc)
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
Chris@16: 
Chris@16:             BOOST_TRY
Chris@16:             {
Chris@16:                 // push new child node
Chris@16:                 rtree::elements(n).push_back(base::m_element);                                              // MAY THROW, STRONG (E: alloc, copy)
Chris@16:             }
Chris@16:             BOOST_CATCH(...)
Chris@16:             {
Chris@16:                 // NOTE: exception-safety
Chris@16:                 // if the insert fails above, the element won't be stored in the tree, so delete it
Chris@16: 
Chris@16:                 rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
Chris@16:                 rtree::apply_visitor(del_v, *base::m_element.second);
Chris@16: 
Chris@16:                 BOOST_RETHROW                                                                                 // RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16: 
Chris@16:             // first insert
Chris@16:             if ( 0 == InsertIndex )
Chris@16:             {
Chris@16:                 base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
Chris@16:             }
Chris@16:             // not the first insert
Chris@16:             else
Chris@16:             {
Chris@16:                 base::handle_possible_split(n);                                                             // MAY THROW (E: alloc, N: alloc)
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         base::recalculate_aabb_if_necessary(n);
Chris@16:     }
Chris@16: 
Chris@16:     inline void operator()(leaf &)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <size_t InsertIndex, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct level_insert<InsertIndex, Value, Value, Options, Translator, Box, Allocators>
Chris@16:     : public level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators>
Chris@16: {
Chris@16:     typedef level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators> base;
Chris@16:     typedef typename base::node node;
Chris@16:     typedef typename base::internal_node internal_node;
Chris@16:     typedef typename base::leaf leaf;
Chris@16: 
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename Allocators::node_pointer node_pointer;
Chris@101:     typedef typename Allocators::size_type size_type;
Chris@16: 
Chris@16:     inline level_insert(node_pointer & root,
Chris@101:                         size_type & leafs_level,
Chris@16:                         Value const& v,
Chris@16:                         parameters_type const& parameters,
Chris@16:                         Translator const& translator,
Chris@16:                         Allocators & allocators,
Chris@101:                         size_type relative_level)
Chris@16:         : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
Chris@16:     {}
Chris@16: 
Chris@16:     inline void operator()(internal_node & n)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
Chris@16: 
Chris@16:         // next traversing step
Chris@16:         base::traverse(*this, n);                                                                       // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16: 
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
Chris@16:         
Chris@16:         if ( base::m_traverse_data.current_level == base::m_level - 1 )
Chris@16:         {
Chris@16:             base::handle_possible_reinsert_or_split_of_root(n);                                         // MAY THROW (E: alloc, copy, N: alloc)
Chris@16:         }
Chris@16: 
Chris@16:         base::recalculate_aabb_if_necessary(n);
Chris@16:     }
Chris@16: 
Chris@16:     inline void operator()(leaf & n)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
Chris@16:                                     "unexpected level");
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
Chris@16:                                     base::m_level == (std::numeric_limits<size_t>::max)(),
Chris@16:                                     "unexpected level");
Chris@16:         
Chris@16:         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
Chris@16: 
Chris@16:         base::handle_possible_split(n);                                                                 // MAY THROW (V: alloc, copy, N: alloc)
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct level_insert<0, Value, Value, Options, Translator, Box, Allocators>
Chris@16:     : public level_insert_base<0, Value, Value, Options, Translator, Box, Allocators>
Chris@16: {
Chris@16:     typedef level_insert_base<0, Value, Value, Options, Translator, Box, Allocators> base;
Chris@16:     typedef typename base::node node;
Chris@16:     typedef typename base::internal_node internal_node;
Chris@16:     typedef typename base::leaf leaf;
Chris@16: 
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename Allocators::node_pointer node_pointer;
Chris@101:     typedef typename Allocators::size_type size_type;
Chris@16: 
Chris@16:     inline level_insert(node_pointer & root,
Chris@101:                         size_type & leafs_level,
Chris@16:                         Value const& v,
Chris@16:                         parameters_type const& parameters,
Chris@16:                         Translator const& translator,
Chris@16:                         Allocators & allocators,
Chris@101:                         size_type relative_level)
Chris@16:         : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
Chris@16:     {}
Chris@16: 
Chris@16:     inline void operator()(internal_node & n)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
Chris@16:                                     "unexpected level");
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
Chris@16:                                     "unexpected level");
Chris@16: 
Chris@16:         // next traversing step
Chris@16:         base::traverse(*this, n);                                                                       // MAY THROW (V: alloc, copy, N: alloc)
Chris@16: 
Chris@16:         base::recalculate_aabb_if_necessary(n);
Chris@16:     }
Chris@16: 
Chris@16:     inline void operator()(leaf & n)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
Chris@16:                                     "unexpected level");
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
Chris@16:                                     base::m_level == (std::numeric_limits<size_t>::max)(),
Chris@16:                                     "unexpected level");
Chris@16: 
Chris@16:         rtree::elements(n).push_back(base::m_element);                                                  // MAY THROW, STRONG (V: alloc, copy)
Chris@16: 
Chris@16:         base::handle_possible_reinsert_or_split_of_root(n);                                             // MAY THROW (V: alloc, copy, N: alloc)
Chris@16:         
Chris@16:         base::recalculate_aabb_if_necessary(n);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: } // namespace rstar
Chris@16: 
Chris@16: // R*-tree insert visitor
Chris@16: // After passing the Element to insert visitor the Element is managed by the tree
Chris@16: // I.e. one should not delete the node passed to the insert visitor after exception is thrown
Chris@16: // because this visitor may delete it
Chris@16: template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: class insert<Element, Value, Options, Translator, Box, Allocators, insert_reinsert_tag>
Chris@16:     : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
Chris@16: {
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
Chris@16:     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
Chris@16:     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
Chris@16: 
Chris@16:     typedef typename Allocators::node_pointer node_pointer;
Chris@101:     typedef typename Allocators::size_type size_type;
Chris@16: 
Chris@16: public:
Chris@16:     inline insert(node_pointer & root,
Chris@101:                   size_type & leafs_level,
Chris@16:                   Element const& element,
Chris@16:                   parameters_type const& parameters,
Chris@16:                   Translator const& translator,
Chris@16:                   Allocators & allocators,
Chris@101:                   size_type relative_level = 0)
Chris@16:         : m_root(root), m_leafs_level(leafs_level), m_element(element)
Chris@16:         , m_parameters(parameters), m_translator(translator)
Chris@16:         , m_relative_level(relative_level), m_allocators(allocators)
Chris@16:     {}
Chris@16: 
Chris@101:     inline void operator()(internal_node & n)
Chris@16:     {
Chris@101:         boost::ignore_unused(n);
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root");
Chris@16: 
Chris@16:         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
Chris@16:         if ( m_parameters.get_reinserted_elements() > 0 )
Chris@16:         {
Chris@16:             rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
Chris@16:                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
Chris@16: 
Chris@16:             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16: 
Chris@16:             if ( !lins_v.result_elements.empty() )
Chris@16:             {
Chris@16:                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                       // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16:             }
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v(
Chris@16:                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
Chris@16: 
Chris@16:             rtree::apply_visitor(ins_v, *m_root); 
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@101:     inline void operator()(leaf & n)
Chris@16:     {
Chris@101:         boost::ignore_unused(n);
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root");
Chris@16: 
Chris@16:         // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
Chris@16:         if ( m_parameters.get_reinserted_elements() > 0 )
Chris@16:         {
Chris@16:             rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
Chris@16:                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
Chris@16: 
Chris@16:             rtree::apply_visitor(lins_v, *m_root);                                                              // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16: 
Chris@16:             // we're in the root, so root should be split and there should be no elements to reinsert
Chris@16:             BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v(
Chris@16:                 m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
Chris@16: 
Chris@16:             rtree::apply_visitor(ins_v, *m_root); 
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     template <typename Elements>
Chris@16:     inline void recursive_reinsert(Elements & elements, size_t relative_level)
Chris@16:     {
Chris@16:         typedef typename Elements::value_type element_type;
Chris@16: 
Chris@16:         // reinsert children starting from the minimum distance
Chris@16:         typename Elements::reverse_iterator it = elements.rbegin();
Chris@16:         for ( ; it != elements.rend() ; ++it)
Chris@16:         {
Chris@16:             rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v(
Chris@16:                 m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
Chris@16: 
Chris@16:             BOOST_TRY
Chris@16:             {
Chris@16:                 rtree::apply_visitor(lins_v, *m_root);                                                          // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16:             }
Chris@16:             BOOST_CATCH(...)
Chris@16:             {
Chris@16:                 ++it;
Chris@16:                 for ( ; it != elements.rend() ; ++it)
Chris@16:                     rtree::destroy_element<Value, Options, Translator, Box, Allocators>::apply(*it, m_allocators);
Chris@16:                 BOOST_RETHROW                                                                                     // RETHROW
Chris@16:             }
Chris@16:             BOOST_CATCH_END
Chris@16: 
Chris@16:             BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level");
Chris@16: 
Chris@16:             // non-root relative level
Chris@16:             if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
Chris@16:             {
Chris@16:                 recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);                   // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer & m_root;
Chris@101:     size_type & m_leafs_level;
Chris@16:     Element const& m_element;
Chris@16: 
Chris@16:     parameters_type const& m_parameters;
Chris@16:     Translator const& m_translator;
Chris@16: 
Chris@101:     size_type m_relative_level;
Chris@16: 
Chris@16:     Allocators & m_allocators;
Chris@16: };
Chris@16: 
Chris@16: }}} // namespace detail::rtree::visitors
Chris@16: 
Chris@16: }}} // namespace boost::geometry::index
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP