]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree R*-tree insert algorithm implementation | |
4 | // | |
5 | // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
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) | |
10 | ||
11 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP | |
12 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP | |
13 | ||
14 | #include <boost/geometry/index/detail/algorithms/content.hpp> | |
15 | ||
16 | namespace boost { namespace geometry { namespace index { | |
17 | ||
18 | namespace detail { namespace rtree { namespace visitors { | |
19 | ||
20 | namespace rstar { | |
21 | ||
22 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
23 | class remove_elements_to_reinsert | |
24 | { | |
25 | public: | |
26 | typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
27 | typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
28 | typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
29 | ||
30 | typedef typename Options::parameters_type parameters_type; | |
31 | ||
32 | //typedef typename Allocators::internal_node_pointer internal_node_pointer; | |
33 | typedef internal_node * internal_node_pointer; | |
34 | ||
35 | template <typename ResultElements, typename Node> | |
36 | static inline void apply(ResultElements & result_elements, | |
37 | Node & n, | |
38 | internal_node_pointer parent, | |
39 | size_t current_child_index, | |
40 | parameters_type const& parameters, | |
41 | Translator const& translator, | |
42 | Allocators & allocators) | |
43 | { | |
44 | typedef typename rtree::elements_type<Node>::type elements_type; | |
45 | typedef typename elements_type::value_type element_type; | |
46 | typedef typename geometry::point_type<Box>::type point_type; | |
47 | // TODO: awulkiew - change second point_type to the point type of the Indexable? | |
48 | typedef typename | |
49 | geometry::default_comparable_distance_result<point_type>::type | |
50 | comparable_distance_type; | |
51 | ||
52 | elements_type & elements = rtree::elements(n); | |
53 | ||
54 | const size_t elements_count = parameters.get_max_elements() + 1; | |
55 | const size_t reinserted_elements_count = (::std::min)(parameters.get_reinserted_elements(), elements_count - parameters.get_min_elements()); | |
56 | ||
57 | BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node"); | |
58 | BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number"); | |
59 | BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert"); | |
60 | ||
61 | // calculate current node's center | |
62 | point_type node_center; | |
63 | geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center); | |
64 | ||
65 | // fill the container of centers' distances of children from current node's center | |
66 | typedef typename index::detail::rtree::container_from_elements_type< | |
67 | elements_type, | |
68 | std::pair<comparable_distance_type, element_type> | |
69 | >::type sorted_elements_type; | |
70 | ||
71 | sorted_elements_type sorted_elements; | |
72 | // If constructor is used instead of resize() MS implementation leaks here | |
73 | sorted_elements.reserve(elements_count); // MAY THROW, STRONG (V, E: alloc, copy) | |
74 | ||
75 | for ( typename elements_type::const_iterator it = elements.begin() ; | |
76 | it != elements.end() ; ++it ) | |
77 | { | |
78 | point_type element_center; | |
79 | geometry::centroid( rtree::element_indexable(*it, translator), element_center); | |
80 | sorted_elements.push_back(std::make_pair( | |
81 | geometry::comparable_distance(node_center, element_center), | |
82 | *it)); // MAY THROW (V, E: copy) | |
83 | } | |
84 | ||
85 | // sort elements by distances from center | |
86 | std::partial_sort( | |
87 | sorted_elements.begin(), | |
88 | sorted_elements.begin() + reinserted_elements_count, | |
89 | sorted_elements.end(), | |
90 | distances_dsc<comparable_distance_type, element_type>); // MAY THROW, BASIC (V, E: copy) | |
91 | ||
92 | // copy elements which will be reinserted | |
93 | result_elements.clear(); | |
94 | result_elements.reserve(reinserted_elements_count); // MAY THROW, STRONG (V, E: alloc, copy) | |
95 | for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() ; | |
96 | it != sorted_elements.begin() + reinserted_elements_count ; ++it ) | |
97 | { | |
98 | result_elements.push_back(it->second); // MAY THROW (V, E: copy) | |
99 | } | |
100 | ||
101 | BOOST_TRY | |
102 | { | |
103 | // copy remaining elements to the current node | |
104 | elements.clear(); | |
105 | elements.reserve(elements_count - reinserted_elements_count); // SHOULDN'T THROW (new_size <= old size) | |
106 | for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() + reinserted_elements_count; | |
107 | it != sorted_elements.end() ; ++it ) | |
108 | { | |
109 | elements.push_back(it->second); // MAY THROW (V, E: copy) | |
110 | } | |
111 | } | |
112 | BOOST_CATCH(...) | |
113 | { | |
114 | elements.clear(); | |
115 | ||
116 | for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ; | |
117 | it != sorted_elements.end() ; ++it ) | |
118 | { | |
119 | destroy_element<Value, Options, Translator, Box, Allocators>::apply(it->second, allocators); | |
120 | } | |
121 | ||
122 | BOOST_RETHROW // RETHROW | |
123 | } | |
124 | BOOST_CATCH_END | |
125 | ||
126 | ::boost::ignore_unused_variable_warning(parameters); | |
127 | } | |
128 | ||
129 | private: | |
130 | template <typename Distance, typename El> | |
131 | static inline bool distances_asc( | |
132 | std::pair<Distance, El> const& d1, | |
133 | std::pair<Distance, El> const& d2) | |
134 | { | |
135 | return d1.first < d2.first; | |
136 | } | |
137 | ||
138 | template <typename Distance, typename El> | |
139 | static inline bool distances_dsc( | |
140 | std::pair<Distance, El> const& d1, | |
141 | std::pair<Distance, El> const& d2) | |
142 | { | |
143 | return d1.first > d2.first; | |
144 | } | |
145 | }; | |
146 | ||
147 | template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators> | |
148 | struct level_insert_elements_type | |
149 | { | |
150 | typedef typename rtree::elements_type< | |
151 | typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type | |
152 | >::type type; | |
153 | }; | |
154 | ||
155 | template <typename Value, typename Options, typename Box, typename Allocators> | |
156 | struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators> | |
157 | { | |
158 | typedef typename rtree::elements_type< | |
159 | typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type | |
160 | >::type type; | |
161 | }; | |
162 | ||
163 | template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
164 | struct level_insert_base | |
165 | : public detail::insert<Element, Value, Options, Translator, Box, Allocators> | |
166 | { | |
167 | typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base; | |
168 | typedef typename base::node node; | |
169 | typedef typename base::internal_node internal_node; | |
170 | typedef typename base::leaf leaf; | |
171 | ||
172 | typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type; | |
173 | typedef typename index::detail::rtree::container_from_elements_type< | |
174 | elements_type, | |
175 | typename elements_type::value_type | |
176 | >::type result_elements_type; | |
177 | ||
178 | typedef typename Options::parameters_type parameters_type; | |
179 | ||
180 | typedef typename Allocators::node_pointer node_pointer; | |
181 | typedef typename Allocators::size_type size_type; | |
182 | ||
183 | inline level_insert_base(node_pointer & root, | |
184 | size_type & leafs_level, | |
185 | Element const& element, | |
186 | parameters_type const& parameters, | |
187 | Translator const& translator, | |
188 | Allocators & allocators, | |
189 | size_type relative_level) | |
190 | : base(root, leafs_level, element, parameters, translator, allocators, relative_level) | |
191 | , result_relative_level(0) | |
192 | {} | |
193 | ||
194 | template <typename Node> | |
195 | inline void handle_possible_reinsert_or_split_of_root(Node &n) | |
196 | { | |
197 | BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level"); | |
198 | ||
199 | result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level; | |
200 | ||
201 | // overflow | |
202 | if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() ) | |
203 | { | |
204 | // node isn't root node | |
205 | if ( !base::m_traverse_data.current_is_root() ) | |
206 | { | |
207 | // NOTE: exception-safety | |
208 | // After an exception result_elements may contain garbage, don't use it | |
209 | rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply( | |
210 | result_elements, n, | |
211 | base::m_traverse_data.parent, base::m_traverse_data.current_child_index, | |
212 | base::m_parameters, base::m_translator, base::m_allocators); // MAY THROW, BASIC (V, E: alloc, copy) | |
213 | } | |
214 | // node is root node | |
215 | else | |
216 | { | |
217 | BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*base::m_root_node), "node should be the root node"); | |
218 | base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc) | |
219 | } | |
220 | } | |
221 | } | |
222 | ||
223 | template <typename Node> | |
224 | inline void handle_possible_split(Node &n) const | |
225 | { | |
226 | // overflow | |
227 | if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() ) | |
228 | { | |
229 | base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc) | |
230 | } | |
231 | } | |
232 | ||
233 | template <typename Node> | |
234 | inline void recalculate_aabb_if_necessary(Node const& n) const | |
235 | { | |
236 | if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() ) | |
237 | { | |
238 | // calulate node's new box | |
239 | recalculate_aabb(n); | |
240 | } | |
241 | } | |
242 | ||
243 | template <typename Node> | |
244 | inline void recalculate_aabb(Node const& n) const | |
245 | { | |
246 | base::m_traverse_data.current_element().first = | |
247 | elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); | |
248 | } | |
249 | ||
250 | inline void recalculate_aabb(leaf const& n) const | |
251 | { | |
252 | base::m_traverse_data.current_element().first = | |
253 | values_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); | |
254 | } | |
255 | ||
256 | size_type result_relative_level; | |
257 | result_elements_type result_elements; | |
258 | }; | |
259 | ||
260 | template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
261 | struct level_insert | |
262 | : public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> | |
263 | { | |
264 | typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base; | |
265 | typedef typename base::node node; | |
266 | typedef typename base::internal_node internal_node; | |
267 | typedef typename base::leaf leaf; | |
268 | ||
269 | typedef typename Options::parameters_type parameters_type; | |
270 | ||
271 | typedef typename Allocators::node_pointer node_pointer; | |
272 | typedef typename Allocators::size_type size_type; | |
273 | ||
274 | inline level_insert(node_pointer & root, | |
275 | size_type & leafs_level, | |
276 | Element const& element, | |
277 | parameters_type const& parameters, | |
278 | Translator const& translator, | |
279 | Allocators & allocators, | |
280 | size_type relative_level) | |
281 | : base(root, leafs_level, element, parameters, translator, allocators, relative_level) | |
282 | {} | |
283 | ||
284 | inline void operator()(internal_node & n) | |
285 | { | |
286 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level"); | |
287 | ||
288 | if ( base::m_traverse_data.current_level < base::m_level ) | |
289 | { | |
290 | // next traversing step | |
291 | base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc) | |
292 | ||
293 | // further insert | |
294 | if ( 0 < InsertIndex ) | |
295 | { | |
296 | BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex"); | |
297 | ||
298 | if ( base::m_traverse_data.current_level == base::m_level - 1 ) | |
299 | { | |
300 | base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc) | |
301 | } | |
302 | } | |
303 | } | |
304 | else | |
305 | { | |
306 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level"); | |
307 | ||
308 | BOOST_TRY | |
309 | { | |
310 | // push new child node | |
311 | rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy) | |
312 | } | |
313 | BOOST_CATCH(...) | |
314 | { | |
315 | // NOTE: exception-safety | |
316 | // if the insert fails above, the element won't be stored in the tree, so delete it | |
317 | ||
318 | rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators); | |
319 | rtree::apply_visitor(del_v, *base::m_element.second); | |
320 | ||
321 | BOOST_RETHROW // RETHROW | |
322 | } | |
323 | BOOST_CATCH_END | |
324 | ||
325 | // first insert | |
326 | if ( 0 == InsertIndex ) | |
327 | { | |
328 | base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc) | |
329 | } | |
330 | // not the first insert | |
331 | else | |
332 | { | |
333 | base::handle_possible_split(n); // MAY THROW (E: alloc, N: alloc) | |
334 | } | |
335 | } | |
336 | ||
337 | base::recalculate_aabb_if_necessary(n); | |
338 | } | |
339 | ||
340 | inline void operator()(leaf &) | |
341 | { | |
342 | BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf"); | |
343 | } | |
344 | }; | |
345 | ||
346 | template <size_t InsertIndex, typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
347 | struct level_insert<InsertIndex, Value, Value, Options, Translator, Box, Allocators> | |
348 | : public level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators> | |
349 | { | |
350 | typedef level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators> base; | |
351 | typedef typename base::node node; | |
352 | typedef typename base::internal_node internal_node; | |
353 | typedef typename base::leaf leaf; | |
354 | ||
355 | typedef typename Options::parameters_type parameters_type; | |
356 | ||
357 | typedef typename Allocators::node_pointer node_pointer; | |
358 | typedef typename Allocators::size_type size_type; | |
359 | ||
360 | inline level_insert(node_pointer & root, | |
361 | size_type & leafs_level, | |
362 | Value const& v, | |
363 | parameters_type const& parameters, | |
364 | Translator const& translator, | |
365 | Allocators & allocators, | |
366 | size_type relative_level) | |
367 | : base(root, leafs_level, v, parameters, translator, allocators, relative_level) | |
368 | {} | |
369 | ||
370 | inline void operator()(internal_node & n) | |
371 | { | |
372 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level"); | |
373 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level"); | |
374 | ||
375 | // next traversing step | |
376 | base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc) | |
377 | ||
378 | BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex"); | |
379 | ||
380 | if ( base::m_traverse_data.current_level == base::m_level - 1 ) | |
381 | { | |
382 | base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc) | |
383 | } | |
384 | ||
385 | base::recalculate_aabb_if_necessary(n); | |
386 | } | |
387 | ||
388 | inline void operator()(leaf & n) | |
389 | { | |
390 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, | |
391 | "unexpected level"); | |
392 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level || | |
393 | base::m_level == (std::numeric_limits<size_t>::max)(), | |
394 | "unexpected level"); | |
395 | ||
396 | rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy) | |
397 | ||
398 | base::handle_possible_split(n); // MAY THROW (V: alloc, copy, N: alloc) | |
399 | } | |
400 | }; | |
401 | ||
402 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
403 | struct level_insert<0, Value, Value, Options, Translator, Box, Allocators> | |
404 | : public level_insert_base<0, Value, Value, Options, Translator, Box, Allocators> | |
405 | { | |
406 | typedef level_insert_base<0, Value, Value, Options, Translator, Box, Allocators> base; | |
407 | typedef typename base::node node; | |
408 | typedef typename base::internal_node internal_node; | |
409 | typedef typename base::leaf leaf; | |
410 | ||
411 | typedef typename Options::parameters_type parameters_type; | |
412 | ||
413 | typedef typename Allocators::node_pointer node_pointer; | |
414 | typedef typename Allocators::size_type size_type; | |
415 | ||
416 | inline level_insert(node_pointer & root, | |
417 | size_type & leafs_level, | |
418 | Value const& v, | |
419 | parameters_type const& parameters, | |
420 | Translator const& translator, | |
421 | Allocators & allocators, | |
422 | size_type relative_level) | |
423 | : base(root, leafs_level, v, parameters, translator, allocators, relative_level) | |
424 | {} | |
425 | ||
426 | inline void operator()(internal_node & n) | |
427 | { | |
428 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, | |
429 | "unexpected level"); | |
430 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, | |
431 | "unexpected level"); | |
432 | ||
433 | // next traversing step | |
434 | base::traverse(*this, n); // MAY THROW (V: alloc, copy, N: alloc) | |
435 | ||
436 | base::recalculate_aabb_if_necessary(n); | |
437 | } | |
438 | ||
439 | inline void operator()(leaf & n) | |
440 | { | |
441 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, | |
442 | "unexpected level"); | |
443 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level || | |
444 | base::m_level == (std::numeric_limits<size_t>::max)(), | |
445 | "unexpected level"); | |
446 | ||
447 | rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy) | |
448 | ||
449 | base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (V: alloc, copy, N: alloc) | |
450 | ||
451 | base::recalculate_aabb_if_necessary(n); | |
452 | } | |
453 | }; | |
454 | ||
455 | } // namespace rstar | |
456 | ||
457 | // R*-tree insert visitor | |
458 | // After passing the Element to insert visitor the Element is managed by the tree | |
459 | // I.e. one should not delete the node passed to the insert visitor after exception is thrown | |
460 | // because this visitor may delete it | |
461 | template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
462 | class insert<Element, Value, Options, Translator, Box, Allocators, insert_reinsert_tag> | |
463 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type | |
464 | { | |
465 | typedef typename Options::parameters_type parameters_type; | |
466 | ||
467 | typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
468 | typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
469 | typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
470 | ||
471 | typedef typename Allocators::node_pointer node_pointer; | |
472 | typedef typename Allocators::size_type size_type; | |
473 | ||
474 | public: | |
475 | inline insert(node_pointer & root, | |
476 | size_type & leafs_level, | |
477 | Element const& element, | |
478 | parameters_type const& parameters, | |
479 | Translator const& translator, | |
480 | Allocators & allocators, | |
481 | size_type relative_level = 0) | |
482 | : m_root(root), m_leafs_level(leafs_level), m_element(element) | |
483 | , m_parameters(parameters), m_translator(translator) | |
484 | , m_relative_level(relative_level), m_allocators(allocators) | |
485 | {} | |
486 | ||
487 | inline void operator()(internal_node & n) | |
488 | { | |
489 | boost::ignore_unused(n); | |
490 | BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root"); | |
491 | ||
492 | // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one | |
493 | if ( m_parameters.get_reinserted_elements() > 0 ) | |
494 | { | |
495 | rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v( | |
496 | m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level); | |
497 | ||
498 | rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc) | |
499 | ||
500 | if ( !lins_v.result_elements.empty() ) | |
501 | { | |
502 | recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc) | |
503 | } | |
504 | } | |
505 | else | |
506 | { | |
507 | visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v( | |
508 | m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level); | |
509 | ||
510 | rtree::apply_visitor(ins_v, *m_root); | |
511 | } | |
512 | } | |
513 | ||
514 | inline void operator()(leaf & n) | |
515 | { | |
516 | boost::ignore_unused(n); | |
517 | BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root"); | |
518 | ||
519 | // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one | |
520 | if ( m_parameters.get_reinserted_elements() > 0 ) | |
521 | { | |
522 | rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v( | |
523 | m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level); | |
524 | ||
525 | rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc) | |
526 | ||
527 | // we're in the root, so root should be split and there should be no elements to reinsert | |
528 | BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state"); | |
529 | } | |
530 | else | |
531 | { | |
532 | visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v( | |
533 | m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level); | |
534 | ||
535 | rtree::apply_visitor(ins_v, *m_root); | |
536 | } | |
537 | } | |
538 | ||
539 | private: | |
540 | template <typename Elements> | |
541 | inline void recursive_reinsert(Elements & elements, size_t relative_level) | |
542 | { | |
543 | typedef typename Elements::value_type element_type; | |
544 | ||
545 | // reinsert children starting from the minimum distance | |
546 | typename Elements::reverse_iterator it = elements.rbegin(); | |
547 | for ( ; it != elements.rend() ; ++it) | |
548 | { | |
549 | rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v( | |
550 | m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level); | |
551 | ||
552 | BOOST_TRY | |
553 | { | |
554 | rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc) | |
555 | } | |
556 | BOOST_CATCH(...) | |
557 | { | |
558 | ++it; | |
559 | for ( ; it != elements.rend() ; ++it) | |
560 | rtree::destroy_element<Value, Options, Translator, Box, Allocators>::apply(*it, m_allocators); | |
561 | BOOST_RETHROW // RETHROW | |
562 | } | |
563 | BOOST_CATCH_END | |
564 | ||
565 | BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level"); | |
566 | ||
567 | // non-root relative level | |
568 | if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty()) | |
569 | { | |
570 | recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc) | |
571 | } | |
572 | } | |
573 | } | |
574 | ||
575 | node_pointer & m_root; | |
576 | size_type & m_leafs_level; | |
577 | Element const& m_element; | |
578 | ||
579 | parameters_type const& m_parameters; | |
580 | Translator const& m_translator; | |
581 | ||
582 | size_type m_relative_level; | |
583 | ||
584 | Allocators & m_allocators; | |
585 | }; | |
586 | ||
587 | }}} // namespace detail::rtree::visitors | |
588 | ||
589 | }}} // namespace boost::geometry::index | |
590 | ||
591 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_INSERT_HPP |