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