ceph/src/boost/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree linear split algorithm implementation
   4 //
   5 // Copyright (c) 2008 Federico J. Fernandez.
   6 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
   7 //
   8 // This file was modified by Oracle on 2019-2020.
   9 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11 //
  12 // Use, modification and distribution is subject to the Boost Software License,
  13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  14 // http://www.boost.org/LICENSE_1_0.txt)
  15
  16 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
  17 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
  18
  19 #include <type_traits>
  20
  21 #include <boost/core/ignore_unused.hpp>
  22
  23 #include <boost/geometry/core/static_assert.hpp>
  24
  25 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
  26 #include <boost/geometry/index/detail/algorithms/content.hpp>
  27 #include <boost/geometry/index/detail/bounded_view.hpp>
  28
  29 #include <boost/geometry/index/detail/rtree/node/node.hpp>
  30 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
  31 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
  32
  33 namespace boost { namespace geometry { namespace index {
  34
  35 namespace detail { namespace rtree {
  36
  37 namespace linear {
  38
  39 template <typename R, typename T>
  40 inline R difference_dispatch(T const& from, T const& to, std::false_type /*is_unsigned*/)
  41 {
  42     return to - from;
  43 }
  44
  45 template <typename R, typename T>
  46 inline R difference_dispatch(T const& from, T const& to, std::true_type /*is_unsigned*/)
  47 {
  48     return from <= to ? R(to - from) : -R(from - to);
  49 }
  50
  51 template <typename R, typename T>
  52 inline R difference(T const& from, T const& to)
  53 {
  54     BOOST_GEOMETRY_STATIC_ASSERT((! std::is_unsigned<R>::value),
  55         "Result can not be an unsigned type.",
  56         R);
  57
  58     return difference_dispatch<R>(from, to, std::is_unsigned<T>());
  59 }
  60
  61 // TODO: awulkiew
  62 // In general, all aerial Indexables in the tree with box-like nodes will be analyzed as boxes
  63 // because they must fit into larger box. Therefore the algorithm could be the same for Bounds type.
  64 // E.g. if Bounds type is sphere, Indexables probably should be analyzed as spheres.
  65 // 1. View could be provided to 'see' all Indexables as Bounds type.
  66 //    Not ok in the case of big types like Ring, however it's possible that Rings won't be supported,
  67 //    only simple types. Even then if we consider storing Box inside the Sphere we must calculate
  68 //    the bounding sphere 2x for each box because there are 2 loops. For each calculation this means
  69 //    4-2d or 8-3d expansions or -, / and sqrt().
  70 // 2. Additional container could be used and reused if the Indexable type is other than the Bounds type.
  71
  72 // IMPORTANT!
  73 // Still probably the best way would be providing specialized algorithms for each Indexable-Bounds pair!
  74 // Probably on pick_seeds algorithm level - For Bounds=Sphere seeds would be choosen differently
  75
  76 // TODO: awulkiew
  77 // there are loops inside find_greatest_normalized_separation::apply()
  78 // iteration is done for each DimensionIndex.
  79 // Separations and seeds for all DimensionIndex(es) could be calculated at once, stored, then the greatest would be choosen.
  80
  81 // The following struct/method was adapted for the preliminary version of the R-tree. Then it was called:
  82 // void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
  83
  84 template <typename Elements, typename Parameters, typename Translator, typename Tag, size_t DimensionIndex>
  85 struct find_greatest_normalized_separation
  86 {
  87     typedef typename Elements::value_type element_type;
  88     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
  89     typedef typename coordinate_type<indexable_type>::type coordinate_type;
  90
  91     typedef std::conditional_t
  92         <
  93             std::is_integral<coordinate_type>::value,
  94             double,
  95             coordinate_type
  96         > separation_type;
  97
  98     typedef typename geometry::point_type<indexable_type>::type point_type;
  99     typedef geometry::model::box<point_type> bounds_type;
 100     typedef index::detail::bounded_view
 101         <
 102             indexable_type, bounds_type,
 103             typename index::detail::strategy_type<Parameters>::type
 104         > bounded_view_type;
 105
 106     static inline void apply(Elements const& elements,
 107                              Parameters const& parameters,
 108                              Translator const& translator,
 109                              separation_type & separation,
 110                              size_t & seed1,
 111                              size_t & seed2)
 112     {
 113         const size_t elements_count = parameters.get_max_elements() + 1;
 114         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
 115         BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
 116
 117         typename index::detail::strategy_type<Parameters>::type const&
 118             strategy = index::detail::get_strategy(parameters);
 119
 120         // find the lowest low, highest high
 121         bounded_view_type bounded_indexable_0(rtree::element_indexable(elements[0], translator),
 122                                               strategy);
 123         coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_0);
 124         coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(bounded_indexable_0);
 125
 126         // and the lowest high
 127         coordinate_type lowest_high = highest_high;
 128         size_t lowest_high_index = 0;
 129         for ( size_t i = 1 ; i < elements_count ; ++i )
 130         {
 131             bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator),
 132                                                 strategy);
 133             coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable);
 134             coordinate_type max_coord = geometry::get<max_corner, DimensionIndex>(bounded_indexable);
 135
 136             if ( max_coord < lowest_high )
 137             {
 138                 lowest_high = max_coord;
 139                 lowest_high_index = i;
 140             }
 141
 142             if ( min_coord < lowest_low )
 143                 lowest_low = min_coord;
 144
 145             if ( highest_high < max_coord )
 146                 highest_high = max_coord;
 147         }
 148
 149         // find the highest low
 150         size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
 151         bounded_view_type bounded_indexable_hl(rtree::element_indexable(elements[highest_low_index], translator),
 152                                                strategy);
 153         coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_hl);
 154         for ( size_t i = highest_low_index ; i < elements_count ; ++i )
 155         {
 156             bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator),
 157                                                 strategy);
 158             coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable);
 159             if ( highest_low < min_coord &&
 160                  i != lowest_high_index )
 161             {
 162                 highest_low = min_coord;
 163                 highest_low_index = i;
 164             }
 165         }
 166
 167         coordinate_type const width = highest_high - lowest_low;
 168
 169         // highest_low - lowest_high
 170         separation = difference<separation_type>(lowest_high, highest_low);
 171         // BOOST_GEOMETRY_INDEX_ASSERT(0 <= width);
 172         if ( std::numeric_limits<coordinate_type>::epsilon() < width )
 173             separation /= width;
 174
 175         seed1 = highest_low_index;
 176         seed2 = lowest_high_index;
 177
 178         ::boost::ignore_unused(parameters);
 179     }
 180 };
 181
 182 // Version for points doesn't calculate normalized separation since it would always be equal to 1
 183 // It returns two seeds most distant to each other, separation is equal to distance
 184 template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
 185 struct find_greatest_normalized_separation<Elements, Parameters, Translator, point_tag, DimensionIndex>
 186 {
 187     typedef typename Elements::value_type element_type;
 188     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 189     typedef typename coordinate_type<indexable_type>::type coordinate_type;
 190
 191     typedef coordinate_type separation_type;
 192
 193     static inline void apply(Elements const& elements,
 194                              Parameters const& parameters,
 195                              Translator const& translator,
 196                              separation_type & separation,
 197                              size_t & seed1,
 198                              size_t & seed2)
 199     {
 200         const size_t elements_count = parameters.get_max_elements() + 1;
 201         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
 202         BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
 203
 204         // find the lowest low, highest high
 205         coordinate_type lowest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator));
 206         coordinate_type highest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator));
 207         size_t lowest_index = 0;
 208         size_t highest_index = 0;
 209         for ( size_t i = 1 ; i < elements_count ; ++i )
 210         {
 211             coordinate_type coord = geometry::get<DimensionIndex>(rtree::element_indexable(elements[i], translator));
 212
 213             if ( coord < lowest )
 214             {
 215                 lowest = coord;
 216                 lowest_index = i;
 217             }
 218
 219             if ( highest < coord )
 220             {
 221                 highest = coord;
 222                 highest_index = i;
 223             }
 224         }
 225
 226         separation = highest - lowest;
 227         seed1 = lowest_index;
 228         seed2 = highest_index;
 229
 230         if ( lowest_index == highest_index )
 231             seed2 = (lowest_index + 1) % elements_count; // % is just in case since if this is true lowest_index is 0
 232
 233         ::boost::ignore_unused(parameters);
 234     }
 235 };
 236
 237 template <typename Elements, typename Parameters, typename Translator, size_t Dimension>
 238 struct pick_seeds_impl
 239 {
 240     BOOST_STATIC_ASSERT(0 < Dimension);
 241
 242     typedef typename Elements::value_type element_type;
 243     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 244
 245     typedef find_greatest_normalized_separation<
 246         Elements, Parameters, Translator,
 247         typename tag<indexable_type>::type, Dimension - 1
 248     > find_norm_sep;
 249
 250     typedef typename find_norm_sep::separation_type separation_type;
 251
 252     static inline void apply(Elements const& elements,
 253                              Parameters const& parameters,
 254                              Translator const& tr,
 255                              separation_type & separation,
 256                              size_t & seed1,
 257                              size_t & seed2)
 258     {
 259         pick_seeds_impl<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, separation, seed1, seed2);
 260
 261         separation_type current_separation;
 262         size_t s1, s2;
 263         find_norm_sep::apply(elements, parameters, tr, current_separation, s1, s2);
 264
 265         // in the old implementation different operator was used: <= (y axis prefered)
 266         if ( separation < current_separation )
 267         {
 268             separation = current_separation;
 269             seed1 = s1;
 270             seed2 = s2;
 271         }
 272     }
 273 };
 274
 275 template <typename Elements, typename Parameters, typename Translator>
 276 struct pick_seeds_impl<Elements, Parameters, Translator, 1>
 277 {
 278     typedef typename Elements::value_type element_type;
 279     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 280     typedef typename coordinate_type<indexable_type>::type coordinate_type;
 281
 282     typedef find_greatest_normalized_separation<
 283         Elements, Parameters, Translator,
 284         typename tag<indexable_type>::type, 0
 285     > find_norm_sep;
 286
 287     typedef typename find_norm_sep::separation_type separation_type;
 288
 289     static inline void apply(Elements const& elements,
 290                              Parameters const& parameters,
 291                              Translator const& tr,
 292                              separation_type & separation,
 293                              size_t & seed1,
 294                              size_t & seed2)
 295     {
 296         find_norm_sep::apply(elements, parameters, tr, separation, seed1, seed2);
 297     }
 298 };
 299
 300 // from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
 301
 302 template <typename Elements, typename Parameters, typename Translator>
 303 inline void pick_seeds(Elements const& elements,
 304                        Parameters const& parameters,
 305                        Translator const& tr,
 306                        size_t & seed1,
 307                        size_t & seed2)
 308 {
 309     typedef typename Elements::value_type element_type;
 310     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 311
 312     typedef pick_seeds_impl
 313         <
 314             Elements, Parameters, Translator,
 315             geometry::dimension<indexable_type>::value
 316         > impl;
 317     typedef typename impl::separation_type separation_type;
 318
 319     separation_type separation = 0;
 320     impl::apply(elements, parameters, tr, separation, seed1, seed2);
 321 }
 322
 323 } // namespace linear
 324
 325 // from void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const
 326
 327 template <typename MembersHolder>
 328 struct redistribute_elements<MembersHolder, linear_tag>
 329 {
 330     typedef typename MembersHolder::box_type box_type;
 331     typedef typename MembersHolder::parameters_type parameters_type;
 332     typedef typename MembersHolder::translator_type translator_type;
 333     typedef typename MembersHolder::allocators_type allocators_type;
 334
 335     typedef typename MembersHolder::node node;
 336     typedef typename MembersHolder::internal_node internal_node;
 337     typedef typename MembersHolder::leaf leaf;
 338
 339     template <typename Node>
 340     static inline void apply(Node & n,
 341                              Node & second_node,
 342                              box_type & box1,
 343                              box_type & box2,
 344                              parameters_type const& parameters,
 345                              translator_type const& translator,
 346                              allocators_type & allocators)
 347     {
 348         typedef typename rtree::elements_type<Node>::type elements_type;
 349         typedef typename elements_type::value_type element_type;
 350         typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
 351         typedef typename index::detail::default_content_result<box_type>::type content_type;
 352
 353         typename index::detail::strategy_type<parameters_type>::type const&
 354             strategy = index::detail::get_strategy(parameters);
 355
 356         elements_type & elements1 = rtree::elements(n);
 357         elements_type & elements2 = rtree::elements(second_node);
 358         const size_t elements1_count = parameters.get_max_elements() + 1;
 359
 360         BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
 361
 362         // copy original elements - use in-memory storage (std::allocator)
 363         // TODO: move if noexcept
 364         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
 365             container_type;
 366         container_type elements_copy(elements1.begin(), elements1.end());                                   // MAY THROW, STRONG (alloc, copy)
 367
 368         // calculate initial seeds
 369         size_t seed1 = 0;
 370         size_t seed2 = 0;
 371         linear::pick_seeds(elements_copy, parameters, translator, seed1, seed2);
 372
 373         // prepare nodes' elements containers
 374         elements1.clear();
 375         BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state");
 376
 377         BOOST_TRY
 378         {
 379             // add seeds
 380             elements1.push_back(elements_copy[seed1]);                                                      // MAY THROW, STRONG (copy)
 381             elements2.push_back(elements_copy[seed2]);                                                      // MAY THROW, STRONG (alloc, copy)
 382
 383             // calculate boxes
 384             detail::bounds(rtree::element_indexable(elements_copy[seed1], translator),
 385                            box1, strategy);
 386             detail::bounds(rtree::element_indexable(elements_copy[seed2], translator),
 387                            box2, strategy);
 388
 389             // initialize areas
 390             content_type content1 = index::detail::content(box1);
 391             content_type content2 = index::detail::content(box2);
 392
 393             BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
 394             size_t remaining = elements1_count - 2;
 395
 396             // redistribute the rest of the elements
 397             for ( size_t i = 0 ; i < elements1_count ; ++i )
 398             {
 399                 if (i != seed1 && i != seed2)
 400                 {
 401                     element_type const& elem = elements_copy[i];
 402                     indexable_type const& indexable = rtree::element_indexable(elem, translator);
 403
 404                     // if there is small number of elements left and the number of elements in node is lesser than min_elems
 405                     // just insert them to this node
 406                     if ( elements1.size() + remaining <= parameters.get_min_elements() )
 407                     {
 408                         elements1.push_back(elem);                                                          // MAY THROW, STRONG (copy)
 409                         index::detail::expand(box1, indexable, strategy);
 410                         content1 = index::detail::content(box1);
 411                     }
 412                     else if ( elements2.size() + remaining <= parameters.get_min_elements() )
 413                     {
 414                         elements2.push_back(elem);                                                          // MAY THROW, STRONG (alloc, copy)
 415                         index::detail::expand(box2, indexable, strategy);
 416                         content2 = index::detail::content(box2);
 417                     }
 418                     // choose better node and insert element
 419                     else
 420                     {
 421                         // calculate enlarged boxes and areas
 422                         box_type enlarged_box1(box1);
 423                         box_type enlarged_box2(box2);
 424                         index::detail::expand(enlarged_box1, indexable, strategy);
 425                         index::detail::expand(enlarged_box2, indexable, strategy);
 426                         content_type enlarged_content1 = index::detail::content(enlarged_box1);
 427                         content_type enlarged_content2 = index::detail::content(enlarged_box2);
 428
 429                         content_type content_increase1 = enlarged_content1 - content1;
 430                         content_type content_increase2 = enlarged_content2 - content2;
 431
 432                         // choose group which box content have to be enlarged least or has smaller content or has fewer elements
 433                         if ( content_increase1 < content_increase2 ||
 434                                 ( content_increase1 == content_increase2 &&
 435                                     ( content1 < content2 ||
 436                                         ( content1 == content2 && elements1.size() <= elements2.size() ) ) ) )
 437                         {
 438                             elements1.push_back(elem);                                                      // MAY THROW, STRONG (copy)
 439                             box1 = enlarged_box1;
 440                             content1 = enlarged_content1;
 441                         }
 442                         else
 443                         {
 444                             elements2.push_back(elem);                                                      // MAY THROW, STRONG (alloc, copy)
 445                             box2 = enlarged_box2;
 446                             content2 = enlarged_content2;
 447                         }
 448                     }
 449
 450                     BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "unexpected value");
 451                     --remaining;
 452                 }
 453             }
 454         }
 455         BOOST_CATCH(...)
 456         {
 457             elements1.clear();
 458             elements2.clear();
 459
 460             rtree::destroy_elements<MembersHolder>::apply(elements_copy, allocators);
 461             //elements_copy.clear();
 462
 463             BOOST_RETHROW                                                                                     // RETHROW, BASIC
 464         }
 465         BOOST_CATCH_END
 466     }
 467 };
 468
 469 }} // namespace detail::rtree
 470
 471 }}} // namespace boost::geometry::index
 472
 473 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP