1 // Boost.Geometry Index 2 // 3 // R-tree R*-tree split algorithm implementation 4 // 5 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. 6 // 7 // This file was modified by Oracle on 2019. 8 // Modifications copyright (c) 2019 Oracle and/or its affiliates. 9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 10 // 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_RSTAR_REDISTRIBUTE_ELEMENTS_HPP 16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP 17 18 #include <boost/core/ignore_unused.hpp> 19 20 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp> 21 #include <boost/geometry/index/detail/algorithms/margin.hpp> 22 #include <boost/geometry/index/detail/algorithms/nth_element.hpp> 23 #include <boost/geometry/index/detail/algorithms/union_content.hpp> 24 25 #include <boost/geometry/index/detail/bounded_view.hpp> 26 27 #include <boost/geometry/index/detail/rtree/node/node.hpp> 28 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp> 29 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> 30 31 namespace boost { namespace geometry { namespace index { 32 33 namespace detail { namespace rtree { 34 35 namespace rstar { 36 37 template <typename Element, typename Parameters, typename Translator, typename Tag, size_t Corner, size_t AxisIndex> 38 class element_axis_corner_less 39 { 40 typedef typename rtree::element_indexable_type<Element, Translator>::type indexable_type; 41 typedef typename geometry::point_type<indexable_type>::type point_type; 42 typedef geometry::model::box<point_type> bounds_type; 43 typedef typename index::detail::strategy_type<Parameters>::type strategy_type; 44 typedef index::detail::bounded_view 45 < 46 indexable_type, bounds_type, strategy_type 47 > bounded_view_type; 48 49 public: element_axis_corner_less(Translator const & tr,strategy_type const & strategy)50 element_axis_corner_less(Translator const& tr, strategy_type const& strategy) 51 : m_tr(tr), m_strategy(strategy) 52 {} 53 operator ()(Element const & e1,Element const & e2) const54 bool operator()(Element const& e1, Element const& e2) const 55 { 56 bounded_view_type bounded_ind1(rtree::element_indexable(e1, m_tr), m_strategy); 57 bounded_view_type bounded_ind2(rtree::element_indexable(e2, m_tr), m_strategy); 58 59 return geometry::get<Corner, AxisIndex>(bounded_ind1) 60 < geometry::get<Corner, AxisIndex>(bounded_ind2); 61 } 62 63 private: 64 Translator const& m_tr; 65 strategy_type const& m_strategy; 66 }; 67 68 template <typename Element, typename Parameters, typename Translator, size_t Corner, size_t AxisIndex> 69 class element_axis_corner_less<Element, Parameters, Translator, box_tag, Corner, AxisIndex> 70 { 71 typedef typename index::detail::strategy_type<Parameters>::type strategy_type; 72 73 public: element_axis_corner_less(Translator const & tr,strategy_type const &)74 element_axis_corner_less(Translator const& tr, strategy_type const&) 75 : m_tr(tr) 76 {} 77 operator ()(Element const & e1,Element const & e2) const78 bool operator()(Element const& e1, Element const& e2) const 79 { 80 return geometry::get<Corner, AxisIndex>(rtree::element_indexable(e1, m_tr)) 81 < geometry::get<Corner, AxisIndex>(rtree::element_indexable(e2, m_tr)); 82 } 83 84 private: 85 Translator const& m_tr; 86 }; 87 88 template <typename Element, typename Parameters, typename Translator, size_t Corner, size_t AxisIndex> 89 class element_axis_corner_less<Element, Parameters, Translator, point_tag, Corner, AxisIndex> 90 { 91 typedef typename index::detail::strategy_type<Parameters>::type strategy_type; 92 93 public: element_axis_corner_less(Translator const & tr,strategy_type const &)94 element_axis_corner_less(Translator const& tr, strategy_type const& ) 95 : m_tr(tr) 96 {} 97 operator ()(Element const & e1,Element const & e2) const98 bool operator()(Element const& e1, Element const& e2) const 99 { 100 return geometry::get<AxisIndex>(rtree::element_indexable(e1, m_tr)) 101 < geometry::get<AxisIndex>(rtree::element_indexable(e2, m_tr)); 102 } 103 104 private: 105 Translator const& m_tr; 106 }; 107 108 template <typename Box, size_t Corner, size_t AxisIndex> 109 struct choose_split_axis_and_index_for_corner 110 { 111 typedef typename index::detail::default_margin_result<Box>::type margin_type; 112 typedef typename index::detail::default_content_result<Box>::type content_type; 113 114 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index_for_corner115 static inline void apply(Elements const& elements, 116 size_t & choosen_index, 117 margin_type & sum_of_margins, 118 content_type & smallest_overlap, 119 content_type & smallest_content, 120 Parameters const& parameters, 121 Translator const& translator) 122 { 123 typedef typename Elements::value_type element_type; 124 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; 125 typedef typename tag<indexable_type>::type indexable_tag; 126 127 BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements"); 128 129 typename index::detail::strategy_type<Parameters>::type const& 130 strategy = index::detail::get_strategy(parameters); 131 132 // copy elements 133 Elements elements_copy(elements); // MAY THROW, STRONG (alloc, copy) 134 135 size_t const index_first = parameters.get_min_elements(); 136 size_t const index_last = parameters.get_max_elements() - parameters.get_min_elements() + 2; 137 138 // sort elements 139 element_axis_corner_less 140 < 141 element_type, Parameters, Translator, indexable_tag, Corner, AxisIndex 142 > elements_less(translator, strategy); 143 std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) 144 // { 145 // typename Elements::iterator f = elements_copy.begin() + index_first; 146 // typename Elements::iterator l = elements_copy.begin() + index_last; 147 // // NOTE: for stdlibc++ shipped with gcc 4.8.2 std::nth_element is replaced with std::sort anyway 148 // index::detail::nth_element(elements_copy.begin(), f, elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) 149 // index::detail::nth_element(f, l, elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) 150 // std::sort(f, l, elements_less); // MAY THROW, BASIC (copy) 151 // } 152 153 // init outputs 154 choosen_index = index_first; 155 sum_of_margins = 0; 156 smallest_overlap = (std::numeric_limits<content_type>::max)(); 157 smallest_content = (std::numeric_limits<content_type>::max)(); 158 159 // calculate sum of margins for all distributions 160 for ( size_t i = index_first ; i < index_last ; ++i ) 161 { 162 // TODO - awulkiew: may be optimized - box of group 1 may be initialized with 163 // box of min_elems number of elements and expanded for each iteration by another element 164 165 Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i, 166 translator, strategy); 167 Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(), 168 translator, strategy); 169 170 sum_of_margins += index::detail::comparable_margin(box1) + index::detail::comparable_margin(box2); 171 172 content_type ovl = index::detail::intersection_content(box1, box2, strategy); 173 content_type con = index::detail::content(box1) + index::detail::content(box2); 174 175 // TODO - shouldn't here be < instead of <= ? 176 if ( ovl < smallest_overlap || (ovl == smallest_overlap && con <= smallest_content) ) 177 { 178 choosen_index = i; 179 smallest_overlap = ovl; 180 smallest_content = con; 181 } 182 } 183 184 ::boost::ignore_unused(parameters); 185 } 186 }; 187 188 //template <typename Box, size_t AxisIndex, typename ElementIndexableTag> 189 //struct choose_split_axis_and_index_for_axis 190 //{ 191 // BOOST_MPL_ASSERT_MSG(false, NOT_IMPLEMENTED_FOR_THIS_TAG, (ElementIndexableTag)); 192 //}; 193 194 template <typename Box, size_t AxisIndex, typename ElementIndexableTag> 195 struct choose_split_axis_and_index_for_axis 196 { 197 typedef typename index::detail::default_margin_result<Box>::type margin_type; 198 typedef typename index::detail::default_content_result<Box>::type content_type; 199 200 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index_for_axis201 static inline void apply(Elements const& elements, 202 size_t & choosen_corner, 203 size_t & choosen_index, 204 margin_type & sum_of_margins, 205 content_type & smallest_overlap, 206 content_type & smallest_content, 207 Parameters const& parameters, 208 Translator const& translator) 209 { 210 size_t index1 = 0; 211 margin_type som1 = 0; 212 content_type ovl1 = (std::numeric_limits<content_type>::max)(); 213 content_type con1 = (std::numeric_limits<content_type>::max)(); 214 215 choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex> 216 ::apply(elements, index1, 217 som1, ovl1, con1, 218 parameters, translator); // MAY THROW, STRONG 219 220 size_t index2 = 0; 221 margin_type som2 = 0; 222 content_type ovl2 = (std::numeric_limits<content_type>::max)(); 223 content_type con2 = (std::numeric_limits<content_type>::max)(); 224 225 choose_split_axis_and_index_for_corner<Box, max_corner, AxisIndex> 226 ::apply(elements, index2, 227 som2, ovl2, con2, 228 parameters, translator); // MAY THROW, STRONG 229 230 sum_of_margins = som1 + som2; 231 232 if ( ovl1 < ovl2 || (ovl1 == ovl2 && con1 <= con2) ) 233 { 234 choosen_corner = min_corner; 235 choosen_index = index1; 236 smallest_overlap = ovl1; 237 smallest_content = con1; 238 } 239 else 240 { 241 choosen_corner = max_corner; 242 choosen_index = index2; 243 smallest_overlap = ovl2; 244 smallest_content = con2; 245 } 246 } 247 }; 248 249 template <typename Box, size_t AxisIndex> 250 struct choose_split_axis_and_index_for_axis<Box, AxisIndex, point_tag> 251 { 252 typedef typename index::detail::default_margin_result<Box>::type margin_type; 253 typedef typename index::detail::default_content_result<Box>::type content_type; 254 255 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index_for_axis256 static inline void apply(Elements const& elements, 257 size_t & choosen_corner, 258 size_t & choosen_index, 259 margin_type & sum_of_margins, 260 content_type & smallest_overlap, 261 content_type & smallest_content, 262 Parameters const& parameters, 263 Translator const& translator) 264 { 265 choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex> 266 ::apply(elements, choosen_index, 267 sum_of_margins, smallest_overlap, smallest_content, 268 parameters, translator); // MAY THROW, STRONG 269 270 choosen_corner = min_corner; 271 } 272 }; 273 274 template <typename Box, size_t Dimension> 275 struct choose_split_axis_and_index 276 { 277 BOOST_STATIC_ASSERT(0 < Dimension); 278 279 typedef typename index::detail::default_margin_result<Box>::type margin_type; 280 typedef typename index::detail::default_content_result<Box>::type content_type; 281 282 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index283 static inline void apply(Elements const& elements, 284 size_t & choosen_axis, 285 size_t & choosen_corner, 286 size_t & choosen_index, 287 margin_type & smallest_sum_of_margins, 288 content_type & smallest_overlap, 289 content_type & smallest_content, 290 Parameters const& parameters, 291 Translator const& translator) 292 { 293 typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type; 294 295 choose_split_axis_and_index<Box, Dimension - 1> 296 ::apply(elements, choosen_axis, choosen_corner, choosen_index, 297 smallest_sum_of_margins, smallest_overlap, smallest_content, 298 parameters, translator); // MAY THROW, STRONG 299 300 margin_type sum_of_margins = 0; 301 302 size_t corner = min_corner; 303 size_t index = 0; 304 305 content_type overlap_val = (std::numeric_limits<content_type>::max)(); 306 content_type content_val = (std::numeric_limits<content_type>::max)(); 307 308 choose_split_axis_and_index_for_axis< 309 Box, 310 Dimension - 1, 311 typename tag<element_indexable_type>::type 312 >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW, STRONG 313 314 if ( sum_of_margins < smallest_sum_of_margins ) 315 { 316 choosen_axis = Dimension - 1; 317 choosen_corner = corner; 318 choosen_index = index; 319 smallest_sum_of_margins = sum_of_margins; 320 smallest_overlap = overlap_val; 321 smallest_content = content_val; 322 } 323 } 324 }; 325 326 template <typename Box> 327 struct choose_split_axis_and_index<Box, 1> 328 { 329 typedef typename index::detail::default_margin_result<Box>::type margin_type; 330 typedef typename index::detail::default_content_result<Box>::type content_type; 331 332 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index333 static inline void apply(Elements const& elements, 334 size_t & choosen_axis, 335 size_t & choosen_corner, 336 size_t & choosen_index, 337 margin_type & smallest_sum_of_margins, 338 content_type & smallest_overlap, 339 content_type & smallest_content, 340 Parameters const& parameters, 341 Translator const& translator) 342 { 343 typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type; 344 345 choosen_axis = 0; 346 347 choose_split_axis_and_index_for_axis< 348 Box, 349 0, 350 typename tag<element_indexable_type>::type 351 >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_content, parameters, translator); // MAY THROW 352 } 353 }; 354 355 template <size_t Corner, size_t Dimension, size_t I = 0> 356 struct nth_element 357 { 358 BOOST_STATIC_ASSERT(0 < Dimension); 359 BOOST_STATIC_ASSERT(I < Dimension); 360 361 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::nth_element362 static inline void apply(Elements & elements, Parameters const& parameters, 363 const size_t axis, const size_t index, Translator const& tr) 364 { 365 //BOOST_GEOMETRY_INDEX_ASSERT(axis < Dimension, "unexpected axis value"); 366 367 if ( axis != I ) 368 { 369 nth_element<Corner, Dimension, I + 1>::apply(elements, parameters, axis, index, tr); // MAY THROW, BASIC (copy) 370 } 371 else 372 { 373 typedef typename Elements::value_type element_type; 374 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; 375 typedef typename tag<indexable_type>::type indexable_tag; 376 377 typename index::detail::strategy_type<Parameters>::type 378 strategy = index::detail::get_strategy(parameters); 379 380 element_axis_corner_less 381 < 382 element_type, Parameters, Translator, indexable_tag, Corner, I 383 > less(tr, strategy); 384 index::detail::nth_element(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy) 385 } 386 } 387 }; 388 389 template <size_t Corner, size_t Dimension> 390 struct nth_element<Corner, Dimension, Dimension> 391 { 392 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::nth_element393 static inline void apply(Elements & /*elements*/, Parameters const& /*parameters*/, 394 const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/) 395 {} 396 }; 397 398 } // namespace rstar 399 400 template <typename MembersHolder> 401 struct redistribute_elements<MembersHolder, rstar_tag> 402 { 403 typedef typename MembersHolder::box_type box_type; 404 typedef typename MembersHolder::parameters_type parameters_type; 405 typedef typename MembersHolder::translator_type translator_type; 406 typedef typename MembersHolder::allocators_type allocators_type; 407 408 typedef typename MembersHolder::node node; 409 typedef typename MembersHolder::internal_node internal_node; 410 typedef typename MembersHolder::leaf leaf; 411 412 static const size_t dimension = geometry::dimension<box_type>::value; 413 414 typedef typename index::detail::default_margin_result<box_type>::type margin_type; 415 typedef typename index::detail::default_content_result<box_type>::type content_type; 416 417 template <typename Node> applyboost::geometry::index::detail::rtree::redistribute_elements418 static inline void apply( 419 Node & n, 420 Node & second_node, 421 box_type & box1, 422 box_type & box2, 423 parameters_type const& parameters, 424 translator_type const& translator, 425 allocators_type & allocators) 426 { 427 typedef typename rtree::elements_type<Node>::type elements_type; 428 typedef typename elements_type::value_type element_type; 429 430 elements_type & elements1 = rtree::elements(n); 431 elements_type & elements2 = rtree::elements(second_node); 432 433 // copy original elements - use in-memory storage (std::allocator) 434 // TODO: move if noexcept 435 typedef typename rtree::container_from_elements_type<elements_type, element_type>::type 436 container_type; 437 container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG 438 container_type elements_backup(elements1.begin(), elements1.end()); // MAY THROW, STRONG 439 440 size_t split_axis = 0; 441 size_t split_corner = 0; 442 size_t split_index = parameters.get_min_elements(); 443 margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)(); 444 content_type smallest_overlap = (std::numeric_limits<content_type>::max)(); 445 content_type smallest_content = (std::numeric_limits<content_type>::max)(); 446 447 // NOTE: this function internally copies passed elements 448 // why not pass mutable elements and use the same container for all axes/corners 449 // and again, the same below calling partial_sort/nth_element 450 // It would be even possible to not re-sort/find nth_element if the axis/corner 451 // was found for the last sorting - last combination of axis/corner 452 rstar::choose_split_axis_and_index<box_type, dimension> 453 ::apply(elements_copy, 454 split_axis, split_corner, split_index, 455 smallest_sum_of_margins, smallest_overlap, smallest_content, 456 parameters, translator); // MAY THROW, STRONG 457 458 // TODO: awulkiew - get rid of following static_casts? 459 BOOST_GEOMETRY_INDEX_ASSERT(split_axis < dimension, "unexpected value"); 460 BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value"); 461 BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value"); 462 463 // TODO: consider using nth_element 464 if ( split_corner == static_cast<size_t>(min_corner) ) 465 { 466 rstar::nth_element<min_corner, dimension> 467 ::apply(elements_copy, parameters, split_axis, split_index, translator); // MAY THROW, BASIC (copy) 468 } 469 else 470 { 471 rstar::nth_element<max_corner, dimension> 472 ::apply(elements_copy, parameters, split_axis, split_index, translator); // MAY THROW, BASIC (copy) 473 } 474 475 BOOST_TRY 476 { 477 typename index::detail::strategy_type<parameters_type>::type const& 478 strategy = index::detail::get_strategy(parameters); 479 480 // copy elements to nodes 481 elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index); // MAY THROW, BASIC 482 elements2.assign(elements_copy.begin() + split_index, elements_copy.end()); // MAY THROW, BASIC 483 484 // calculate boxes 485 box1 = rtree::elements_box<box_type>(elements1.begin(), elements1.end(), 486 translator, strategy); 487 box2 = rtree::elements_box<box_type>(elements2.begin(), elements2.end(), 488 translator, strategy); 489 } 490 BOOST_CATCH(...) 491 { 492 //elements_copy.clear(); 493 elements1.clear(); 494 elements2.clear(); 495 496 rtree::destroy_elements<MembersHolder>::apply(elements_backup, allocators); 497 //elements_backup.clear(); 498 499 BOOST_RETHROW // RETHROW, BASIC 500 } 501 BOOST_CATCH_END 502 } 503 }; 504 505 }} // namespace detail::rtree 506 507 }}} // namespace boost::geometry::index 508 509 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP 510