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

   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:
  50     element_axis_corner_less(Translator const& tr, strategy_type const& strategy)
  51         : m_tr(tr), m_strategy(strategy)
  52     {}
  53
  54     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:
  74     element_axis_corner_less(Translator const& tr, strategy_type const&)
  75         : m_tr(tr)
  76     {}
  77
  78     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:
  94     element_axis_corner_less(Translator const& tr, strategy_type const& )
  95         : m_tr(tr)
  96     {}
  97
  98     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>
 115     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>
 201     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>
 256     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>
 283     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>
 333     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>
 362     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>
 393     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 Value, typename Options, typename Translator, typename Box, typename Allocators>
 401 struct redistribute_elements<Value, Options, Translator, Box, Allocators, rstar_tag>
 402 {
 403     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
 404     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
 405     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
 406
 407     typedef typename Options::parameters_type parameters_type;
 408
 409     static const size_t dimension = geometry::dimension<Box>::value;
 410
 411     typedef typename index::detail::default_margin_result<Box>::type margin_type;
 412     typedef typename index::detail::default_content_result<Box>::type content_type;
 413
 414     template <typename Node>
 415     static inline void apply(
 416         Node & n,
 417         Node & second_node,
 418         Box & box1,
 419         Box & box2,
 420         parameters_type const& parameters,
 421         Translator const& translator,
 422         Allocators & allocators)
 423     {
 424         typedef typename rtree::elements_type<Node>::type elements_type;
 425         typedef typename elements_type::value_type element_type;
 426
 427         elements_type & elements1 = rtree::elements(n);
 428         elements_type & elements2 = rtree::elements(second_node);
 429
 430         // copy original elements - use in-memory storage (std::allocator)
 431         // TODO: move if noexcept
 432         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
 433             container_type;
 434         container_type elements_copy(elements1.begin(), elements1.end());                               // MAY THROW, STRONG
 435         container_type elements_backup(elements1.begin(), elements1.end());                             // MAY THROW, STRONG
 436
 437         size_t split_axis = 0;
 438         size_t split_corner = 0;
 439         size_t split_index = parameters.get_min_elements();
 440         margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)();
 441         content_type smallest_overlap = (std::numeric_limits<content_type>::max)();
 442         content_type smallest_content = (std::numeric_limits<content_type>::max)();
 443
 444         // NOTE: this function internally copies passed elements
 445         //       why not pass mutable elements and use the same container for all axes/corners
 446         //       and again, the same below calling partial_sort/nth_element
 447         //       It would be even possible to not re-sort/find nth_element if the axis/corner
 448         //       was found for the last sorting - last combination of axis/corner
 449         rstar::choose_split_axis_and_index<Box, dimension>
 450             ::apply(elements_copy,
 451                     split_axis, split_corner, split_index,
 452                     smallest_sum_of_margins, smallest_overlap, smallest_content,
 453                     parameters, translator);                                                            // MAY THROW, STRONG
 454
 455         // TODO: awulkiew - get rid of following static_casts?
 456         BOOST_GEOMETRY_INDEX_ASSERT(split_axis < dimension, "unexpected value");
 457         BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value");
 458         BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value");
 459
 460         // TODO: consider using nth_element
 461         if ( split_corner == static_cast<size_t>(min_corner) )
 462         {
 463             rstar::nth_element<min_corner, dimension>
 464                 ::apply(elements_copy, parameters, split_axis, split_index, translator);                // MAY THROW, BASIC (copy)
 465         }
 466         else
 467         {
 468             rstar::nth_element<max_corner, dimension>
 469                 ::apply(elements_copy, parameters, split_axis, split_index, translator);                // MAY THROW, BASIC (copy)
 470         }
 471
 472         BOOST_TRY
 473         {
 474             typename index::detail::strategy_type<parameters_type>::type const&
 475                 strategy = index::detail::get_strategy(parameters);
 476
 477             // copy elements to nodes
 478             elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index);               // MAY THROW, BASIC
 479             elements2.assign(elements_copy.begin() + split_index, elements_copy.end());                 // MAY THROW, BASIC
 480
 481             // calculate boxes
 482             box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(),
 483                                             translator, strategy);
 484             box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(),
 485                                             translator, strategy);
 486         }
 487         BOOST_CATCH(...)
 488         {
 489             //elements_copy.clear();
 490             elements1.clear();
 491             elements2.clear();
 492
 493             rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
 494             //elements_backup.clear();
 495
 496             BOOST_RETHROW                                                                                 // RETHROW, BASIC
 497         }
 498         BOOST_CATCH_END
 499     }
 500 };
 501
 502 }} // namespace detail::rtree
 503
 504 }}} // namespace boost::geometry::index
 505
 506 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP