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