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

   1 // Boost.Geometry Index
   2 //
   3 // R-tree R*-tree next node choosing algorithm implementation
   4 //
   5 // Copyright (c) 2011-2019 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_CHOOSE_NEXT_NODE_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP
  17
  18 #include <algorithm>
  19
  20 #include <boost/core/ignore_unused.hpp>
  21
  22 #include <boost/geometry/algorithms/expand.hpp>
  23
  24 #include <boost/geometry/index/detail/algorithms/content.hpp>
  25 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp>
  26 #include <boost/geometry/index/detail/algorithms/nth_element.hpp>
  27 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
  28
  29 #include <boost/geometry/index/detail/rtree/node/node.hpp>
  30 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
  31
  32 namespace boost { namespace geometry { namespace index {
  33
  34 namespace detail { namespace rtree {
  35
  36 template <typename Value, typename Options, typename Box, typename Allocators>
  37 class choose_next_node<Value, Options, Box, Allocators, choose_by_overlap_diff_tag>
  38 {
  39     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
  40     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
  41     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
  42
  43     typedef typename rtree::elements_type<internal_node>::type children_type;
  44     typedef typename children_type::value_type child_type;
  45
  46     typedef typename Options::parameters_type parameters_type;
  47
  48     typedef typename index::detail::default_content_result<Box>::type content_type;
  49
  50 public:
  51     template <typename Indexable>
  52     static inline size_t apply(internal_node & n,
  53                                Indexable const& indexable,
  54                                parameters_type const& parameters,
  55                                size_t node_relative_level)
  56     {
  57         ::boost::ignore_unused(parameters);
  58
  59         children_type & children = rtree::elements(n);
  60
  61         // children are leafs
  62         if ( node_relative_level <= 1 )
  63         {
  64             return choose_by_minimum_overlap_cost(children, indexable,
  65                                                   parameters.get_overlap_cost_threshold(),
  66                                                   index::detail::get_strategy(parameters));
  67         }
  68         // children are internal nodes
  69         else
  70         {
  71             return choose_by_minimum_content_cost(children, indexable,
  72                                                   index::detail::get_strategy(parameters));
  73         }
  74     }
  75
  76 private:
  77     struct child_contents
  78     {
  79         content_type content_diff;
  80         content_type content;
  81         size_t i;
  82
  83         void set(size_t i_, content_type const& content_, content_type const& content_diff_)
  84         {
  85             i = i_;
  86             content = content_;
  87             content_diff = content_diff_;
  88         }
  89     };
  90
  91     template <typename Indexable, typename Strategy>
  92     static inline size_t choose_by_minimum_overlap_cost(children_type const& children,
  93                                                         Indexable const& indexable,
  94                                                         size_t overlap_cost_threshold,
  95                                                         Strategy const& strategy)
  96     {
  97         const size_t children_count = children.size();
  98
  99         content_type min_content_diff = (std::numeric_limits<content_type>::max)();
 100         content_type min_content = (std::numeric_limits<content_type>::max)();
 101         size_t choosen_index = 0;
 102
 103         // create container of children sorted by content enlargement needed to include the new value
 104         typename rtree::container_from_elements_type<children_type, child_contents>::type
 105             children_contents(children_count);
 106
 107         for ( size_t i = 0 ; i < children_count ; ++i )
 108         {
 109             child_type const& ch_i = children[i];
 110
 111             // expanded child node's box
 112             Box box_exp(ch_i.first);
 113             index::detail::expand(box_exp, indexable, strategy);
 114
 115             // areas difference
 116             content_type content = index::detail::content(box_exp);
 117             content_type content_diff = content - index::detail::content(ch_i.first);
 118
 119             children_contents[i].set(i, content, content_diff);
 120
 121             if ( content_diff < min_content_diff ||
 122                  (content_diff == min_content_diff && content < min_content) )
 123             {
 124                 min_content_diff = content_diff;
 125                 min_content = content;
 126                 choosen_index = i;
 127             }
 128         }
 129
 130         // is this assumption ok? if min_content_diff == 0 there is no overlap increase?
 131
 132         if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff )
 133         {
 134             size_t first_n_children_count = children_count;
 135             if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() )
 136             {
 137                 first_n_children_count = overlap_cost_threshold;
 138                 // rearrange by content_diff
 139                 // in order to calculate nearly minimum overlap cost
 140                 index::detail::nth_element(children_contents.begin(), children_contents.begin() + first_n_children_count, children_contents.end(), content_diff_less);
 141             }
 142
 143             // calculate minimum or nearly minimum overlap cost
 144             choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable,
 145                                                                    first_n_children_count,
 146                                                                    children_count,
 147                                                                    children_contents,
 148                                                                    strategy);
 149         }
 150
 151         return choosen_index;
 152     }
 153
 154     static inline bool content_diff_less(child_contents const& p1, child_contents const& p2)
 155     {
 156         return p1.content_diff < p2.content_diff
 157             || (p1.content_diff == p2.content_diff && (p1.content) < (p2.content));
 158     }
 159
 160     template <typename Indexable, typename ChildrenContents, typename Strategy>
 161     static inline size_t choose_by_minimum_overlap_cost_first_n(children_type const& children,
 162                                                                 Indexable const& indexable,
 163                                                                 size_t const first_n_children_count,
 164                                                                 size_t const children_count,
 165                                                                 ChildrenContents const& children_contents,
 166                                                                 Strategy const& strategy)
 167     {
 168         BOOST_GEOMETRY_INDEX_ASSERT(first_n_children_count <= children_count, "unexpected value");
 169         BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements");
 170
 171         // choose index with smallest overlap change value, or content change or smallest content
 172         size_t choosen_index = 0;
 173         content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)();
 174         content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
 175         content_type smallest_content = (std::numeric_limits<content_type>::max)();
 176
 177         // for each child node
 178         for (size_t first_i = 0 ; first_i < first_n_children_count ; ++first_i)
 179         {
 180             size_t i = children_contents[first_i].i;
 181             content_type const& content = children_contents[first_i].content;
 182             content_type const& content_diff = children_contents[first_i].content_diff;
 183
 184             child_type const& ch_i = children[i];
 185
 186             Box box_exp(ch_i.first);
 187             // calculate expanded box of child node ch_i
 188             index::detail::expand(box_exp, indexable, strategy);
 189
 190             content_type overlap_diff = 0;
 191
 192             // calculate overlap
 193             for ( size_t j = 0 ; j < children_count ; ++j )
 194             {
 195                 if ( i != j )
 196                 {
 197                     child_type const& ch_j = children[j];
 198
 199                     content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first, strategy);
 200                     if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp )
 201                     {
 202                         overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first, strategy);
 203                     }
 204                 }
 205             }
 206
 207             // update result
 208             if ( overlap_diff < smallest_overlap_diff ||
 209                 ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
 210                 ( content_diff == smallest_content_diff && content < smallest_content ) )
 211                 ) )
 212             {
 213                 smallest_overlap_diff = overlap_diff;
 214                 smallest_content_diff = content_diff;
 215                 smallest_content = content;
 216                 choosen_index = i;
 217             }
 218         }
 219
 220         return choosen_index;
 221     }
 222
 223     template <typename Indexable, typename Strategy>
 224     static inline size_t choose_by_minimum_content_cost(children_type const& children,
 225                                                         Indexable const& indexable,
 226                                                         Strategy const& strategy)
 227     {
 228         size_t children_count = children.size();
 229
 230         // choose index with smallest content change or smallest content
 231         size_t choosen_index = 0;
 232         content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
 233         content_type smallest_content = (std::numeric_limits<content_type>::max)();
 234
 235         // choose the child which requires smallest box expansion to store the indexable
 236         for ( size_t i = 0 ; i < children_count ; ++i )
 237         {
 238             child_type const& ch_i = children[i];
 239
 240             // expanded child node's box
 241             Box box_exp(ch_i.first);
 242             index::detail::expand(box_exp, indexable, strategy);
 243
 244             // areas difference
 245             content_type content = index::detail::content(box_exp);
 246             content_type content_diff = content - index::detail::content(ch_i.first);
 247
 248             // update the result
 249             if ( content_diff < smallest_content_diff ||
 250                 ( content_diff == smallest_content_diff && content < smallest_content ) )
 251             {
 252                 smallest_content_diff = content_diff;
 253                 smallest_content = content;
 254                 choosen_index = i;
 255             }
 256         }
 257
 258         return choosen_index;
 259     }
 260 };
 261
 262 }} // namespace detail::rtree
 263
 264 }}} // namespace boost::geometry::index
 265
 266 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP