rtree/quadratic/redistribute_elements.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree quadratic split algorithm implementation
0004 //
0005 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019.
0008 // Modifications copyright (c) 2019 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_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
0017
0018 #include <algorithm>
0019
0020 #include <boost/core/ignore_unused.hpp>
0021
0022 #include <boost/geometry/index/detail/algorithms/content.hpp>
0023 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
0024
0025 #include <boost/geometry/index/detail/bounded_view.hpp>
0026
0027 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0028 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
0029 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
0030
0031 namespace boost { namespace geometry { namespace index {
0032
0033 namespace detail { namespace rtree {
0034
0035 namespace quadratic {
0036
0037 template <typename Box, typename Elements, typename Parameters, typename Translator>
0038 inline void pick_seeds(Elements const& elements,
0039                        Parameters const& parameters,
0040                        Translator const& tr,
0041                        size_t & seed1,
0042                        size_t & seed2)
0043 {
0044     typedef typename Elements::value_type element_type;
0045     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0046     typedef Box box_type;
0047     typedef typename index::detail::default_content_result<box_type>::type content_type;
0048     typedef typename index::detail::strategy_type<Parameters>::type strategy_type;
0049     typedef index::detail::bounded_view
0050         <
0051             indexable_type, box_type, strategy_type
0052         > bounded_indexable_view;
0053
0054     const size_t elements_count = parameters.get_max_elements() + 1;
0055     BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
0056     BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
0057
0058     strategy_type const& strategy = index::detail::get_strategy(parameters);
0059
0060     content_type greatest_free_content = 0;
0061     seed1 = 0;
0062     seed2 = 1;
0063
0064     for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
0065     {
0066         for ( size_t j = i + 1 ; j < elements_count ; ++j )
0067         {
0068             indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
0069             indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
0070
0071             box_type enlarged_box;
0072             index::detail::bounds(ind1, enlarged_box, strategy);
0073             index::detail::expand(enlarged_box, ind2, strategy);
0074
0075             bounded_indexable_view bounded_ind1(ind1, strategy);
0076             bounded_indexable_view bounded_ind2(ind2, strategy);
0077             content_type free_content = ( index::detail::content(enlarged_box)
0078                                             - index::detail::content(bounded_ind1) )
0079                                                 - index::detail::content(bounded_ind2);
0080
0081             if ( greatest_free_content < free_content )
0082             {
0083                 greatest_free_content = free_content;
0084                 seed1 = i;
0085                 seed2 = j;
0086             }
0087         }
0088     }
0089
0090     ::boost::ignore_unused(parameters);
0091 }
0092
0093 } // namespace quadratic
0094
0095 template <typename MembersHolder>
0096 struct redistribute_elements<MembersHolder, quadratic_tag>
0097 {
0098     typedef typename MembersHolder::box_type box_type;
0099     typedef typename MembersHolder::parameters_type parameters_type;
0100     typedef typename MembersHolder::translator_type translator_type;
0101     typedef typename MembersHolder::allocators_type allocators_type;
0102
0103     typedef typename MembersHolder::node node;
0104     typedef typename MembersHolder::internal_node internal_node;
0105     typedef typename MembersHolder::leaf leaf;
0106
0107     typedef typename index::detail::default_content_result<box_type>::type content_type;
0108
0109     template <typename Node>
0110     static inline void apply(Node & n,
0111                              Node & second_node,
0112                              box_type & box1,
0113                              box_type & box2,
0114                              parameters_type const& parameters,
0115                              translator_type const& translator,
0116                              allocators_type & allocators)
0117     {
0118         typedef typename rtree::elements_type<Node>::type elements_type;
0119         typedef typename elements_type::value_type element_type;
0120         typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
0121
0122         elements_type & elements1 = rtree::elements(n);
0123         elements_type & elements2 = rtree::elements(second_node);
0124
0125         BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == parameters.get_max_elements() + 1, "unexpected elements number");
0126
0127         // copy original elements - use in-memory storage (std::allocator)
0128         // TODO: move if noexcept
0129         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
0130             container_type;
0131         container_type elements_copy(elements1.begin(), elements1.end());                                   // MAY THROW, STRONG (alloc, copy)
0132         container_type elements_backup(elements1.begin(), elements1.end());                                 // MAY THROW, STRONG (alloc, copy)
0133
0134         // calculate initial seeds
0135         size_t seed1 = 0;
0136         size_t seed2 = 0;
0137         quadratic::pick_seeds<box_type>(elements_copy, parameters, translator, seed1, seed2);
0138
0139         // prepare nodes' elements containers
0140         elements1.clear();
0141         BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
0142
0143         BOOST_TRY
0144         {
0145             typename index::detail::strategy_type<parameters_type>::type const&
0146                 strategy = index::detail::get_strategy(parameters);
0147
0148             // add seeds
0149             elements1.push_back(elements_copy[seed1]);                                                      // MAY THROW, STRONG (copy)
0150             elements2.push_back(elements_copy[seed2]);                                                      // MAY THROW, STRONG (alloc, copy)
0151
0152             // calculate boxes
0153             detail::bounds(rtree::element_indexable(elements_copy[seed1], translator),
0154                            box1, strategy);
0155             detail::bounds(rtree::element_indexable(elements_copy[seed2], translator),
0156                            box2, strategy);
0157
0158             // remove seeds
0159             if (seed1 < seed2)
0160             {
0161                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed2);                        // MAY THROW, STRONG (copy)
0162                 elements_copy.pop_back();
0163                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed1);                        // MAY THROW, STRONG (copy)
0164                 elements_copy.pop_back();
0165             }
0166             else
0167             {
0168                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed1);                        // MAY THROW, STRONG (copy)
0169                 elements_copy.pop_back();
0170                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed2);                        // MAY THROW, STRONG (copy)
0171                 elements_copy.pop_back();
0172             }
0173
0174             // initialize areas
0175             content_type content1 = index::detail::content(box1);
0176             content_type content2 = index::detail::content(box2);
0177
0178             size_t remaining = elements_copy.size();
0179
0180             // redistribute the rest of the elements
0181             while ( !elements_copy.empty() )
0182             {
0183                 typename container_type::reverse_iterator el_it = elements_copy.rbegin();
0184                 bool insert_into_group1 = false;
0185
0186                 size_t elements1_count = elements1.size();
0187                 size_t elements2_count = elements2.size();
0188
0189                 // if there is small number of elements left and the number of elements in node is lesser than min_elems
0190                 // just insert them to this node
0191                 if ( elements1_count + remaining <= parameters.get_min_elements() )
0192                 {
0193                     insert_into_group1 = true;
0194                 }
0195                 else if ( elements2_count + remaining <= parameters.get_min_elements() )
0196                 {
0197                     insert_into_group1 = false;
0198                 }
0199                 // insert the best element
0200                 else
0201                 {
0202                     // find element with minimum groups areas increses differences
0203                     content_type content_increase1 = 0;
0204                     content_type content_increase2 = 0;
0205                     el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
0206                                       box1, box2, content1, content2,
0207                                       translator, strategy,
0208                                       content_increase1, content_increase2);
0209
0210                     if ( content_increase1 < content_increase2 ||
0211                          ( content_increase1 == content_increase2 && ( content1 < content2 ||
0212                            ( content1 == content2 && elements1_count <= elements2_count ) )
0213                          ) )
0214                     {
0215                         insert_into_group1 = true;
0216                     }
0217                     else
0218                     {
0219                         insert_into_group1 = false;
0220                     }
0221                 }
0222
0223                 // move element to the choosen group
0224                 element_type const& elem = *el_it;
0225                 indexable_type const& indexable = rtree::element_indexable(elem, translator);
0226
0227                 if ( insert_into_group1 )
0228                 {
0229                     elements1.push_back(elem);                                                              // MAY THROW, STRONG (copy)
0230                     index::detail::expand(box1, indexable, strategy);
0231                     content1 = index::detail::content(box1);
0232                 }
0233                 else
0234                 {
0235                     elements2.push_back(elem);                                                              // MAY THROW, STRONG (alloc, copy)
0236                     index::detail::expand(box2, indexable, strategy);
0237                     content2 = index::detail::content(box2);
0238                 }
0239
0240                 BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
0241                 typename container_type::iterator el_it_base = el_it.base();
0242                 rtree::move_from_back(elements_copy, --el_it_base);                                         // MAY THROW, STRONG (copy)
0243                 elements_copy.pop_back();
0244
0245                 BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
0246                 --remaining;
0247             }
0248         }
0249         BOOST_CATCH(...)
0250         {
0251             //elements_copy.clear();
0252             elements1.clear();
0253             elements2.clear();
0254
0255             rtree::destroy_elements<MembersHolder>::apply(elements_backup, allocators);
0256             //elements_backup.clear();
0257
0258             BOOST_RETHROW                                                                                     // RETHROW, BASIC
0259         }
0260         BOOST_CATCH_END
0261     }
0262
0263     // TODO: awulkiew - change following function to static member of the pick_next class?
0264
0265     template <typename It>
0266     static inline It pick_next(It first, It last,
0267                                box_type const& box1, box_type const& box2,
0268                                content_type const& content1, content_type const& content2,
0269                                translator_type const& translator,
0270                                typename index::detail::strategy_type<parameters_type>::type const& strategy,
0271                                content_type & out_content_increase1, content_type & out_content_increase2)
0272     {
0273         typedef typename boost::iterator_value<It>::type element_type;
0274         typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
0275
0276         content_type greatest_content_incrase_diff = 0;
0277         It out_it = first;
0278         out_content_increase1 = 0;
0279         out_content_increase2 = 0;
0280
0281         // find element with greatest difference between increased group's boxes areas
0282         for ( It el_it = first ; el_it != last ; ++el_it )
0283         {
0284             indexable_type const& indexable = rtree::element_indexable(*el_it, translator);
0285
0286             // calculate enlarged boxes and areas
0287             box_type enlarged_box1(box1);
0288             box_type enlarged_box2(box2);
0289             index::detail::expand(enlarged_box1, indexable, strategy);
0290             index::detail::expand(enlarged_box2, indexable, strategy);
0291             content_type enlarged_content1 = index::detail::content(enlarged_box1);
0292             content_type enlarged_content2 = index::detail::content(enlarged_box2);
0293
0294             content_type content_incrase1 = (enlarged_content1 - content1);
0295             content_type content_incrase2 = (enlarged_content2 - content2);
0296
0297             content_type content_incrase_diff = content_incrase1 < content_incrase2 ?
0298                 content_incrase2 - content_incrase1 : content_incrase1 - content_incrase2;
0299
0300             if ( greatest_content_incrase_diff < content_incrase_diff )
0301             {
0302                 greatest_content_incrase_diff = content_incrase_diff;
0303                 out_it = el_it;
0304                 out_content_increase1 = content_incrase1;
0305                 out_content_increase2 = content_incrase2;
0306             }
0307         }
0308
0309         return out_it;
0310     }
0311 };
0312
0313 }} // namespace detail::rtree
0314
0315 }}} // namespace boost::geometry::index
0316
0317 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP