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