1 // Boost.Geometry Index
2 //
3 // R-tree spatial 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_SPATIAL_QUERY_HPP
16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
17 
18 namespace boost { namespace geometry { namespace index {
19 
20 namespace detail { namespace rtree { namespace visitors {
21 
22 template <typename MembersHolder, typename Predicates, typename OutIter>
23 struct spatial_query
24     : public MembersHolder::visitor_const
25 {
26     typedef typename MembersHolder::parameters_type parameters_type;
27     typedef typename MembersHolder::translator_type translator_type;
28     typedef typename MembersHolder::allocators_type allocators_type;
29 
30     typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
31 
32     typedef typename MembersHolder::node node;
33     typedef typename MembersHolder::internal_node internal_node;
34     typedef typename MembersHolder::leaf leaf;
35 
36     typedef typename allocators_type::size_type size_type;
37 
38     static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
39 
spatial_queryboost::geometry::index::detail::rtree::visitors::spatial_query40     inline spatial_query(parameters_type const& par, translator_type const& t, Predicates const& p, OutIter out_it)
41         : tr(t), pred(p), out_iter(out_it), found_count(0), strategy(index::detail::get_strategy(par))
42     {}
43 
operator ()boost::geometry::index::detail::rtree::visitors::spatial_query44     inline void operator()(internal_node const& n)
45     {
46         typedef typename rtree::elements_type<internal_node>::type elements_type;
47         elements_type const& elements = rtree::elements(n);
48 
49         // traverse nodes meeting predicates
50         for (typename elements_type::const_iterator it = elements.begin();
51             it != elements.end(); ++it)
52         {
53             // if node meets predicates
54             // 0 - dummy value
55             if ( index::detail::predicates_check
56                     <
57                         index::detail::bounds_tag, 0, predicates_len
58                     >(pred, 0, it->first, strategy) )
59             {
60                 rtree::apply_visitor(*this, *it->second);
61             }
62         }
63     }
64 
operator ()boost::geometry::index::detail::rtree::visitors::spatial_query65     inline void operator()(leaf const& n)
66     {
67         typedef typename rtree::elements_type<leaf>::type elements_type;
68         elements_type const& elements = rtree::elements(n);
69 
70         // get all values meeting predicates
71         for (typename elements_type::const_iterator it = elements.begin();
72             it != elements.end(); ++it)
73         {
74             // if value meets predicates
75             if ( index::detail::predicates_check
76                     <
77                         index::detail::value_tag, 0, predicates_len
78                     >(pred, *it, tr(*it), strategy) )
79             {
80                 *out_iter = *it;
81                 ++out_iter;
82 
83                 ++found_count;
84             }
85         }
86     }
87 
88     translator_type const& tr;
89 
90     Predicates pred;
91 
92     OutIter out_iter;
93     size_type found_count;
94 
95     strategy_type strategy;
96 };
97 
98 template <typename MembersHolder, typename Predicates>
99 class spatial_query_incremental
100     : public MembersHolder::visitor_const
101 {
102     typedef typename MembersHolder::value_type value_type;
103     typedef typename MembersHolder::parameters_type parameters_type;
104     typedef typename MembersHolder::translator_type translator_type;
105     typedef typename MembersHolder::allocators_type allocators_type;
106 
107     typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
108 
109 public:
110     typedef typename MembersHolder::node node;
111     typedef typename MembersHolder::internal_node internal_node;
112     typedef typename MembersHolder::leaf leaf;
113 
114     typedef typename allocators_type::size_type size_type;
115     typedef typename allocators_type::const_reference const_reference;
116     typedef typename allocators_type::node_pointer node_pointer;
117 
118     typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
119     typedef typename rtree::elements_type<leaf>::type leaf_elements;
120     typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
121 
122     static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
123 
spatial_query_incremental()124     inline spatial_query_incremental()
125         : m_translator(NULL)
126 //        , m_pred()
127         , m_values(NULL)
128         , m_current()
129 //        , m_strategy()
130     {}
131 
spatial_query_incremental(parameters_type const & params,translator_type const & t,Predicates const & p)132     inline spatial_query_incremental(parameters_type const& params, translator_type const& t, Predicates const& p)
133         : m_translator(::boost::addressof(t))
134         , m_pred(p)
135         , m_values(NULL)
136         , m_current()
137         , m_strategy(index::detail::get_strategy(params))
138     {}
139 
operator ()(internal_node const & n)140     inline void operator()(internal_node const& n)
141     {
142         typedef typename rtree::elements_type<internal_node>::type elements_type;
143         elements_type const& elements = rtree::elements(n);
144 
145         m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
146     }
147 
operator ()(leaf const & n)148     inline void operator()(leaf const& n)
149     {
150         m_values = ::boost::addressof(rtree::elements(n));
151         m_current = rtree::elements(n).begin();
152     }
153 
dereference() const154     const_reference dereference() const
155     {
156         BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
157         return *m_current;
158     }
159 
initialize(node_pointer root)160     void initialize(node_pointer root)
161     {
162         rtree::apply_visitor(*this, *root);
163         search_value();
164     }
165 
increment()166     void increment()
167     {
168         ++m_current;
169         search_value();
170     }
171 
search_value()172     void search_value()
173     {
174         for (;;)
175         {
176             // if leaf is choosen, move to the next value in leaf
177             if ( m_values )
178             {
179                 if ( m_current != m_values->end() )
180                 {
181                     // return if next value is found
182                     value_type const& v = *m_current;
183                     if (index::detail::predicates_check
184                             <
185                                index::detail::value_tag, 0, predicates_len
186                             >(m_pred, v, (*m_translator)(v), m_strategy))
187                     {
188                         return;
189                     }
190 
191                     ++m_current;
192                 }
193                 // no more values, clear current leaf
194                 else
195                 {
196                     m_values = 0;
197                 }
198             }
199             // if leaf isn't choosen, move to the next leaf
200             else
201             {
202                 // return if there is no more nodes to traverse
203                 if ( m_internal_stack.empty() )
204                     return;
205 
206                 // no more children in current node, remove it from stack
207                 if ( m_internal_stack.back().first == m_internal_stack.back().second )
208                 {
209                     m_internal_stack.pop_back();
210                     continue;
211                 }
212 
213                 internal_iterator it = m_internal_stack.back().first;
214                 ++m_internal_stack.back().first;
215 
216                 // next node is found, push it to the stack
217                 if (index::detail::predicates_check
218                         <
219                             index::detail::bounds_tag, 0, predicates_len
220                         >(m_pred, 0, it->first, m_strategy))
221                 {
222                     rtree::apply_visitor(*this, *(it->second));
223                 }
224             }
225         }
226     }
227 
is_end() const228     bool is_end() const
229     {
230         return 0 == m_values;
231     }
232 
operator ==(spatial_query_incremental const & l,spatial_query_incremental const & r)233     friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r)
234     {
235         return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
236     }
237 
238 private:
239 
240     const translator_type * m_translator;
241 
242     Predicates m_pred;
243 
244     std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack;
245     const leaf_elements * m_values;
246     leaf_iterator m_current;
247 
248     strategy_type m_strategy;
249 };
250 
251 }}} // namespace detail::rtree::visitors
252 
253 }}} // namespace boost::geometry::index
254 
255 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
256