rtree/visitors/spatial_query.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree spatial 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_SPATIAL_QUERY_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
0018
0019 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0020 #include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
0021 #include <boost/geometry/index/detail/predicates.hpp>
0022 #include <boost/geometry/index/parameters.hpp>
0023
0024 namespace boost { namespace geometry { namespace index {
0025
0026 namespace detail { namespace rtree { namespace visitors {
0027
0028 template <typename MembersHolder, typename Predicates, typename OutIter>
0029 struct spatial_query
0030 {
0031     typedef typename MembersHolder::parameters_type parameters_type;
0032     typedef typename MembersHolder::translator_type translator_type;
0033     typedef typename MembersHolder::allocators_type allocators_type;
0034
0035     typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
0036
0037     typedef typename MembersHolder::node node;
0038     typedef typename MembersHolder::internal_node internal_node;
0039     typedef typename MembersHolder::leaf leaf;
0040
0041     typedef typename allocators_type::node_pointer node_pointer;
0042     typedef typename allocators_type::size_type size_type;
0043
0044     spatial_query(MembersHolder const& members, Predicates const& p, OutIter out_it)
0045         : m_tr(members.translator())
0046         , m_strategy(index::detail::get_strategy(members.parameters()))
0047         , m_pred(p)
0048         , m_out_iter(out_it)
0049         , m_found_count(0)
0050     {}
0051
0052     size_type apply(node_pointer ptr, size_type reverse_level)
0053     {
0054         namespace id = index::detail;
0055         if (reverse_level > 0)
0056         {
0057             internal_node& n = rtree::get<internal_node>(*ptr);
0058             // traverse nodes meeting predicates
0059             for (auto const& p : rtree::elements(n))
0060             {
0061                 // if node meets predicates (0 is dummy value)
0062                 if (id::predicates_check<id::bounds_tag>(m_pred, 0, p.first, m_strategy))
0063                 {
0064                     apply(p.second, reverse_level - 1);
0065                 }
0066             }
0067         }
0068         else
0069         {
0070             leaf& n = rtree::get<leaf>(*ptr);
0071             // get all values meeting predicates
0072             for (auto const& v : rtree::elements(n))
0073             {
0074                 // if value meets predicates
0075                 if (id::predicates_check<id::value_tag>(m_pred, v, m_tr(v), m_strategy))
0076                 {
0077                     *m_out_iter = v;
0078                     ++m_out_iter;
0079                     ++m_found_count;
0080                 }
0081             }
0082         }
0083
0084         return m_found_count;
0085     }
0086
0087     size_type apply(MembersHolder const& members)
0088     {
0089         return apply(members.root, members.leafs_level);
0090     }
0091
0092 private:
0093     translator_type const& m_tr;
0094     strategy_type m_strategy;
0095
0096     Predicates const& m_pred;
0097     OutIter m_out_iter;
0098
0099     size_type m_found_count;
0100 };
0101
0102 template <typename MembersHolder, typename Predicates>
0103 class spatial_query_incremental
0104 {
0105     typedef typename MembersHolder::value_type value_type;
0106     typedef typename MembersHolder::parameters_type parameters_type;
0107     typedef typename MembersHolder::translator_type translator_type;
0108     typedef typename MembersHolder::allocators_type allocators_type;
0109
0110     typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
0111
0112     typedef typename MembersHolder::node node;
0113     typedef typename MembersHolder::internal_node internal_node;
0114     typedef typename MembersHolder::leaf leaf;
0115
0116     typedef typename allocators_type::size_type size_type;
0117     typedef typename allocators_type::const_reference const_reference;
0118     typedef typename allocators_type::node_pointer node_pointer;
0119
0120     typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
0121     typedef typename rtree::elements_type<leaf>::type leaf_elements;
0122     typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
0123
0124     struct internal_data
0125     {
0126         internal_data(internal_iterator f, internal_iterator l, size_type rl)
0127             : first(f), last(l), reverse_level(rl)
0128         {}
0129         internal_iterator first;
0130         internal_iterator last;
0131         size_type reverse_level;
0132     };
0133
0134 public:
0135     spatial_query_incremental()
0136         : m_translator(nullptr)
0137 //        , m_strategy()
0138 //        , m_pred()
0139         , m_values(nullptr)
0140         , m_current()
0141     {}
0142
0143     spatial_query_incremental(Predicates const& p)
0144         : m_translator(nullptr)
0145 //        , m_strategy()
0146         , m_pred(p)
0147         , m_values(nullptr)
0148         , m_current()
0149     {}
0150
0151     spatial_query_incremental(MembersHolder const& members, Predicates const& p)
0152         : m_translator(::boost::addressof(members.translator()))
0153         , m_strategy(index::detail::get_strategy(members.parameters()))
0154         , m_pred(p)
0155         , m_values(nullptr)
0156         , m_current()
0157     {}
0158
0159     const_reference dereference() const
0160     {
0161         BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
0162         return *m_current;
0163     }
0164
0165     void initialize(MembersHolder const& members)
0166     {
0167         apply(members.root, members.leafs_level);
0168         search_value();
0169     }
0170
0171     void increment()
0172     {
0173         ++m_current;
0174         search_value();
0175     }
0176
0177     bool is_end() const
0178     {
0179         return 0 == m_values;
0180     }
0181
0182     friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r)
0183     {
0184         return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current);
0185     }
0186
0187 private:
0188     void apply(node_pointer ptr, size_type reverse_level)
0189     {
0190         namespace id = index::detail;
0191
0192         if (reverse_level > 0)
0193         {
0194             internal_node& n = rtree::get<internal_node>(*ptr);
0195             auto const& elements = rtree::elements(n);
0196             m_internal_stack.push_back(internal_data(elements.begin(), elements.end(), reverse_level - 1));
0197         }
0198         else
0199         {
0200             leaf& n = rtree::get<leaf>(*ptr);
0201             m_values = ::boost::addressof(rtree::elements(n));
0202             m_current = rtree::elements(n).begin();
0203         }
0204     }
0205
0206     void search_value()
0207     {
0208         namespace id = index::detail;
0209         for (;;)
0210         {
0211             // if leaf is choosen, move to the next value in leaf
0212             if ( m_values )
0213             {
0214                 if ( m_current != m_values->end() )
0215                 {
0216                     // return if next value is found
0217                     value_type const& v = *m_current;
0218                     if (id::predicates_check<id::value_tag>(m_pred, v, (*m_translator)(v), m_strategy))
0219                     {
0220                         return;
0221                     }
0222
0223                     ++m_current;
0224                 }
0225                 // no more values, clear current leaf
0226                 else
0227                 {
0228                     m_values = 0;
0229                 }
0230             }
0231             // if leaf isn't choosen, move to the next leaf
0232             else
0233             {
0234                 // return if there is no more nodes to traverse
0235                 if (m_internal_stack.empty())
0236                 {
0237                     return;
0238                 }
0239
0240                 internal_data& current_data = m_internal_stack.back();
0241
0242                 // no more children in current node, remove it from stack
0243                 if (current_data.first == current_data.last)
0244                 {
0245                     m_internal_stack.pop_back();
0246                     continue;
0247                 }
0248
0249                 internal_iterator it = current_data.first;
0250                 ++current_data.first;
0251
0252                 // next node is found, push it to the stack
0253                 if (id::predicates_check<id::bounds_tag>(m_pred, 0, it->first, m_strategy))
0254                 {
0255                     apply(it->second, current_data.reverse_level);
0256                 }
0257             }
0258         }
0259     }
0260
0261     const translator_type * m_translator;
0262     strategy_type m_strategy;
0263
0264     Predicates m_pred;
0265
0266     std::vector<internal_data> m_internal_stack;
0267     const leaf_elements * m_values;
0268     leaf_iterator m_current;
0269 };
0270
0271 }}} // namespace detail::rtree::visitors
0272
0273 }}} // namespace boost::geometry::index
0274
0275 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP