1 // Boost.Geometry Index
3 // R-tree spatial query visitor implementation
5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
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)
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
14 namespace boost { namespace geometry { namespace index {
16 namespace detail { namespace rtree { namespace visitors {
18 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, typename OutIter>
20 : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
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;
26 typedef typename Allocators::size_type size_type;
28 static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
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)
34 inline void operator()(internal_node const& n)
36 typedef typename rtree::elements_type<internal_node>::type elements_type;
37 elements_type const& elements = rtree::elements(n);
39 // traverse nodes meeting predicates
40 for (typename elements_type::const_iterator it = elements.begin();
41 it != elements.end(); ++it)
43 // if node meets predicates
45 if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(pred, 0, it->first) )
46 rtree::apply_visitor(*this, *it->second);
50 inline void operator()(leaf const& n)
52 typedef typename rtree::elements_type<leaf>::type elements_type;
53 elements_type const& elements = rtree::elements(n);
55 // get all values meeting predicates
56 for (typename elements_type::const_iterator it = elements.begin();
57 it != elements.end(); ++it)
59 // if value meets predicates
60 if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(pred, *it, tr(*it)) )
75 size_type found_count;
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
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;
87 typedef typename Allocators::size_type size_type;
88 typedef typename Allocators::const_reference const_reference;
89 typedef typename Allocators::node_pointer node_pointer;
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;
95 static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
97 inline spatial_query_incremental()
104 inline spatial_query_incremental(Translator const& t, Predicates const& p)
105 : m_translator(::boost::addressof(t))
111 inline void operator()(internal_node const& n)
113 typedef typename rtree::elements_type<internal_node>::type elements_type;
114 elements_type const& elements = rtree::elements(n);
116 m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
119 inline void operator()(leaf const& n)
121 m_values = ::boost::addressof(rtree::elements(n));
122 m_current = rtree::elements(n).begin();
125 const_reference dereference() const
127 BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
131 void initialize(node_pointer root)
133 rtree::apply_visitor(*this, *root);
147 // if leaf is choosen, move to the next value in leaf
150 if ( m_current != m_values->end() )
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)) )
159 // no more values, clear current leaf
165 // if leaf isn't choosen, move to the next leaf
168 // return if there is no more nodes to traverse
169 if ( m_internal_stack.empty() )
172 // no more children in current node, remove it from stack
173 if ( m_internal_stack.back().first == m_internal_stack.back().second )
175 m_internal_stack.pop_back();
179 internal_iterator it = m_internal_stack.back().first;
180 ++m_internal_stack.back().first;
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));
191 return 0 == m_values;
194 friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r)
196 return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
201 const Translator * m_translator;
205 std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack;
206 const leaf_elements * m_values;
207 leaf_iterator m_current;
210 }}} // namespace detail::rtree::visitors
212 }}} // namespace boost::geometry::index
214 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP