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