rtree/linear/redistribute_elements.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree linear split algorithm implementation
0004 //
0005 // Copyright (c) 2008 Federico J. Fernandez.
0006 // Copyright (c) 2011-2022 Adam Wulkiewicz, Lodz, Poland.
0007 //
0008 // This file was modified by Oracle on 2019-2020.
0009 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
0018
0019 #include <type_traits>
0020
0021 #include <boost/core/ignore_unused.hpp>
0022
0023 #include <boost/geometry/core/static_assert.hpp>
0024
0025 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
0026 #include <boost/geometry/index/detail/algorithms/content.hpp>
0027 #include <boost/geometry/index/detail/bounded_view.hpp>
0028
0029 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0030 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
0031 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
0032
0033 namespace boost { namespace geometry { namespace index {
0034
0035 namespace detail { namespace rtree {
0036
0037 namespace linear {
0038
0039 template <typename R, typename T>
0040 inline R difference_dispatch(T const& from, T const& to, std::false_type /*is_unsigned*/)
0041 {
0042     return to - from;
0043 }
0044
0045 template <typename R, typename T>
0046 inline R difference_dispatch(T const& from, T const& to, std::true_type /*is_unsigned*/)
0047 {
0048     return from <= to ? R(to - from) : -R(from - to);
0049 }
0050
0051 template <typename R, typename T>
0052 inline R difference(T const& from, T const& to)
0053 {
0054     BOOST_GEOMETRY_STATIC_ASSERT((! std::is_unsigned<R>::value),
0055         "Result can not be an unsigned type.",
0056         R);
0057
0058     return difference_dispatch<R>(from, to, std::is_unsigned<T>());
0059 }
0060
0061 // TODO: awulkiew
0062 // In general, all aerial Indexables in the tree with box-like nodes will be analyzed as boxes
0063 // because they must fit into larger box. Therefore the algorithm could be the same for Bounds type.
0064 // E.g. if Bounds type is sphere, Indexables probably should be analyzed as spheres.
0065 // 1. View could be provided to 'see' all Indexables as Bounds type.
0066 //    Not ok in the case of big types like Ring, however it's possible that Rings won't be supported,
0067 //    only simple types. Even then if we consider storing Box inside the Sphere we must calculate
0068 //    the bounding sphere 2x for each box because there are 2 loops. For each calculation this means
0069 //    4-2d or 8-3d expansions or -, / and sqrt().
0070 // 2. Additional container could be used and reused if the Indexable type is other than the Bounds type.
0071
0072 // IMPORTANT!
0073 // Still probably the best way would be providing specialized algorithms for each Indexable-Bounds pair!
0074 // Probably on pick_seeds algorithm level - For Bounds=Sphere seeds would be choosen differently
0075
0076 // TODO: awulkiew
0077 // there are loops inside find_greatest_normalized_separation::apply()
0078 // iteration is done for each DimensionIndex.
0079 // Separations and seeds for all DimensionIndex(es) could be calculated at once, stored, then the greatest would be choosen.
0080
0081 // The following struct/method was adapted for the preliminary version of the R-tree. Then it was called:
0082 // void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
0083
0084 template <typename Elements, typename Parameters, typename Translator, typename Tag, size_t DimensionIndex>
0085 struct find_greatest_normalized_separation
0086 {
0087     typedef typename Elements::value_type element_type;
0088     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0089     typedef typename coordinate_type<indexable_type>::type coordinate_type;
0090
0091     typedef std::conditional_t
0092         <
0093             std::is_integral<coordinate_type>::value,
0094             double,
0095             coordinate_type
0096         > separation_type;
0097
0098     typedef typename geometry::point_type<indexable_type>::type point_type;
0099     typedef geometry::model::box<point_type> bounds_type;
0100     typedef index::detail::bounded_view
0101         <
0102             indexable_type, bounds_type,
0103             typename index::detail::strategy_type<Parameters>::type
0104         > bounded_view_type;
0105
0106     static inline void apply(Elements const& elements,
0107                              Parameters const& parameters,
0108                              Translator const& translator,
0109                              separation_type & separation,
0110                              size_t & seed1,
0111                              size_t & seed2)
0112     {
0113         const size_t elements_count = parameters.get_max_elements() + 1;
0114         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
0115         BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
0116
0117         auto const& strategy = index::detail::get_strategy(parameters);
0118
0119         // find the lowest low, highest high
0120         indexable_type const& indexable_0 = rtree::element_indexable(elements[0], translator);
0121         bounded_view_type const bounded_indexable_0(indexable_0, strategy);
0122         coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_0);
0123         coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(bounded_indexable_0);
0124
0125         // and the lowest high
0126         coordinate_type lowest_high = highest_high;
0127         size_t lowest_high_index = 0;
0128         for (size_t i = 1 ; i < elements_count ; ++i)
0129         {
0130             indexable_type const& indexable_i = rtree::element_indexable(elements[i], translator);
0131             bounded_view_type const bounded_indexable(indexable_i, strategy);
0132             coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable);
0133             coordinate_type max_coord = geometry::get<max_corner, DimensionIndex>(bounded_indexable);
0134
0135             if (max_coord < lowest_high)
0136             {
0137                 lowest_high = max_coord;
0138                 lowest_high_index = i;
0139             }
0140
0141             if (min_coord < lowest_low)
0142             {
0143                 lowest_low = min_coord;
0144             }
0145
0146             if (highest_high < max_coord)
0147             {
0148                 highest_high = max_coord;
0149             }
0150         }
0151
0152         // find the highest low
0153         size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
0154         indexable_type const& indexable_hl = rtree::element_indexable(elements[highest_low_index], translator);
0155         bounded_view_type const bounded_indexable_hl(indexable_hl, strategy);
0156         coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_hl);
0157         for (size_t i = highest_low_index ; i < elements_count ; ++i)
0158         {
0159             indexable_type const& indexable = rtree::element_indexable(elements[i], translator);
0160             bounded_view_type const bounded_indexable(indexable, strategy);
0161             coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable);
0162             if (highest_low < min_coord && i != lowest_high_index)
0163             {
0164                 highest_low = min_coord;
0165                 highest_low_index = i;
0166             }
0167         }
0168
0169         coordinate_type const width = highest_high - lowest_low;
0170
0171         // highest_low - lowest_high
0172         separation = difference<separation_type>(lowest_high, highest_low);
0173         // BOOST_GEOMETRY_INDEX_ASSERT(0 <= width);
0174         if (std::numeric_limits<coordinate_type>::epsilon() < width)
0175         {
0176             separation /= width;
0177         }
0178
0179         seed1 = highest_low_index;
0180         seed2 = lowest_high_index;
0181
0182         ::boost::ignore_unused(parameters);
0183     }
0184 };
0185
0186 // Version for points doesn't calculate normalized separation since it would always be equal to 1
0187 // It returns two seeds most distant to each other, separation is equal to distance
0188 template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
0189 struct find_greatest_normalized_separation<Elements, Parameters, Translator, point_tag, DimensionIndex>
0190 {
0191     typedef typename Elements::value_type element_type;
0192     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0193     typedef typename coordinate_type<indexable_type>::type coordinate_type;
0194
0195     typedef coordinate_type separation_type;
0196
0197     static inline void apply(Elements const& elements,
0198                              Parameters const& parameters,
0199                              Translator const& translator,
0200                              separation_type & separation,
0201                              size_t & seed1,
0202                              size_t & seed2)
0203     {
0204         const size_t elements_count = parameters.get_max_elements() + 1;
0205         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
0206         BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
0207
0208         // find the lowest low, highest high
0209         coordinate_type lowest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator));
0210         coordinate_type highest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator));
0211         size_t lowest_index = 0;
0212         size_t highest_index = 0;
0213         for ( size_t i = 1 ; i < elements_count ; ++i )
0214         {
0215             coordinate_type coord = geometry::get<DimensionIndex>(rtree::element_indexable(elements[i], translator));
0216
0217             if ( coord < lowest )
0218             {
0219                 lowest = coord;
0220                 lowest_index = i;
0221             }
0222
0223             if ( highest < coord )
0224             {
0225                 highest = coord;
0226                 highest_index = i;
0227             }
0228         }
0229
0230         separation = highest - lowest;
0231         seed1 = lowest_index;
0232         seed2 = highest_index;
0233
0234         if ( lowest_index == highest_index )
0235             seed2 = (lowest_index + 1) % elements_count; // % is just in case since if this is true lowest_index is 0
0236
0237         ::boost::ignore_unused(parameters);
0238     }
0239 };
0240
0241 template <typename Elements, typename Parameters, typename Translator, size_t Dimension>
0242 struct pick_seeds_impl
0243 {
0244     BOOST_STATIC_ASSERT(0 < Dimension);
0245
0246     typedef typename Elements::value_type element_type;
0247     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0248
0249     typedef find_greatest_normalized_separation<
0250         Elements, Parameters, Translator,
0251         typename tag<indexable_type>::type, Dimension - 1
0252     > find_norm_sep;
0253
0254     typedef typename find_norm_sep::separation_type separation_type;
0255
0256     static inline void apply(Elements const& elements,
0257                              Parameters const& parameters,
0258                              Translator const& tr,
0259                              separation_type & separation,
0260                              size_t & seed1,
0261                              size_t & seed2)
0262     {
0263         pick_seeds_impl<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, separation, seed1, seed2);
0264
0265         separation_type current_separation;
0266         size_t s1, s2;
0267         find_norm_sep::apply(elements, parameters, tr, current_separation, s1, s2);
0268
0269         // in the old implementation different operator was used: <= (y axis prefered)
0270         if ( separation < current_separation )
0271         {
0272             separation = current_separation;
0273             seed1 = s1;
0274             seed2 = s2;
0275         }
0276     }
0277 };
0278
0279 template <typename Elements, typename Parameters, typename Translator>
0280 struct pick_seeds_impl<Elements, Parameters, Translator, 1>
0281 {
0282     typedef typename Elements::value_type element_type;
0283     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0284     typedef typename coordinate_type<indexable_type>::type coordinate_type;
0285
0286     typedef find_greatest_normalized_separation<
0287         Elements, Parameters, Translator,
0288         typename tag<indexable_type>::type, 0
0289     > find_norm_sep;
0290
0291     typedef typename find_norm_sep::separation_type separation_type;
0292
0293     static inline void apply(Elements const& elements,
0294                              Parameters const& parameters,
0295                              Translator const& tr,
0296                              separation_type & separation,
0297                              size_t & seed1,
0298                              size_t & seed2)
0299     {
0300         find_norm_sep::apply(elements, parameters, tr, separation, seed1, seed2);
0301     }
0302 };
0303
0304 // from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
0305
0306 template <typename Elements, typename Parameters, typename Translator>
0307 inline void pick_seeds(Elements const& elements,
0308                        Parameters const& parameters,
0309                        Translator const& tr,
0310                        size_t & seed1,
0311                        size_t & seed2)
0312 {
0313     typedef typename Elements::value_type element_type;
0314     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0315
0316     typedef pick_seeds_impl
0317         <
0318             Elements, Parameters, Translator,
0319             geometry::dimension<indexable_type>::value
0320         > impl;
0321     typedef typename impl::separation_type separation_type;
0322
0323     separation_type separation = 0;
0324     impl::apply(elements, parameters, tr, separation, seed1, seed2);
0325 }
0326
0327 } // namespace linear
0328
0329 // from void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const
0330
0331 template <typename MembersHolder>
0332 struct redistribute_elements<MembersHolder, linear_tag>
0333 {
0334     typedef typename MembersHolder::box_type box_type;
0335     typedef typename MembersHolder::parameters_type parameters_type;
0336     typedef typename MembersHolder::translator_type translator_type;
0337     typedef typename MembersHolder::allocators_type allocators_type;
0338
0339     typedef typename MembersHolder::node node;
0340     typedef typename MembersHolder::internal_node internal_node;
0341     typedef typename MembersHolder::leaf leaf;
0342
0343     template <typename Node>
0344     static inline void apply(Node & n,
0345                              Node & second_node,
0346                              box_type & box1,
0347                              box_type & box2,
0348                              parameters_type const& parameters,
0349                              translator_type const& translator,
0350                              allocators_type & allocators)
0351     {
0352         typedef typename rtree::elements_type<Node>::type elements_type;
0353         typedef typename elements_type::value_type element_type;
0354         typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
0355         typedef typename index::detail::default_content_result<box_type>::type content_type;
0356
0357         typename index::detail::strategy_type<parameters_type>::type const&
0358             strategy = index::detail::get_strategy(parameters);
0359
0360         elements_type & elements1 = rtree::elements(n);
0361         elements_type & elements2 = rtree::elements(second_node);
0362         const size_t elements1_count = parameters.get_max_elements() + 1;
0363
0364         BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
0365
0366         // copy original elements - use in-memory storage (std::allocator)
0367         // TODO: move if noexcept
0368         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
0369             container_type;
0370         container_type elements_copy(elements1.begin(), elements1.end());                                   // MAY THROW, STRONG (alloc, copy)
0371
0372         // calculate initial seeds
0373         size_t seed1 = 0;
0374         size_t seed2 = 0;
0375         linear::pick_seeds(elements_copy, parameters, translator, seed1, seed2);
0376
0377         // prepare nodes' elements containers
0378         elements1.clear();
0379         BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state");
0380
0381         BOOST_TRY
0382         {
0383             // add seeds
0384             elements1.push_back(elements_copy[seed1]);                                                      // MAY THROW, STRONG (copy)
0385             elements2.push_back(elements_copy[seed2]);                                                      // MAY THROW, STRONG (alloc, copy)
0386
0387             // calculate boxes
0388             detail::bounds(rtree::element_indexable(elements_copy[seed1], translator),
0389                            box1, strategy);
0390             detail::bounds(rtree::element_indexable(elements_copy[seed2], translator),
0391                            box2, strategy);
0392
0393             // initialize areas
0394             content_type content1 = index::detail::content(box1);
0395             content_type content2 = index::detail::content(box2);
0396
0397             BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
0398             size_t remaining = elements1_count - 2;
0399
0400             // redistribute the rest of the elements
0401             for ( size_t i = 0 ; i < elements1_count ; ++i )
0402             {
0403                 if (i != seed1 && i != seed2)
0404                 {
0405                     element_type const& elem = elements_copy[i];
0406                     indexable_type const& indexable = rtree::element_indexable(elem, translator);
0407
0408                     // if there is small number of elements left and the number of elements in node is lesser than min_elems
0409                     // just insert them to this node
0410                     if ( elements1.size() + remaining <= parameters.get_min_elements() )
0411                     {
0412                         elements1.push_back(elem);                                                          // MAY THROW, STRONG (copy)
0413                         index::detail::expand(box1, indexable, strategy);
0414                         content1 = index::detail::content(box1);
0415                     }
0416                     else if ( elements2.size() + remaining <= parameters.get_min_elements() )
0417                     {
0418                         elements2.push_back(elem);                                                          // MAY THROW, STRONG (alloc, copy)
0419                         index::detail::expand(box2, indexable, strategy);
0420                         content2 = index::detail::content(box2);
0421                     }
0422                     // choose better node and insert element
0423                     else
0424                     {
0425                         // calculate enlarged boxes and areas
0426                         box_type enlarged_box1(box1);
0427                         box_type enlarged_box2(box2);
0428                         index::detail::expand(enlarged_box1, indexable, strategy);
0429                         index::detail::expand(enlarged_box2, indexable, strategy);
0430                         content_type enlarged_content1 = index::detail::content(enlarged_box1);
0431                         content_type enlarged_content2 = index::detail::content(enlarged_box2);
0432
0433                         content_type content_increase1 = enlarged_content1 - content1;
0434                         content_type content_increase2 = enlarged_content2 - content2;
0435
0436                         // choose group which box content have to be enlarged least or has smaller content or has fewer elements
0437                         if ( content_increase1 < content_increase2 ||
0438                                 ( content_increase1 == content_increase2 &&
0439                                     ( content1 < content2 ||
0440                                         ( content1 == content2 && elements1.size() <= elements2.size() ) ) ) )
0441                         {
0442                             elements1.push_back(elem);                                                      // MAY THROW, STRONG (copy)
0443                             box1 = enlarged_box1;
0444                             content1 = enlarged_content1;
0445                         }
0446                         else
0447                         {
0448                             elements2.push_back(elem);                                                      // MAY THROW, STRONG (alloc, copy)
0449                             box2 = enlarged_box2;
0450                             content2 = enlarged_content2;
0451                         }
0452                     }
0453
0454                     BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "unexpected value");
0455                     --remaining;
0456                 }
0457             }
0458         }
0459         BOOST_CATCH(...)
0460         {
0461             elements1.clear();
0462             elements2.clear();
0463
0464             rtree::destroy_elements<MembersHolder>::apply(elements_copy, allocators);
0465             //elements_copy.clear();
0466
0467             BOOST_RETHROW                                                                                     // RETHROW, BASIC
0468         }
0469         BOOST_CATCH_END
0470     }
0471 };
0472
0473 }} // namespace detail::rtree
0474
0475 }}} // namespace boost::geometry::index
0476
0477 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP