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