1 // Boost.Geometry Index
3 // R-tree distance (knn, path, etc. ) query visitor implementation
5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
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)
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP
14 namespace boost { namespace geometry { namespace index {
16 namespace detail { namespace rtree { namespace visitors {
18 template <typename Value, typename Translator, typename DistanceType, typename OutIt>
19 class distance_query_result
22 typedef DistanceType distance_type;
24 inline explicit distance_query_result(size_t k, OutIt out_it)
25 : m_count(k), m_out_it(out_it)
27 BOOST_GEOMETRY_INDEX_ASSERT(0 < m_count, "Number of neighbors should be greater than 0");
29 m_neighbors.reserve(m_count);
32 inline void store(Value const& val, distance_type const& curr_comp_dist)
34 if ( m_neighbors.size() < m_count )
36 m_neighbors.push_back(std::make_pair(curr_comp_dist, val));
38 if ( m_neighbors.size() == m_count )
39 std::make_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
43 if ( curr_comp_dist < m_neighbors.front().first )
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);
53 inline bool has_enough_neighbors() const
55 return m_count <= m_neighbors.size();
58 inline distance_type greatest_comparable_distance() const
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;
69 inline size_t finish()
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;
75 return m_neighbors.size();
79 inline static bool neighbors_less(
80 std::pair<distance_type, Value> const& p1,
81 std::pair<distance_type, Value> const& p2)
83 return p1.first < p2.first;
89 std::vector< std::pair<distance_type, Value> > m_neighbors;
99 unsigned DistancePredicateIndex,
103 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
106 typedef typename Options::parameters_type parameters_type;
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;
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;
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;
121 static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
123 inline distance_query(parameters_type const& parameters, Translator const& translator, Predicates const& pred, OutIter out_it)
124 : m_parameters(parameters), m_translator(translator)
126 , m_result(nearest_predicate_access::get(m_pred).count, out_it)
129 inline void operator()(internal_node const& n)
131 typedef typename rtree::elements_type<internal_node>::type elements_type;
133 // array of active nodes
134 typedef typename index::detail::rtree::container_from_elements_type<
136 std::pair<node_distance_type, typename Allocators::node_pointer>
137 >::type active_branch_list_type;
139 active_branch_list_type active_branch_list;
140 active_branch_list.reserve(m_parameters.get_max_elements());
142 elements_type const& elements = rtree::elements(n);
144 // fill array of nodes meeting predicates
145 for (typename elements_type::const_iterator it = elements.begin();
146 it != elements.end(); ++it)
148 // if current node meets predicates
150 if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) )
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) )
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) )
167 // add current node's data into the list
168 active_branch_list.push_back( std::make_pair(node_distance, it->second) );
172 // if there aren't any nodes in ABL - return
173 if ( active_branch_list.empty() )
177 std::sort(active_branch_list.begin(), active_branch_list.end(), abl_less);
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 )
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) )
188 rtree::apply_visitor(*this, *(it->second));
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
200 //std::make_heap(active_branch_list.begin(), active_branch_list.end(), abl_greater);
202 //// recursively visit nodes
203 //while ( !active_branch_list.empty() )
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) )
212 // rtree::apply_visitor(*this, *(active_branch_list.front().second));
214 // std::pop_heap(active_branch_list.begin(), active_branch_list.end(), abl_greater);
215 // active_branch_list.pop_back();
219 inline void operator()(leaf const& n)
221 typedef typename rtree::elements_type<leaf>::type elements_type;
222 elements_type const& elements = rtree::elements(n);
224 // search leaf for closest value meeting predicates
225 for (typename elements_type::const_iterator it = elements.begin();
226 it != elements.end(); ++it)
228 // if value meets predicates
229 if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, m_translator(*it)) )
231 // calculate values distance for distance predicate
232 value_distance_type value_distance;
234 if ( calculate_value_distance::apply(predicate(), m_translator(*it), value_distance) )
237 m_result.store(*it, value_distance);
243 inline size_t finish()
245 return m_result.finish();
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)
253 return p1.first < p2.first;
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)
260 // return p1.first > p2.first;
263 template <typename Distance>
264 static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d)
266 return greatest_dist <= d;
269 nearest_predicate_type const& predicate() const
271 return nearest_predicate_access::get(m_pred);
274 parameters_type const& m_parameters;
275 Translator const& m_translator;
278 distance_query_result<Value, Translator, value_distance_type, OutIter> m_result;
288 unsigned DistancePredicateIndex
290 class distance_query_incremental
291 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
294 typedef typename Options::parameters_type parameters_type;
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;
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;
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;
309 typedef typename Allocators::size_type size_type;
310 typedef typename Allocators::const_reference const_reference;
311 typedef typename Allocators::node_pointer node_pointer;
313 static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
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;
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
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)
330 branches = o.branches;
331 current_branch = o.current_branch;
335 active_branch_list_type branches;
336 typename active_branch_list_type::size_type current_branch;
338 typedef std::vector<internal_stack_element> internal_stack_type;
340 inline distance_query_incremental()
343 , current_neighbor((std::numeric_limits<size_type>::max)())
344 // , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)())
347 inline distance_query_incremental(Translator const& translator, Predicates const& pred)
348 : m_translator(::boost::addressof(translator))
350 , current_neighbor((std::numeric_limits<size_type>::max)())
352 , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)())
354 BOOST_GEOMETRY_INDEX_ASSERT(0 < max_count(), "k must be greather than 0");
357 const_reference dereference() const
359 return *(neighbors[current_neighbor].second);
362 void initialize(node_pointer root)
364 rtree::apply_visitor(*this, *root);
372 size_type new_neighbor = current_neighbor == (std::numeric_limits<size_type>::max)() ? 0 : current_neighbor + 1;
374 if ( internal_stack.empty() )
376 if ( new_neighbor < neighbors.size() )
377 current_neighbor = new_neighbor;
380 current_neighbor = (std::numeric_limits<size_type>::max)();
381 // clear() is used to disable the condition above
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;
392 if ( branches.size() <= current_branch )
394 internal_stack.pop_back();
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 )
404 current_neighbor = new_neighbor;
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) )
413 // stop traversing current level
414 internal_stack.pop_back();
419 // new level - must increment current_branch before traversing of another level (mem reallocation)
421 rtree::apply_visitor(*this, *(branches[current_branch - 1].second));
423 next_closest_node_distance = calc_closest_node_distance(internal_stack.begin(), internal_stack.end());
431 return (std::numeric_limits<size_type>::max)() == current_neighbor;
434 friend bool operator==(distance_query_incremental const& l, distance_query_incremental const& r)
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;
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)
449 typedef typename rtree::elements_type<internal_node>::type elements_type;
450 elements_type const& elements = rtree::elements(n);
453 internal_stack.resize(internal_stack.size()+1);
455 // fill active branch list array of nodes meeting predicates
456 for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it )
458 // if current node meets predicates
460 if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) )
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) )
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) )
477 // add current node's data into the list
478 internal_stack.back().branches.push_back( std::make_pair(node_distance, it->second) );
482 if ( internal_stack.back().branches.empty() )
483 internal_stack.pop_back();
486 std::sort(internal_stack.back().branches.begin(), internal_stack.back().branches.end(), abl_less);
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)
494 typedef typename rtree::elements_type<leaf>::type elements_type;
495 elements_type const& elements = rtree::elements(n);
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)();
501 // search leaf for closest value meeting predicates
502 for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it)
504 // if value meets predicates
505 if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, (*m_translator)(*it)) )
507 // calculate values distance for distance predicate
508 value_distance_type value_distance;
510 if ( calculate_value_distance::apply(predicate(), (*m_translator)(*it), value_distance) )
512 // if there is not enough values or current value is closer than furthest neighbour
513 if ( not_enough_neighbors || value_distance < greatest_distance )
515 neighbors.push_back(std::make_pair(value_distance, boost::addressof(*it)));
522 std::sort(neighbors.begin(), neighbors.end(), neighbors_less);
523 // remove furthest values
524 if ( max_count() < neighbors.size() )
525 neighbors.resize(max_count());
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)
532 return p1.first < p2.first;
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)
538 return p1.first < p2.first;
542 calc_closest_node_distance(typename internal_stack_type::const_iterator first,
543 typename internal_stack_type::const_iterator last)
545 node_distance_type result = (std::numeric_limits<node_distance_type>::max)();
546 for ( ; first != last ; ++first )
548 if ( first->branches.size() <= first->current_branch )
551 node_distance_type curr_dist = first->branches[first->current_branch].first;
552 if ( curr_dist < result )
558 template <typename Distance>
559 static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d)
561 return greatest_dist <= d;
564 inline unsigned max_count() const
566 return nearest_predicate_access::get(m_pred).count;
569 nearest_predicate_type const& predicate() const
571 return nearest_predicate_access::get(m_pred);
574 const Translator * m_translator;
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;
584 }}} // namespace detail::rtree::visitors
586 }}} // namespace boost::geometry::index
588 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP