1 // Boost.Geometry Index
2 //
3 // R-tree quadratic split algorithm implementation
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_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
17
18 #include <algorithm>
19
20 #include <boost/core/ignore_unused.hpp>
21
22 #include <boost/geometry/index/detail/algorithms/content.hpp>
23 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
24
25 #include <boost/geometry/index/detail/bounded_view.hpp>
26
27 #include <boost/geometry/index/detail/rtree/node/node.hpp>
28 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
29 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
30
31 namespace boost { namespace geometry { namespace index {
32
33 namespace detail { namespace rtree {
34
35 namespace quadratic {
36
37 template <typename Box, typename Elements, typename Parameters, typename Translator>
pick_seeds(Elements const & elements,Parameters const & parameters,Translator const & tr,size_t & seed1,size_t & seed2)38 inline void pick_seeds(Elements const& elements,
39 Parameters const& parameters,
40 Translator const& tr,
41 size_t & seed1,
42 size_t & seed2)
43 {
44 typedef typename Elements::value_type element_type;
45 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
46 typedef Box box_type;
47 typedef typename index::detail::default_content_result<box_type>::type content_type;
48 typedef typename index::detail::strategy_type<Parameters>::type strategy_type;
49 typedef index::detail::bounded_view
50 <
51 indexable_type, box_type, strategy_type
52 > bounded_indexable_view;
53
54 const size_t elements_count = parameters.get_max_elements() + 1;
55 BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
56 BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
57
58 strategy_type const& strategy = index::detail::get_strategy(parameters);
59
60 content_type greatest_free_content = 0;
61 seed1 = 0;
62 seed2 = 1;
63
64 for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
65 {
66 for ( size_t j = i + 1 ; j < elements_count ; ++j )
67 {
68 indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
69 indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
70
71 box_type enlarged_box;
72 index::detail::bounds(ind1, enlarged_box, strategy);
73 index::detail::expand(enlarged_box, ind2, strategy);
74
75 bounded_indexable_view bounded_ind1(ind1, strategy);
76 bounded_indexable_view bounded_ind2(ind2, strategy);
77 content_type free_content = ( index::detail::content(enlarged_box)
78 - index::detail::content(bounded_ind1) )
79 - index::detail::content(bounded_ind2);
80
81 if ( greatest_free_content < free_content )
82 {
83 greatest_free_content = free_content;
84 seed1 = i;
85 seed2 = j;
86 }
87 }
88 }
89
90 ::boost::ignore_unused(parameters);
91 }
92
93 } // namespace quadratic
94
95 template <typename MembersHolder>
96 struct redistribute_elements<MembersHolder, quadratic_tag>
97 {
98 typedef typename MembersHolder::box_type box_type;
99 typedef typename MembersHolder::parameters_type parameters_type;
100 typedef typename MembersHolder::translator_type translator_type;
101 typedef typename MembersHolder::allocators_type allocators_type;
102
103 typedef typename MembersHolder::node node;
104 typedef typename MembersHolder::internal_node internal_node;
105 typedef typename MembersHolder::leaf leaf;
106
107 typedef typename index::detail::default_content_result<box_type>::type content_type;
108
109 template <typename Node>
applyboost::geometry::index::detail::rtree::redistribute_elements110 static inline void apply(Node & n,
111 Node & second_node,
112 box_type & box1,
113 box_type & box2,
114 parameters_type const& parameters,
115 translator_type const& translator,
116 allocators_type & allocators)
117 {
118 typedef typename rtree::elements_type<Node>::type elements_type;
119 typedef typename elements_type::value_type element_type;
120 typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
121
122 elements_type & elements1 = rtree::elements(n);
123 elements_type & elements2 = rtree::elements(second_node);
124
125 BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == parameters.get_max_elements() + 1, "unexpected elements number");
126
127 // copy original elements - use in-memory storage (std::allocator)
128 // TODO: move if noexcept
129 typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
130 container_type;
131 container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG (alloc, copy)
132 container_type elements_backup(elements1.begin(), elements1.end()); // MAY THROW, STRONG (alloc, copy)
133
134 // calculate initial seeds
135 size_t seed1 = 0;
136 size_t seed2 = 0;
137 quadratic::pick_seeds<box_type>(elements_copy, parameters, translator, seed1, seed2);
138
139 // prepare nodes' elements containers
140 elements1.clear();
141 BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
142
143 BOOST_TRY
144 {
145 typename index::detail::strategy_type<parameters_type>::type const&
146 strategy = index::detail::get_strategy(parameters);
147
148 // add seeds
149 elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
150 elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
151
152 // calculate boxes
153 detail::bounds(rtree::element_indexable(elements_copy[seed1], translator),
154 box1, strategy);
155 detail::bounds(rtree::element_indexable(elements_copy[seed2], translator),
156 box2, strategy);
157
158 // remove seeds
159 if (seed1 < seed2)
160 {
161 rtree::move_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
162 elements_copy.pop_back();
163 rtree::move_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
164 elements_copy.pop_back();
165 }
166 else
167 {
168 rtree::move_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
169 elements_copy.pop_back();
170 rtree::move_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
171 elements_copy.pop_back();
172 }
173
174 // initialize areas
175 content_type content1 = index::detail::content(box1);
176 content_type content2 = index::detail::content(box2);
177
178 size_t remaining = elements_copy.size();
179
180 // redistribute the rest of the elements
181 while ( !elements_copy.empty() )
182 {
183 typename container_type::reverse_iterator el_it = elements_copy.rbegin();
184 bool insert_into_group1 = false;
185
186 size_t elements1_count = elements1.size();
187 size_t elements2_count = elements2.size();
188
189 // if there is small number of elements left and the number of elements in node is lesser than min_elems
190 // just insert them to this node
191 if ( elements1_count + remaining <= parameters.get_min_elements() )
192 {
193 insert_into_group1 = true;
194 }
195 else if ( elements2_count + remaining <= parameters.get_min_elements() )
196 {
197 insert_into_group1 = false;
198 }
199 // insert the best element
200 else
201 {
202 // find element with minimum groups areas increses differences
203 content_type content_increase1 = 0;
204 content_type content_increase2 = 0;
205 el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
206 box1, box2, content1, content2,
207 translator, strategy,
208 content_increase1, content_increase2);
209
210 if ( content_increase1 < content_increase2 ||
211 ( content_increase1 == content_increase2 && ( content1 < content2 ||
212 ( content1 == content2 && elements1_count <= elements2_count ) )
213 ) )
214 {
215 insert_into_group1 = true;
216 }
217 else
218 {
219 insert_into_group1 = false;
220 }
221 }
222
223 // move element to the choosen group
224 element_type const& elem = *el_it;
225 indexable_type const& indexable = rtree::element_indexable(elem, translator);
226
227 if ( insert_into_group1 )
228 {
229 elements1.push_back(elem); // MAY THROW, STRONG (copy)
230 index::detail::expand(box1, indexable, strategy);
231 content1 = index::detail::content(box1);
232 }
233 else
234 {
235 elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
236 index::detail::expand(box2, indexable, strategy);
237 content2 = index::detail::content(box2);
238 }
239
240 BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
241 typename container_type::iterator el_it_base = el_it.base();
242 rtree::move_from_back(elements_copy, --el_it_base); // MAY THROW, STRONG (copy)
243 elements_copy.pop_back();
244
245 BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
246 --remaining;
247 }
248 }
249 BOOST_CATCH(...)
250 {
251 //elements_copy.clear();
252 elements1.clear();
253 elements2.clear();
254
255 rtree::destroy_elements<MembersHolder>::apply(elements_backup, allocators);
256 //elements_backup.clear();
257
258 BOOST_RETHROW // RETHROW, BASIC
259 }
260 BOOST_CATCH_END
261 }
262
263 // TODO: awulkiew - change following function to static member of the pick_next class?
264
265 template <typename It>
pick_nextboost::geometry::index::detail::rtree::redistribute_elements266 static inline It pick_next(It first, It last,
267 box_type const& box1, box_type const& box2,
268 content_type const& content1, content_type const& content2,
269 translator_type const& translator,
270 typename index::detail::strategy_type<parameters_type>::type const& strategy,
271 content_type & out_content_increase1, content_type & out_content_increase2)
272 {
273 typedef typename boost::iterator_value<It>::type element_type;
274 typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
275
276 content_type greatest_content_incrase_diff = 0;
277 It out_it = first;
278 out_content_increase1 = 0;
279 out_content_increase2 = 0;
280
281 // find element with greatest difference between increased group's boxes areas
282 for ( It el_it = first ; el_it != last ; ++el_it )
283 {
284 indexable_type const& indexable = rtree::element_indexable(*el_it, translator);
285
286 // calculate enlarged boxes and areas
287 box_type enlarged_box1(box1);
288 box_type enlarged_box2(box2);
289 index::detail::expand(enlarged_box1, indexable, strategy);
290 index::detail::expand(enlarged_box2, indexable, strategy);
291 content_type enlarged_content1 = index::detail::content(enlarged_box1);
292 content_type enlarged_content2 = index::detail::content(enlarged_box2);
293
294 content_type content_incrase1 = (enlarged_content1 - content1);
295 content_type content_incrase2 = (enlarged_content2 - content2);
296
297 content_type content_incrase_diff = content_incrase1 < content_incrase2 ?
298 content_incrase2 - content_incrase1 : content_incrase1 - content_incrase2;
299
300 if ( greatest_content_incrase_diff < content_incrase_diff )
301 {
302 greatest_content_incrase_diff = content_incrase_diff;
303 out_it = el_it;
304 out_content_increase1 = content_incrase1;
305 out_content_increase2 = content_incrase2;
306 }
307 }
308
309 return out_it;
310 }
311 };
312
313 }} // namespace detail::rtree
314
315 }}} // namespace boost::geometry::index
316
317 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
318