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