1 // Boost.Geometry Index
3 // R-tree inserting 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_INSERT_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP
14 #include <boost/type_traits/is_same.hpp>
16 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
17 #include <boost/geometry/util/condition.hpp>
19 #include <boost/geometry/index/detail/algorithms/content.hpp>
21 namespace boost { namespace geometry { namespace index {
23 namespace detail { namespace rtree {
25 // Default choose_next_node
26 template <typename Value, typename Options, typename Box, typename Allocators, typename ChooseNextNodeTag>
27 class choose_next_node;
29 template <typename Value, typename Options, typename Box, typename Allocators>
30 class choose_next_node<Value, Options, Box, Allocators, choose_by_content_diff_tag>
33 typedef typename Options::parameters_type parameters_type;
35 typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
36 typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
37 typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
39 typedef typename rtree::elements_type<internal_node>::type children_type;
41 typedef typename index::detail::default_content_result<Box>::type content_type;
43 template <typename Indexable>
44 static inline size_t apply(internal_node & n,
45 Indexable const& indexable,
46 parameters_type const& /*parameters*/,
47 size_t /*node_relative_level*/)
49 children_type & children = rtree::elements(n);
51 BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty");
53 size_t children_count = children.size();
55 // choose index with smallest content change or smallest content
56 size_t choosen_index = 0;
57 content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
58 content_type smallest_content = (std::numeric_limits<content_type>::max)();
60 // caculate areas and areas of all nodes' boxes
61 for ( size_t i = 0 ; i < children_count ; ++i )
63 typedef typename children_type::value_type child_type;
64 child_type const& ch_i = children[i];
66 // expanded child node's box
67 Box box_exp(ch_i.first);
68 geometry::expand(box_exp, indexable);
71 content_type content = index::detail::content(box_exp);
72 content_type content_diff = content - index::detail::content(ch_i.first);
75 if ( content_diff < smallest_content_diff ||
76 ( content_diff == smallest_content_diff && content < smallest_content ) )
78 smallest_content_diff = content_diff;
79 smallest_content = content;
88 // ----------------------------------------------------------------------- //
90 // Not implemented here
91 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename RedistributeTag>
92 struct redistribute_elements
96 NOT_IMPLEMENTED_FOR_THIS_REDISTRIBUTE_TAG_TYPE,
97 (redistribute_elements));
100 // ----------------------------------------------------------------------- //
103 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename SplitTag>
106 BOOST_MPL_ASSERT_MSG(
108 NOT_IMPLEMENTED_FOR_THIS_SPLIT_TAG_TYPE,
112 // Default split algorithm
113 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
114 class split<Value, Options, Translator, Box, Allocators, split_default_tag>
117 typedef typename Options::parameters_type parameters_type;
119 typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
120 typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
121 typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
123 typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
126 typedef index::detail::varray<
127 typename rtree::elements_type<internal_node>::type::value_type,
129 > nodes_container_type;
131 template <typename Node>
132 static inline void apply(nodes_container_type & additional_nodes,
135 parameters_type const& parameters,
136 Translator const& translator,
137 Allocators & allocators)
139 // TODO - consider creating nodes always with sufficient memory allocated
141 // create additional node, use auto destroyer for automatic destruction on exception
142 subtree_destroyer second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW, STRONG (N: alloc)
143 // create reference to the newly created node
144 Node & n2 = rtree::get<Node>(*second_node);
146 // NOTE: thread-safety
147 // After throwing an exception by redistribute_elements the original node may be not changed or
148 // both nodes may be empty. In both cases the tree won't be valid r-tree.
149 // The alternative is to create 2 (or more) additional nodes here and store backup info
150 // in the original node, then, if exception was thrown, the node would always have more than max
152 // The alternative is to use moving semantics in the implementations of redistribute_elements,
153 // it will be possible to throw from boost::move() in the case of e.g. static size nodes.
155 // redistribute elements
157 redistribute_elements<
163 typename Options::redistribute_tag
164 >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V, E: alloc, copy, copy)
166 // check numbers of elements
167 BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
168 rtree::elements(n).size() <= parameters.get_max_elements(),
169 "unexpected number of elements");
170 BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
171 rtree::elements(n2).size() <= parameters.get_max_elements(),
172 "unexpected number of elements");
174 // return the list of newly created nodes (this algorithm returns one)
175 additional_nodes.push_back(rtree::make_ptr_pair(box2, second_node.get())); // MAY THROW, STRONG (alloc, copy)
178 second_node.release();
182 // ----------------------------------------------------------------------- //
184 namespace visitors { namespace detail {
186 template <typename InternalNode, typename InternalNodePtr, typename SizeType>
187 struct insert_traverse_data
189 typedef typename rtree::elements_type<InternalNode>::type elements_type;
190 typedef typename elements_type::value_type element_type;
191 typedef typename elements_type::size_type elements_size_type;
192 typedef SizeType size_type;
194 insert_traverse_data()
195 : parent(0), current_child_index(0), current_level(0)
198 void move_to_next_level(InternalNodePtr new_parent,
199 elements_size_type new_child_index)
202 current_child_index = new_child_index;
206 bool current_is_root() const
211 elements_type & parent_elements() const
213 BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
214 return rtree::elements(*parent);
217 element_type & current_element() const
219 BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
220 return rtree::elements(*parent)[current_child_index];
223 InternalNodePtr parent;
224 elements_size_type current_child_index;
225 size_type current_level;
228 // Default insert visitor
229 template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
231 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
234 typedef typename Options::parameters_type parameters_type;
236 typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
237 typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
238 typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
240 typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
241 typedef typename Allocators::node_pointer node_pointer;
242 typedef typename Allocators::size_type size_type;
244 //typedef typename Allocators::internal_node_pointer internal_node_pointer;
245 typedef internal_node * internal_node_pointer;
247 inline insert(node_pointer & root,
248 size_type & leafs_level,
249 Element const& element,
250 parameters_type const& parameters,
251 Translator const& translator,
252 Allocators & allocators,
253 size_type relative_level = 0
256 , m_parameters(parameters)
257 , m_translator(translator)
258 , m_relative_level(relative_level)
259 , m_level(leafs_level - relative_level)
261 , m_leafs_level(leafs_level)
263 , m_allocators(allocators)
265 BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
266 BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
267 BOOST_GEOMETRY_INDEX_ASSERT(0 != m_root_node, "there is no root node");
269 // assert - check if Box is correct
271 // When a value is inserted, during the tree traversal bounds of nodes
272 // on a path from the root to a leaf must be expanded. So prepare
273 // a bounding object at the beginning to not do it later for each node.
274 // NOTE: This is actually only needed because conditionally the bounding
275 // object may be expanded below. Otherwise the indexable could be
276 // directly used instead
277 index::detail::bounds(rtree::element_indexable(m_element, m_translator), m_element_bounds);
279 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
280 // Enlarge it in case if it's not bounding geometry type.
281 // It's because Points and Segments are compared WRT machine epsilon
282 // This ensures that leafs bounds correspond to the stored elements
283 if (BOOST_GEOMETRY_CONDITION((
284 boost::is_same<Element, Value>::value
285 && ! index::detail::is_bounding_geometry
287 typename indexable_type<Translator>::type
290 geometry::detail::expand_by_epsilon(m_element_bounds);
295 template <typename Visitor>
296 inline void traverse(Visitor & visitor, internal_node & n)
299 size_t choosen_node_index = rtree::choose_next_node<Value, Options, Box, Allocators, typename Options::choose_next_node_tag>::
300 apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_traverse_data.current_level);
302 // expand the node to contain value
304 rtree::elements(n)[choosen_node_index].first,
306 /*rtree::element_indexable(m_element, m_translator)*/);
308 // next traversing step
309 traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V, E: alloc, copy, N:alloc)
312 // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
314 template <typename Node>
315 inline void post_traverse(Node &n)
317 BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
318 &n == &rtree::get<Node>(*m_traverse_data.current_element().second),
319 "if node isn't the root current_child_index should be valid");
322 if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
324 // NOTE: If the exception is thrown current node may contain more than MAX elements or be empty.
325 // Furthermore it may be empty root - internal node.
326 split(n); // MAY THROW (V, E: alloc, copy, N:alloc)
330 template <typename Visitor>
331 inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
333 // save previous traverse inputs and set new ones
334 insert_traverse_data<internal_node, internal_node_pointer, size_type>
335 backup_traverse_data = m_traverse_data;
337 // calculate new traverse inputs
338 m_traverse_data.move_to_next_level(&n, choosen_node_index);
340 // next traversing step
341 rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N:alloc)
343 // restore previous traverse inputs
344 m_traverse_data = backup_traverse_data;
347 // TODO: consider - split result returned as OutIter is faster than reference to the container. Why?
349 template <typename Node>
350 inline void split(Node & n) const
352 typedef rtree::split<Value, Options, Translator, Box, Allocators, typename Options::split_tag> split_algo;
354 typename split_algo::nodes_container_type additional_nodes;
357 split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V, E: alloc, copy, N:alloc)
359 BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
361 // TODO add all additional nodes
362 // For kmeans algorithm:
363 // elements number may be greater than node max elements count
364 // split and reinsert must take node with some elements count
365 // and container of additional elements (std::pair<Box, node*>s or Values)
366 // and translator + allocators
367 // where node_elements_count + additional_elements > node_max_elements_count
368 // What with elements other than std::pair<Box, node*> ?
369 // Implement template <node_tag> struct node_element_type or something like that
371 // for exception safety
372 subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators);
374 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
375 // Enlarge bounds of a leaf node.
376 // It's because Points and Segments are compared WRT machine epsilon
377 // This ensures that leafs' bounds correspond to the stored elements.
378 if (BOOST_GEOMETRY_CONDITION((
379 boost::is_same<Node, leaf>::value
380 && ! index::detail::is_bounding_geometry
382 typename indexable_type<Translator>::type
385 geometry::detail::expand_by_epsilon(n_box);
386 geometry::detail::expand_by_epsilon(additional_nodes[0].first);
390 // node is not the root - just add the new node
391 if ( !m_traverse_data.current_is_root() )
393 // update old node's box
394 m_traverse_data.current_element().first = n_box;
395 // add new node to parent's children
396 m_traverse_data.parent_elements().push_back(additional_nodes[0]); // MAY THROW, STRONG (V, E: alloc, copy)
398 // node is the root - add level
401 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root");
403 // create new root and add nodes
404 subtree_destroyer new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
408 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)
409 rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]); // MAY THROW, STRONG (E:alloc, copy)
413 // clear new root to not delete in the ~subtree_destroyer() potentially stored old root node
414 rtree::elements(rtree::get<internal_node>(*new_root)).clear();
415 BOOST_RETHROW // RETHROW
419 m_root_node = new_root.get();
425 additional_node_ptr.release();
428 // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
430 Element const& m_element;
431 Box m_element_bounds;
432 parameters_type const& m_parameters;
433 Translator const& m_translator;
434 size_type const m_relative_level;
435 size_type const m_level;
437 node_pointer & m_root_node;
438 size_type & m_leafs_level;
440 // traversing input parameters
441 insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data;
443 Allocators & m_allocators;
446 } // namespace detail
448 // Insert visitor forward declaration
449 template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename InsertTag>
452 // Default insert visitor used for nodes elements
453 // After passing the Element to insert visitor the Element is managed by the tree
454 // I.e. one should not delete the node passed to the insert visitor after exception is thrown
455 // because this visitor may delete it
456 template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
457 class insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag>
458 : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
461 typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
462 typedef typename base::node node;
463 typedef typename base::internal_node internal_node;
464 typedef typename base::leaf leaf;
466 typedef typename Options::parameters_type parameters_type;
467 typedef typename base::node_pointer node_pointer;
468 typedef typename base::size_type size_type;
470 inline insert(node_pointer & root,
471 size_type & leafs_level,
472 Element const& element,
473 parameters_type const& parameters,
474 Translator const& translator,
475 Allocators & allocators,
476 size_type relative_level = 0
478 : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
481 inline void operator()(internal_node & n)
483 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
485 if ( base::m_traverse_data.current_level < base::m_level )
487 // next traversing step
488 base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc)
492 BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
496 // push new child node
497 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy)
501 // if the insert fails above, the element won't be stored in the tree
503 rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
504 rtree::apply_visitor(del_v, *base::m_element.second);
506 BOOST_RETHROW // RETHROW
511 base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc)
514 inline void operator()(leaf &)
516 BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf");
520 // Default insert visitor specialized for Values elements
521 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
522 class insert<Value, Value, Options, Translator, Box, Allocators, insert_default_tag>
523 : public detail::insert<Value, Value, Options, Translator, Box, Allocators>
526 typedef detail::insert<Value, Value, Options, Translator, Box, Allocators> base;
527 typedef typename base::node node;
528 typedef typename base::internal_node internal_node;
529 typedef typename base::leaf leaf;
531 typedef typename Options::parameters_type parameters_type;
532 typedef typename base::node_pointer node_pointer;
533 typedef typename base::size_type size_type;
535 inline insert(node_pointer & root,
536 size_type & leafs_level,
538 parameters_type const& parameters,
539 Translator const& translator,
540 Allocators & allocators,
541 size_type relative_level = 0
543 : base(root, leafs_level, value, parameters, translator, allocators, relative_level)
546 inline void operator()(internal_node & n)
548 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
549 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
551 // next traversing step
552 base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc)
554 base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc)
557 inline void operator()(leaf & n)
559 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
560 BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
561 base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
563 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
565 base::post_traverse(n); // MAY THROW (V: alloc, copy, N: alloc)
569 }}} // namespace detail::rtree::visitors
571 }}} // namespace boost::geometry::index
573 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP