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