]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree spatial query visitor implementation | |
4 | // | |
5 | // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
7 | // Use, modification and distribution is subject to the Boost Software License, | |
8 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
9 | // http://www.boost.org/LICENSE_1_0.txt) | |
10 | ||
11 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP | |
12 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP | |
13 | ||
14 | namespace boost { namespace geometry { namespace index { | |
15 | ||
16 | namespace detail { namespace rtree { namespace visitors { | |
17 | ||
18 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, typename OutIter> | |
19 | struct spatial_query | |
20 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
21 | { | |
22 | typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
23 | typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
24 | typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
25 | ||
26 | typedef typename Allocators::size_type size_type; | |
27 | ||
28 | static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value; | |
29 | ||
30 | inline spatial_query(Translator const& t, Predicates const& p, OutIter out_it) | |
31 | : tr(t), pred(p), out_iter(out_it), found_count(0) | |
32 | {} | |
33 | ||
34 | inline void operator()(internal_node const& n) | |
35 | { | |
36 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
37 | elements_type const& elements = rtree::elements(n); | |
38 | ||
39 | // traverse nodes meeting predicates | |
40 | for (typename elements_type::const_iterator it = elements.begin(); | |
41 | it != elements.end(); ++it) | |
42 | { | |
43 | // if node meets predicates | |
44 | // 0 - dummy value | |
45 | if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(pred, 0, it->first) ) | |
46 | rtree::apply_visitor(*this, *it->second); | |
47 | } | |
48 | } | |
49 | ||
50 | inline void operator()(leaf const& n) | |
51 | { | |
52 | typedef typename rtree::elements_type<leaf>::type elements_type; | |
53 | elements_type const& elements = rtree::elements(n); | |
54 | ||
55 | // get all values meeting predicates | |
56 | for (typename elements_type::const_iterator it = elements.begin(); | |
57 | it != elements.end(); ++it) | |
58 | { | |
59 | // if value meets predicates | |
60 | if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(pred, *it, tr(*it)) ) | |
61 | { | |
62 | *out_iter = *it; | |
63 | ++out_iter; | |
64 | ||
65 | ++found_count; | |
66 | } | |
67 | } | |
68 | } | |
69 | ||
70 | Translator const& tr; | |
71 | ||
72 | Predicates pred; | |
73 | ||
74 | OutIter out_iter; | |
75 | size_type found_count; | |
76 | }; | |
77 | ||
78 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates> | |
79 | class spatial_query_incremental | |
80 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
81 | { | |
82 | public: | |
83 | typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
84 | typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
85 | typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
86 | ||
87 | typedef typename Allocators::size_type size_type; | |
88 | typedef typename Allocators::const_reference const_reference; | |
89 | typedef typename Allocators::node_pointer node_pointer; | |
90 | ||
91 | typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator; | |
92 | typedef typename rtree::elements_type<leaf>::type leaf_elements; | |
93 | typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator; | |
94 | ||
95 | static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value; | |
96 | ||
97 | inline spatial_query_incremental() | |
98 | : m_translator(NULL) | |
99 | // , m_pred() | |
100 | , m_values(NULL) | |
101 | , m_current() | |
102 | {} | |
103 | ||
104 | inline spatial_query_incremental(Translator const& t, Predicates const& p) | |
105 | : m_translator(::boost::addressof(t)) | |
106 | , m_pred(p) | |
107 | , m_values(NULL) | |
108 | , m_current() | |
109 | {} | |
110 | ||
111 | inline void operator()(internal_node const& n) | |
112 | { | |
113 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
114 | elements_type const& elements = rtree::elements(n); | |
115 | ||
116 | m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end())); | |
117 | } | |
118 | ||
119 | inline void operator()(leaf const& n) | |
120 | { | |
121 | m_values = ::boost::addressof(rtree::elements(n)); | |
122 | m_current = rtree::elements(n).begin(); | |
123 | } | |
124 | ||
125 | const_reference dereference() const | |
126 | { | |
127 | BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable"); | |
128 | return *m_current; | |
129 | } | |
130 | ||
131 | void initialize(node_pointer root) | |
132 | { | |
133 | rtree::apply_visitor(*this, *root); | |
134 | search_value(); | |
135 | } | |
136 | ||
137 | void increment() | |
138 | { | |
139 | ++m_current; | |
140 | search_value(); | |
141 | } | |
142 | ||
143 | void search_value() | |
144 | { | |
145 | for (;;) | |
146 | { | |
147 | // if leaf is choosen, move to the next value in leaf | |
148 | if ( m_values ) | |
149 | { | |
150 | if ( m_current != m_values->end() ) | |
151 | { | |
152 | // return if next value is found | |
153 | Value const& v = *m_current; | |
154 | if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, v, (*m_translator)(v)) ) | |
155 | return; | |
156 | ||
157 | ++m_current; | |
158 | } | |
159 | // no more values, clear current leaf | |
160 | else | |
161 | { | |
162 | m_values = 0; | |
163 | } | |
164 | } | |
165 | // if leaf isn't choosen, move to the next leaf | |
166 | else | |
167 | { | |
168 | // return if there is no more nodes to traverse | |
169 | if ( m_internal_stack.empty() ) | |
170 | return; | |
171 | ||
172 | // no more children in current node, remove it from stack | |
173 | if ( m_internal_stack.back().first == m_internal_stack.back().second ) | |
174 | { | |
175 | m_internal_stack.pop_back(); | |
176 | continue; | |
177 | } | |
178 | ||
179 | internal_iterator it = m_internal_stack.back().first; | |
180 | ++m_internal_stack.back().first; | |
181 | ||
182 | // next node is found, push it to the stack | |
183 | if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) ) | |
184 | rtree::apply_visitor(*this, *(it->second)); | |
185 | } | |
186 | } | |
187 | } | |
188 | ||
189 | bool is_end() const | |
190 | { | |
191 | return 0 == m_values; | |
192 | } | |
193 | ||
194 | friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r) | |
195 | { | |
196 | return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current ); | |
197 | } | |
198 | ||
199 | private: | |
200 | ||
201 | const Translator * m_translator; | |
202 | ||
203 | Predicates m_pred; | |
204 | ||
205 | std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack; | |
206 | const leaf_elements * m_values; | |
207 | leaf_iterator m_current; | |
208 | }; | |
209 | ||
210 | }}} // namespace detail::rtree::visitors | |
211 | ||
212 | }}} // namespace boost::geometry::index | |
213 | ||
214 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP |