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