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         typedef typename Elements::value_type element_type;
0125         typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0126         typedef typename tag<indexable_type>::type indexable_tag;
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             Box,
0311             Dimension - 1,
0312             typename tag<element_indexable_type>::type
0313         >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW, STRONG
0314
0315         if ( sum_of_margins < smallest_sum_of_margins )
0316         {
0317             choosen_axis = Dimension - 1;
0318             choosen_corner = corner;
0319             choosen_index = index;
0320             smallest_sum_of_margins = sum_of_margins;
0321             smallest_overlap = overlap_val;
0322             smallest_content = content_val;
0323         }
0324     }
0325 };
0326
0327 template <typename Box>
0328 struct choose_split_axis_and_index<Box, 1>
0329 {
0330     typedef typename index::detail::default_margin_result<Box>::type margin_type;
0331     typedef typename index::detail::default_content_result<Box>::type content_type;
0332
0333     template <typename Elements, typename Parameters, typename Translator>
0334     static inline void apply(Elements const& elements,
0335                              size_t & choosen_axis,
0336                              size_t & choosen_corner,
0337                              size_t & choosen_index,
0338                              margin_type & smallest_sum_of_margins,
0339                              content_type & smallest_overlap,
0340                              content_type & smallest_content,
0341                              Parameters const& parameters,
0342                              Translator const& translator)
0343     {
0344         typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
0345
0346         choosen_axis = 0;
0347
0348         choose_split_axis_and_index_for_axis<
0349             Box,
0350             0,
0351             typename tag<element_indexable_type>::type
0352         >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_content, parameters, translator); // MAY THROW
0353     }
0354 };
0355
0356 template <size_t Corner, size_t Dimension, size_t I = 0>
0357 struct nth_element
0358 {
0359     BOOST_STATIC_ASSERT(0 < Dimension);
0360     BOOST_STATIC_ASSERT(I < Dimension);
0361
0362     template <typename Elements, typename Parameters, typename Translator>
0363     static inline void apply(Elements & elements, Parameters const& parameters,
0364                              const size_t axis, const size_t index, Translator const& tr)
0365     {
0366         //BOOST_GEOMETRY_INDEX_ASSERT(axis < Dimension, "unexpected axis value");
0367
0368         if ( axis != I )
0369         {
0370             nth_element<Corner, Dimension, I + 1>::apply(elements, parameters, axis, index, tr);                     // MAY THROW, BASIC (copy)
0371         }
0372         else
0373         {
0374             typedef typename Elements::value_type element_type;
0375             typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0376             typedef typename tag<indexable_type>::type indexable_tag;
0377
0378             typename index::detail::strategy_type<Parameters>::type
0379                 strategy = index::detail::get_strategy(parameters);
0380
0381             element_axis_corner_less
0382                 <
0383                     element_type, Parameters, Translator, indexable_tag, Corner, I
0384                 > less(tr, strategy);
0385             index::detail::nth_element(elements.begin(), elements.begin() + index, elements.end(), less);            // MAY THROW, BASIC (copy)
0386         }
0387     }
0388 };
0389
0390 template <size_t Corner, size_t Dimension>
0391 struct nth_element<Corner, Dimension, Dimension>
0392 {
0393     template <typename Elements, typename Parameters, typename Translator>
0394     static inline void apply(Elements & /*elements*/, Parameters const& /*parameters*/,
0395                              const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/)
0396     {}
0397 };
0398
0399 } // namespace rstar
0400
0401 template <typename MembersHolder>
0402 struct redistribute_elements<MembersHolder, rstar_tag>
0403 {
0404     typedef typename MembersHolder::box_type box_type;
0405     typedef typename MembersHolder::parameters_type parameters_type;
0406     typedef typename MembersHolder::translator_type translator_type;
0407     typedef typename MembersHolder::allocators_type allocators_type;
0408
0409     typedef typename MembersHolder::node node;
0410     typedef typename MembersHolder::internal_node internal_node;
0411     typedef typename MembersHolder::leaf leaf;
0412
0413     static const size_t dimension = geometry::dimension<box_type>::value;
0414
0415     typedef typename index::detail::default_margin_result<box_type>::type margin_type;
0416     typedef typename index::detail::default_content_result<box_type>::type content_type;
0417
0418     template <typename Node>
0419     static inline void apply(
0420         Node & n,
0421         Node & second_node,
0422         box_type & box1,
0423         box_type & box2,
0424         parameters_type const& parameters,
0425         translator_type const& translator,
0426         allocators_type & allocators)
0427     {
0428         typedef typename rtree::elements_type<Node>::type elements_type;
0429         typedef typename elements_type::value_type element_type;
0430
0431         elements_type & elements1 = rtree::elements(n);
0432         elements_type & elements2 = rtree::elements(second_node);
0433
0434         // copy original elements - use in-memory storage (std::allocator)
0435         // TODO: move if noexcept
0436         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
0437             container_type;
0438         container_type elements_copy(elements1.begin(), elements1.end());                               // MAY THROW, STRONG
0439         container_type elements_backup(elements1.begin(), elements1.end());                             // MAY THROW, STRONG
0440
0441         size_t split_axis = 0;
0442         size_t split_corner = 0;
0443         size_t split_index = parameters.get_min_elements();
0444         margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)();
0445         content_type smallest_overlap = (std::numeric_limits<content_type>::max)();
0446         content_type smallest_content = (std::numeric_limits<content_type>::max)();
0447
0448         // NOTE: this function internally copies passed elements
0449         //       why not pass mutable elements and use the same container for all axes/corners
0450         //       and again, the same below calling partial_sort/nth_element
0451         //       It would be even possible to not re-sort/find nth_element if the axis/corner
0452         //       was found for the last sorting - last combination of axis/corner
0453         rstar::choose_split_axis_and_index<box_type, dimension>
0454             ::apply(elements_copy,
0455                     split_axis, split_corner, split_index,
0456                     smallest_sum_of_margins, smallest_overlap, smallest_content,
0457                     parameters, translator);                                                            // MAY THROW, STRONG
0458
0459         // TODO: awulkiew - get rid of following static_casts?
0460         BOOST_GEOMETRY_INDEX_ASSERT(split_axis < dimension, "unexpected value");
0461         BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value");
0462         BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value");
0463
0464         // TODO: consider using nth_element
0465         if ( split_corner == static_cast<size_t>(min_corner) )
0466         {
0467             rstar::nth_element<min_corner, dimension>
0468                 ::apply(elements_copy, parameters, split_axis, split_index, translator);                // MAY THROW, BASIC (copy)
0469         }
0470         else
0471         {
0472             rstar::nth_element<max_corner, dimension>
0473                 ::apply(elements_copy, parameters, split_axis, split_index, translator);                // MAY THROW, BASIC (copy)
0474         }
0475
0476         BOOST_TRY
0477         {
0478             typename index::detail::strategy_type<parameters_type>::type const&
0479                 strategy = index::detail::get_strategy(parameters);
0480
0481             // copy elements to nodes
0482             elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index);               // MAY THROW, BASIC
0483             elements2.assign(elements_copy.begin() + split_index, elements_copy.end());                 // MAY THROW, BASIC
0484
0485             // calculate boxes
0486             box1 = rtree::elements_box<box_type>(elements1.begin(), elements1.end(),
0487                                                  translator, strategy);
0488             box2 = rtree::elements_box<box_type>(elements2.begin(), elements2.end(),
0489                                                  translator, strategy);
0490         }
0491         BOOST_CATCH(...)
0492         {
0493             //elements_copy.clear();
0494             elements1.clear();
0495             elements2.clear();
0496
0497             rtree::destroy_elements<MembersHolder>::apply(elements_backup, allocators);
0498             //elements_backup.clear();
0499
0500             BOOST_RETHROW                                                                                 // RETHROW, BASIC
0501         }
0502         BOOST_CATCH_END
0503     }
0504 };
0505
0506 }} // namespace detail::rtree
0507
0508 }}} // namespace boost::geometry::index
0509
0510 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP