ceph/src/boost/boost/geometry/index/detail/rtree/node/node.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree nodes
   4 //
   5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // This file was modified by Oracle on 2019-2020.
   8 // Modifications copyright (c) 2019-2020 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_NODE_NODE_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
  17
  18 #include <type_traits>
  19
  20 #include <boost/container/vector.hpp>
  21
  22 #include <boost/geometry/core/static_assert.hpp>
  23
  24 #include <boost/geometry/index/detail/varray.hpp>
  25
  26 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
  27 #include <boost/geometry/index/detail/rtree/node/pairs.hpp>
  28 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
  29 #include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp>
  30
  31 //#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
  32 //#include <boost/geometry/index/detail/rtree/node/weak_dynamic.hpp>
  33 //#include <boost/geometry/index/detail/rtree/node/weak_static.hpp>
  34
  35 #include <boost/geometry/index/detail/rtree/node/variant_visitor.hpp>
  36 #include <boost/geometry/index/detail/rtree/node/variant_dynamic.hpp>
  37 #include <boost/geometry/index/detail/rtree/node/variant_static.hpp>
  38
  39 #include <boost/geometry/algorithms/expand.hpp>
  40
  41 #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
  42 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
  43
  44 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
  45 #include <boost/geometry/index/detail/is_bounding_geometry.hpp>
  46
  47 namespace boost { namespace geometry { namespace index {
  48
  49 namespace detail { namespace rtree {
  50
  51 // elements box
  52
  53 template <typename Box, typename FwdIter, typename Translator, typename Strategy>
  54 inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr,
  55                         Strategy const& strategy)
  56 {
  57     Box result;
  58
  59     // Only here to suppress 'uninitialized local variable used' warning
  60     // until the suggestion below is not implemented
  61     geometry::assign_inverse(result);
  62
  63     //BOOST_GEOMETRY_INDEX_ASSERT(first != last, "non-empty range required");
  64     // NOTE: this is not elegant temporary solution,
  65     //       reference to box could be passed as parameter and bool returned
  66     if ( first == last )
  67         return result;
  68
  69     detail::bounds(element_indexable(*first, tr), result, strategy);
  70     ++first;
  71
  72     for ( ; first != last ; ++first )
  73         detail::expand(result, element_indexable(*first, tr), strategy);
  74
  75     return result;
  76 }
  77
  78 // Enlarge bounds of a leaf node WRT epsilon if needed.
  79 // It's because Points and Segments are compared WRT machine epsilon.
  80 // This ensures that leafs bounds correspond to the stored elements.
  81 // NOTE: this is done only if the Indexable is not a Box
  82 //       in the future don't do it also for NSphere
  83 template <typename Box, typename FwdIter, typename Translator, typename Strategy>
  84 inline Box values_box(FwdIter first, FwdIter last, Translator const& tr,
  85                       Strategy const& strategy)
  86 {
  87     typedef typename std::iterator_traits<FwdIter>::value_type element_type;
  88     BOOST_GEOMETRY_STATIC_ASSERT((is_leaf_element<element_type>::value),
  89         "This function should be called only for elements of leaf nodes.",
  90         element_type);
  91
  92     Box result = elements_box<Box>(first, last, tr, strategy);
  93
  94 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
  95     if (BOOST_GEOMETRY_CONDITION((
  96         ! is_bounding_geometry
  97             <
  98                 typename indexable_type<Translator>::type
  99             >::value)))
 100     {
 101         geometry::detail::expand_by_epsilon(result);
 102     }
 103 #endif
 104
 105     return result;
 106 }
 107
 108 // destroys subtree if the element is internal node's element
 109 template <typename MembersHolder>
 110 struct destroy_element
 111 {
 112     typedef typename MembersHolder::parameters_type parameters_type;
 113     typedef typename MembersHolder::allocators_type allocators_type;
 114
 115     typedef typename MembersHolder::internal_node internal_node;
 116     typedef typename MembersHolder::leaf leaf;
 117
 118     inline static void apply(typename internal_node::elements_type::value_type & element,
 119                              allocators_type & allocators)
 120     {
 121          detail::rtree::visitors::destroy<MembersHolder>::apply(element.second, allocators);
 122
 123          element.second = 0;
 124     }
 125
 126     inline static void apply(typename leaf::elements_type::value_type &,
 127                              allocators_type &)
 128     {}
 129 };
 130
 131 // destroys stored subtrees if internal node's elements are passed
 132 template <typename MembersHolder>
 133 struct destroy_elements
 134 {
 135     typedef typename MembersHolder::value_type value_type;
 136     typedef typename MembersHolder::allocators_type allocators_type;
 137
 138     template <typename Range>
 139     inline static void apply(Range & elements, allocators_type & allocators)
 140     {
 141         apply(boost::begin(elements), boost::end(elements), allocators);
 142     }
 143
 144     template <typename It>
 145     inline static void apply(It first, It last, allocators_type & allocators)
 146     {
 147         typedef std::is_same
 148             <
 149                 value_type, typename std::iterator_traits<It>::value_type
 150             > is_range_of_values;
 151
 152         apply_dispatch(first, last, allocators, is_range_of_values());
 153     }
 154
 155 private:
 156     template <typename It>
 157     inline static void apply_dispatch(It first, It last, allocators_type & allocators,
 158                                       std::false_type /*is_range_of_values*/)
 159     {
 160         for ( ; first != last ; ++first )
 161         {
 162             detail::rtree::visitors::destroy<MembersHolder>::apply(first->second, allocators);
 163
 164             first->second = 0;
 165         }
 166     }
 167
 168     template <typename It>
 169     inline static void apply_dispatch(It /*first*/, It /*last*/, allocators_type & /*allocators*/,
 170                                       std::true_type /*is_range_of_values*/)
 171     {}
 172 };
 173
 174 // clears node, deletes all subtrees stored in node
 175 /*
 176 template <typename MembersHolder>
 177 struct clear_node
 178 {
 179     typedef typename MembersHolder::parameters_type parameters_type;
 180     typedef typename MembersHolder::allocators_type allocators_type;
 181
 182     typedef typename MembersHolder::node node;
 183     typedef typename MembersHolder::internal_node internal_node;
 184     typedef typename MembersHolder::leaf leaf;
 185
 186     inline static void apply(node & node, allocators_type & allocators)
 187     {
 188         rtree::visitors::is_leaf<MembersHolder> ilv;
 189         rtree::apply_visitor(ilv, node);
 190         if ( ilv.result )
 191         {
 192             apply(rtree::get<leaf>(node), allocators);
 193         }
 194         else
 195         {
 196             apply(rtree::get<internal_node>(node), allocators);
 197         }
 198     }
 199
 200     inline static void apply(internal_node & internal_node, allocators_type & allocators)
 201     {
 202         destroy_elements<MembersHolder>::apply(rtree::elements(internal_node), allocators);
 203         rtree::elements(internal_node).clear();
 204     }
 205
 206     inline static void apply(leaf & leaf, allocators_type &)
 207     {
 208         rtree::elements(leaf).clear();
 209     }
 210 };
 211 */
 212
 213 template <typename Container, typename Iterator>
 214 void move_from_back(Container & container, Iterator it)
 215 {
 216     BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container");
 217     Iterator back_it = container.end();
 218     --back_it;
 219     if ( it != back_it )
 220     {
 221         *it = boost::move(*back_it);                                                             // MAY THROW (copy)
 222     }
 223 }
 224
 225 }} // namespace detail::rtree
 226
 227 }}} // namespace boost::geometry::index
 228
 229 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP