ceph/src/boost/libs/geometry/include/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 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
  13
  14 #include <boost/container/vector.hpp>
  15 #include <boost/geometry/index/detail/varray.hpp>
  16
  17 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
  18 #include <boost/geometry/index/detail/rtree/node/pairs.hpp>
  19 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
  20 #include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp>
  21
  22 //#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
  23 //#include <boost/geometry/index/detail/rtree/node/weak_dynamic.hpp>
  24 //#include <boost/geometry/index/detail/rtree/node/weak_static.hpp>
  25
  26 #include <boost/geometry/index/detail/rtree/node/variant_visitor.hpp>
  27 #include <boost/geometry/index/detail/rtree/node/variant_dynamic.hpp>
  28 #include <boost/geometry/index/detail/rtree/node/variant_static.hpp>
  29
  30 #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
  31
  32 #include <boost/geometry/algorithms/expand.hpp>
  33
  34 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
  35
  36 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
  37 #include <boost/geometry/index/detail/is_bounding_geometry.hpp>
  38
  39 namespace boost { namespace geometry { namespace index {
  40
  41 namespace detail { namespace rtree {
  42
  43 // elements box
  44
  45 template <typename Box, typename FwdIter, typename Translator>
  46 inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr)
  47 {
  48     Box result;
  49
  50     // Only here to suppress 'uninitialized local variable used' warning
  51     // until the suggestion below is not implemented
  52     geometry::assign_inverse(result);
  53
  54     //BOOST_GEOMETRY_INDEX_ASSERT(first != last, "non-empty range required");
  55     // NOTE: this is not elegant temporary solution,
  56     //       reference to box could be passed as parameter and bool returned
  57     if ( first == last )
  58         return result;
  59
  60     detail::bounds(element_indexable(*first, tr), result);
  61     ++first;
  62
  63     for ( ; first != last ; ++first )
  64         geometry::expand(result, element_indexable(*first, tr));
  65
  66     return result;
  67 }
  68
  69 // Enlarge bounds of a leaf node WRT epsilon if needed.
  70 // It's because Points and Segments are compared WRT machine epsilon.
  71 // This ensures that leafs bounds correspond to the stored elements.
  72 // NOTE: this is done only if the Indexable is not a Box
  73 //       in the future don't do it also for NSphere
  74 template <typename Box, typename FwdIter, typename Translator>
  75 inline Box values_box(FwdIter first, FwdIter last, Translator const& tr)
  76 {
  77     typedef typename std::iterator_traits<FwdIter>::value_type element_type;
  78     BOOST_MPL_ASSERT_MSG((is_leaf_element<element_type>::value),
  79                          SHOULD_BE_CALLED_ONLY_FOR_LEAF_ELEMENTS,
  80                          (element_type));
  81
  82     Box result = elements_box<Box>(first, last, tr);
  83
  84 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
  85     if (BOOST_GEOMETRY_CONDITION((
  86         ! is_bounding_geometry
  87             <
  88                 typename indexable_type<Translator>::type
  89             >::value)))
  90     {
  91         geometry::detail::expand_by_epsilon(result);
  92     }
  93 #endif
  94
  95     return result;
  96 }
  97
  98 // destroys subtree if the element is internal node's element
  99 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
 100 struct destroy_element
 101 {
 102     typedef typename Options::parameters_type parameters_type;
 103
 104     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
 105     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
 106
 107     typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
 108
 109     inline static void apply(typename internal_node::elements_type::value_type & element, Allocators & allocators)
 110     {
 111          subtree_destroyer dummy(element.second, allocators);
 112          element.second = 0;
 113     }
 114
 115     inline static void apply(typename leaf::elements_type::value_type &, Allocators &) {}
 116 };
 117
 118 // destroys stored subtrees if internal node's elements are passed
 119 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
 120 struct destroy_elements
 121 {
 122     template <typename Range>
 123     inline static void apply(Range & elements, Allocators & allocators)
 124     {
 125         apply(boost::begin(elements), boost::end(elements), allocators);
 126     }
 127
 128     template <typename It>
 129     inline static void apply(It first, It last, Allocators & allocators)
 130     {
 131         typedef boost::mpl::bool_<
 132             boost::is_same<
 133                 Value, typename std::iterator_traits<It>::value_type
 134             >::value
 135         > is_range_of_values;
 136
 137         apply_dispatch(first, last, allocators, is_range_of_values());
 138     }
 139
 140 private:
 141     template <typename It>
 142     inline static void apply_dispatch(It first, It last, Allocators & allocators,
 143                                       boost::mpl::bool_<false> const& /*is_range_of_values*/)
 144     {
 145         typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
 146
 147         for ( ; first != last ; ++first )
 148         {
 149             subtree_destroyer dummy(first->second, allocators);
 150             first->second = 0;
 151         }
 152     }
 153
 154     template <typename It>
 155     inline static void apply_dispatch(It /*first*/, It /*last*/, Allocators & /*allocators*/,
 156                                       boost::mpl::bool_<true> const& /*is_range_of_values*/)
 157     {}
 158 };
 159
 160 // clears node, deletes all subtrees stored in node
 161 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
 162 struct clear_node
 163 {
 164     typedef typename Options::parameters_type parameters_type;
 165
 166     typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
 167     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
 168     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
 169
 170     inline static void apply(node & node, Allocators & allocators)
 171     {
 172         rtree::visitors::is_leaf<Value, Options, Box, Allocators> ilv;
 173         rtree::apply_visitor(ilv, node);
 174         if ( ilv.result )
 175         {
 176             apply(rtree::get<leaf>(node), allocators);
 177         }
 178         else
 179         {
 180             apply(rtree::get<internal_node>(node), allocators);
 181         }
 182     }
 183
 184     inline static void apply(internal_node & internal_node, Allocators & allocators)
 185     {
 186         destroy_elements<Value, Options, Translator, Box, Allocators>::apply(rtree::elements(internal_node), allocators);
 187         rtree::elements(internal_node).clear();
 188     }
 189
 190     inline static void apply(leaf & leaf, Allocators &)
 191     {
 192         rtree::elements(leaf).clear();
 193     }
 194 };
 195
 196 template <typename Container, typename Iterator>
 197 void move_from_back(Container & container, Iterator it)
 198 {
 199     BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container");
 200     Iterator back_it = container.end();
 201     --back_it;
 202     if ( it != back_it )
 203     {
 204         *it = boost::move(*back_it);                                                             // MAY THROW (copy)
 205     }
 206 }
 207
 208 }} // namespace detail::rtree
 209
 210 }}} // namespace boost::geometry::index
 211
 212 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP