1 // Boost.Geometry Index 2 // 3 // R-tree inserting visitor 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_VISITORS_INSERT_HPP 12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP 13 14 #include <boost/type_traits/is_same.hpp> 15 16 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> 17 #include <boost/geometry/util/condition.hpp> 18 19 #include <boost/geometry/index/detail/algorithms/content.hpp> 20 21 namespace boost { namespace geometry { namespace index { 22 23 namespace detail { namespace rtree { 24 25 // Default choose_next_node 26 template <typename Value, typename Options, typename Box, typename Allocators, typename ChooseNextNodeTag> 27 class choose_next_node; 28 29 template <typename Value, typename Options, typename Box, typename Allocators> 30 class choose_next_node<Value, Options, Box, Allocators, choose_by_content_diff_tag> 31 { 32 public: 33 typedef typename Options::parameters_type parameters_type; 34 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; 38 39 typedef typename rtree::elements_type<internal_node>::type children_type; 40 41 typedef typename index::detail::default_content_result<Box>::type content_type; 42 43 template <typename Indexable> apply(internal_node & n,Indexable const & indexable,parameters_type const &,size_t)44 static inline size_t apply(internal_node & n, 45 Indexable const& indexable, 46 parameters_type const& /*parameters*/, 47 size_t /*node_relative_level*/) 48 { 49 children_type & children = rtree::elements(n); 50 51 BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty"); 52 53 size_t children_count = children.size(); 54 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)(); 59 60 // caculate areas and areas of all nodes' boxes 61 for ( size_t i = 0 ; i < children_count ; ++i ) 62 { 63 typedef typename children_type::value_type child_type; 64 child_type const& ch_i = children[i]; 65 66 // expanded child node's box 67 Box box_exp(ch_i.first); 68 geometry::expand(box_exp, indexable); 69 70 // areas difference 71 content_type content = index::detail::content(box_exp); 72 content_type content_diff = content - index::detail::content(ch_i.first); 73 74 // update the result 75 if ( content_diff < smallest_content_diff || 76 ( content_diff == smallest_content_diff && content < smallest_content ) ) 77 { 78 smallest_content_diff = content_diff; 79 smallest_content = content; 80 choosen_index = i; 81 } 82 } 83 84 return choosen_index; 85 } 86 }; 87 88 // ----------------------------------------------------------------------- // 89 90 // Not implemented here 91 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename RedistributeTag> 92 struct redistribute_elements 93 { 94 BOOST_MPL_ASSERT_MSG( 95 (false), 96 NOT_IMPLEMENTED_FOR_THIS_REDISTRIBUTE_TAG_TYPE, 97 (redistribute_elements)); 98 }; 99 100 // ----------------------------------------------------------------------- // 101 102 // Split algorithm 103 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename SplitTag> 104 class split 105 { 106 BOOST_MPL_ASSERT_MSG( 107 (false), 108 NOT_IMPLEMENTED_FOR_THIS_SPLIT_TAG_TYPE, 109 (split)); 110 }; 111 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> 115 { 116 protected: 117 typedef typename Options::parameters_type parameters_type; 118 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; 122 123 typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; 124 125 public: 126 typedef index::detail::varray< 127 typename rtree::elements_type<internal_node>::type::value_type, 128 1 129 > nodes_container_type; 130 131 template <typename Node> apply(nodes_container_type & additional_nodes,Node & n,Box & n_box,parameters_type const & parameters,Translator const & translator,Allocators & allocators)132 static inline void apply(nodes_container_type & additional_nodes, 133 Node & n, 134 Box & n_box, 135 parameters_type const& parameters, 136 Translator const& translator, 137 Allocators & allocators) 138 { 139 // TODO - consider creating nodes always with sufficient memory allocated 140 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); 145 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 151 // elements. 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. 154 155 // redistribute elements 156 Box box2; 157 redistribute_elements< 158 Value, 159 Options, 160 Translator, 161 Box, 162 Allocators, 163 typename Options::redistribute_tag 164 >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V, E: alloc, copy, copy) 165 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"); 173 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) 176 177 // release the ptr 178 second_node.release(); 179 } 180 }; 181 182 // ----------------------------------------------------------------------- // 183 184 namespace visitors { namespace detail { 185 186 template <typename InternalNode, typename InternalNodePtr, typename SizeType> 187 struct insert_traverse_data 188 { 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; 193 insert_traverse_databoost::geometry::index::detail::rtree::visitors::detail::insert_traverse_data194 insert_traverse_data() 195 : parent(0), current_child_index(0), current_level(0) 196 {} 197 move_to_next_levelboost::geometry::index::detail::rtree::visitors::detail::insert_traverse_data198 void move_to_next_level(InternalNodePtr new_parent, 199 elements_size_type new_child_index) 200 { 201 parent = new_parent; 202 current_child_index = new_child_index; 203 ++current_level; 204 } 205 current_is_rootboost::geometry::index::detail::rtree::visitors::detail::insert_traverse_data206 bool current_is_root() const 207 { 208 return 0 == parent; 209 } 210 parent_elementsboost::geometry::index::detail::rtree::visitors::detail::insert_traverse_data211 elements_type & parent_elements() const 212 { 213 BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer"); 214 return rtree::elements(*parent); 215 } 216 current_elementboost::geometry::index::detail::rtree::visitors::detail::insert_traverse_data217 element_type & current_element() const 218 { 219 BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer"); 220 return rtree::elements(*parent)[current_child_index]; 221 } 222 223 InternalNodePtr parent; 224 elements_size_type current_child_index; 225 size_type current_level; 226 }; 227 228 // Default insert visitor 229 template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators> 230 class insert 231 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type 232 { 233 protected: 234 typedef typename Options::parameters_type parameters_type; 235 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; 239 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; 243 244 //typedef typename Allocators::internal_node_pointer internal_node_pointer; 245 typedef internal_node * internal_node_pointer; 246 insert(node_pointer & root,size_type & leafs_level,Element const & element,parameters_type const & parameters,Translator const & translator,Allocators & allocators,size_type relative_level=0)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 254 ) 255 : m_element(element) 256 , m_parameters(parameters) 257 , m_translator(translator) 258 , m_relative_level(relative_level) 259 , m_level(leafs_level - relative_level) 260 , m_root_node(root) 261 , m_leafs_level(leafs_level) 262 , m_traverse_data() 263 , m_allocators(allocators) 264 { 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"); 268 // TODO 269 // assert - check if Box is correct 270 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); 278 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 286 < 287 typename indexable_type<Translator>::type 288 >::value )) ) 289 { 290 geometry::detail::expand_by_epsilon(m_element_bounds); 291 } 292 #endif 293 } 294 295 template <typename Visitor> traverse(Visitor & visitor,internal_node & n)296 inline void traverse(Visitor & visitor, internal_node & n) 297 { 298 // choose next node 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); 301 302 // expand the node to contain value 303 geometry::expand( 304 rtree::elements(n)[choosen_node_index].first, 305 m_element_bounds 306 /*rtree::element_indexable(m_element, m_translator)*/); 307 308 // next traversing step 309 traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V, E: alloc, copy, N:alloc) 310 } 311 312 // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment? 313 314 template <typename Node> post_traverse(Node & n)315 inline void post_traverse(Node &n) 316 { 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"); 320 321 // handle overflow 322 if ( m_parameters.get_max_elements() < rtree::elements(n).size() ) 323 { 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) 327 } 328 } 329 330 template <typename Visitor> traverse_apply_visitor(Visitor & visitor,internal_node & n,size_t choosen_node_index)331 inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index) 332 { 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; 336 337 // calculate new traverse inputs 338 m_traverse_data.move_to_next_level(&n, choosen_node_index); 339 340 // next traversing step 341 rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N:alloc) 342 343 // restore previous traverse inputs 344 m_traverse_data = backup_traverse_data; 345 } 346 347 // TODO: consider - split result returned as OutIter is faster than reference to the container. Why? 348 349 template <typename Node> split(Node & n) const350 inline void split(Node & n) const 351 { 352 typedef rtree::split<Value, Options, Translator, Box, Allocators, typename Options::split_tag> split_algo; 353 354 typename split_algo::nodes_container_type additional_nodes; 355 Box n_box; 356 357 split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V, E: alloc, copy, N:alloc) 358 359 BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes"); 360 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 370 371 // for exception safety 372 subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators); 373 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 381 < 382 typename indexable_type<Translator>::type 383 >::value ))) 384 { 385 geometry::detail::expand_by_epsilon(n_box); 386 geometry::detail::expand_by_epsilon(additional_nodes[0].first); 387 } 388 #endif 389 390 // node is not the root - just add the new node 391 if ( !m_traverse_data.current_is_root() ) 392 { 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) 397 } 398 // node is the root - add level 399 else 400 { 401 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root"); 402 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) 405 406 BOOST_TRY 407 { 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) 410 } 411 BOOST_CATCH(...) 412 { 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 416 } 417 BOOST_CATCH_END 418 419 m_root_node = new_root.get(); 420 ++m_leafs_level; 421 422 new_root.release(); 423 } 424 425 additional_node_ptr.release(); 426 } 427 428 // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation 429 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; 436 437 node_pointer & m_root_node; 438 size_type & m_leafs_level; 439 440 // traversing input parameters 441 insert_traverse_data<internal_node, internal_node_pointer, size_type> m_traverse_data; 442 443 Allocators & m_allocators; 444 }; 445 446 } // namespace detail 447 448 // Insert visitor forward declaration 449 template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename InsertTag> 450 class insert; 451 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> 459 { 460 public: 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; 465 466 typedef typename Options::parameters_type parameters_type; 467 typedef typename base::node_pointer node_pointer; 468 typedef typename base::size_type size_type; 469 insert(node_pointer & root,size_type & leafs_level,Element const & element,parameters_type const & parameters,Translator const & translator,Allocators & allocators,size_type relative_level=0)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 477 ) 478 : base(root, leafs_level, element, parameters, translator, allocators, relative_level) 479 {} 480 operator ()(internal_node & n)481 inline void operator()(internal_node & n) 482 { 483 BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level"); 484 485 if ( base::m_traverse_data.current_level < base::m_level ) 486 { 487 // next traversing step 488 base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc) 489 } 490 else 491 { 492 BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level"); 493 494 BOOST_TRY 495 { 496 // push new child node 497 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy) 498 } 499 BOOST_CATCH(...) 500 { 501 // if the insert fails above, the element won't be stored in the tree 502 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); 505 506 BOOST_RETHROW // RETHROW 507 } 508 BOOST_CATCH_END 509 } 510 511 base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc) 512 } 513 operator ()(leaf &)514 inline void operator()(leaf &) 515 { 516 BOOST_GEOMETRY_INDEX_ASSERT(false, "this visitor can't be used for a leaf"); 517 } 518 }; 519 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> 524 { 525 public: 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; 530 531 typedef typename Options::parameters_type parameters_type; 532 typedef typename base::node_pointer node_pointer; 533 typedef typename base::size_type size_type; 534 insert(node_pointer & root,size_type & leafs_level,Value const & value,parameters_type const & parameters,Translator const & translator,Allocators & allocators,size_type relative_level=0)535 inline insert(node_pointer & root, 536 size_type & leafs_level, 537 Value const& value, 538 parameters_type const& parameters, 539 Translator const& translator, 540 Allocators & allocators, 541 size_type relative_level = 0 542 ) 543 : base(root, leafs_level, value, parameters, translator, allocators, relative_level) 544 {} 545 operator ()(internal_node & n)546 inline void operator()(internal_node & n) 547 { 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"); 550 551 // next traversing step 552 base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc) 553 554 base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc) 555 } 556 operator ()(leaf & n)557 inline void operator()(leaf & n) 558 { 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"); 562 563 rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy) 564 565 base::post_traverse(n); // MAY THROW (V: alloc, copy, N: alloc) 566 } 567 }; 568 569 }}} // namespace detail::rtree::visitors 570 571 }}} // namespace boost::geometry::index 572 573 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP 574