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