]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree distance (knn, path, etc. ) query visitor implementation | |
4 | // | |
5 | // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
92f5a8d4 TL |
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 | // | |
7c673cae FG |
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_VISITORS_DISTANCE_QUERY_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP | |
17 | ||
18 | namespace boost { namespace geometry { namespace index { | |
19 | ||
20 | namespace detail { namespace rtree { namespace visitors { | |
21 | ||
22 | template <typename Value, typename Translator, typename DistanceType, typename OutIt> | |
23 | class distance_query_result | |
24 | { | |
25 | public: | |
26 | typedef DistanceType distance_type; | |
27 | ||
28 | inline explicit distance_query_result(size_t k, OutIt out_it) | |
29 | : m_count(k), m_out_it(out_it) | |
30 | { | |
31 | BOOST_GEOMETRY_INDEX_ASSERT(0 < m_count, "Number of neighbors should be greater than 0"); | |
32 | ||
33 | m_neighbors.reserve(m_count); | |
34 | } | |
35 | ||
36 | inline void store(Value const& val, distance_type const& curr_comp_dist) | |
37 | { | |
38 | if ( m_neighbors.size() < m_count ) | |
39 | { | |
40 | m_neighbors.push_back(std::make_pair(curr_comp_dist, val)); | |
41 | ||
42 | if ( m_neighbors.size() == m_count ) | |
43 | std::make_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less); | |
44 | } | |
45 | else | |
46 | { | |
47 | if ( curr_comp_dist < m_neighbors.front().first ) | |
48 | { | |
49 | std::pop_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less); | |
50 | m_neighbors.back().first = curr_comp_dist; | |
51 | m_neighbors.back().second = val; | |
52 | std::push_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less); | |
53 | } | |
54 | } | |
55 | } | |
56 | ||
57 | inline bool has_enough_neighbors() const | |
58 | { | |
59 | return m_count <= m_neighbors.size(); | |
60 | } | |
61 | ||
62 | inline distance_type greatest_comparable_distance() const | |
63 | { | |
64 | // greatest distance is in the first neighbor only | |
65 | // if there is at least m_count values found | |
66 | // this is just for safety reasons since is_comparable_distance_valid() is checked earlier | |
67 | // TODO - may be replaced by ASSERT | |
68 | return m_neighbors.size() < m_count | |
69 | ? (std::numeric_limits<distance_type>::max)() | |
70 | : m_neighbors.front().first; | |
71 | } | |
72 | ||
73 | inline size_t finish() | |
74 | { | |
75 | typedef typename std::vector< std::pair<distance_type, Value> >::const_iterator neighbors_iterator; | |
76 | for ( neighbors_iterator it = m_neighbors.begin() ; it != m_neighbors.end() ; ++it, ++m_out_it ) | |
77 | *m_out_it = it->second; | |
78 | ||
79 | return m_neighbors.size(); | |
80 | } | |
81 | ||
82 | private: | |
83 | inline static bool neighbors_less( | |
84 | std::pair<distance_type, Value> const& p1, | |
85 | std::pair<distance_type, Value> const& p2) | |
86 | { | |
87 | return p1.first < p2.first; | |
88 | } | |
89 | ||
90 | size_t m_count; | |
91 | OutIt m_out_it; | |
92 | ||
93 | std::vector< std::pair<distance_type, Value> > m_neighbors; | |
94 | }; | |
95 | ||
96 | template < | |
97 | typename Value, | |
98 | typename Options, | |
99 | typename Translator, | |
100 | typename Box, | |
101 | typename Allocators, | |
102 | typename Predicates, | |
103 | unsigned DistancePredicateIndex, | |
104 | typename OutIter | |
105 | > | |
106 | class distance_query | |
107 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
108 | { | |
109 | public: | |
110 | typedef typename Options::parameters_type parameters_type; | |
92f5a8d4 | 111 | typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; |
7c673cae FG |
112 | |
113 | typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
114 | typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
115 | typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
116 | ||
117 | typedef index::detail::predicates_element<DistancePredicateIndex, Predicates> nearest_predicate_access; | |
118 | typedef typename nearest_predicate_access::type nearest_predicate_type; | |
119 | typedef typename indexable_type<Translator>::type indexable_type; | |
120 | ||
92f5a8d4 TL |
121 | typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, strategy_type, value_tag> calculate_value_distance; |
122 | typedef index::detail::calculate_distance<nearest_predicate_type, Box, strategy_type, bounds_tag> calculate_node_distance; | |
7c673cae FG |
123 | typedef typename calculate_value_distance::result_type value_distance_type; |
124 | typedef typename calculate_node_distance::result_type node_distance_type; | |
125 | ||
126 | static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value; | |
127 | ||
128 | inline distance_query(parameters_type const& parameters, Translator const& translator, Predicates const& pred, OutIter out_it) | |
129 | : m_parameters(parameters), m_translator(translator) | |
130 | , m_pred(pred) | |
131 | , m_result(nearest_predicate_access::get(m_pred).count, out_it) | |
92f5a8d4 | 132 | , m_strategy(index::detail::get_strategy(parameters)) |
7c673cae FG |
133 | {} |
134 | ||
135 | inline void operator()(internal_node const& n) | |
136 | { | |
137 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
138 | ||
139 | // array of active nodes | |
140 | typedef typename index::detail::rtree::container_from_elements_type< | |
141 | elements_type, | |
142 | std::pair<node_distance_type, typename Allocators::node_pointer> | |
143 | >::type active_branch_list_type; | |
144 | ||
145 | active_branch_list_type active_branch_list; | |
146 | active_branch_list.reserve(m_parameters.get_max_elements()); | |
147 | ||
148 | elements_type const& elements = rtree::elements(n); | |
149 | ||
150 | // fill array of nodes meeting predicates | |
151 | for (typename elements_type::const_iterator it = elements.begin(); | |
152 | it != elements.end(); ++it) | |
153 | { | |
154 | // if current node meets predicates | |
155 | // 0 - dummy value | |
92f5a8d4 TL |
156 | if ( index::detail::predicates_check |
157 | < | |
158 | index::detail::bounds_tag, 0, predicates_len | |
159 | >(m_pred, 0, it->first, m_strategy) ) | |
7c673cae FG |
160 | { |
161 | // calculate node's distance(s) for distance predicate | |
162 | node_distance_type node_distance; | |
163 | // if distance isn't ok - move to the next node | |
92f5a8d4 TL |
164 | if ( !calculate_node_distance::apply(predicate(), it->first, |
165 | m_strategy, node_distance) ) | |
7c673cae FG |
166 | { |
167 | continue; | |
168 | } | |
169 | ||
170 | // if current node is further than found neighbors - don't analyze it | |
171 | if ( m_result.has_enough_neighbors() && | |
172 | is_node_prunable(m_result.greatest_comparable_distance(), node_distance) ) | |
173 | { | |
174 | continue; | |
175 | } | |
176 | ||
177 | // add current node's data into the list | |
178 | active_branch_list.push_back( std::make_pair(node_distance, it->second) ); | |
179 | } | |
180 | } | |
181 | ||
182 | // if there aren't any nodes in ABL - return | |
183 | if ( active_branch_list.empty() ) | |
184 | return; | |
185 | ||
186 | // sort array | |
187 | std::sort(active_branch_list.begin(), active_branch_list.end(), abl_less); | |
188 | ||
189 | // recursively visit nodes | |
190 | for ( typename active_branch_list_type::const_iterator it = active_branch_list.begin(); | |
191 | it != active_branch_list.end() ; ++it ) | |
192 | { | |
193 | // if current node is further than furthest neighbor, the rest of nodes also will be further | |
194 | if ( m_result.has_enough_neighbors() && | |
195 | is_node_prunable(m_result.greatest_comparable_distance(), it->first) ) | |
196 | break; | |
197 | ||
198 | rtree::apply_visitor(*this, *(it->second)); | |
199 | } | |
200 | ||
201 | // ALTERNATIVE VERSION - use heap instead of sorted container | |
202 | // It seems to be faster for greater MaxElements and slower otherwise | |
203 | // CONSIDER: using one global container/heap for active branches | |
204 | // instead of a sorted container per level | |
205 | // This would also change the way how branches are traversed! | |
206 | // The same may be applied to the iterative version which btw suffers | |
207 | // from the copying of the whole containers on resize of the ABLs container | |
208 | ||
209 | //// make a heap | |
210 | //std::make_heap(active_branch_list.begin(), active_branch_list.end(), abl_greater); | |
211 | ||
212 | //// recursively visit nodes | |
213 | //while ( !active_branch_list.empty() ) | |
214 | //{ | |
215 | // //if current node is further than furthest neighbor, the rest of nodes also will be further | |
216 | // if ( m_result.has_enough_neighbors() | |
217 | // && is_node_prunable(m_result.greatest_comparable_distance(), active_branch_list.front().first) ) | |
218 | // { | |
219 | // break; | |
220 | // } | |
221 | ||
222 | // rtree::apply_visitor(*this, *(active_branch_list.front().second)); | |
223 | ||
224 | // std::pop_heap(active_branch_list.begin(), active_branch_list.end(), abl_greater); | |
225 | // active_branch_list.pop_back(); | |
226 | //} | |
227 | } | |
228 | ||
229 | inline void operator()(leaf const& n) | |
230 | { | |
231 | typedef typename rtree::elements_type<leaf>::type elements_type; | |
232 | elements_type const& elements = rtree::elements(n); | |
233 | ||
234 | // search leaf for closest value meeting predicates | |
235 | for (typename elements_type::const_iterator it = elements.begin(); | |
236 | it != elements.end(); ++it) | |
237 | { | |
238 | // if value meets predicates | |
92f5a8d4 TL |
239 | if ( index::detail::predicates_check |
240 | < | |
241 | index::detail::value_tag, 0, predicates_len | |
242 | >(m_pred, *it, m_translator(*it), m_strategy) ) | |
7c673cae FG |
243 | { |
244 | // calculate values distance for distance predicate | |
245 | value_distance_type value_distance; | |
246 | // if distance is ok | |
92f5a8d4 TL |
247 | if ( calculate_value_distance::apply(predicate(), m_translator(*it), |
248 | m_strategy, value_distance) ) | |
7c673cae FG |
249 | { |
250 | // store value | |
251 | m_result.store(*it, value_distance); | |
252 | } | |
253 | } | |
254 | } | |
255 | } | |
256 | ||
257 | inline size_t finish() | |
258 | { | |
259 | return m_result.finish(); | |
260 | } | |
261 | ||
262 | private: | |
263 | static inline bool abl_less( | |
264 | std::pair<node_distance_type, typename Allocators::node_pointer> const& p1, | |
265 | std::pair<node_distance_type, typename Allocators::node_pointer> const& p2) | |
266 | { | |
267 | return p1.first < p2.first; | |
268 | } | |
269 | ||
270 | //static inline bool abl_greater( | |
271 | // std::pair<node_distance_type, typename Allocators::node_pointer> const& p1, | |
272 | // std::pair<node_distance_type, typename Allocators::node_pointer> const& p2) | |
273 | //{ | |
274 | // return p1.first > p2.first; | |
275 | //} | |
276 | ||
277 | template <typename Distance> | |
278 | static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d) | |
279 | { | |
280 | return greatest_dist <= d; | |
281 | } | |
282 | ||
283 | nearest_predicate_type const& predicate() const | |
284 | { | |
285 | return nearest_predicate_access::get(m_pred); | |
286 | } | |
287 | ||
288 | parameters_type const& m_parameters; | |
289 | Translator const& m_translator; | |
290 | ||
291 | Predicates m_pred; | |
292 | distance_query_result<Value, Translator, value_distance_type, OutIter> m_result; | |
92f5a8d4 TL |
293 | |
294 | strategy_type m_strategy; | |
7c673cae FG |
295 | }; |
296 | ||
297 | template < | |
298 | typename Value, | |
299 | typename Options, | |
300 | typename Translator, | |
301 | typename Box, | |
302 | typename Allocators, | |
303 | typename Predicates, | |
304 | unsigned DistancePredicateIndex | |
305 | > | |
306 | class distance_query_incremental | |
307 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
308 | { | |
309 | public: | |
310 | typedef typename Options::parameters_type parameters_type; | |
92f5a8d4 | 311 | typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; |
7c673cae FG |
312 | |
313 | typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
314 | typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
315 | typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
316 | ||
317 | typedef index::detail::predicates_element<DistancePredicateIndex, Predicates> nearest_predicate_access; | |
318 | typedef typename nearest_predicate_access::type nearest_predicate_type; | |
319 | typedef typename indexable_type<Translator>::type indexable_type; | |
320 | ||
92f5a8d4 TL |
321 | typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, strategy_type, value_tag> calculate_value_distance; |
322 | typedef index::detail::calculate_distance<nearest_predicate_type, Box, strategy_type, bounds_tag> calculate_node_distance; | |
7c673cae FG |
323 | typedef typename calculate_value_distance::result_type value_distance_type; |
324 | typedef typename calculate_node_distance::result_type node_distance_type; | |
325 | ||
326 | typedef typename Allocators::size_type size_type; | |
327 | typedef typename Allocators::const_reference const_reference; | |
328 | typedef typename Allocators::node_pointer node_pointer; | |
329 | ||
330 | static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value; | |
331 | ||
332 | typedef typename rtree::elements_type<internal_node>::type internal_elements; | |
333 | typedef typename internal_elements::const_iterator internal_iterator; | |
334 | typedef typename rtree::elements_type<leaf>::type leaf_elements; | |
335 | ||
336 | typedef std::pair<node_distance_type, node_pointer> branch_data; | |
337 | typedef typename index::detail::rtree::container_from_elements_type< | |
338 | internal_elements, branch_data | |
339 | >::type active_branch_list_type; | |
340 | struct internal_stack_element | |
341 | { | |
342 | internal_stack_element() : current_branch(0) {} | |
343 | #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES | |
344 | // Required in c++03 for containers using Boost.Move | |
345 | internal_stack_element & operator=(internal_stack_element const& o) | |
346 | { | |
347 | branches = o.branches; | |
348 | current_branch = o.current_branch; | |
349 | return *this; | |
350 | } | |
351 | #endif | |
352 | active_branch_list_type branches; | |
353 | typename active_branch_list_type::size_type current_branch; | |
354 | }; | |
355 | typedef std::vector<internal_stack_element> internal_stack_type; | |
356 | ||
357 | inline distance_query_incremental() | |
358 | : m_translator(NULL) | |
359 | // , m_pred() | |
360 | , current_neighbor((std::numeric_limits<size_type>::max)()) | |
361 | // , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)()) | |
92f5a8d4 | 362 | // , m_strategy_type() |
7c673cae FG |
363 | {} |
364 | ||
92f5a8d4 | 365 | inline distance_query_incremental(parameters_type const& params, Translator const& translator, Predicates const& pred) |
7c673cae FG |
366 | : m_translator(::boost::addressof(translator)) |
367 | , m_pred(pred) | |
368 | , current_neighbor((std::numeric_limits<size_type>::max)()) | |
7c673cae | 369 | , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)()) |
92f5a8d4 | 370 | , m_strategy(index::detail::get_strategy(params)) |
7c673cae FG |
371 | { |
372 | BOOST_GEOMETRY_INDEX_ASSERT(0 < max_count(), "k must be greather than 0"); | |
373 | } | |
374 | ||
375 | const_reference dereference() const | |
376 | { | |
377 | return *(neighbors[current_neighbor].second); | |
378 | } | |
379 | ||
380 | void initialize(node_pointer root) | |
381 | { | |
382 | rtree::apply_visitor(*this, *root); | |
383 | increment(); | |
384 | } | |
385 | ||
386 | void increment() | |
387 | { | |
388 | for (;;) | |
389 | { | |
390 | size_type new_neighbor = current_neighbor == (std::numeric_limits<size_type>::max)() ? 0 : current_neighbor + 1; | |
391 | ||
392 | if ( internal_stack.empty() ) | |
393 | { | |
394 | if ( new_neighbor < neighbors.size() ) | |
395 | current_neighbor = new_neighbor; | |
396 | else | |
397 | { | |
398 | current_neighbor = (std::numeric_limits<size_type>::max)(); | |
399 | // clear() is used to disable the condition above | |
400 | neighbors.clear(); | |
401 | } | |
402 | ||
403 | return; | |
404 | } | |
405 | else | |
406 | { | |
407 | active_branch_list_type & branches = internal_stack.back().branches; | |
408 | typename active_branch_list_type::size_type & current_branch = internal_stack.back().current_branch; | |
409 | ||
410 | if ( branches.size() <= current_branch ) | |
411 | { | |
412 | internal_stack.pop_back(); | |
413 | continue; | |
414 | } | |
415 | ||
416 | // if there are no nodes which can have closer values, set new value | |
417 | if ( new_neighbor < neighbors.size() && | |
418 | // here must be < because otherwise neighbours may be sorted in different order | |
419 | // if there is another value with equal distance | |
420 | neighbors[new_neighbor].first < next_closest_node_distance ) | |
421 | { | |
422 | current_neighbor = new_neighbor; | |
423 | return; | |
424 | } | |
425 | ||
426 | // if node is further than the furthest neighbour, following nodes also will be further | |
427 | BOOST_GEOMETRY_INDEX_ASSERT(neighbors.size() <= max_count(), "unexpected neighbours count"); | |
428 | if ( max_count() <= neighbors.size() && | |
429 | is_node_prunable(neighbors.back().first, branches[current_branch].first) ) | |
430 | { | |
431 | // stop traversing current level | |
432 | internal_stack.pop_back(); | |
433 | continue; | |
434 | } | |
435 | else | |
436 | { | |
437 | // new level - must increment current_branch before traversing of another level (mem reallocation) | |
438 | ++current_branch; | |
439 | rtree::apply_visitor(*this, *(branches[current_branch - 1].second)); | |
440 | ||
441 | next_closest_node_distance = calc_closest_node_distance(internal_stack.begin(), internal_stack.end()); | |
442 | } | |
443 | } | |
444 | } | |
445 | } | |
446 | ||
447 | bool is_end() const | |
448 | { | |
449 | return (std::numeric_limits<size_type>::max)() == current_neighbor; | |
450 | } | |
451 | ||
452 | friend bool operator==(distance_query_incremental const& l, distance_query_incremental const& r) | |
453 | { | |
454 | BOOST_GEOMETRY_INDEX_ASSERT(l.current_neighbor != r.current_neighbor || | |
455 | (std::numeric_limits<size_type>::max)() == l.current_neighbor || | |
456 | (std::numeric_limits<size_type>::max)() == r.current_neighbor || | |
457 | l.neighbors[l.current_neighbor].second == r.neighbors[r.current_neighbor].second, | |
458 | "not corresponding iterators"); | |
459 | return l.current_neighbor == r.current_neighbor; | |
460 | } | |
461 | ||
462 | // Put node's elements into the list of active branches if those elements meets predicates | |
463 | // and distance predicates(currently not used) | |
464 | // and aren't further than found neighbours (if there is enough neighbours) | |
465 | inline void operator()(internal_node const& n) | |
466 | { | |
467 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
468 | elements_type const& elements = rtree::elements(n); | |
469 | ||
470 | // add new element | |
471 | internal_stack.resize(internal_stack.size()+1); | |
472 | ||
473 | // fill active branch list array of nodes meeting predicates | |
474 | for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it ) | |
475 | { | |
476 | // if current node meets predicates | |
477 | // 0 - dummy value | |
92f5a8d4 TL |
478 | if ( index::detail::predicates_check |
479 | < | |
480 | index::detail::bounds_tag, 0, predicates_len | |
481 | >(m_pred, 0, it->first, m_strategy) ) | |
7c673cae FG |
482 | { |
483 | // calculate node's distance(s) for distance predicate | |
484 | node_distance_type node_distance; | |
485 | // if distance isn't ok - move to the next node | |
92f5a8d4 TL |
486 | if ( !calculate_node_distance::apply(predicate(), it->first, |
487 | m_strategy, node_distance) ) | |
7c673cae FG |
488 | { |
489 | continue; | |
490 | } | |
491 | ||
492 | // if current node is further than found neighbors - don't analyze it | |
493 | if ( max_count() <= neighbors.size() && | |
494 | is_node_prunable(neighbors.back().first, node_distance) ) | |
495 | { | |
496 | continue; | |
497 | } | |
498 | ||
499 | // add current node's data into the list | |
500 | internal_stack.back().branches.push_back( std::make_pair(node_distance, it->second) ); | |
501 | } | |
502 | } | |
503 | ||
504 | if ( internal_stack.back().branches.empty() ) | |
505 | internal_stack.pop_back(); | |
506 | else | |
507 | // sort array | |
508 | std::sort(internal_stack.back().branches.begin(), internal_stack.back().branches.end(), abl_less); | |
509 | } | |
510 | ||
511 | // Put values into the list of neighbours if those values meets predicates | |
512 | // and distance predicates(currently not used) | |
513 | // and aren't further than already found neighbours (if there is enough neighbours) | |
514 | inline void operator()(leaf const& n) | |
515 | { | |
516 | typedef typename rtree::elements_type<leaf>::type elements_type; | |
517 | elements_type const& elements = rtree::elements(n); | |
518 | ||
519 | // store distance to the furthest neighbour | |
520 | bool not_enough_neighbors = neighbors.size() < max_count(); | |
521 | value_distance_type greatest_distance = !not_enough_neighbors ? neighbors.back().first : (std::numeric_limits<value_distance_type>::max)(); | |
522 | ||
523 | // search leaf for closest value meeting predicates | |
524 | for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it) | |
525 | { | |
526 | // if value meets predicates | |
92f5a8d4 TL |
527 | if ( index::detail::predicates_check |
528 | < | |
529 | index::detail::value_tag, 0, predicates_len | |
530 | >(m_pred, *it, (*m_translator)(*it), m_strategy) ) | |
7c673cae FG |
531 | { |
532 | // calculate values distance for distance predicate | |
533 | value_distance_type value_distance; | |
534 | // if distance is ok | |
92f5a8d4 TL |
535 | if ( calculate_value_distance::apply(predicate(), (*m_translator)(*it), |
536 | m_strategy, value_distance) ) | |
7c673cae FG |
537 | { |
538 | // if there is not enough values or current value is closer than furthest neighbour | |
539 | if ( not_enough_neighbors || value_distance < greatest_distance ) | |
540 | { | |
541 | neighbors.push_back(std::make_pair(value_distance, boost::addressof(*it))); | |
542 | } | |
543 | } | |
544 | } | |
545 | } | |
546 | ||
547 | // sort array | |
548 | std::sort(neighbors.begin(), neighbors.end(), neighbors_less); | |
549 | // remove furthest values | |
550 | if ( max_count() < neighbors.size() ) | |
551 | neighbors.resize(max_count()); | |
552 | } | |
553 | ||
554 | private: | |
555 | static inline bool abl_less(std::pair<node_distance_type, typename Allocators::node_pointer> const& p1, | |
556 | std::pair<node_distance_type, typename Allocators::node_pointer> const& p2) | |
557 | { | |
558 | return p1.first < p2.first; | |
559 | } | |
560 | ||
561 | static inline bool neighbors_less(std::pair<value_distance_type, const Value *> const& p1, | |
562 | std::pair<value_distance_type, const Value *> const& p2) | |
563 | { | |
564 | return p1.first < p2.first; | |
565 | } | |
566 | ||
567 | node_distance_type | |
568 | calc_closest_node_distance(typename internal_stack_type::const_iterator first, | |
569 | typename internal_stack_type::const_iterator last) | |
570 | { | |
571 | node_distance_type result = (std::numeric_limits<node_distance_type>::max)(); | |
572 | for ( ; first != last ; ++first ) | |
573 | { | |
574 | if ( first->branches.size() <= first->current_branch ) | |
575 | continue; | |
576 | ||
577 | node_distance_type curr_dist = first->branches[first->current_branch].first; | |
578 | if ( curr_dist < result ) | |
579 | result = curr_dist; | |
580 | } | |
581 | return result; | |
582 | } | |
583 | ||
584 | template <typename Distance> | |
585 | static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d) | |
586 | { | |
587 | return greatest_dist <= d; | |
588 | } | |
589 | ||
590 | inline unsigned max_count() const | |
591 | { | |
592 | return nearest_predicate_access::get(m_pred).count; | |
593 | } | |
594 | ||
595 | nearest_predicate_type const& predicate() const | |
596 | { | |
597 | return nearest_predicate_access::get(m_pred); | |
598 | } | |
599 | ||
600 | const Translator * m_translator; | |
601 | ||
602 | Predicates m_pred; | |
92f5a8d4 | 603 | |
7c673cae FG |
604 | internal_stack_type internal_stack; |
605 | std::vector< std::pair<value_distance_type, const Value *> > neighbors; | |
606 | size_type current_neighbor; | |
607 | node_distance_type next_closest_node_distance; | |
92f5a8d4 TL |
608 | |
609 | strategy_type m_strategy; | |
7c673cae FG |
610 | }; |
611 | ||
612 | }}} // namespace detail::rtree::visitors | |
613 | ||
614 | }}} // namespace boost::geometry::index | |
615 | ||
616 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP |