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 //
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 //
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
19 #include <boost/core/ignore_unused.hpp>
20 #include <boost/type_traits/is_unsigned.hpp>
21
22 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
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>
difference_dispatch(T const & from,T const & to,::boost::mpl::bool_<false> const &)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>
difference_dispatch(T const & from,T const & to,::boost::mpl::bool_<true> const &)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>
difference(T const & from,T const & to)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;
98 typedef index::detail::bounded_view
99 <
100 indexable_type, bounds_type,
101 typename index::detail::strategy_type<Parameters>::type
102 > bounded_view_type;
103
applyboost::geometry::index::detail::rtree::linear::find_greatest_normalized_separation104 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
115 typename index::detail::strategy_type<Parameters>::type const&
116 strategy = index::detail::get_strategy(parameters);
117
118 // find the lowest low, highest high
119 bounded_view_type bounded_indexable_0(rtree::element_indexable(elements[0], translator),
120 strategy);
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 {
129 bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator),
130 strategy);
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;
149 bounded_view_type bounded_indexable_hl(rtree::element_indexable(elements[highest_low_index], translator),
150 strategy);
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 {
154 bounded_view_type bounded_indexable(rtree::element_indexable(elements[i], translator),
155 strategy);
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
176 ::boost::ignore_unused(parameters);
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
applyboost::geometry::index::detail::rtree::linear::find_greatest_normalized_separation191 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
231 ::boost::ignore_unused(parameters);
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
applyboost::geometry::index::detail::rtree::linear::pick_seeds_impl250 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
applyboost::geometry::index::detail::rtree::linear::pick_seeds_impl287 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>
pick_seeds(Elements const & elements,Parameters const & parameters,Translator const & tr,size_t & seed1,size_t & seed2)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 MembersHolder>
326 struct redistribute_elements<MembersHolder, linear_tag>
327 {
328 typedef typename MembersHolder::box_type box_type;
329 typedef typename MembersHolder::parameters_type parameters_type;
330 typedef typename MembersHolder::translator_type translator_type;
331 typedef typename MembersHolder::allocators_type allocators_type;
332
333 typedef typename MembersHolder::node node;
334 typedef typename MembersHolder::internal_node internal_node;
335 typedef typename MembersHolder::leaf leaf;
336
337 template <typename Node>
applyboost::geometry::index::detail::rtree::redistribute_elements338 static inline void apply(Node & n,
339 Node & second_node,
340 box_type & box1,
341 box_type & box2,
342 parameters_type const& parameters,
343 translator_type const& translator,
344 allocators_type & allocators)
345 {
346 typedef typename rtree::elements_type<Node>::type elements_type;
347 typedef typename elements_type::value_type element_type;
348 typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
349 typedef typename index::detail::default_content_result<box_type>::type content_type;
350
351 typename index::detail::strategy_type<parameters_type>::type const&
352 strategy = index::detail::get_strategy(parameters);
353
354 elements_type & elements1 = rtree::elements(n);
355 elements_type & elements2 = rtree::elements(second_node);
356 const size_t elements1_count = parameters.get_max_elements() + 1;
357
358 BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
359
360 // copy original elements - use in-memory storage (std::allocator)
361 // TODO: move if noexcept
362 typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
363 container_type;
364 container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG (alloc, copy)
365
366 // calculate initial seeds
367 size_t seed1 = 0;
368 size_t seed2 = 0;
369 linear::pick_seeds(elements_copy, parameters, translator, seed1, seed2);
370
371 // prepare nodes' elements containers
372 elements1.clear();
373 BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state");
374
375 BOOST_TRY
376 {
377 // add seeds
378 elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
379 elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
380
381 // calculate boxes
382 detail::bounds(rtree::element_indexable(elements_copy[seed1], translator),
383 box1, strategy);
384 detail::bounds(rtree::element_indexable(elements_copy[seed2], translator),
385 box2, strategy);
386
387 // initialize areas
388 content_type content1 = index::detail::content(box1);
389 content_type content2 = index::detail::content(box2);
390
391 BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
392 size_t remaining = elements1_count - 2;
393
394 // redistribute the rest of the elements
395 for ( size_t i = 0 ; i < elements1_count ; ++i )
396 {
397 if (i != seed1 && i != seed2)
398 {
399 element_type const& elem = elements_copy[i];
400 indexable_type const& indexable = rtree::element_indexable(elem, translator);
401
402 // if there is small number of elements left and the number of elements in node is lesser than min_elems
403 // just insert them to this node
404 if ( elements1.size() + remaining <= parameters.get_min_elements() )
405 {
406 elements1.push_back(elem); // MAY THROW, STRONG (copy)
407 index::detail::expand(box1, indexable, strategy);
408 content1 = index::detail::content(box1);
409 }
410 else if ( elements2.size() + remaining <= parameters.get_min_elements() )
411 {
412 elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
413 index::detail::expand(box2, indexable, strategy);
414 content2 = index::detail::content(box2);
415 }
416 // choose better node and insert element
417 else
418 {
419 // calculate enlarged boxes and areas
420 box_type enlarged_box1(box1);
421 box_type enlarged_box2(box2);
422 index::detail::expand(enlarged_box1, indexable, strategy);
423 index::detail::expand(enlarged_box2, indexable, strategy);
424 content_type enlarged_content1 = index::detail::content(enlarged_box1);
425 content_type enlarged_content2 = index::detail::content(enlarged_box2);
426
427 content_type content_increase1 = enlarged_content1 - content1;
428 content_type content_increase2 = enlarged_content2 - content2;
429
430 // choose group which box content have to be enlarged least or has smaller content or has fewer elements
431 if ( content_increase1 < content_increase2 ||
432 ( content_increase1 == content_increase2 &&
433 ( content1 < content2 ||
434 ( content1 == content2 && elements1.size() <= elements2.size() ) ) ) )
435 {
436 elements1.push_back(elem); // MAY THROW, STRONG (copy)
437 box1 = enlarged_box1;
438 content1 = enlarged_content1;
439 }
440 else
441 {
442 elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
443 box2 = enlarged_box2;
444 content2 = enlarged_content2;
445 }
446 }
447
448 BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "unexpected value");
449 --remaining;
450 }
451 }
452 }
453 BOOST_CATCH(...)
454 {
455 elements1.clear();
456 elements2.clear();
457
458 rtree::destroy_elements<MembersHolder>::apply(elements_copy, allocators);
459 //elements_copy.clear();
460
461 BOOST_RETHROW // RETHROW, BASIC
462 }
463 BOOST_CATCH_END
464 }
465 };
466
467 }} // namespace detail::rtree
468
469 }}} // namespace boost::geometry::index
470
471 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
472