]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree inserting visitor implementation | |
4 | // | |
5 | // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
1e59de90 TL |
7 | // This file was modified by Oracle on 2019-2021. |
8 | // Modifications copyright (c) 2019-2021 Oracle and/or its affiliates. | |
92f5a8d4 TL |
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_INSERT_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP | |
17 | ||
20effc67 TL |
18 | #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON |
19 | #include <type_traits> | |
20 | #endif | |
7c673cae FG |
21 | |
22 | #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> | |
20effc67 | 23 | #include <boost/geometry/core/static_assert.hpp> |
7c673cae | 24 | |
92f5a8d4 | 25 | #include <boost/geometry/index/detail/algorithms/bounds.hpp> |
7c673cae | 26 | #include <boost/geometry/index/detail/algorithms/content.hpp> |
1e59de90 | 27 | #include <boost/geometry/index/detail/rtree/node/node_elements.hpp> |
f67539c2 | 28 | #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp> |
1e59de90 TL |
29 | #include <boost/geometry/index/detail/rtree/options.hpp> |
30 | ||
31 | #include <boost/geometry/util/condition.hpp> | |
f67539c2 | 32 | |
7c673cae FG |
33 | namespace boost { namespace geometry { namespace index { |
34 | ||
35 | namespace detail { namespace rtree { | |
36 | ||
37 | // Default choose_next_node | |
f67539c2 TL |
38 | template |
39 | < | |
40 | typename MembersHolder, | |
41 | typename ChooseNextNodeTag = typename MembersHolder::options_type::choose_next_node_tag | |
42 | > | |
7c673cae FG |
43 | class choose_next_node; |
44 | ||
f67539c2 TL |
45 | template <typename MembersHolder> |
46 | class choose_next_node<MembersHolder, choose_by_content_diff_tag> | |
7c673cae FG |
47 | { |
48 | public: | |
f67539c2 TL |
49 | typedef typename MembersHolder::box_type box_type; |
50 | typedef typename MembersHolder::parameters_type parameters_type; | |
7c673cae | 51 | |
f67539c2 TL |
52 | typedef typename MembersHolder::node node; |
53 | typedef typename MembersHolder::internal_node internal_node; | |
54 | typedef typename MembersHolder::leaf leaf; | |
7c673cae FG |
55 | |
56 | typedef typename rtree::elements_type<internal_node>::type children_type; | |
57 | ||
f67539c2 | 58 | typedef typename index::detail::default_content_result<box_type>::type content_type; |
7c673cae FG |
59 | |
60 | template <typename Indexable> | |
61 | static inline size_t apply(internal_node & n, | |
62 | Indexable const& indexable, | |
92f5a8d4 | 63 | parameters_type const& parameters, |
7c673cae FG |
64 | size_t /*node_relative_level*/) |
65 | { | |
66 | children_type & children = rtree::elements(n); | |
67 | ||
68 | BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty"); | |
69 | ||
70 | size_t children_count = children.size(); | |
71 | ||
72 | // choose index with smallest content change or smallest content | |
73 | size_t choosen_index = 0; | |
74 | content_type smallest_content_diff = (std::numeric_limits<content_type>::max)(); | |
75 | content_type smallest_content = (std::numeric_limits<content_type>::max)(); | |
76 | ||
77 | // caculate areas and areas of all nodes' boxes | |
78 | for ( size_t i = 0 ; i < children_count ; ++i ) | |
79 | { | |
80 | typedef typename children_type::value_type child_type; | |
81 | child_type const& ch_i = children[i]; | |
82 | ||
83 | // expanded child node's box | |
f67539c2 | 84 | box_type box_exp(ch_i.first); |
92f5a8d4 TL |
85 | index::detail::expand(box_exp, indexable, |
86 | index::detail::get_strategy(parameters)); | |
7c673cae FG |
87 | |
88 | // areas difference | |
89 | content_type content = index::detail::content(box_exp); | |
90 | content_type content_diff = content - index::detail::content(ch_i.first); | |
91 | ||
92 | // update the result | |
93 | if ( content_diff < smallest_content_diff || | |
94 | ( content_diff == smallest_content_diff && content < smallest_content ) ) | |
95 | { | |
96 | smallest_content_diff = content_diff; | |
97 | smallest_content = content; | |
98 | choosen_index = i; | |
99 | } | |
100 | } | |
101 | ||
102 | return choosen_index; | |
103 | } | |
104 | }; | |
105 | ||
106 | // ----------------------------------------------------------------------- // | |
107 | ||
108 | // Not implemented here | |
f67539c2 TL |
109 | template |
110 | < | |
111 | typename MembersHolder, | |
112 | typename RedistributeTag = typename MembersHolder::options_type::redistribute_tag | |
113 | > | |
7c673cae FG |
114 | struct redistribute_elements |
115 | { | |
20effc67 TL |
116 | BOOST_GEOMETRY_STATIC_ASSERT_FALSE( |
117 | "Not implemented for this RedistributeTag type.", | |
118 | MembersHolder, RedistributeTag); | |
7c673cae FG |
119 | }; |
120 | ||
121 | // ----------------------------------------------------------------------- // | |
122 | ||
123 | // Split algorithm | |
f67539c2 TL |
124 | template |
125 | < | |
126 | typename MembersHolder, | |
127 | typename SplitTag = typename MembersHolder::options_type::split_tag | |
128 | > | |
7c673cae FG |
129 | class split |
130 | { | |
20effc67 TL |
131 | BOOST_GEOMETRY_STATIC_ASSERT_FALSE( |
132 | "Not implemented for this SplitTag type.", | |
133 | MembersHolder, SplitTag); | |
7c673cae FG |
134 | }; |
135 | ||
136 | // Default split algorithm | |
f67539c2 TL |
137 | template <typename MembersHolder> |
138 | class split<MembersHolder, split_default_tag> | |
7c673cae FG |
139 | { |
140 | protected: | |
f67539c2 TL |
141 | typedef typename MembersHolder::parameters_type parameters_type; |
142 | typedef typename MembersHolder::box_type box_type; | |
143 | typedef typename MembersHolder::translator_type translator_type; | |
144 | typedef typename MembersHolder::allocators_type allocators_type; | |
145 | typedef typename MembersHolder::size_type size_type; | |
7c673cae | 146 | |
f67539c2 TL |
147 | typedef typename MembersHolder::node node; |
148 | typedef typename MembersHolder::internal_node internal_node; | |
149 | typedef typename MembersHolder::leaf leaf; | |
7c673cae | 150 | |
f67539c2 | 151 | typedef typename MembersHolder::node_pointer node_pointer; |
7c673cae FG |
152 | |
153 | public: | |
154 | typedef index::detail::varray< | |
155 | typename rtree::elements_type<internal_node>::type::value_type, | |
156 | 1 | |
157 | > nodes_container_type; | |
158 | ||
159 | template <typename Node> | |
160 | static inline void apply(nodes_container_type & additional_nodes, | |
161 | Node & n, | |
f67539c2 | 162 | box_type & n_box, |
7c673cae | 163 | parameters_type const& parameters, |
f67539c2 TL |
164 | translator_type const& translator, |
165 | allocators_type & allocators) | |
7c673cae FG |
166 | { |
167 | // TODO - consider creating nodes always with sufficient memory allocated | |
168 | ||
169 | // create additional node, use auto destroyer for automatic destruction on exception | |
f67539c2 | 170 | node_pointer n2_ptr = rtree::create_node<allocators_type, Node>::apply(allocators); // MAY THROW, STRONG (N: alloc) |
7c673cae | 171 | // create reference to the newly created node |
f67539c2 TL |
172 | Node & n2 = rtree::get<Node>(*n2_ptr); |
173 | ||
174 | BOOST_TRY | |
175 | { | |
176 | // NOTE: thread-safety | |
177 | // After throwing an exception by redistribute_elements the original node may be not changed or | |
178 | // both nodes may be empty. In both cases the tree won't be valid r-tree. | |
179 | // The alternative is to create 2 (or more) additional nodes here and store backup info | |
180 | // in the original node, then, if exception was thrown, the node would always have more than max | |
181 | // elements. | |
182 | // The alternative is to use moving semantics in the implementations of redistribute_elements, | |
183 | // it will be possible to throw from boost::move() in the case of e.g. static size nodes. | |
184 | ||
185 | // redistribute elements | |
186 | box_type box2; | |
187 | redistribute_elements<MembersHolder> | |
188 | ::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V, E: alloc, copy, copy) | |
189 | ||
190 | // check numbers of elements | |
191 | BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() && | |
192 | rtree::elements(n).size() <= parameters.get_max_elements(), | |
193 | "unexpected number of elements"); | |
194 | BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() && | |
195 | rtree::elements(n2).size() <= parameters.get_max_elements(), | |
196 | "unexpected number of elements"); | |
197 | ||
198 | // return the list of newly created nodes (this algorithm returns one) | |
199 | additional_nodes.push_back(rtree::make_ptr_pair(box2, n2_ptr)); // MAY THROW, STRONG (alloc, copy) | |
200 | } | |
201 | BOOST_CATCH(...) | |
202 | { | |
203 | // NOTE: This code is here to prevent leaving the rtree in a state | |
204 | // after an exception is thrown in which pushing new element could | |
205 | // result in assert or putting it outside the memory of node elements. | |
206 | typename rtree::elements_type<Node>::type & elements = rtree::elements(n); | |
207 | size_type const max_size = parameters.get_max_elements(); | |
208 | if (elements.size() > max_size) | |
209 | { | |
210 | rtree::destroy_element<MembersHolder>::apply(elements[max_size], allocators); | |
211 | elements.pop_back(); | |
212 | } | |
213 | ||
214 | rtree::visitors::destroy<MembersHolder>::apply(n2_ptr, allocators); | |
215 | ||
216 | BOOST_RETHROW | |
217 | } | |
218 | BOOST_CATCH_END | |
7c673cae FG |
219 | } |
220 | }; | |
221 | ||
222 | // ----------------------------------------------------------------------- // | |
223 | ||
224 | namespace visitors { namespace detail { | |
225 | ||
226 | template <typename InternalNode, typename InternalNodePtr, typename SizeType> | |
227 | struct insert_traverse_data | |
228 | { | |
229 | typedef typename rtree::elements_type<InternalNode>::type elements_type; | |
230 | typedef typename elements_type::value_type element_type; | |
231 | typedef typename elements_type::size_type elements_size_type; | |
232 | typedef SizeType size_type; | |
233 | ||
234 | insert_traverse_data() | |
235 | : parent(0), current_child_index(0), current_level(0) | |
236 | {} | |
237 | ||
238 | void move_to_next_level(InternalNodePtr new_parent, | |
239 | elements_size_type new_child_index) | |
240 | { | |
241 | parent = new_parent; | |
242 | current_child_index = new_child_index; | |
243 | ++current_level; | |
244 | } | |
245 | ||
246 | bool current_is_root() const | |
247 | { | |
248 | return 0 == parent; | |
249 | } | |
250 | ||
251 | elements_type & parent_elements() const | |
252 | { | |
253 | BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer"); | |
254 | return rtree::elements(*parent); | |
255 | } | |
256 | ||
257 | element_type & current_element() const | |
258 | { | |
259 | BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer"); | |
260 | return rtree::elements(*parent)[current_child_index]; | |
261 | } | |
262 | ||
263 | InternalNodePtr parent; | |
264 | elements_size_type current_child_index; | |
265 | size_type current_level; | |
266 | }; | |
267 | ||
268 | // Default insert visitor | |
f67539c2 | 269 | template <typename Element, typename MembersHolder> |
7c673cae | 270 | class insert |
20effc67 | 271 | : public MembersHolder::visitor |
7c673cae FG |
272 | { |
273 | protected: | |
f67539c2 TL |
274 | typedef typename MembersHolder::box_type box_type; |
275 | typedef typename MembersHolder::value_type value_type; | |
276 | typedef typename MembersHolder::parameters_type parameters_type; | |
277 | typedef typename MembersHolder::translator_type translator_type; | |
278 | typedef typename MembersHolder::allocators_type allocators_type; | |
7c673cae | 279 | |
f67539c2 TL |
280 | typedef typename MembersHolder::node node; |
281 | typedef typename MembersHolder::internal_node internal_node; | |
282 | typedef typename MembersHolder::leaf leaf; | |
7c673cae | 283 | |
f67539c2 TL |
284 | typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer; |
285 | typedef typename allocators_type::node_pointer node_pointer; | |
286 | typedef typename allocators_type::size_type size_type; | |
7c673cae | 287 | |
f67539c2 | 288 | //typedef typename allocators_type::internal_node_pointer internal_node_pointer; |
7c673cae FG |
289 | typedef internal_node * internal_node_pointer; |
290 | ||
291 | inline insert(node_pointer & root, | |
292 | size_type & leafs_level, | |
293 | Element const& element, | |
294 | parameters_type const& parameters, | |
f67539c2 TL |
295 | translator_type const& translator, |
296 | allocators_type & allocators, | |
7c673cae FG |
297 | size_type relative_level = 0 |
298 | ) | |
299 | : m_element(element) | |
300 | , m_parameters(parameters) | |
301 | , m_translator(translator) | |
302 | , m_relative_level(relative_level) | |
303 | , m_level(leafs_level - relative_level) | |
304 | , m_root_node(root) | |
305 | , m_leafs_level(leafs_level) | |
306 | , m_traverse_data() | |
307 | , m_allocators(allocators) | |
308 | { | |
309 | BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value"); | |
310 | BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value"); | |
311 | BOOST_GEOMETRY_INDEX_ASSERT(0 != m_root_node, "there is no root node"); | |
312 | // TODO | |
313 | // assert - check if Box is correct | |
314 | ||
315 | // When a value is inserted, during the tree traversal bounds of nodes | |
316 | // on a path from the root to a leaf must be expanded. So prepare | |
317 | // a bounding object at the beginning to not do it later for each node. | |
318 | // NOTE: This is actually only needed because conditionally the bounding | |
319 | // object may be expanded below. Otherwise the indexable could be | |
320 | // directly used instead | |
92f5a8d4 TL |
321 | index::detail::bounds(rtree::element_indexable(m_element, m_translator), |
322 | m_element_bounds, | |
323 | index::detail::get_strategy(m_parameters)); | |
7c673cae FG |
324 | |
325 | #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON | |
326 | // Enlarge it in case if it's not bounding geometry type. | |
327 | // It's because Points and Segments are compared WRT machine epsilon | |
328 | // This ensures that leafs bounds correspond to the stored elements | |
329 | if (BOOST_GEOMETRY_CONDITION(( | |
20effc67 | 330 | std::is_same<Element, value_type>::value |
7c673cae FG |
331 | && ! index::detail::is_bounding_geometry |
332 | < | |
f67539c2 | 333 | typename indexable_type<translator_type>::type |
7c673cae FG |
334 | >::value )) ) |
335 | { | |
336 | geometry::detail::expand_by_epsilon(m_element_bounds); | |
337 | } | |
338 | #endif | |
339 | } | |
340 | ||
341 | template <typename Visitor> | |
342 | inline void traverse(Visitor & visitor, internal_node & n) | |
343 | { | |
344 | // choose next node | |
f67539c2 TL |
345 | size_t choosen_node_index = rtree::choose_next_node<MembersHolder> |
346 | ::apply(n, rtree::element_indexable(m_element, m_translator), | |
347 | m_parameters, | |
348 | m_leafs_level - m_traverse_data.current_level); | |
7c673cae FG |
349 | |
350 | // expand the node to contain value | |
92f5a8d4 | 351 | index::detail::expand( |
7c673cae | 352 | rtree::elements(n)[choosen_node_index].first, |
92f5a8d4 TL |
353 | m_element_bounds, |
354 | index::detail::get_strategy(m_parameters)); | |
7c673cae FG |
355 | |
356 | // next traversing step | |
357 | traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V, E: alloc, copy, N:alloc) | |
358 | } | |
359 | ||
360 | // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment? | |
361 | ||
362 | template <typename Node> | |
363 | inline void post_traverse(Node &n) | |
364 | { | |
365 | BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() || | |
366 | &n == &rtree::get<Node>(*m_traverse_data.current_element().second), | |
367 | "if node isn't the root current_child_index should be valid"); | |
368 | ||
369 | // handle overflow | |
370 | if ( m_parameters.get_max_elements() < rtree::elements(n).size() ) | |
371 | { | |
372 | // NOTE: If the exception is thrown current node may contain more than MAX elements or be empty. | |
373 | // Furthermore it may be empty root - internal node. | |
374 | split(n); // MAY THROW (V, E: alloc, copy, N:alloc) | |
375 | } | |
376 | } | |
377 | ||
378 | template <typename Visitor> | |
379 | inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index) | |
380 | { | |
381 | // save previous traverse inputs and set new ones | |
382 | insert_traverse_data<internal_node, internal_node_pointer, size_type> | |
383 | backup_traverse_data = m_traverse_data; | |
384 | ||
385 | // calculate new traverse inputs | |
386 | m_traverse_data.move_to_next_level(&n, choosen_node_index); | |
387 | ||
388 | // next traversing step | |
389 | rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N:alloc) | |
390 | ||
391 | // restore previous traverse inputs | |
392 | m_traverse_data = backup_traverse_data; | |
393 | } | |
394 | ||
395 | // TODO: consider - split result returned as OutIter is faster than reference to the container. Why? | |
396 | ||
397 | template <typename Node> | |
398 | inline void split(Node & n) const | |
399 | { | |
f67539c2 | 400 | typedef rtree::split<MembersHolder> split_algo; |
7c673cae FG |
401 | |
402 | typename split_algo::nodes_container_type additional_nodes; | |
f67539c2 | 403 | box_type n_box; |
7c673cae FG |
404 | |
405 | split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V, E: alloc, copy, N:alloc) | |
406 | ||
407 | BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes"); | |
408 | ||
409 | // TODO add all additional nodes | |
410 | // For kmeans algorithm: | |
411 | // elements number may be greater than node max elements count | |
412 | // split and reinsert must take node with some elements count | |
413 | // and container of additional elements (std::pair<Box, node*>s or Values) | |
414 | // and translator + allocators | |
415 | // where node_elements_count + additional_elements > node_max_elements_count | |
416 | // What with elements other than std::pair<Box, node*> ? | |
417 | // Implement template <node_tag> struct node_element_type or something like that | |
418 | ||
419 | // for exception safety | |
420 | subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators); | |
421 | ||
422 | #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON | |
423 | // Enlarge bounds of a leaf node. | |
424 | // It's because Points and Segments are compared WRT machine epsilon | |
425 | // This ensures that leafs' bounds correspond to the stored elements. | |
426 | if (BOOST_GEOMETRY_CONDITION(( | |
20effc67 | 427 | std::is_same<Node, leaf>::value |
7c673cae FG |
428 | && ! index::detail::is_bounding_geometry |
429 | < | |
f67539c2 | 430 | typename indexable_type<translator_type>::type |
7c673cae FG |
431 | >::value ))) |
432 | { | |
433 | geometry::detail::expand_by_epsilon(n_box); | |
434 | geometry::detail::expand_by_epsilon(additional_nodes[0].first); | |
435 | } | |
436 | #endif | |
437 | ||
438 | // node is not the root - just add the new node | |
439 | if ( !m_traverse_data.current_is_root() ) | |
440 | { | |
441 | // update old node's box | |
442 | m_traverse_data.current_element().first = n_box; | |
443 | // add new node to parent's children | |
444 | m_traverse_data.parent_elements().push_back(additional_nodes[0]); // MAY THROW, STRONG (V, E: alloc, copy) | |
445 | } | |
446 | // node is the root - add level | |
447 | else | |
448 | { | |
449 | BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root"); | |
450 | ||
451 | // create new root and add nodes | |
f67539c2 | 452 | subtree_destroyer new_root(rtree::create_node<allocators_type, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc) |
7c673cae FG |
453 | |
454 | BOOST_TRY | |
455 | { | |
456 | rtree::elements(rtree::get<internal_node>(*new_root)).push_back(rtree::make_ptr_pair(n_box, m_root_node)); // MAY THROW, STRONG (E:alloc, copy) | |
457 | rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]); // MAY THROW, STRONG (E:alloc, copy) | |
458 | } | |
459 | BOOST_CATCH(...) | |
460 | { | |
461 | // clear new root to not delete in the ~subtree_destroyer() potentially stored old root node | |
462 | rtree::elements(rtree::get<internal_node>(*new_root)).clear(); | |
463 | BOOST_RETHROW // RETHROW | |
464 | } | |
465 | BOOST_CATCH_END | |
466 | ||
467 | m_root_node = new_root.get(); | |
468 | ++m_leafs_level; | |
469 | ||
470 | new_root.release(); | |
471 | } | |
472 | ||
473 | additional_node_ptr.release(); | |
474 | } | |
475 | ||
476 | // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation | |
477 | ||
478 | Element const& m_element; | |
f67539c2 | 479 | box_type m_element_bounds; |
7c673cae | 480 | parameters_type const& m_parameters; |
f67539c2 | 481 | translator_type const& m_translator; |
7c673cae FG |
482 | size_type const m_relative_level; |
483 | size_type const m_level; | |
484 | ||
485 | node_pointer & m_root_node; | |
486 | size_type & m_leafs_level; | |
487 | ||
488 | // traversing input parameters | |
489 | insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data; | |
490 | ||
f67539c2 | 491 | allocators_type & m_allocators; |
7c673cae FG |
492 | }; |
493 | ||
494 | } // namespace detail | |
495 | ||
496 | // Insert visitor forward declaration | |
f67539c2 TL |
497 | template |
498 | < | |
499 | typename Element, | |
500 | typename MembersHolder, | |
501 | typename InsertTag = typename MembersHolder::options_type::insert_tag | |
502 | > | |
7c673cae FG |
503 | class insert; |
504 | ||
505 | // Default insert visitor used for nodes elements | |
506 | // After passing the Element to insert visitor the Element is managed by the tree | |
507 | // I.e. one should not delete the node passed to the insert visitor after exception is thrown | |
508 | // because this visitor may delete it | |
f67539c2 TL |
509 | template <typename Element, typename MembersHolder> |
510 | class insert<Element, MembersHolder, insert_default_tag> | |
511 | : public detail::insert<Element, MembersHolder> | |
7c673cae FG |
512 | { |
513 | public: | |
f67539c2 TL |
514 | typedef detail::insert<Element, MembersHolder> base; |
515 | ||
516 | typedef typename base::parameters_type parameters_type; | |
517 | typedef typename base::translator_type translator_type; | |
518 | typedef typename base::allocators_type allocators_type; | |
519 | ||
7c673cae FG |
520 | typedef typename base::node node; |
521 | typedef typename base::internal_node internal_node; | |
522 | typedef typename base::leaf leaf; | |
523 | ||
7c673cae FG |
524 | typedef typename base::node_pointer node_pointer; |
525 | typedef typename base::size_type size_type; | |
526 | ||
527 | inline insert(node_pointer & root, | |
528 | size_type & leafs_level, | |
529 | Element const& element, | |
530 | parameters_type const& parameters, | |
f67539c2 TL |
531 | translator_type const& translator, |
532 | allocators_type & allocators, | |
7c673cae FG |
533 | size_type relative_level = 0 |
534 | ) | |
535 | : base(root, leafs_level, element, parameters, translator, allocators, relative_level) | |
536 | {} | |
537 | ||
538 | inline void operator()(internal_node & n) | |
539 | { | |
540 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level"); | |
541 | ||
542 | if ( base::m_traverse_data.current_level < base::m_level ) | |
543 | { | |
544 | // next traversing step | |
545 | base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc) | |
546 | } | |
547 | else | |
548 | { | |
549 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level"); | |
550 | ||
551 | BOOST_TRY | |
552 | { | |
553 | // push new child node | |
554 | rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy) | |
555 | } | |
556 | BOOST_CATCH(...) | |
557 | { | |
558 | // if the insert fails above, the element won't be stored in the tree | |
559 | ||
f67539c2 | 560 | rtree::visitors::destroy<MembersHolder>::apply(base::m_element.second, base::m_allocators); |
7c673cae FG |
561 | |
562 | BOOST_RETHROW // RETHROW | |
563 | } | |
564 | BOOST_CATCH_END | |
565 | } | |
566 | ||
567 | base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc) | |
568 | } | |
569 | ||
570 | inline void operator()(leaf &) | |
571 | { | |
572 | BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf"); | |
573 | } | |
574 | }; | |
575 | ||
576 | // Default insert visitor specialized for Values elements | |
f67539c2 TL |
577 | template <typename MembersHolder> |
578 | class insert<typename MembersHolder::value_type, MembersHolder, insert_default_tag> | |
579 | : public detail::insert<typename MembersHolder::value_type, MembersHolder> | |
7c673cae FG |
580 | { |
581 | public: | |
f67539c2 TL |
582 | typedef detail::insert<typename MembersHolder::value_type, MembersHolder> base; |
583 | ||
584 | typedef typename base::value_type value_type; | |
585 | typedef typename base::parameters_type parameters_type; | |
586 | typedef typename base::translator_type translator_type; | |
587 | typedef typename base::allocators_type allocators_type; | |
588 | ||
7c673cae FG |
589 | typedef typename base::node node; |
590 | typedef typename base::internal_node internal_node; | |
591 | typedef typename base::leaf leaf; | |
592 | ||
7c673cae FG |
593 | typedef typename base::node_pointer node_pointer; |
594 | typedef typename base::size_type size_type; | |
595 | ||
596 | inline insert(node_pointer & root, | |
597 | size_type & leafs_level, | |
f67539c2 | 598 | value_type const& value, |
7c673cae | 599 | parameters_type const& parameters, |
f67539c2 TL |
600 | translator_type const& translator, |
601 | allocators_type & allocators, | |
7c673cae FG |
602 | size_type relative_level = 0 |
603 | ) | |
604 | : base(root, leafs_level, value, parameters, translator, allocators, relative_level) | |
605 | {} | |
606 | ||
607 | inline void operator()(internal_node & n) | |
608 | { | |
609 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level"); | |
610 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level"); | |
611 | ||
612 | // next traversing step | |
613 | base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc) | |
614 | ||
615 | base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc) | |
616 | } | |
617 | ||
618 | inline void operator()(leaf & n) | |
619 | { | |
620 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level"); | |
621 | BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level || | |
622 | base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level"); | |
623 | ||
624 | rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy) | |
625 | ||
626 | base::post_traverse(n); // MAY THROW (V: alloc, copy, N: alloc) | |
627 | } | |
628 | }; | |
629 | ||
630 | }}} // namespace detail::rtree::visitors | |
631 | ||
632 | }}} // namespace boost::geometry::index | |
633 | ||
634 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP |