rtree/rstar/redistribute_elements.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree R*-tree split algorithm implementation
0004 //
0005 // Copyright (c) 2011-2022 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2020.
0008 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
0017
0018 #include <boost/core/ignore_unused.hpp>
0019
0020 #include <boost/geometry/core/static_assert.hpp>
0021
0022 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp>
0023 #include <boost/geometry/index/detail/algorithms/margin.hpp>
0024 #include <boost/geometry/index/detail/algorithms/nth_element.hpp>
0025 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
0026
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 rstar {
0038
0039 template <typename Element, typename Parameters, typename Translator, typename Tag, size_t Corner, size_t AxisIndex>
0040 class element_axis_corner_less
0041 {
0042     typedef typename rtree::element_indexable_type<Element, Translator>::type indexable_type;
0043     typedef typename geometry::point_type<indexable_type>::type point_type;
0044     typedef geometry::model::box<point_type> bounds_type;
0045     typedef typename index::detail::strategy_type<Parameters>::type strategy_type;
0046     typedef index::detail::bounded_view
0047         <
0048             indexable_type, bounds_type, strategy_type
0049         > bounded_view_type;
0050
0051 public:
0052     element_axis_corner_less(Translator const& tr, strategy_type const& strategy)
0053         : m_tr(tr), m_strategy(strategy)
0054     {}
0055
0056     bool operator()(Element const& e1, Element const& e2) const
0057     {
0058         indexable_type const& ind1 = rtree::element_indexable(e1, m_tr);
0059         indexable_type const& ind2 = rtree::element_indexable(e2, m_tr);
0060         return geometry::get<Corner, AxisIndex>(bounded_view_type(ind1, m_strategy))
0061             < geometry::get<Corner, AxisIndex>(bounded_view_type(ind2, m_strategy));
0062     }
0063
0064 private:
0065     Translator const& m_tr;
0066     strategy_type const& m_strategy;
0067 };
0068
0069 template <typename Element, typename Parameters, typename Translator, size_t Corner, size_t AxisIndex>
0070 class element_axis_corner_less<Element, Parameters, Translator, box_tag, Corner, AxisIndex>
0071 {
0072     typedef typename index::detail::strategy_type<Parameters>::type strategy_type;
0073
0074 public:
0075     element_axis_corner_less(Translator const& tr, strategy_type const&)
0076         : m_tr(tr)
0077     {}
0078
0079     bool operator()(Element const& e1, Element const& e2) const
0080     {
0081         return geometry::get<Corner, AxisIndex>(rtree::element_indexable(e1, m_tr))
0082             < geometry::get<Corner, AxisIndex>(rtree::element_indexable(e2, m_tr));
0083     }
0084
0085 private:
0086     Translator const& m_tr;
0087 };
0088
0089 template <typename Element, typename Parameters, typename Translator, size_t Corner, size_t AxisIndex>
0090 class element_axis_corner_less<Element, Parameters, Translator, point_tag, Corner, AxisIndex>
0091 {
0092     typedef typename index::detail::strategy_type<Parameters>::type strategy_type;
0093
0094 public:
0095     element_axis_corner_less(Translator const& tr, strategy_type const& )
0096         : m_tr(tr)
0097     {}
0098
0099     bool operator()(Element const& e1, Element const& e2) const
0100     {
0101         return geometry::get<AxisIndex>(rtree::element_indexable(e1, m_tr))
0102             < geometry::get<AxisIndex>(rtree::element_indexable(e2, m_tr));
0103     }
0104
0105 private:
0106     Translator const& m_tr;
0107 };
0108
0109 template <typename Box, size_t Corner, size_t AxisIndex>
0110 struct choose_split_axis_and_index_for_corner
0111 {
0112     typedef typename index::detail::default_margin_result<Box>::type margin_type;
0113     typedef typename index::detail::default_content_result<Box>::type content_type;
0114
0115     template <typename Elements, typename Parameters, typename Translator>
0116     static inline void apply(Elements const& elements,
0117                              size_t & choosen_index,
0118                              margin_type & sum_of_margins,
0119                              content_type & smallest_overlap,
0120                              content_type & smallest_content,
0121                              Parameters const& parameters,
0122                              Translator const& translator)
0123     {
0124         using element_type = typename Elements::value_type;
0125         using indexable_type = typename rtree::element_indexable_type<element_type, Translator>::type;
0126         using indexable_tag = tag_t<indexable_type>;
0127
0128         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements");
0129
0130         typename index::detail::strategy_type<Parameters>::type const&
0131             strategy = index::detail::get_strategy(parameters);
0132
0133         // copy elements
0134         Elements elements_copy(elements);                                                                       // MAY THROW, STRONG (alloc, copy)
0135
0136         size_t const index_first = parameters.get_min_elements();
0137         size_t const index_last = parameters.get_max_elements() - parameters.get_min_elements() + 2;
0138
0139         // sort elements
0140         element_axis_corner_less
0141             <
0142                 element_type, Parameters, Translator, indexable_tag, Corner, AxisIndex
0143             > elements_less(translator, strategy);
0144         std::sort(elements_copy.begin(), elements_copy.end(), elements_less);                                   // MAY THROW, BASIC (copy)
0145 //        {
0146 //            typename Elements::iterator f = elements_copy.begin() + index_first;
0147 //            typename Elements::iterator l = elements_copy.begin() + index_last;
0148 //            // NOTE: for stdlibc++ shipped with gcc 4.8.2 std::nth_element is replaced with std::sort anyway
0149 //            index::detail::nth_element(elements_copy.begin(), f, elements_copy.end(), elements_less);                // MAY THROW, BASIC (copy)
0150 //            index::detail::nth_element(f, l, elements_copy.end(), elements_less);                                    // MAY THROW, BASIC (copy)
0151 //            std::sort(f, l, elements_less);                                                                   // MAY THROW, BASIC (copy)
0152 //        }
0153
0154         // init outputs
0155         choosen_index = index_first;
0156         sum_of_margins = 0;
0157         smallest_overlap = (std::numeric_limits<content_type>::max)();
0158         smallest_content = (std::numeric_limits<content_type>::max)();
0159
0160         // calculate sum of margins for all distributions
0161         for ( size_t i = index_first ; i < index_last ; ++i )
0162         {
0163             // TODO - awulkiew: may be optimized - box of group 1 may be initialized with
0164             // box of min_elems number of elements and expanded for each iteration by another element
0165
0166             Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i,
0167                                                 translator, strategy);
0168             Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(),
0169                                                 translator, strategy);
0170
0171             sum_of_margins += index::detail::comparable_margin(box1) + index::detail::comparable_margin(box2);
0172
0173             content_type ovl = index::detail::intersection_content(box1, box2, strategy);
0174             content_type con = index::detail::content(box1) + index::detail::content(box2);
0175
0176             // TODO - shouldn't here be < instead of <= ?
0177             if ( ovl < smallest_overlap || (ovl == smallest_overlap && con <= smallest_content) )
0178             {
0179                 choosen_index = i;
0180                 smallest_overlap = ovl;
0181                 smallest_content = con;
0182             }
0183         }
0184
0185         ::boost::ignore_unused(parameters);
0186     }
0187 };
0188
0189 //template <typename Box, size_t AxisIndex, typename ElementIndexableTag>
0190 //struct choose_split_axis_and_index_for_axis
0191 //{
0192 //    BOOST_GEOMETRY_STATIC_ASSERT_FALSE("Not implemented for this Tag type.", ElementIndexableTag);
0193 //};
0194
0195 template <typename Box, size_t AxisIndex, typename ElementIndexableTag>
0196 struct choose_split_axis_and_index_for_axis
0197 {
0198     typedef typename index::detail::default_margin_result<Box>::type margin_type;
0199     typedef typename index::detail::default_content_result<Box>::type content_type;
0200
0201     template <typename Elements, typename Parameters, typename Translator>
0202     static inline void apply(Elements const& elements,
0203                              size_t & choosen_corner,
0204                              size_t & choosen_index,
0205                              margin_type & sum_of_margins,
0206                              content_type & smallest_overlap,
0207                              content_type & smallest_content,
0208                              Parameters const& parameters,
0209                              Translator const& translator)
0210     {
0211         size_t index1 = 0;
0212         margin_type som1 = 0;
0213         content_type ovl1 = (std::numeric_limits<content_type>::max)();
0214         content_type con1 = (std::numeric_limits<content_type>::max)();
0215
0216         choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex>
0217             ::apply(elements, index1,
0218                     som1, ovl1, con1,
0219                     parameters, translator);                                                                // MAY THROW, STRONG
0220
0221         size_t index2 = 0;
0222         margin_type som2 = 0;
0223         content_type ovl2 = (std::numeric_limits<content_type>::max)();
0224         content_type con2 = (std::numeric_limits<content_type>::max)();
0225
0226         choose_split_axis_and_index_for_corner<Box, max_corner, AxisIndex>
0227             ::apply(elements, index2,
0228                     som2, ovl2, con2,
0229                     parameters, translator);                                                                // MAY THROW, STRONG
0230
0231         sum_of_margins = som1 + som2;
0232
0233         if ( ovl1 < ovl2 || (ovl1 == ovl2 && con1 <= con2) )
0234         {
0235             choosen_corner = min_corner;
0236             choosen_index = index1;
0237             smallest_overlap = ovl1;
0238             smallest_content = con1;
0239         }
0240         else
0241         {
0242             choosen_corner = max_corner;
0243             choosen_index = index2;
0244             smallest_overlap = ovl2;
0245             smallest_content = con2;
0246         }
0247     }
0248 };
0249
0250 template <typename Box, size_t AxisIndex>
0251 struct choose_split_axis_and_index_for_axis<Box, AxisIndex, point_tag>
0252 {
0253     typedef typename index::detail::default_margin_result<Box>::type margin_type;
0254     typedef typename index::detail::default_content_result<Box>::type content_type;
0255
0256     template <typename Elements, typename Parameters, typename Translator>
0257     static inline void apply(Elements const& elements,
0258                              size_t & choosen_corner,
0259                              size_t & choosen_index,
0260                              margin_type & sum_of_margins,
0261                              content_type & smallest_overlap,
0262                              content_type & smallest_content,
0263                              Parameters const& parameters,
0264                              Translator const& translator)
0265     {
0266         choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex>
0267             ::apply(elements, choosen_index,
0268                     sum_of_margins, smallest_overlap, smallest_content,
0269                     parameters, translator);                                                                // MAY THROW, STRONG
0270
0271         choosen_corner = min_corner;
0272     }
0273 };
0274
0275 template <typename Box, size_t Dimension>
0276 struct choose_split_axis_and_index
0277 {
0278     BOOST_STATIC_ASSERT(0 < Dimension);
0279
0280     typedef typename index::detail::default_margin_result<Box>::type margin_type;
0281     typedef typename index::detail::default_content_result<Box>::type content_type;
0282
0283     template <typename Elements, typename Parameters, typename Translator>
0284     static inline void apply(Elements const& elements,
0285                              size_t & choosen_axis,
0286                              size_t & choosen_corner,
0287                              size_t & choosen_index,
0288                              margin_type & smallest_sum_of_margins,
0289                              content_type & smallest_overlap,
0290                              content_type & smallest_content,
0291                              Parameters const& parameters,
0292                              Translator const& translator)
0293     {
0294         typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
0295
0296         choose_split_axis_and_index<Box, Dimension - 1>
0297             ::apply(elements, choosen_axis, choosen_corner, choosen_index,
0298                     smallest_sum_of_margins, smallest_overlap, smallest_content,
0299                     parameters, translator);                                                                // MAY THROW, STRONG
0300
0301         margin_type sum_of_margins = 0;
0302
0303         size_t corner = min_corner;
0304         size_t index = 0;
0305
0306         content_type overlap_val = (std::numeric_limits<content_type>::max)();
0307         content_type content_val = (std::numeric_limits<content_type>::max)();
0308
0309         choose_split_axis_and_index_for_axis
0310             <
0311                 Box,
0312                 Dimension - 1,
0313                 tag_t<element_indexable_type>
0314             >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val,
0315                      parameters, translator); // MAY THROW, STRONG
0316
0317         if (sum_of_margins < smallest_sum_of_margins)
0318         {
0319             choosen_axis = Dimension - 1;
0320             choosen_corner = corner;
0321             choosen_index = index;
0322             smallest_sum_of_margins = sum_of_margins;
0323             smallest_overlap = overlap_val;
0324             smallest_content = content_val;
0325         }
0326     }
0327 };
0328
0329 template <typename Box>
0330 struct choose_split_axis_and_index<Box, 1>
0331 {
0332     typedef typename index::detail::default_margin_result<Box>::type margin_type;
0333     typedef typename index::detail::default_content_result<Box>::type content_type;
0334
0335     template <typename Elements, typename Parameters, typename Translator>
0336     static inline void apply(Elements const& elements,
0337                              size_t & choosen_axis,
0338                              size_t & choosen_corner,
0339                              size_t & choosen_index,
0340                              margin_type & smallest_sum_of_margins,
0341                              content_type & smallest_overlap,
0342                              content_type & smallest_content,
0343                              Parameters const& parameters,
0344                              Translator const& translator)
0345     {
0346         using element_indexable_type = typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type;
0347
0348         choosen_axis = 0;
0349
0350         choose_split_axis_and_index_for_axis
0351             <
0352                 Box,
0353                 0,
0354                 tag_t<element_indexable_type>
0355             >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins,
0356                      smallest_overlap, smallest_content, parameters, translator); // MAY THROW
0357     }
0358 };
0359
0360 template <size_t Corner, size_t Dimension, size_t I = 0>
0361 struct nth_element
0362 {
0363     BOOST_STATIC_ASSERT(0 < Dimension);
0364     BOOST_STATIC_ASSERT(I < Dimension);
0365
0366     template <typename Elements, typename Parameters, typename Translator>
0367     static inline void apply(Elements & elements, Parameters const& parameters,
0368                              const size_t axis, const size_t index, Translator const& tr)
0369     {
0370         //BOOST_GEOMETRY_INDEX_ASSERT(axis < Dimension, "unexpected axis value");
0371
0372         if ( axis != I )
0373         {
0374             nth_element<Corner, Dimension, I + 1>::apply(elements, parameters, axis, index, tr);                     // MAY THROW, BASIC (copy)
0375         }
0376         else
0377         {
0378             using element_type = typename Elements::value_type;
0379             using indexable_type = typename rtree::element_indexable_type<element_type, Translator>::type;
0380             using indexable_tag = tag_t<indexable_type>;
0381
0382             typename index::detail::strategy_type<Parameters>::type
0383                 strategy = index::detail::get_strategy(parameters);
0384
0385             element_axis_corner_less
0386                 <
0387                     element_type, Parameters, Translator, indexable_tag, Corner, I
0388                 > less(tr, strategy);
0389             index::detail::nth_element(elements.begin(), elements.begin() + index, elements.end(), less);            // MAY THROW, BASIC (copy)
0390         }
0391     }
0392 };
0393
0394 template <size_t Corner, size_t Dimension>
0395 struct nth_element<Corner, Dimension, Dimension>
0396 {
0397     template <typename Elements, typename Parameters, typename Translator>
0398     static inline void apply(Elements & /*elements*/, Parameters const& /*parameters*/,
0399                              const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/)
0400     {}
0401 };
0402
0403 } // namespace rstar
0404
0405 template <typename MembersHolder>
0406 struct redistribute_elements<MembersHolder, rstar_tag>
0407 {
0408     typedef typename MembersHolder::box_type box_type;
0409     typedef typename MembersHolder::parameters_type parameters_type;
0410     typedef typename MembersHolder::translator_type translator_type;
0411     typedef typename MembersHolder::allocators_type allocators_type;
0412
0413     typedef typename MembersHolder::node node;
0414     typedef typename MembersHolder::internal_node internal_node;
0415     typedef typename MembersHolder::leaf leaf;
0416
0417     static const size_t dimension = geometry::dimension<box_type>::value;
0418
0419     typedef typename index::detail::default_margin_result<box_type>::type margin_type;
0420     typedef typename index::detail::default_content_result<box_type>::type content_type;
0421
0422     template <typename Node>
0423     static inline void apply(
0424         Node & n,
0425         Node & second_node,
0426         box_type & box1,
0427         box_type & box2,
0428         parameters_type const& parameters,
0429         translator_type const& translator,
0430         allocators_type & allocators)
0431     {
0432         typedef typename rtree::elements_type<Node>::type elements_type;
0433         typedef typename elements_type::value_type element_type;
0434
0435         elements_type & elements1 = rtree::elements(n);
0436         elements_type & elements2 = rtree::elements(second_node);
0437
0438         // copy original elements - use in-memory storage (std::allocator)
0439         // TODO: move if noexcept
0440         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
0441             container_type;
0442         container_type elements_copy(elements1.begin(), elements1.end());                               // MAY THROW, STRONG
0443         container_type elements_backup(elements1.begin(), elements1.end());                             // MAY THROW, STRONG
0444
0445         size_t split_axis = 0;
0446         size_t split_corner = 0;
0447         size_t split_index = parameters.get_min_elements();
0448         margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)();
0449         content_type smallest_overlap = (std::numeric_limits<content_type>::max)();
0450         content_type smallest_content = (std::numeric_limits<content_type>::max)();
0451
0452         // NOTE: this function internally copies passed elements
0453         //       why not pass mutable elements and use the same container for all axes/corners
0454         //       and again, the same below calling partial_sort/nth_element
0455         //       It would be even possible to not re-sort/find nth_element if the axis/corner
0456         //       was found for the last sorting - last combination of axis/corner
0457         rstar::choose_split_axis_and_index<box_type, dimension>
0458             ::apply(elements_copy,
0459                     split_axis, split_corner, split_index,
0460                     smallest_sum_of_margins, smallest_overlap, smallest_content,
0461                     parameters, translator);                                                            // MAY THROW, STRONG
0462
0463         // TODO: awulkiew - get rid of following static_casts?
0464         BOOST_GEOMETRY_INDEX_ASSERT(split_axis < dimension, "unexpected value");
0465         BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value");
0466         BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value");
0467
0468         // TODO: consider using nth_element
0469         if ( split_corner == static_cast<size_t>(min_corner) )
0470         {
0471             rstar::nth_element<min_corner, dimension>
0472                 ::apply(elements_copy, parameters, split_axis, split_index, translator);                // MAY THROW, BASIC (copy)
0473         }
0474         else
0475         {
0476             rstar::nth_element<max_corner, dimension>
0477                 ::apply(elements_copy, parameters, split_axis, split_index, translator);                // MAY THROW, BASIC (copy)
0478         }
0479
0480         BOOST_TRY
0481         {
0482             typename index::detail::strategy_type<parameters_type>::type const&
0483                 strategy = index::detail::get_strategy(parameters);
0484
0485             // copy elements to nodes
0486             elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index);               // MAY THROW, BASIC
0487             elements2.assign(elements_copy.begin() + split_index, elements_copy.end());                 // MAY THROW, BASIC
0488
0489             // calculate boxes
0490             box1 = rtree::elements_box<box_type>(elements1.begin(), elements1.end(),
0491                                                  translator, strategy);
0492             box2 = rtree::elements_box<box_type>(elements2.begin(), elements2.end(),
0493                                                  translator, strategy);
0494         }
0495         BOOST_CATCH(...)
0496         {
0497             //elements_copy.clear();
0498             elements1.clear();
0499             elements2.clear();
0500
0501             rtree::destroy_elements<MembersHolder>::apply(elements_backup, allocators);
0502             //elements_backup.clear();
0503
0504             BOOST_RETHROW                                                                                 // RETHROW, BASIC
0505         }
0506         BOOST_CATCH_END
0507     }
0508 };
0509
0510 }} // namespace detail::rtree
0511
0512 }}} // namespace boost::geometry::index
0513
0514 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP