ceph/src/boost/boost/geometry/index/detail/rtree/pack_create.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree initial packing
   4 //
   5 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
   6 // Copyright (c) 2020 Caian Benedicto, Campinas, Brazil.
   7 //
   8 // This file was modified by Oracle on 2019-2021.
   9 // Modifications copyright (c) 2019-2021 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_PACK_CREATE_HPP
  17 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP
  18
  19 #include <boost/core/ignore_unused.hpp>
  20
  21 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
  22 #include <boost/geometry/algorithms/expand.hpp>
  23
  24 #include <boost/geometry/index/detail/algorithms/content.hpp>
  25 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
  26 #include <boost/geometry/index/detail/algorithms/nth_element.hpp>
  27 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
  28 #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
  29 #include <boost/geometry/index/parameters.hpp>
  30
  31 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
  32
  33 namespace pack_utils {
  34
  35 template <std::size_t Dimension>
  36 struct biggest_edge
  37 {
  38     BOOST_STATIC_ASSERT(0 < Dimension);
  39     template <typename Box>
  40     static inline void apply(Box const& box, typename coordinate_type<Box>::type & length, std::size_t & dim_index)
  41     {
  42         biggest_edge<Dimension-1>::apply(box, length, dim_index);
  43         typename coordinate_type<Box>::type curr
  44             = geometry::get<max_corner, Dimension-1>(box) - geometry::get<min_corner, Dimension-1>(box);
  45         if ( length < curr )
  46         {
  47             dim_index = Dimension - 1;
  48             length = curr;
  49         }
  50     }
  51 };
  52
  53 template <>
  54 struct biggest_edge<1>
  55 {
  56     template <typename Box>
  57     static inline void apply(Box const& box, typename coordinate_type<Box>::type & length, std::size_t & dim_index)
  58     {
  59         dim_index = 0;
  60         length = geometry::get<max_corner, 0>(box) - geometry::get<min_corner, 0>(box);
  61     }
  62 };
  63
  64 template <std::size_t I>
  65 struct point_entries_comparer
  66 {
  67     template <typename PointEntry>
  68     bool operator()(PointEntry const& e1, PointEntry const& e2) const
  69     {
  70         return geometry::get<I>(e1.first) < geometry::get<I>(e2.first);
  71     }
  72 };
  73
  74 template <std::size_t I, std::size_t Dimension>
  75 struct nth_element_and_half_boxes
  76 {
  77     template <typename EIt, typename Box>
  78     static inline void apply(EIt first, EIt median, EIt last, Box const& box, Box & left, Box & right, std::size_t dim_index)
  79     {
  80         if ( I == dim_index )
  81         {
  82             index::detail::nth_element(first, median, last, point_entries_comparer<I>());
  83
  84             geometry::convert(box, left);
  85             geometry::convert(box, right);
  86             typename coordinate_type<Box>::type edge_len
  87                 = geometry::get<max_corner, I>(box) - geometry::get<min_corner, I>(box);
  88             typename coordinate_type<Box>::type median
  89                 = geometry::get<min_corner, I>(box) + edge_len / 2;
  90             geometry::set<max_corner, I>(left, median);
  91             geometry::set<min_corner, I>(right, median);
  92         }
  93         else
  94             nth_element_and_half_boxes<I+1, Dimension>::apply(first, median, last, box, left, right, dim_index);
  95     }
  96 };
  97
  98 template <std::size_t Dimension>
  99 struct nth_element_and_half_boxes<Dimension, Dimension>
 100 {
 101     template <typename EIt, typename Box>
 102     static inline void apply(EIt , EIt , EIt , Box const& , Box & , Box & , std::size_t ) {}
 103 };
 104
 105 } // namespace pack_utils
 106
 107 // STR leafs number are calculated as rcount/max
 108 // and the number of splitting planes for each dimension as (count/max)^(1/dimension)
 109 // <-> for dimension==2 -> sqrt(count/max)
 110 //
 111 // The main flaw of this algorithm is that the resulting tree will have bad structure for:
 112 // 1. non-uniformly distributed elements
 113 //      Statistic check could be performed, e.g. based on variance of lengths of elements edges for each dimension
 114 // 2. elements distributed mainly along one axis
 115 //      Calculate bounding box of all elements and then number of dividing planes for a dimension
 116 //      from the length of BB edge for this dimension (more or less assuming that elements are uniformly-distributed squares)
 117 //
 118 // Another thing is that the last node may have less elements than Max or even Min.
 119 // The number of splitting planes must be chosen more carefully than count/max
 120 //
 121 // This algorithm is something between STR and TGS
 122 // it is more similar to the top-down recursive kd-tree creation algorithm
 123 // using object median split and split axis of greatest BB edge
 124 // BB is only used as a hint (assuming objects are distributed uniformly)
 125 //
 126 // Implemented algorithm guarantees that the number of elements in nodes will be between Min and Max
 127 // and that nodes are packed as tightly as possible
 128 // e.g. for 177 values Max = 5 and Min = 2 it will construct the following tree:
 129 // ROOT                 177
 130 // L1          125               52
 131 // L2  25  25  25  25  25   25  17    10
 132 // L3  5x5 5x5 5x5 5x5 5x5  5x5 3x5+2 2x5
 133
 134 template <typename MembersHolder>
 135 class pack
 136 {
 137     typedef typename MembersHolder::node node;
 138     typedef typename MembersHolder::internal_node internal_node;
 139     typedef typename MembersHolder::leaf leaf;
 140
 141     typedef typename MembersHolder::node_pointer node_pointer;
 142     typedef typename MembersHolder::size_type size_type;
 143     typedef typename MembersHolder::parameters_type parameters_type;
 144     typedef typename MembersHolder::translator_type translator_type;
 145     typedef typename MembersHolder::allocators_type allocators_type;
 146
 147     typedef typename MembersHolder::box_type box_type;
 148     typedef typename geometry::point_type<box_type>::type point_type;
 149     typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
 150     typedef typename detail::default_content_result<box_type>::type content_type;
 151     typedef typename detail::strategy_type<parameters_type>::type strategy_type;
 152     static const std::size_t dimension = geometry::dimension<point_type>::value;
 153
 154     typedef typename rtree::container_from_elements_type<
 155         typename rtree::elements_type<leaf>::type,
 156         size_type
 157     >::type values_counts_container;
 158
 159     typedef typename rtree::elements_type<internal_node>::type internal_elements;
 160     typedef typename internal_elements::value_type internal_element;
 161
 162     typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
 163
 164 public:
 165     // Arbitrary iterators
 166     template <typename InIt> inline static
 167     node_pointer apply(InIt first, InIt last,
 168                        size_type & values_count,
 169                        size_type & leafs_level,
 170                        parameters_type const& parameters,
 171                        translator_type const& translator,
 172                        allocators_type & allocators)
 173     {
 174         return apply(first, last, values_count, leafs_level, parameters, translator,
 175                      allocators, boost::container::new_allocator<void>());
 176     }
 177
 178     template <typename InIt, typename TmpAlloc> inline static
 179     node_pointer apply(InIt first, InIt last,
 180                        size_type & values_count,
 181                        size_type & leafs_level,
 182                        parameters_type const& parameters,
 183                        translator_type const& translator,
 184                        allocators_type & allocators,
 185                        TmpAlloc const& temp_allocator)
 186     {
 187         typedef typename std::iterator_traits<InIt>::difference_type diff_type;
 188
 189         diff_type diff = std::distance(first, last);
 190         if ( diff <= 0 )
 191             return node_pointer(0);
 192
 193         typedef std::pair<point_type, InIt> entry_type;
 194         typedef typename boost::container::allocator_traits<TmpAlloc>::
 195             template rebind_alloc<entry_type> temp_entry_allocator_type;
 196
 197         temp_entry_allocator_type temp_entry_allocator(temp_allocator);
 198         boost::container::vector<entry_type, temp_entry_allocator_type> entries(temp_entry_allocator);
 199
 200         values_count = static_cast<size_type>(diff);
 201         entries.reserve(values_count);
 202
 203         auto const& strategy = index::detail::get_strategy(parameters);
 204
 205         expandable_box<box_type, strategy_type> hint_box(strategy);
 206         for ( ; first != last ; ++first )
 207         {
 208             // NOTE: support for iterators not returning true references adapted
 209             // to Geometry concept and default translator returning true reference
 210             // An alternative would be to dereference the iterator and translate
 211             // in one expression each time the indexable was needed.
 212             typename std::iterator_traits<InIt>::reference in_ref = *first;
 213             typename translator_type::result_type indexable = translator(in_ref);
 214
 215             // NOTE: added for consistency with insert()
 216             // CONSIDER: alternative - ignore invalid indexable or throw an exception
 217             BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(indexable), "Indexable is invalid");
 218
 219             hint_box.expand(indexable);
 220
 221             point_type pt;
 222             geometry::centroid(indexable, pt, strategy);
 223             entries.push_back(std::make_pair(pt, first));
 224         }
 225
 226         subtree_elements_counts subtree_counts = calculate_subtree_elements_counts(values_count, parameters, leafs_level);
 227         internal_element el = per_level(entries.begin(), entries.end(), hint_box.get(), values_count, subtree_counts,
 228                                         parameters, translator, allocators);
 229
 230         return el.second;
 231     }
 232
 233 private:
 234     template <typename BoxType, typename Strategy>
 235     class expandable_box
 236     {
 237     public:
 238         explicit expandable_box(Strategy const& strategy)
 239             : m_strategy(strategy), m_initialized(false)
 240         {}
 241
 242         template <typename Indexable>
 243         explicit expandable_box(Indexable const& indexable, Strategy const& strategy)
 244             : m_strategy(strategy), m_initialized(true)
 245         {
 246             detail::bounds(indexable, m_box, m_strategy);
 247         }
 248
 249         template <typename Indexable>
 250         void expand(Indexable const& indexable)
 251         {
 252             if ( !m_initialized )
 253             {
 254                 // it's guaranteed that the Box will be initialized
 255                 // only for Points, Boxes and Segments but that's ok
 256                 // since only those Geometries can be stored
 257                 detail::bounds(indexable, m_box, m_strategy);
 258                 m_initialized = true;
 259             }
 260             else
 261             {
 262                 detail::expand(m_box, indexable, m_strategy);
 263             }
 264         }
 265
 266         void expand_by_epsilon()
 267         {
 268             geometry::detail::expand_by_epsilon(m_box);
 269         }
 270
 271         BoxType const& get() const
 272         {
 273             BOOST_GEOMETRY_INDEX_ASSERT(m_initialized, "uninitialized envelope accessed");
 274             return m_box;
 275         }
 276
 277     private:
 278         BoxType m_box;
 279         Strategy m_strategy;
 280         bool m_initialized;
 281     };
 282
 283     struct subtree_elements_counts
 284     {
 285         subtree_elements_counts(size_type ma, size_type mi) : maxc(ma), minc(mi) {}
 286         size_type maxc;
 287         size_type minc;
 288     };
 289
 290     template <typename EIt> inline static
 291     internal_element per_level(EIt first, EIt last,
 292                                box_type const& hint_box,
 293                                size_type values_count,
 294                                subtree_elements_counts const& subtree_counts,
 295                                parameters_type const& parameters,
 296                                translator_type const& translator,
 297                                allocators_type & allocators)
 298     {
 299         BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<size_type>(std::distance(first, last)) == values_count,
 300                                     "unexpected parameters");
 301
 302         if ( subtree_counts.maxc <= 1 )
 303         {
 304             // ROOT or LEAF
 305             BOOST_GEOMETRY_INDEX_ASSERT(values_count <= parameters.get_max_elements(),
 306                                         "too big number of elements");
 307             // if !root check m_parameters.get_min_elements() <= count
 308
 309             // create new leaf node
 310             node_pointer n = rtree::create_node<allocators_type, leaf>::apply(allocators);                       // MAY THROW (A)
 311             subtree_destroyer auto_remover(n, allocators);
 312             leaf & l = rtree::get<leaf>(*n);
 313
 314             // reserve space for values
 315             rtree::elements(l).reserve(values_count);                                                       // MAY THROW (A)
 316
 317             // calculate values box and copy values
 318             //   initialize the box explicitly to avoid GCC-4.4 uninitialized variable warnings with O2
 319             expandable_box<box_type, strategy_type> elements_box(translator(*(first->second)),
 320                                                                  detail::get_strategy(parameters));
 321             rtree::elements(l).push_back(*(first->second));                                                 // MAY THROW (A?,C)
 322             for ( ++first ; first != last ; ++first )
 323             {
 324                 // NOTE: push_back() must be called at the end in order to support move_iterator.
 325                 //       The iterator is dereferenced 2x (no temporary reference) to support
 326                 //       non-true reference types and move_iterator without boost::forward<>.
 327                 elements_box.expand(translator(*(first->second)));
 328                 rtree::elements(l).push_back(*(first->second));                                             // MAY THROW (A?,C)
 329             }
 330
 331 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
 332             // Enlarge bounds of a leaf node.
 333             // It's because Points and Segments are compared WRT machine epsilon
 334             // This ensures that leafs bounds correspond to the stored elements
 335             // NOTE: this is done only if the Indexable is a different kind of Geometry
 336             //   than the bounds (only Box for now). Spatial predicates are checked
 337             //   the same way for Geometry of the same kind.
 338             if ( BOOST_GEOMETRY_CONDITION((
 339                     ! index::detail::is_bounding_geometry
 340                         <
 341                             typename indexable_type<translator_type>::type
 342                         >::value )) )
 343             {
 344                 elements_box.expand_by_epsilon();
 345             }
 346 #endif
 347
 348             auto_remover.release();
 349             return internal_element(elements_box.get(), n);
 350         }
 351
 352         // calculate next max and min subtree counts
 353         subtree_elements_counts next_subtree_counts = subtree_counts;
 354         next_subtree_counts.maxc /= parameters.get_max_elements();
 355         next_subtree_counts.minc /= parameters.get_max_elements();
 356
 357         // create new internal node
 358         node_pointer n = rtree::create_node<allocators_type, internal_node>::apply(allocators);                  // MAY THROW (A)
 359         subtree_destroyer auto_remover(n, allocators);
 360         internal_node & in = rtree::get<internal_node>(*n);
 361
 362         // reserve space for values
 363         size_type nodes_count = calculate_nodes_count(values_count, subtree_counts);
 364         rtree::elements(in).reserve(nodes_count);                                                           // MAY THROW (A)
 365         // calculate values box and copy values
 366         expandable_box<box_type, strategy_type> elements_box(detail::get_strategy(parameters));
 367
 368         per_level_packets(first, last, hint_box, values_count, subtree_counts, next_subtree_counts,
 369                           rtree::elements(in), elements_box,
 370                           parameters, translator, allocators);
 371
 372         auto_remover.release();
 373         return internal_element(elements_box.get(), n);
 374     }
 375
 376     template <typename EIt, typename ExpandableBox> inline static
 377     void per_level_packets(EIt first, EIt last,
 378                            box_type const& hint_box,
 379                            size_type values_count,
 380                            subtree_elements_counts const& subtree_counts,
 381                            subtree_elements_counts const& next_subtree_counts,
 382                            internal_elements & elements,
 383                            ExpandableBox & elements_box,
 384                            parameters_type const& parameters,
 385                            translator_type const& translator,
 386                            allocators_type & allocators)
 387     {
 388         BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<size_type>(std::distance(first, last)) == values_count,
 389                                     "unexpected parameters");
 390
 391         BOOST_GEOMETRY_INDEX_ASSERT(subtree_counts.minc <= values_count,
 392                                     "too small number of elements");
 393
 394         // only one packet
 395         if ( values_count <= subtree_counts.maxc )
 396         {
 397             // the end, move to the next level
 398             internal_element el = per_level(first, last, hint_box, values_count, next_subtree_counts,
 399                                             parameters, translator, allocators);
 400
 401             // in case if push_back() do throw here
 402             // and even if this is not probable (previously reserved memory, nonthrowing pairs copy)
 403             // this case is also tested by exceptions test.
 404             subtree_destroyer auto_remover(el.second, allocators);
 405             // this container should have memory allocated, reserve() called outside
 406             elements.push_back(el);                                                 // MAY THROW (A?,C) - however in normal conditions shouldn't
 407             auto_remover.release();
 408
 409             elements_box.expand(el.first);
 410             return;
 411         }
 412
 413         size_type median_count = calculate_median_count(values_count, subtree_counts);
 414         EIt median = first + median_count;
 415
 416         coordinate_type greatest_length;
 417         std::size_t greatest_dim_index = 0;
 418         pack_utils::biggest_edge<dimension>::apply(hint_box, greatest_length, greatest_dim_index);
 419         box_type left, right;
 420         pack_utils::nth_element_and_half_boxes<0, dimension>
 421             ::apply(first, median, last, hint_box, left, right, greatest_dim_index);
 422
 423         per_level_packets(first, median, left,
 424                           median_count, subtree_counts, next_subtree_counts,
 425                           elements, elements_box,
 426                           parameters, translator, allocators);
 427         per_level_packets(median, last, right,
 428                           values_count - median_count, subtree_counts, next_subtree_counts,
 429                           elements, elements_box,
 430                           parameters, translator, allocators);
 431     }
 432
 433     inline static
 434     subtree_elements_counts calculate_subtree_elements_counts(size_type elements_count, parameters_type const& parameters, size_type & leafs_level)
 435     {
 436         boost::ignore_unused(parameters);
 437
 438         subtree_elements_counts res(1, 1);
 439         leafs_level = 0;
 440
 441         size_type smax = parameters.get_max_elements();
 442         for ( ; smax < elements_count ; smax *= parameters.get_max_elements(), ++leafs_level )
 443             res.maxc = smax;
 444
 445         res.minc = parameters.get_min_elements() * (res.maxc / parameters.get_max_elements());
 446
 447         return res;
 448     }
 449
 450     inline static
 451     size_type calculate_nodes_count(size_type count,
 452                                     subtree_elements_counts const& subtree_counts)
 453     {
 454         size_type n = count / subtree_counts.maxc;
 455         size_type r = count % subtree_counts.maxc;
 456
 457         if ( 0 < r && r < subtree_counts.minc )
 458         {
 459             size_type count_minus_min = count - subtree_counts.minc;
 460             n = count_minus_min / subtree_counts.maxc;
 461             r = count_minus_min % subtree_counts.maxc;
 462             ++n;
 463         }
 464
 465         if ( 0 < r )
 466             ++n;
 467
 468         return n;
 469     }
 470
 471     inline static
 472     size_type calculate_median_count(size_type count,
 473                                      subtree_elements_counts const& subtree_counts)
 474     {
 475         // e.g. for max = 5, min = 2, count = 52, subtree_max = 25, subtree_min = 10
 476
 477         size_type n = count / subtree_counts.maxc; // e.g. 52 / 25 = 2
 478         size_type r = count % subtree_counts.maxc; // e.g. 52 % 25 = 2
 479         size_type median_count = (n / 2) * subtree_counts.maxc; // e.g. 2 / 2 * 25 = 25
 480
 481         if ( 0 != r ) // e.g. 0 != 2
 482         {
 483             if ( subtree_counts.minc <= r ) // e.g. 10 <= 2 == false
 484             {
 485                 //BOOST_GEOMETRY_INDEX_ASSERT(0 < n, "unexpected value");
 486                 median_count = ((n+1)/2) * subtree_counts.maxc; // if calculated ((2+1)/2) * 25 which would be ok, but not in all cases
 487             }
 488             else // r < subtree_counts.second  // e.g. 2 < 10 == true
 489             {
 490                 size_type count_minus_min = count - subtree_counts.minc; // e.g. 52 - 10 = 42
 491                 n = count_minus_min / subtree_counts.maxc; // e.g. 42 / 25 = 1
 492                 r = count_minus_min % subtree_counts.maxc; // e.g. 42 % 25 = 17
 493                 if ( r == 0 )                               // e.g. false
 494                 {
 495                     // n can't be equal to 0 because then there wouldn't be any element in the other node
 496                     //BOOST_GEOMETRY_INDEX_ASSERT(0 < n, "unexpected value");
 497                     median_count = ((n+1)/2) * subtree_counts.maxc;     // if calculated ((1+1)/2) * 25 which would be ok, but not in all cases
 498                 }
 499                 else
 500                 {
 501                     if ( n == 0 )                                        // e.g. false
 502                         median_count = r;                                // if calculated -> 17 which is wrong!
 503                     else
 504                         median_count = ((n+2)/2) * subtree_counts.maxc; // e.g. ((1+2)/2) * 25 = 25
 505                 }
 506             }
 507         }
 508
 509         return median_count;
 510     }
 511 };
 512
 513 }}}}} // namespace boost::geometry::index::detail::rtree
 514
 515 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP