ceph/src/boost/boost/geometry/index/detail/rtree/visitors/distance_query.hpp

   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
  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;
 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
 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
 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
 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
 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;
 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     {
 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)())
 362 //        , m_strategy_type()
 363     {}
 364
 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
 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
 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)
 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:
 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;
 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