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 distance_query_result(size_t k,OutIt out_it)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 store(Value const & val,distance_type const & curr_comp_dist)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 has_enough_neighbors() const53 inline bool has_enough_neighbors() const 54 { 55 return m_count <= m_neighbors.size(); 56 } 57 greatest_comparable_distance() const58 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 finish()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: neighbors_less(std::pair<distance_type,Value> const & p1,std::pair<distance_type,Value> const & p2)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 distance_query(parameters_type const & parameters,Translator const & translator,Predicates const & pred,OutIter out_it)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 operator ()(internal_node const & n)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 operator ()(leaf const & n)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 finish()243 inline size_t finish() 244 { 245 return m_result.finish(); 246 } 247 248 private: abl_less(std::pair<node_distance_type,typename Allocators::node_pointer> const & p1,std::pair<node_distance_type,typename Allocators::node_pointer> const & p2)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> is_node_prunable(Distance const & greatest_dist,node_distance_type const & d)264 static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d) 265 { 266 return greatest_dist <= d; 267 } 268 predicate() const269 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 { internal_stack_elementboost::geometry::index::detail::rtree::visitors::distance_query_incremental::internal_stack_element325 internal_stack_element() : current_branch(0) {} 326 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES 327 // Required in c++03 for containers using Boost.Move operator =boost::geometry::index::detail::rtree::visitors::distance_query_incremental::internal_stack_element328 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 distance_query_incremental()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 distance_query_incremental(Translator const & translator,Predicates const & pred)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 dereference() const357 const_reference dereference() const 358 { 359 return *(neighbors[current_neighbor].second); 360 } 361 initialize(node_pointer root)362 void initialize(node_pointer root) 363 { 364 rtree::apply_visitor(*this, *root); 365 increment(); 366 } 367 increment()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 is_end() const429 bool is_end() const 430 { 431 return (std::numeric_limits<size_type>::max)() == current_neighbor; 432 } 433 operator ==(distance_query_incremental const & l,distance_query_incremental const & r)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) operator ()(internal_node const & n)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) operator ()(leaf const & n)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: abl_less(std::pair<node_distance_type,typename Allocators::node_pointer> const & p1,std::pair<node_distance_type,typename Allocators::node_pointer> const & p2)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 neighbors_less(std::pair<value_distance_type,const Value * > const & p1,std::pair<value_distance_type,const Value * > const & p2)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 calc_closest_node_distance(typename internal_stack_type::const_iterator first,typename internal_stack_type::const_iterator last)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> is_node_prunable(Distance const & greatest_dist,node_distance_type const & d)559 static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d) 560 { 561 return greatest_dist <= d; 562 } 563 max_count() const564 inline unsigned max_count() const 565 { 566 return nearest_predicate_access::get(m_pred).count; 567 } 568 predicate() const569 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 589