1 // Boost.Geometry Index
3 // R-tree removing visitor implementation
5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP
14 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
16 #include <boost/geometry/algorithms/covered_by.hpp>
18 namespace boost { namespace geometry { namespace index {
20 namespace detail { namespace rtree { namespace visitors {
22 // Default remove algorithm
23 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
25 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
27 typedef typename Options::parameters_type parameters_type;
29 typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
30 typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
31 typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
33 typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
34 typedef typename Allocators::node_pointer node_pointer;
35 typedef typename Allocators::size_type size_type;
37 typedef typename rtree::elements_type<internal_node>::type::size_type internal_size_type;
39 //typedef typename Allocators::internal_node_pointer internal_node_pointer;
40 typedef internal_node * internal_node_pointer;
43 inline remove(node_pointer & root,
44 size_type & leafs_level,
46 parameters_type const& parameters,
47 Translator const& translator,
48 Allocators & allocators)
50 , m_parameters(parameters)
51 , m_translator(translator)
52 , m_allocators(allocators)
54 , m_leafs_level(leafs_level)
55 , m_is_value_removed(false)
57 , m_current_child_index(0)
59 , m_is_underflow(false)
62 // assert - check if Value/Box is correct
65 inline void operator()(internal_node & n)
67 typedef typename rtree::elements_type<internal_node>::type children_type;
68 children_type & children = rtree::elements(n);
70 // traverse children which boxes intersects value's box
71 internal_size_type child_node_index = 0;
72 for ( ; child_node_index < children.size() ; ++child_node_index )
74 if ( geometry::covered_by(
75 return_ref_or_bounds(m_translator(m_value)),
76 children[child_node_index].first) )
78 // next traversing step
79 traverse_apply_visitor(n, child_node_index); // MAY THROW
81 if ( m_is_value_removed )
86 // value was found and removed
87 if ( m_is_value_removed )
89 typedef typename rtree::elements_type<internal_node>::type elements_type;
90 typedef typename elements_type::iterator element_iterator;
91 elements_type & elements = rtree::elements(n);
93 // underflow occured - child node should be removed
96 element_iterator underfl_el_it = elements.begin() + child_node_index;
97 size_type relative_level = m_leafs_level - m_current_level;
99 // move node to the container - store node's relative level as well and return new underflow state
100 // NOTE: if the min elements number is 1, then after an underflow
101 // here the child elements count is 0, so it's not required to store this node,
102 // it could just be destroyed
103 m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level); // MAY THROW (E: alloc, copy)
106 // n is not root - adjust aabb
109 // underflow state should be ok here
110 // note that there may be less than min_elems elements in root
111 // so this condition should be checked only here
112 BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state");
114 rtree::elements(*m_parent)[m_current_child_index].first
115 = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
120 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root_node), "node must be the root");
122 // reinsert elements from removed nodes (underflows)
123 reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc)
126 // NOTE: if the min elements number is 1, then after underflow
127 // here the number of elements may be equal to 0
128 // this can occur only for the last removed element
129 if ( rtree::elements(n).size() <= 1 )
131 node_pointer root_to_destroy = m_root_node;
132 if ( rtree::elements(n).size() == 0 )
135 m_root_node = rtree::elements(n)[0].second;
138 rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, root_to_destroy);
144 inline void operator()(leaf & n)
146 typedef typename rtree::elements_type<leaf>::type elements_type;
147 elements_type & elements = rtree::elements(n);
149 // find value and remove it
150 for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
152 if ( m_translator.equals(*it, m_value) )
154 rtree::move_from_back(elements, it); // MAY THROW (V: copy)
156 m_is_value_removed = true;
161 // if value was removed
162 if ( m_is_value_removed )
164 BOOST_GEOMETRY_INDEX_ASSERT(0 < m_parameters.get_min_elements(), "min number of elements is too small");
167 m_is_underflow = elements.size() < m_parameters.get_min_elements();
169 // n is not root - adjust aabb
172 rtree::elements(*m_parent)[m_current_child_index].first
173 = rtree::values_box<Box>(elements.begin(), elements.end(), m_translator);
178 bool is_value_removed() const
180 return m_is_value_removed;
185 typedef std::vector< std::pair<size_type, node_pointer> > UnderflowNodes;
187 void traverse_apply_visitor(internal_node &n, internal_size_type choosen_node_index)
189 // save previous traverse inputs and set new ones
190 internal_node_pointer parent_bckup = m_parent;
191 internal_size_type current_child_index_bckup = m_current_child_index;
192 size_type current_level_bckup = m_current_level;
195 m_current_child_index = choosen_node_index;
198 // next traversing step
199 rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N: alloc)
201 // restore previous traverse inputs
202 m_parent = parent_bckup;
203 m_current_child_index = current_child_index_bckup;
204 m_current_level = current_level_bckup;
207 bool store_underflowed_node(
208 typename rtree::elements_type<internal_node>::type & elements,
209 typename rtree::elements_type<internal_node>::type::iterator underfl_el_it,
210 size_type relative_level)
212 // move node to the container - store node's relative level as well
213 m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second)); // MAY THROW (E: alloc, copy)
217 // NOTE: those are elements of the internal node which means that copy/move shouldn't throw
218 // Though it's safer in case if the pointer type could throw in copy ctor.
219 // In the future this try-catch block could be removed.
220 rtree::move_from_back(elements, underfl_el_it); // MAY THROW (E: copy)
225 m_underflowed_nodes.pop_back();
226 BOOST_RETHROW // RETHROW
231 return elements.size() < m_parameters.get_min_elements();
234 static inline bool is_leaf(node const& n)
236 visitors::is_leaf<Value, Options, Box, Allocators> ilv;
237 rtree::apply_visitor(ilv, n);
241 void reinsert_removed_nodes_elements()
243 typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin();
247 // reinsert elements from removed nodes
248 // begin with levels closer to the root
249 for ( ; it != m_underflowed_nodes.rend() ; ++it )
251 // it->first is an index of a level of a node, not children
252 // counted from the leafs level
253 bool const node_is_leaf = it->first == 1;
254 BOOST_GEOMETRY_INDEX_ASSERT(node_is_leaf == is_leaf(*it->second), "unexpected condition");
257 reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
259 rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
263 reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
265 rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
269 //m_underflowed_nodes.clear();
273 // destroy current and remaining nodes
274 for ( ; it != m_underflowed_nodes.rend() ; ++it )
276 subtree_destroyer dummy(it->second, m_allocators);
279 //m_underflowed_nodes.clear();
281 BOOST_RETHROW // RETHROW
286 template <typename Node>
287 void reinsert_node_elements(Node &n, size_type node_relative_level)
289 typedef typename rtree::elements_type<Node>::type elements_type;
290 elements_type & elements = rtree::elements(n);
292 typename elements_type::iterator it = elements.begin();
295 for ( ; it != elements.end() ; ++it )
298 typename elements_type::value_type,
299 Value, Options, Translator, Box, Allocators,
300 typename Options::insert_tag
302 m_root_node, m_leafs_level, *it,
303 m_parameters, m_translator, m_allocators,
304 node_relative_level - 1);
306 rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V, E: alloc, copy, N: alloc)
312 rtree::destroy_elements<Value, Options, Translator, Box, Allocators>
313 ::apply(it, elements.end(), m_allocators);
315 BOOST_RETHROW // RETHROW
320 Value const& m_value;
321 parameters_type const& m_parameters;
322 Translator const& m_translator;
323 Allocators & m_allocators;
325 node_pointer & m_root_node;
326 size_type & m_leafs_level;
328 bool m_is_value_removed;
329 UnderflowNodes m_underflowed_nodes;
331 // traversing input parameters
332 internal_node_pointer m_parent;
333 internal_size_type m_current_child_index;
334 size_type m_current_level;
336 // traversing output parameters
340 }}} // namespace detail::rtree::visitors
342 }}} // namespace boost::geometry::index
344 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP