]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree linear split algorithm implementation | |
4 | // | |
5 | // Copyright (c) 2008 Federico J. Fernandez. | |
6 | // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. | |
7 | // | |
92f5a8d4 TL |
8 | // This file was modified by Oracle on 2019. |
9 | // Modifications copyright (c) 2019 Oracle and/or its affiliates. | |
10 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
11 | // | |
7c673cae FG |
12 | // Use, modification and distribution is subject to the Boost Software License, |
13 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
14 | // http://www.boost.org/LICENSE_1_0.txt) | |
15 | ||
16 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP | |
17 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP | |
18 | ||
92f5a8d4 | 19 | #include <boost/core/ignore_unused.hpp> |
7c673cae FG |
20 | #include <boost/type_traits/is_unsigned.hpp> |
21 | ||
92f5a8d4 | 22 | #include <boost/geometry/index/detail/algorithms/bounds.hpp> |
7c673cae FG |
23 | #include <boost/geometry/index/detail/algorithms/content.hpp> |
24 | #include <boost/geometry/index/detail/bounded_view.hpp> | |
25 | ||
26 | #include <boost/geometry/index/detail/rtree/node/node.hpp> | |
27 | #include <boost/geometry/index/detail/rtree/visitors/insert.hpp> | |
28 | #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> | |
29 | ||
30 | namespace boost { namespace geometry { namespace index { | |
31 | ||
32 | namespace detail { namespace rtree { | |
33 | ||
34 | namespace linear { | |
35 | ||
36 | template <typename R, typename T> | |
37 | inline R difference_dispatch(T const& from, T const& to, ::boost::mpl::bool_<false> const& /*is_unsigned*/) | |
38 | { | |
39 | return to - from; | |
40 | } | |
41 | ||
42 | template <typename R, typename T> | |
43 | inline R difference_dispatch(T const& from, T const& to, ::boost::mpl::bool_<true> const& /*is_unsigned*/) | |
44 | { | |
45 | return from <= to ? R(to - from) : -R(from - to); | |
46 | } | |
47 | ||
48 | template <typename R, typename T> | |
49 | inline R difference(T const& from, T const& to) | |
50 | { | |
51 | BOOST_MPL_ASSERT_MSG(!boost::is_unsigned<R>::value, RESULT_CANT_BE_UNSIGNED, (R)); | |
52 | ||
53 | typedef ::boost::mpl::bool_< | |
54 | boost::is_unsigned<T>::value | |
55 | > is_unsigned; | |
56 | ||
57 | return difference_dispatch<R>(from, to, is_unsigned()); | |
58 | } | |
59 | ||
60 | // TODO: awulkiew | |
61 | // In general, all aerial Indexables in the tree with box-like nodes will be analyzed as boxes | |
62 | // because they must fit into larger box. Therefore the algorithm could be the same for Bounds type. | |
63 | // E.g. if Bounds type is sphere, Indexables probably should be analyzed as spheres. | |
64 | // 1. View could be provided to 'see' all Indexables as Bounds type. | |
65 | // Not ok in the case of big types like Ring, however it's possible that Rings won't be supported, | |
66 | // only simple types. Even then if we consider storing Box inside the Sphere we must calculate | |
67 | // the bounding sphere 2x for each box because there are 2 loops. For each calculation this means | |
68 | // 4-2d or 8-3d expansions or -, / and sqrt(). | |
69 | // 2. Additional container could be used and reused if the Indexable type is other than the Bounds type. | |
70 | ||
71 | // IMPORTANT! | |
72 | // Still probably the best way would be providing specialized algorithms for each Indexable-Bounds pair! | |
73 | // Probably on pick_seeds algorithm level - For Bounds=Sphere seeds would be choosen differently | |
74 | ||
75 | // TODO: awulkiew | |
76 | // there are loops inside find_greatest_normalized_separation::apply() | |
77 | // iteration is done for each DimensionIndex. | |
78 | // Separations and seeds for all DimensionIndex(es) could be calculated at once, stored, then the greatest would be choosen. | |
79 | ||
80 | // The following struct/method was adapted for the preliminary version of the R-tree. Then it was called: | |
81 | // void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const | |
82 | ||
83 | template <typename Elements, typename Parameters, typename Translator, typename Tag, size_t DimensionIndex> | |
84 | struct find_greatest_normalized_separation | |
85 | { | |
86 | typedef typename Elements::value_type element_type; | |
87 | typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; | |
88 | typedef typename coordinate_type<indexable_type>::type coordinate_type; | |
89 | ||
90 | typedef typename boost::mpl::if_c< | |
91 | boost::is_integral<coordinate_type>::value, | |
92 | double, | |
93 | coordinate_type | |
94 | >::type separation_type; | |
95 | ||
96 | typedef typename geometry::point_type<indexable_type>::type point_type; | |
97 | typedef geometry::model::box<point_type> bounds_type; | |
92f5a8d4 TL |
98 | typedef index::detail::bounded_view |
99 | < | |
100 | indexable_type, bounds_type, | |
101 | typename index::detail::strategy_type<Parameters>::type | |
102 | > bounded_view_type; | |
7c673cae FG |
103 | |
104 | static inline void apply(Elements const& elements, | |
105 | Parameters const& parameters, | |
106 | Translator const& translator, | |
107 | separation_type & separation, | |
108 | size_t & seed1, | |
109 | size_t & seed2) | |
110 | { | |
111 | const size_t elements_count = parameters.get_max_elements() + 1; | |
112 | BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements"); | |
113 | BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements"); | |
114 | ||
92f5a8d4 TL |
115 | typename index::detail::strategy_type<Parameters>::type const& |
116 | strategy = index::detail::get_strategy(parameters); | |
117 | ||
7c673cae | 118 | // find the lowest low, highest high |
92f5a8d4 TL |
119 | bounded_view_type bounded_indexable_0(rtree::element_indexable(elements[0], translator), |
120 | strategy); | |
7c673cae FG |
121 | coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_0); |
122 | coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(bounded_indexable_0); | |
123 | ||
124 | // and the lowest high | |
125 | coordinate_type lowest_high = highest_high; | |
126 | size_t lowest_high_index = 0; | |
127 | for ( size_t i = 1 ; i < elements_count ; ++i ) | |
128 | { | |
92f5a8d4 TL |
129 | bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator), |
130 | strategy); | |
7c673cae FG |
131 | coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable); |
132 | coordinate_type max_coord = geometry::get<max_corner, DimensionIndex>(bounded_indexable); | |
133 | ||
134 | if ( max_coord < lowest_high ) | |
135 | { | |
136 | lowest_high = max_coord; | |
137 | lowest_high_index = i; | |
138 | } | |
139 | ||
140 | if ( min_coord < lowest_low ) | |
141 | lowest_low = min_coord; | |
142 | ||
143 | if ( highest_high < max_coord ) | |
144 | highest_high = max_coord; | |
145 | } | |
146 | ||
147 | // find the highest low | |
148 | size_t highest_low_index = lowest_high_index == 0 ? 1 : 0; | |
92f5a8d4 TL |
149 | bounded_view_type bounded_indexable_hl(rtree::element_indexable(elements[highest_low_index], translator), |
150 | strategy); | |
7c673cae FG |
151 | coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_hl); |
152 | for ( size_t i = highest_low_index ; i < elements_count ; ++i ) | |
153 | { | |
92f5a8d4 TL |
154 | bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator), |
155 | strategy); | |
7c673cae FG |
156 | coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable); |
157 | if ( highest_low < min_coord && | |
158 | i != lowest_high_index ) | |
159 | { | |
160 | highest_low = min_coord; | |
161 | highest_low_index = i; | |
162 | } | |
163 | } | |
164 | ||
165 | coordinate_type const width = highest_high - lowest_low; | |
166 | ||
167 | // highest_low - lowest_high | |
168 | separation = difference<separation_type>(lowest_high, highest_low); | |
169 | // BOOST_GEOMETRY_INDEX_ASSERT(0 <= width); | |
170 | if ( std::numeric_limits<coordinate_type>::epsilon() < width ) | |
171 | separation /= width; | |
172 | ||
173 | seed1 = highest_low_index; | |
174 | seed2 = lowest_high_index; | |
175 | ||
92f5a8d4 | 176 | ::boost::ignore_unused(parameters); |
7c673cae FG |
177 | } |
178 | }; | |
179 | ||
180 | // Version for points doesn't calculate normalized separation since it would always be equal to 1 | |
181 | // It returns two seeds most distant to each other, separation is equal to distance | |
182 | template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex> | |
183 | struct find_greatest_normalized_separation<Elements, Parameters, Translator, point_tag, DimensionIndex> | |
184 | { | |
185 | typedef typename Elements::value_type element_type; | |
186 | typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; | |
187 | typedef typename coordinate_type<indexable_type>::type coordinate_type; | |
188 | ||
189 | typedef coordinate_type separation_type; | |
190 | ||
191 | static inline void apply(Elements const& elements, | |
192 | Parameters const& parameters, | |
193 | Translator const& translator, | |
194 | separation_type & separation, | |
195 | size_t & seed1, | |
196 | size_t & seed2) | |
197 | { | |
198 | const size_t elements_count = parameters.get_max_elements() + 1; | |
199 | BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements"); | |
200 | BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements"); | |
201 | ||
202 | // find the lowest low, highest high | |
203 | coordinate_type lowest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator)); | |
204 | coordinate_type highest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator)); | |
205 | size_t lowest_index = 0; | |
206 | size_t highest_index = 0; | |
207 | for ( size_t i = 1 ; i < elements_count ; ++i ) | |
208 | { | |
209 | coordinate_type coord = geometry::get<DimensionIndex>(rtree::element_indexable(elements[i], translator)); | |
210 | ||
211 | if ( coord < lowest ) | |
212 | { | |
213 | lowest = coord; | |
214 | lowest_index = i; | |
215 | } | |
216 | ||
217 | if ( highest < coord ) | |
218 | { | |
219 | highest = coord; | |
220 | highest_index = i; | |
221 | } | |
222 | } | |
223 | ||
224 | separation = highest - lowest; | |
225 | seed1 = lowest_index; | |
226 | seed2 = highest_index; | |
227 | ||
228 | if ( lowest_index == highest_index ) | |
229 | seed2 = (lowest_index + 1) % elements_count; // % is just in case since if this is true lowest_index is 0 | |
230 | ||
92f5a8d4 | 231 | ::boost::ignore_unused(parameters); |
7c673cae FG |
232 | } |
233 | }; | |
234 | ||
235 | template <typename Elements, typename Parameters, typename Translator, size_t Dimension> | |
236 | struct pick_seeds_impl | |
237 | { | |
238 | BOOST_STATIC_ASSERT(0 < Dimension); | |
239 | ||
240 | typedef typename Elements::value_type element_type; | |
241 | typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; | |
242 | ||
243 | typedef find_greatest_normalized_separation< | |
244 | Elements, Parameters, Translator, | |
245 | typename tag<indexable_type>::type, Dimension - 1 | |
246 | > find_norm_sep; | |
247 | ||
248 | typedef typename find_norm_sep::separation_type separation_type; | |
249 | ||
250 | static inline void apply(Elements const& elements, | |
251 | Parameters const& parameters, | |
252 | Translator const& tr, | |
253 | separation_type & separation, | |
254 | size_t & seed1, | |
255 | size_t & seed2) | |
256 | { | |
257 | pick_seeds_impl<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, separation, seed1, seed2); | |
258 | ||
259 | separation_type current_separation; | |
260 | size_t s1, s2; | |
261 | find_norm_sep::apply(elements, parameters, tr, current_separation, s1, s2); | |
262 | ||
263 | // in the old implementation different operator was used: <= (y axis prefered) | |
264 | if ( separation < current_separation ) | |
265 | { | |
266 | separation = current_separation; | |
267 | seed1 = s1; | |
268 | seed2 = s2; | |
269 | } | |
270 | } | |
271 | }; | |
272 | ||
273 | template <typename Elements, typename Parameters, typename Translator> | |
274 | struct pick_seeds_impl<Elements, Parameters, Translator, 1> | |
275 | { | |
276 | typedef typename Elements::value_type element_type; | |
277 | typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; | |
278 | typedef typename coordinate_type<indexable_type>::type coordinate_type; | |
279 | ||
280 | typedef find_greatest_normalized_separation< | |
281 | Elements, Parameters, Translator, | |
282 | typename tag<indexable_type>::type, 0 | |
283 | > find_norm_sep; | |
284 | ||
285 | typedef typename find_norm_sep::separation_type separation_type; | |
286 | ||
287 | static inline void apply(Elements const& elements, | |
288 | Parameters const& parameters, | |
289 | Translator const& tr, | |
290 | separation_type & separation, | |
291 | size_t & seed1, | |
292 | size_t & seed2) | |
293 | { | |
294 | find_norm_sep::apply(elements, parameters, tr, separation, seed1, seed2); | |
295 | } | |
296 | }; | |
297 | ||
298 | // from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const | |
299 | ||
300 | template <typename Elements, typename Parameters, typename Translator> | |
301 | inline void pick_seeds(Elements const& elements, | |
302 | Parameters const& parameters, | |
303 | Translator const& tr, | |
304 | size_t & seed1, | |
305 | size_t & seed2) | |
306 | { | |
307 | typedef typename Elements::value_type element_type; | |
308 | typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; | |
309 | ||
310 | typedef pick_seeds_impl | |
311 | < | |
312 | Elements, Parameters, Translator, | |
313 | geometry::dimension<indexable_type>::value | |
314 | > impl; | |
315 | typedef typename impl::separation_type separation_type; | |
316 | ||
317 | separation_type separation = 0; | |
318 | impl::apply(elements, parameters, tr, separation, seed1, seed2); | |
319 | } | |
320 | ||
321 | } // namespace linear | |
322 | ||
323 | // from void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const | |
324 | ||
325 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
326 | struct redistribute_elements<Value, Options, Translator, Box, Allocators, linear_tag> | |
327 | { | |
328 | typedef typename Options::parameters_type parameters_type; | |
329 | ||
330 | typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
331 | typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
332 | typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
333 | ||
334 | template <typename Node> | |
335 | static inline void apply(Node & n, | |
336 | Node & second_node, | |
337 | Box & box1, | |
338 | Box & box2, | |
339 | parameters_type const& parameters, | |
340 | Translator const& translator, | |
341 | Allocators & allocators) | |
342 | { | |
343 | typedef typename rtree::elements_type<Node>::type elements_type; | |
344 | typedef typename elements_type::value_type element_type; | |
345 | typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; | |
346 | typedef typename index::detail::default_content_result<Box>::type content_type; | |
347 | ||
92f5a8d4 TL |
348 | typename index::detail::strategy_type<parameters_type>::type const& |
349 | strategy = index::detail::get_strategy(parameters); | |
350 | ||
7c673cae FG |
351 | elements_type & elements1 = rtree::elements(n); |
352 | elements_type & elements2 = rtree::elements(second_node); | |
353 | const size_t elements1_count = parameters.get_max_elements() + 1; | |
354 | ||
355 | BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements"); | |
356 | ||
357 | // copy original elements - use in-memory storage (std::allocator) | |
358 | // TODO: move if noexcept | |
359 | typedef typename rtree::container_from_elements_type<elements_type, element_type>::type | |
360 | container_type; | |
361 | container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG (alloc, copy) | |
362 | ||
363 | // calculate initial seeds | |
364 | size_t seed1 = 0; | |
365 | size_t seed2 = 0; | |
366 | linear::pick_seeds(elements_copy, parameters, translator, seed1, seed2); | |
367 | ||
368 | // prepare nodes' elements containers | |
369 | elements1.clear(); | |
370 | BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state"); | |
371 | ||
372 | BOOST_TRY | |
373 | { | |
374 | // add seeds | |
375 | elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy) | |
376 | elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy) | |
377 | ||
378 | // calculate boxes | |
92f5a8d4 TL |
379 | detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), |
380 | box1, strategy); | |
381 | detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), | |
382 | box2, strategy); | |
7c673cae FG |
383 | |
384 | // initialize areas | |
385 | content_type content1 = index::detail::content(box1); | |
386 | content_type content2 = index::detail::content(box2); | |
387 | ||
388 | BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number"); | |
389 | size_t remaining = elements1_count - 2; | |
390 | ||
391 | // redistribute the rest of the elements | |
392 | for ( size_t i = 0 ; i < elements1_count ; ++i ) | |
393 | { | |
394 | if (i != seed1 && i != seed2) | |
395 | { | |
396 | element_type const& elem = elements_copy[i]; | |
397 | indexable_type const& indexable = rtree::element_indexable(elem, translator); | |
398 | ||
399 | // if there is small number of elements left and the number of elements in node is lesser than min_elems | |
400 | // just insert them to this node | |
401 | if ( elements1.size() + remaining <= parameters.get_min_elements() ) | |
402 | { | |
403 | elements1.push_back(elem); // MAY THROW, STRONG (copy) | |
92f5a8d4 | 404 | index::detail::expand(box1, indexable, strategy); |
7c673cae FG |
405 | content1 = index::detail::content(box1); |
406 | } | |
407 | else if ( elements2.size() + remaining <= parameters.get_min_elements() ) | |
408 | { | |
409 | elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy) | |
92f5a8d4 | 410 | index::detail::expand(box2, indexable, strategy); |
7c673cae FG |
411 | content2 = index::detail::content(box2); |
412 | } | |
413 | // choose better node and insert element | |
414 | else | |
415 | { | |
416 | // calculate enlarged boxes and areas | |
417 | Box enlarged_box1(box1); | |
418 | Box enlarged_box2(box2); | |
92f5a8d4 TL |
419 | index::detail::expand(enlarged_box1, indexable, strategy); |
420 | index::detail::expand(enlarged_box2, indexable, strategy); | |
7c673cae FG |
421 | content_type enlarged_content1 = index::detail::content(enlarged_box1); |
422 | content_type enlarged_content2 = index::detail::content(enlarged_box2); | |
423 | ||
424 | content_type content_increase1 = enlarged_content1 - content1; | |
425 | content_type content_increase2 = enlarged_content2 - content2; | |
426 | ||
427 | // choose group which box content have to be enlarged least or has smaller content or has fewer elements | |
428 | if ( content_increase1 < content_increase2 || | |
429 | ( content_increase1 == content_increase2 && | |
430 | ( content1 < content2 || | |
431 | ( content1 == content2 && elements1.size() <= elements2.size() ) ) ) ) | |
432 | { | |
433 | elements1.push_back(elem); // MAY THROW, STRONG (copy) | |
434 | box1 = enlarged_box1; | |
435 | content1 = enlarged_content1; | |
436 | } | |
437 | else | |
438 | { | |
439 | elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy) | |
440 | box2 = enlarged_box2; | |
441 | content2 = enlarged_content2; | |
442 | } | |
443 | } | |
444 | ||
445 | BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "unexpected value"); | |
446 | --remaining; | |
447 | } | |
448 | } | |
449 | } | |
450 | BOOST_CATCH(...) | |
451 | { | |
452 | elements1.clear(); | |
453 | elements2.clear(); | |
454 | ||
455 | rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_copy, allocators); | |
456 | //elements_copy.clear(); | |
457 | ||
458 | BOOST_RETHROW // RETHROW, BASIC | |
459 | } | |
460 | BOOST_CATCH_END | |
461 | } | |
462 | }; | |
463 | ||
464 | }} // namespace detail::rtree | |
465 | ||
466 | }}} // namespace boost::geometry::index | |
467 | ||
468 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP |