]>
Commit | Line | Data |
---|---|---|
1 | // Boost.Geometry Index | |
2 | // | |
3 | // R-tree removing visitor implementation | |
4 | // | |
5 | // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
7 | // This file was modified by Oracle on 2019-2021. | |
8 | // Modifications copyright (c) 2019-2021 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_REMOVE_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP | |
17 | ||
18 | #include <boost/geometry/algorithms/detail/covered_by/interface.hpp> | |
19 | ||
20 | #include <boost/geometry/index/detail/rtree/node/node_elements.hpp> | |
21 | #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp> | |
22 | #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp> | |
23 | #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> | |
24 | ||
25 | namespace boost { namespace geometry { namespace index { | |
26 | ||
27 | namespace detail { namespace rtree { namespace visitors { | |
28 | ||
29 | // Default remove algorithm | |
30 | template <typename MembersHolder> | |
31 | class remove | |
32 | : public MembersHolder::visitor | |
33 | { | |
34 | typedef typename MembersHolder::box_type box_type; | |
35 | typedef typename MembersHolder::value_type value_type; | |
36 | typedef typename MembersHolder::parameters_type parameters_type; | |
37 | typedef typename MembersHolder::translator_type translator_type; | |
38 | typedef typename MembersHolder::allocators_type allocators_type; | |
39 | ||
40 | typedef typename MembersHolder::node node; | |
41 | typedef typename MembersHolder::internal_node internal_node; | |
42 | typedef typename MembersHolder::leaf leaf; | |
43 | ||
44 | typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer; | |
45 | typedef typename allocators_type::node_pointer node_pointer; | |
46 | typedef typename allocators_type::size_type size_type; | |
47 | ||
48 | typedef typename rtree::elements_type<internal_node>::type::size_type internal_size_type; | |
49 | ||
50 | //typedef typename Allocators::internal_node_pointer internal_node_pointer; | |
51 | typedef internal_node * internal_node_pointer; | |
52 | ||
53 | public: | |
54 | inline remove(node_pointer & root, | |
55 | size_type & leafs_level, | |
56 | value_type const& value, | |
57 | parameters_type const& parameters, | |
58 | translator_type const& translator, | |
59 | allocators_type & allocators) | |
60 | : m_value(value) | |
61 | , m_parameters(parameters) | |
62 | , m_translator(translator) | |
63 | , m_allocators(allocators) | |
64 | , m_root_node(root) | |
65 | , m_leafs_level(leafs_level) | |
66 | , m_is_value_removed(false) | |
67 | , m_parent(0) | |
68 | , m_current_child_index(0) | |
69 | , m_current_level(0) | |
70 | , m_is_underflow(false) | |
71 | { | |
72 | // TODO | |
73 | // assert - check if Value/Box is correct | |
74 | } | |
75 | ||
76 | inline void operator()(internal_node & n) | |
77 | { | |
78 | typedef typename rtree::elements_type<internal_node>::type children_type; | |
79 | children_type & children = rtree::elements(n); | |
80 | ||
81 | // traverse children which boxes intersects value's box | |
82 | internal_size_type child_node_index = 0; | |
83 | for ( ; child_node_index < children.size() ; ++child_node_index ) | |
84 | { | |
85 | if ( index::detail::covered_by_bounds(m_translator(m_value), | |
86 | children[child_node_index].first, | |
87 | index::detail::get_strategy(m_parameters)) ) | |
88 | { | |
89 | // next traversing step | |
90 | traverse_apply_visitor(n, child_node_index); // MAY THROW | |
91 | ||
92 | if ( m_is_value_removed ) | |
93 | break; | |
94 | } | |
95 | } | |
96 | ||
97 | // value was found and removed | |
98 | if ( m_is_value_removed ) | |
99 | { | |
100 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
101 | typedef typename elements_type::iterator element_iterator; | |
102 | elements_type & elements = rtree::elements(n); | |
103 | ||
104 | // underflow occured - child node should be removed | |
105 | if ( m_is_underflow ) | |
106 | { | |
107 | element_iterator underfl_el_it = elements.begin() + child_node_index; | |
108 | size_type relative_level = m_leafs_level - m_current_level; | |
109 | ||
110 | // move node to the container - store node's relative level as well and return new underflow state | |
111 | // NOTE: if the min elements number is 1, then after an underflow | |
112 | // here the child elements count is 0, so it's not required to store this node, | |
113 | // it could just be destroyed | |
114 | m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level); // MAY THROW (E: alloc, copy) | |
115 | } | |
116 | ||
117 | // n is not root - adjust aabb | |
118 | if ( 0 != m_parent ) | |
119 | { | |
120 | // underflow state should be ok here | |
121 | // note that there may be less than min_elems elements in root | |
122 | // so this condition should be checked only here | |
123 | BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state"); | |
124 | ||
125 | rtree::elements(*m_parent)[m_current_child_index].first | |
126 | = rtree::elements_box<box_type>(elements.begin(), elements.end(), m_translator, | |
127 | index::detail::get_strategy(m_parameters)); | |
128 | } | |
129 | // n is root node | |
130 | else | |
131 | { | |
132 | BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root_node), "node must be the root"); | |
133 | ||
134 | // reinsert elements from removed nodes (underflows) | |
135 | reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc) | |
136 | ||
137 | // shorten the tree | |
138 | // NOTE: if the min elements number is 1, then after underflow | |
139 | // here the number of elements may be equal to 0 | |
140 | // this can occur only for the last removed element | |
141 | if ( rtree::elements(n).size() <= 1 ) | |
142 | { | |
143 | node_pointer root_to_destroy = m_root_node; | |
144 | if ( rtree::elements(n).size() == 0 ) | |
145 | m_root_node = 0; | |
146 | else | |
147 | m_root_node = rtree::elements(n)[0].second; | |
148 | --m_leafs_level; | |
149 | ||
150 | rtree::destroy_node<allocators_type, internal_node>::apply(m_allocators, root_to_destroy); | |
151 | } | |
152 | } | |
153 | } | |
154 | } | |
155 | ||
156 | inline void operator()(leaf & n) | |
157 | { | |
158 | typedef typename rtree::elements_type<leaf>::type elements_type; | |
159 | elements_type & elements = rtree::elements(n); | |
160 | ||
161 | // find value and remove it | |
162 | for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it ) | |
163 | { | |
164 | if ( m_translator.equals(*it, m_value, index::detail::get_strategy(m_parameters)) ) | |
165 | { | |
166 | rtree::move_from_back(elements, it); // MAY THROW (V: copy) | |
167 | elements.pop_back(); | |
168 | m_is_value_removed = true; | |
169 | break; | |
170 | } | |
171 | } | |
172 | ||
173 | // if value was removed | |
174 | if ( m_is_value_removed ) | |
175 | { | |
176 | BOOST_GEOMETRY_INDEX_ASSERT(0 < m_parameters.get_min_elements(), "min number of elements is too small"); | |
177 | ||
178 | // calc underflow | |
179 | m_is_underflow = elements.size() < m_parameters.get_min_elements(); | |
180 | ||
181 | // n is not root - adjust aabb | |
182 | if ( 0 != m_parent ) | |
183 | { | |
184 | rtree::elements(*m_parent)[m_current_child_index].first | |
185 | = rtree::values_box<box_type>(elements.begin(), elements.end(), m_translator, | |
186 | index::detail::get_strategy(m_parameters)); | |
187 | } | |
188 | } | |
189 | } | |
190 | ||
191 | bool is_value_removed() const | |
192 | { | |
193 | return m_is_value_removed; | |
194 | } | |
195 | ||
196 | private: | |
197 | ||
198 | typedef std::vector< std::pair<size_type, node_pointer> > underflow_nodes; | |
199 | ||
200 | void traverse_apply_visitor(internal_node &n, internal_size_type choosen_node_index) | |
201 | { | |
202 | // save previous traverse inputs and set new ones | |
203 | internal_node_pointer parent_bckup = m_parent; | |
204 | internal_size_type current_child_index_bckup = m_current_child_index; | |
205 | size_type current_level_bckup = m_current_level; | |
206 | ||
207 | m_parent = &n; | |
208 | m_current_child_index = choosen_node_index; | |
209 | ++m_current_level; | |
210 | ||
211 | // next traversing step | |
212 | rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N: alloc) | |
213 | ||
214 | // restore previous traverse inputs | |
215 | m_parent = parent_bckup; | |
216 | m_current_child_index = current_child_index_bckup; | |
217 | m_current_level = current_level_bckup; | |
218 | } | |
219 | ||
220 | bool store_underflowed_node( | |
221 | typename rtree::elements_type<internal_node>::type & elements, | |
222 | typename rtree::elements_type<internal_node>::type::iterator underfl_el_it, | |
223 | size_type relative_level) | |
224 | { | |
225 | // move node to the container - store node's relative level as well | |
226 | m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second)); // MAY THROW (E: alloc, copy) | |
227 | ||
228 | BOOST_TRY | |
229 | { | |
230 | // NOTE: those are elements of the internal node which means that copy/move shouldn't throw | |
231 | // Though it's safer in case if the pointer type could throw in copy ctor. | |
232 | // In the future this try-catch block could be removed. | |
233 | rtree::move_from_back(elements, underfl_el_it); // MAY THROW (E: copy) | |
234 | elements.pop_back(); | |
235 | } | |
236 | BOOST_CATCH(...) | |
237 | { | |
238 | m_underflowed_nodes.pop_back(); | |
239 | BOOST_RETHROW // RETHROW | |
240 | } | |
241 | BOOST_CATCH_END | |
242 | ||
243 | // calc underflow | |
244 | return elements.size() < m_parameters.get_min_elements(); | |
245 | } | |
246 | ||
247 | static inline bool is_leaf(node const& n) | |
248 | { | |
249 | visitors::is_leaf<MembersHolder> ilv; | |
250 | rtree::apply_visitor(ilv, n); | |
251 | return ilv.result; | |
252 | } | |
253 | ||
254 | void reinsert_removed_nodes_elements() | |
255 | { | |
256 | typename underflow_nodes::reverse_iterator it = m_underflowed_nodes.rbegin(); | |
257 | ||
258 | BOOST_TRY | |
259 | { | |
260 | // reinsert elements from removed nodes | |
261 | // begin with levels closer to the root | |
262 | for ( ; it != m_underflowed_nodes.rend() ; ++it ) | |
263 | { | |
264 | // it->first is an index of a level of a node, not children | |
265 | // counted from the leafs level | |
266 | bool const node_is_leaf = it->first == 1; | |
267 | BOOST_GEOMETRY_INDEX_ASSERT(node_is_leaf == is_leaf(*it->second), "unexpected condition"); | |
268 | if ( node_is_leaf ) | |
269 | { | |
270 | reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc) | |
271 | ||
272 | rtree::destroy_node<allocators_type, leaf>::apply(m_allocators, it->second); | |
273 | } | |
274 | else | |
275 | { | |
276 | reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc) | |
277 | ||
278 | rtree::destroy_node<allocators_type, internal_node>::apply(m_allocators, it->second); | |
279 | } | |
280 | } | |
281 | ||
282 | //m_underflowed_nodes.clear(); | |
283 | } | |
284 | BOOST_CATCH(...) | |
285 | { | |
286 | // destroy current and remaining nodes | |
287 | for ( ; it != m_underflowed_nodes.rend() ; ++it ) | |
288 | { | |
289 | rtree::visitors::destroy<MembersHolder>::apply(it->second, m_allocators); | |
290 | } | |
291 | ||
292 | //m_underflowed_nodes.clear(); | |
293 | ||
294 | BOOST_RETHROW // RETHROW | |
295 | } | |
296 | BOOST_CATCH_END | |
297 | } | |
298 | ||
299 | template <typename Node> | |
300 | void reinsert_node_elements(Node &n, size_type node_relative_level) | |
301 | { | |
302 | typedef typename rtree::elements_type<Node>::type elements_type; | |
303 | elements_type & elements = rtree::elements(n); | |
304 | ||
305 | typename elements_type::iterator it = elements.begin(); | |
306 | BOOST_TRY | |
307 | { | |
308 | for ( ; it != elements.end() ; ++it ) | |
309 | { | |
310 | visitors::insert<typename elements_type::value_type, MembersHolder> | |
311 | insert_v(m_root_node, m_leafs_level, *it, | |
312 | m_parameters, m_translator, m_allocators, | |
313 | node_relative_level - 1); | |
314 | ||
315 | rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V, E: alloc, copy, N: alloc) | |
316 | } | |
317 | } | |
318 | BOOST_CATCH(...) | |
319 | { | |
320 | ++it; | |
321 | rtree::destroy_elements<MembersHolder>::apply(it, elements.end(), m_allocators); | |
322 | elements.clear(); | |
323 | BOOST_RETHROW // RETHROW | |
324 | } | |
325 | BOOST_CATCH_END | |
326 | } | |
327 | ||
328 | value_type const& m_value; | |
329 | parameters_type const& m_parameters; | |
330 | translator_type const& m_translator; | |
331 | allocators_type & m_allocators; | |
332 | ||
333 | node_pointer & m_root_node; | |
334 | size_type & m_leafs_level; | |
335 | ||
336 | bool m_is_value_removed; | |
337 | underflow_nodes m_underflowed_nodes; | |
338 | ||
339 | // traversing input parameters | |
340 | internal_node_pointer m_parent; | |
341 | internal_size_type m_current_child_index; | |
342 | size_type m_current_level; | |
343 | ||
344 | // traversing output parameters | |
345 | bool m_is_underflow; | |
346 | }; | |
347 | ||
348 | }}} // namespace detail::rtree::visitors | |
349 | ||
350 | }}} // namespace boost::geometry::index | |
351 | ||
352 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP |