rtree/visitors/distance_query.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree distance (knn, path, etc. ) query visitor implementation
0004 //
0005 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2023.
0008 // Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP
0018
0019 #include <queue>
0020
0021 #include <boost/geometry/index/detail/distance_predicates.hpp>
0022 #include <boost/geometry/index/detail/predicates.hpp>
0023 #include <boost/geometry/index/detail/priority_dequeue.hpp>
0024 #include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
0025 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0026 #include <boost/geometry/index/detail/translator.hpp>
0027 #include <boost/geometry/index/parameters.hpp>
0028
0029 namespace boost { namespace geometry { namespace index {
0030
0031 namespace detail { namespace rtree { namespace visitors {
0032
0033
0034 struct pair_first_less
0035 {
0036     template <typename First, typename Second>
0037     inline bool operator()(std::pair<First, Second> const& p1,
0038                            std::pair<First, Second> const& p2) const
0039     {
0040         return p1.first < p2.first;
0041     }
0042 };
0043
0044 struct pair_first_greater
0045 {
0046     template <typename First, typename Second>
0047     inline bool operator()(std::pair<First, Second> const& p1,
0048                            std::pair<First, Second> const& p2) const
0049     {
0050         return p1.first > p2.first;
0051     }
0052 };
0053
0054 template <typename T, typename Comp>
0055 struct priority_dequeue : index::detail::priority_dequeue<T, std::vector<T>, Comp>
0056 {
0057     priority_dequeue() = default;
0058     //void reserve(typename std::vector<T>::size_type n)
0059     //{
0060     //    this->c.reserve(n);
0061     //}
0062     //void clear()
0063     //{
0064     //    this->c.clear();
0065     //}
0066 };
0067
0068 template <typename T, typename Comp>
0069 struct priority_queue : std::priority_queue<T, std::vector<T>, Comp>
0070 {
0071     priority_queue() = default;
0072     //void reserve(typename std::vector<T>::size_type n)
0073     //{
0074     //    this->c.reserve(n);
0075     //}
0076     void clear()
0077     {
0078         this->c.clear();
0079     }
0080 };
0081
0082 struct branch_data_comp
0083 {
0084     template <typename BranchData>
0085     bool operator()(BranchData const& b1, BranchData const& b2) const
0086     {
0087         return b1.distance > b2.distance || (b1.distance == b2.distance && b1.reverse_level > b2.reverse_level);
0088     }
0089 };
0090
0091 template <typename DistanceType, typename Value>
0092 class distance_query_result
0093 {
0094     using neighbor_data = std::pair<DistanceType, const Value *>;
0095     using neighbors_type = std::vector<neighbor_data>;
0096     using size_type = typename neighbors_type::size_type;
0097
0098 public:
0099     inline distance_query_result(size_type k)
0100         : m_count(k)
0101     {
0102         m_neighbors.reserve(m_count);
0103     }
0104
0105     // NOTE: Do not call if max_count() == 0
0106     inline void store(DistanceType const& distance, const Value * value_ptr)
0107     {
0108         if (m_neighbors.size() < m_count)
0109         {
0110             m_neighbors.push_back(std::make_pair(distance, value_ptr));
0111
0112             if (m_neighbors.size() == m_count)
0113             {
0114                 std::make_heap(m_neighbors.begin(), m_neighbors.end(), pair_first_less());
0115             }
0116         }
0117         else if (distance < m_neighbors.front().first)
0118         {
0119             std::pop_heap(m_neighbors.begin(), m_neighbors.end(), pair_first_less());
0120             m_neighbors.back().first = distance;
0121             m_neighbors.back().second = value_ptr;
0122             std::push_heap(m_neighbors.begin(), m_neighbors.end(), pair_first_less());
0123         }
0124     }
0125
0126     // NOTE: Do not call if max_count() == 0
0127     inline bool ignore_branch(DistanceType const& distance) const
0128     {
0129         return m_neighbors.size() == m_count
0130             && m_neighbors.front().first <= distance;
0131     }
0132
0133     template <typename OutIt>
0134     inline size_type finish(OutIt out_it) const
0135     {
0136         for (auto const& p : m_neighbors)
0137         {
0138             *out_it = *(p.second);
0139             ++out_it;
0140         }
0141
0142         return m_neighbors.size();
0143     }
0144
0145     size_type max_count() const
0146     {
0147         return m_count;
0148     }
0149
0150 private:
0151     size_type m_count;
0152     neighbors_type m_neighbors;
0153 };
0154
0155 template <typename MembersHolder, typename Predicates>
0156 class distance_query
0157 {
0158     typedef typename MembersHolder::value_type value_type;
0159     typedef typename MembersHolder::box_type box_type;
0160     typedef typename MembersHolder::parameters_type parameters_type;
0161     typedef typename MembersHolder::translator_type translator_type;
0162
0163     typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
0164
0165     typedef typename MembersHolder::node node;
0166     typedef typename MembersHolder::internal_node internal_node;
0167     typedef typename MembersHolder::leaf leaf;
0168
0169     typedef index::detail::predicates_element
0170         <
0171             index::detail::predicates_find_distance<Predicates>::value, Predicates
0172         > nearest_predicate_access;
0173     typedef typename nearest_predicate_access::type nearest_predicate_type;
0174     typedef typename indexable_type<translator_type>::type indexable_type;
0175
0176     typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, strategy_type, value_tag> calculate_value_distance;
0177     typedef index::detail::calculate_distance<nearest_predicate_type, box_type, strategy_type, bounds_tag> calculate_node_distance;
0178     typedef typename calculate_value_distance::result_type value_distance_type;
0179     typedef typename calculate_node_distance::result_type node_distance_type;
0180
0181     typedef typename MembersHolder::size_type size_type;
0182     typedef typename MembersHolder::node_pointer node_pointer;
0183
0184     using neighbor_data = std::pair<value_distance_type, const value_type *>;
0185     using neighbors_type = std::vector<neighbor_data>;
0186
0187     struct branch_data
0188     {
0189         branch_data(node_distance_type d, size_type rl, node_pointer p)
0190             : distance(d), reverse_level(rl), ptr(p)
0191         {}
0192
0193         node_distance_type distance;
0194         size_type reverse_level;
0195         node_pointer ptr;
0196     };
0197     using branches_type = priority_queue<branch_data, branch_data_comp>;
0198
0199 public:
0200     distance_query(MembersHolder const& members, Predicates const& pred)
0201         : m_tr(members.translator())
0202         , m_strategy(index::detail::get_strategy(members.parameters()))
0203         , m_pred(pred)
0204     {
0205         m_neighbors.reserve((std::min)(members.values_count, size_type(max_count())));
0206         //m_branches.reserve(members.parameters().get_min_elements() * members.leafs_level); ?
0207         // min, max or average?
0208     }
0209
0210     template <typename OutIter>
0211     size_type apply(MembersHolder const& members, OutIter out_it)
0212     {
0213         return apply(members.root, members.leafs_level, out_it);
0214     }
0215
0216 private:
0217     template <typename OutIter>
0218     size_type apply(node_pointer ptr, size_type reverse_level, OutIter out_it)
0219     {
0220         namespace id = index::detail;
0221
0222         if (max_count() <= 0)
0223         {
0224             return 0;
0225         }
0226
0227         for (;;)
0228         {
0229             if (reverse_level > 0)
0230             {
0231                 internal_node& n = rtree::get<internal_node>(*ptr);
0232                 // fill array of nodes meeting predicates
0233                 for (auto const& p : rtree::elements(n))
0234                 {
0235                     node_distance_type node_distance; // for distance predicate
0236
0237                     // if current node meets predicates (0 is dummy value)
0238                     if (id::predicates_check<id::bounds_tag>(m_pred, 0, p.first, m_strategy)
0239                         // and if distance is ok
0240                         && calculate_node_distance::apply(predicate(), p.first, m_strategy, node_distance)
0241                         // and if current node is closer than the furthest neighbor
0242                         && ! ignore_branch(node_distance))
0243                     {
0244                         // add current node's data into the list
0245                         m_branches.push(branch_data(node_distance, reverse_level - 1, p.second));
0246                     }
0247                 }
0248             }
0249             else
0250             {
0251                 leaf& n = rtree::get<leaf>(*ptr);
0252                 // search leaf for closest value meeting predicates
0253                 for (auto const& v : rtree::elements(n))
0254                 {
0255                     value_distance_type value_distance; // for distance predicate
0256
0257                     // if value meets predicates
0258                     if (id::predicates_check<id::value_tag>(m_pred, v, m_tr(v), m_strategy)
0259                         // and if distance is ok
0260                         && calculate_value_distance::apply(predicate(), m_tr(v), m_strategy, value_distance))
0261                     {
0262                         // store value
0263                         store_value(value_distance, boost::addressof(v));
0264                     }
0265                 }
0266             }
0267
0268             if (m_branches.empty()
0269                 || ignore_branch(m_branches.top().distance))
0270             {
0271                 break;
0272             }
0273
0274             ptr = m_branches.top().ptr;
0275             reverse_level = m_branches.top().reverse_level;
0276             m_branches.pop();
0277         }
0278
0279         for (auto const& p : m_neighbors)
0280         {
0281             *out_it = *(p.second);
0282             ++out_it;
0283         }
0284
0285         return m_neighbors.size();
0286     }
0287
0288     bool ignore_branch(node_distance_type const& node_distance) const
0289     {
0290         return m_neighbors.size() == max_count()
0291             && m_neighbors.front().first <= node_distance;
0292     }
0293
0294     void store_value(value_distance_type value_distance, const value_type * value_ptr)
0295     {
0296         if (m_neighbors.size() < max_count())
0297         {
0298             m_neighbors.push_back(std::make_pair(value_distance, value_ptr));
0299
0300             if (m_neighbors.size() == max_count())
0301             {
0302                 std::make_heap(m_neighbors.begin(), m_neighbors.end(), pair_first_less());
0303             }
0304         }
0305         else if (value_distance < m_neighbors.front().first)
0306         {
0307             std::pop_heap(m_neighbors.begin(), m_neighbors.end(), pair_first_less());
0308             m_neighbors.back() = std::make_pair(value_distance, value_ptr);
0309             std::push_heap(m_neighbors.begin(), m_neighbors.end(), pair_first_less());
0310         }
0311     }
0312
0313     std::size_t max_count() const
0314     {
0315         return nearest_predicate_access::get(m_pred).count;
0316     }
0317
0318     nearest_predicate_type const& predicate() const
0319     {
0320         return nearest_predicate_access::get(m_pred);
0321     }
0322
0323     translator_type const& m_tr;
0324     strategy_type m_strategy;
0325
0326     Predicates const& m_pred;
0327
0328     branches_type m_branches;
0329     neighbors_type m_neighbors;
0330 };
0331
0332 template <typename MembersHolder, typename Predicates>
0333 class distance_query_incremental
0334 {
0335     typedef typename MembersHolder::value_type value_type;
0336     typedef typename MembersHolder::box_type box_type;
0337     typedef typename MembersHolder::parameters_type parameters_type;
0338     typedef typename MembersHolder::translator_type translator_type;
0339     typedef typename MembersHolder::allocators_type allocators_type;
0340
0341     typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
0342
0343     typedef typename MembersHolder::node node;
0344     typedef typename MembersHolder::internal_node internal_node;
0345     typedef typename MembersHolder::leaf leaf;
0346
0347     typedef index::detail::predicates_element
0348         <
0349             index::detail::predicates_find_distance<Predicates>::value, Predicates
0350         > nearest_predicate_access;
0351     typedef typename nearest_predicate_access::type nearest_predicate_type;
0352     typedef typename indexable_type<translator_type>::type indexable_type;
0353
0354     typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, strategy_type, value_tag> calculate_value_distance;
0355     typedef index::detail::calculate_distance<nearest_predicate_type, box_type, strategy_type, bounds_tag> calculate_node_distance;
0356     typedef typename calculate_value_distance::result_type value_distance_type;
0357     typedef typename calculate_node_distance::result_type node_distance_type;
0358
0359     typedef typename allocators_type::size_type size_type;
0360     typedef typename allocators_type::const_reference const_reference;
0361     typedef typename allocators_type::node_pointer node_pointer;
0362
0363     typedef typename rtree::elements_type<internal_node>::type internal_elements;
0364     typedef typename internal_elements::const_iterator internal_iterator;
0365     typedef typename rtree::elements_type<leaf>::type leaf_elements;
0366
0367     using neighbor_data = std::pair<value_distance_type, const value_type *>;
0368     using neighbors_type = priority_dequeue<neighbor_data, pair_first_greater>;
0369
0370     struct branch_data
0371     {
0372         branch_data(node_distance_type d, size_type rl, node_pointer p)
0373             : distance(d), reverse_level(rl), ptr(p)
0374         {}
0375
0376         node_distance_type distance;
0377         size_type reverse_level;
0378         node_pointer ptr;
0379     };
0380     using branches_type = priority_queue<branch_data, branch_data_comp>;
0381
0382 public:
0383     inline distance_query_incremental()
0384         : m_tr(nullptr)
0385 //        , m_strategy()
0386 //        , m_pred()
0387         , m_neighbors_count(0)
0388         , m_neighbor_ptr(nullptr)
0389     {}
0390
0391     inline distance_query_incremental(Predicates const& pred)
0392         : m_tr(nullptr)
0393 //        , m_strategy()
0394         , m_pred(pred)
0395         , m_neighbors_count(0)
0396         , m_neighbor_ptr(nullptr)
0397     {}
0398
0399     inline distance_query_incremental(MembersHolder const& members, Predicates const& pred)
0400         : m_tr(::boost::addressof(members.translator()))
0401         , m_strategy(index::detail::get_strategy(members.parameters()))
0402         , m_pred(pred)
0403         , m_neighbors_count(0)
0404         , m_neighbor_ptr(nullptr)
0405     {}
0406
0407     const_reference dereference() const
0408     {
0409         return *m_neighbor_ptr;
0410     }
0411
0412     void initialize(MembersHolder const& members)
0413     {
0414         if (0 < max_count())
0415         {
0416             apply(members.root, members.leafs_level);
0417             increment();
0418         }
0419     }
0420
0421     void increment()
0422     {
0423         for (;;)
0424         {
0425             if (m_branches.empty())
0426             {
0427                 // there exists a next closest neighbor so we can increment
0428                 if (! m_neighbors.empty())
0429                 {
0430                     m_neighbor_ptr = m_neighbors.top().second;
0431                     ++m_neighbors_count;
0432                     m_neighbors.pop_top();
0433                 }
0434                 else
0435                 {
0436                     // there aren't any neighbors left, end
0437                     m_neighbor_ptr = nullptr;
0438                     m_neighbors_count = max_count();
0439                 }
0440
0441                 return;
0442             }
0443             else
0444             {
0445                 branch_data const& closest_branch = m_branches.top();
0446
0447                 // if next neighbor is closer or as close as the closest branch, set next neighbor
0448                 if (! m_neighbors.empty() && m_neighbors.top().first <= closest_branch.distance )
0449                 {
0450                     m_neighbor_ptr = m_neighbors.top().second;
0451                     ++m_neighbors_count;
0452                     m_neighbors.pop_top();
0453                     return;
0454                 }
0455
0456                 BOOST_GEOMETRY_INDEX_ASSERT(m_neighbors_count + m_neighbors.size() <= max_count(), "unexpected neighbors count");
0457
0458                 // if there is enough neighbors and there is no closer branch
0459                 if (ignore_branch_or_value(closest_branch.distance))
0460                 {
0461                     m_branches.clear();
0462                     continue;
0463                 }
0464                 else
0465                 {
0466                     node_pointer ptr = closest_branch.ptr;
0467                     size_type reverse_level = closest_branch.reverse_level;
0468                     m_branches.pop();
0469
0470                     apply(ptr, reverse_level);
0471                 }
0472             }
0473         }
0474     }
0475
0476     bool is_end() const
0477     {
0478         return m_neighbor_ptr == nullptr;
0479     }
0480
0481     friend bool operator==(distance_query_incremental const& l, distance_query_incremental const& r)
0482     {
0483         return l.m_neighbors_count == r.m_neighbors_count;
0484     }
0485
0486 private:
0487     void apply(node_pointer ptr, size_type reverse_level)
0488     {
0489         namespace id = index::detail;
0490         // Put node's elements into the list of active branches if those elements meets predicates
0491         // and distance predicates(currently not used)
0492         // and aren't further than found neighbours (if there is enough neighbours)
0493         if (reverse_level > 0)
0494         {
0495             internal_node& n = rtree::get<internal_node>(*ptr);
0496             // fill active branch list array of nodes meeting predicates
0497             for (auto const& p : rtree::elements(n))
0498             {
0499                 node_distance_type node_distance; // for distance predicate
0500
0501                 // if current node meets predicates (0 is dummy value)
0502                 if (id::predicates_check<id::bounds_tag>(m_pred, 0, p.first, m_strategy)
0503                     // and if distance is ok
0504                     && calculate_node_distance::apply(predicate(), p.first, m_strategy, node_distance)
0505                     // and if current node is closer than the furthest neighbor
0506                     && ! ignore_branch_or_value(node_distance))
0507                 {
0508                     // add current node into the queue
0509                     m_branches.push(branch_data(node_distance, reverse_level - 1, p.second));
0510                 }
0511             }
0512         }
0513         // Put values into the list of neighbours if those values meets predicates
0514         // and distance predicates(currently not used)
0515         // and aren't further than already found neighbours (if there is enough neighbours)
0516         else
0517         {
0518             leaf& n = rtree::get<leaf>(*ptr);
0519             // search leaf for closest value meeting predicates
0520             for (auto const& v : rtree::elements(n))
0521             {
0522                 value_distance_type value_distance; // for distance predicate
0523
0524                 // if value meets predicates
0525                 if (id::predicates_check<id::value_tag>(m_pred, v, (*m_tr)(v), m_strategy)
0526                     // and if distance is ok
0527                     && calculate_value_distance::apply(predicate(), (*m_tr)(v), m_strategy, value_distance)
0528                     // and if current value is closer than the furthest neighbor
0529                     && ! ignore_branch_or_value(value_distance))
0530                 {
0531                     // add current value into the queue
0532                     m_neighbors.push(std::make_pair(value_distance, boost::addressof(v)));
0533
0534                     // remove unneeded value
0535                     if (m_neighbors_count + m_neighbors.size() > max_count())
0536                     {
0537                         m_neighbors.pop_bottom();
0538                     }
0539                 }
0540             }
0541         }
0542     }
0543
0544     template <typename Distance>
0545     bool ignore_branch_or_value(Distance const& distance)
0546     {
0547         return m_neighbors_count + m_neighbors.size() == max_count()
0548             && (m_neighbors.empty() || m_neighbors.bottom().first <= distance);
0549     }
0550
0551     std::size_t max_count() const
0552     {
0553         return nearest_predicate_access::get(m_pred).count;
0554     }
0555
0556     nearest_predicate_type const& predicate() const
0557     {
0558         return nearest_predicate_access::get(m_pred);
0559     }
0560
0561     const translator_type * m_tr;
0562     strategy_type m_strategy;
0563
0564     Predicates m_pred;
0565
0566     branches_type m_branches;
0567     neighbors_type m_neighbors;
0568     size_type m_neighbors_count;
0569     const value_type * m_neighbor_ptr;
0570 };
0571
0572 }}} // namespace detail::rtree::visitors
0573
0574 }}} // namespace boost::geometry::index
0575
0576 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_DISTANCE_QUERY_HPP