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 // 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 // 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 distance_query_result(size_t k,OutIt out_it)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 store(Value const & val,distance_type const & curr_comp_dist)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 has_enough_neighbors() const57 inline bool has_enough_neighbors() const 58 { 59 return m_count <= m_neighbors.size(); 60 } 61 greatest_comparable_distance() const62 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 finish()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: neighbors_less(std::pair<distance_type,Value> const & p1,std::pair<distance_type,Value> const & p2)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; 111 typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; 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 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; 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 distance_query(parameters_type const & parameters,Translator const & translator,Predicates const & pred,OutIter out_it)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) 132 , m_strategy(index::detail::get_strategy(parameters)) 133 {} 134 operator ()(internal_node const & n)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 156 if ( index::detail::predicates_check 157 < 158 index::detail::bounds_tag, 0, predicates_len 159 >(m_pred, 0, it->first, m_strategy) ) 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 164 if ( !calculate_node_distance::apply(predicate(), it->first, 165 m_strategy, node_distance) ) 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 operator ()(leaf const & n)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 239 if ( index::detail::predicates_check 240 < 241 index::detail::value_tag, 0, predicates_len 242 >(m_pred, *it, m_translator(*it), m_strategy) ) 243 { 244 // calculate values distance for distance predicate 245 value_distance_type value_distance; 246 // if distance is ok 247 if ( calculate_value_distance::apply(predicate(), m_translator(*it), 248 m_strategy, value_distance) ) 249 { 250 // store value 251 m_result.store(*it, value_distance); 252 } 253 } 254 } 255 } 256 finish()257 inline size_t finish() 258 { 259 return m_result.finish(); 260 } 261 262 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)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> is_node_prunable(Distance const & greatest_dist,node_distance_type const & d)278 static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d) 279 { 280 return greatest_dist <= d; 281 } 282 predicate() const283 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; 293 294 strategy_type m_strategy; 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; 311 typedef typename index::detail::strategy_type<parameters_type>::type strategy_type; 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 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; 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 { internal_stack_elementboost::geometry::index::detail::rtree::visitors::distance_query_incremental::internal_stack_element342 internal_stack_element() : current_branch(0) {} 343 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES 344 // Required in c++03 for containers using Boost.Move operator =boost::geometry::index::detail::rtree::visitors::distance_query_incremental::internal_stack_element345 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 distance_query_incremental()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)()) 362 // , m_strategy_type() 363 {} 364 distance_query_incremental(parameters_type const & params,Translator const & translator,Predicates const & pred)365 inline distance_query_incremental(parameters_type const& params, Translator const& translator, Predicates const& pred) 366 : m_translator(::boost::addressof(translator)) 367 , m_pred(pred) 368 , current_neighbor((std::numeric_limits<size_type>::max)()) 369 , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)()) 370 , m_strategy(index::detail::get_strategy(params)) 371 { 372 BOOST_GEOMETRY_INDEX_ASSERT(0 < max_count(), "k must be greather than 0"); 373 } 374 dereference() const375 const_reference dereference() const 376 { 377 return *(neighbors[current_neighbor].second); 378 } 379 initialize(node_pointer root)380 void initialize(node_pointer root) 381 { 382 rtree::apply_visitor(*this, *root); 383 increment(); 384 } 385 increment()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 is_end() const447 bool is_end() const 448 { 449 return (std::numeric_limits<size_type>::max)() == current_neighbor; 450 } 451 operator ==(distance_query_incremental const & l,distance_query_incremental const & r)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) operator ()(internal_node const & n)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 478 if ( index::detail::predicates_check 479 < 480 index::detail::bounds_tag, 0, predicates_len 481 >(m_pred, 0, it->first, m_strategy) ) 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 486 if ( !calculate_node_distance::apply(predicate(), it->first, 487 m_strategy, node_distance) ) 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) operator ()(leaf const & n)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 527 if ( index::detail::predicates_check 528 < 529 index::detail::value_tag, 0, predicates_len 530 >(m_pred, *it, (*m_translator)(*it), m_strategy) ) 531 { 532 // calculate values distance for distance predicate 533 value_distance_type value_distance; 534 // if distance is ok 535 if ( calculate_value_distance::apply(predicate(), (*m_translator)(*it), 536 m_strategy, value_distance) ) 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: abl_less(std::pair<node_distance_type,typename Allocators::node_pointer> const & p1,std::pair<node_distance_type,typename Allocators::node_pointer> const & p2)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 neighbors_less(std::pair<value_distance_type,const Value * > const & p1,std::pair<value_distance_type,const Value * > const & p2)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 calc_closest_node_distance(typename internal_stack_type::const_iterator first,typename internal_stack_type::const_iterator last)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> is_node_prunable(Distance const & greatest_dist,node_distance_type const & d)585 static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d) 586 { 587 return greatest_dist <= d; 588 } 589 max_count() const590 inline unsigned max_count() const 591 { 592 return nearest_predicate_access::get(m_pred).count; 593 } 594 predicate() const595 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; 603 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; 608 609 strategy_type m_strategy; 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 617