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 spatial_queryboost::geometry::index::detail::rtree::visitors::spatial_query30 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 operator ()boost::geometry::index::detail::rtree::visitors::spatial_query34 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 operator ()boost::geometry::index::detail::rtree::visitors::spatial_query50 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 spatial_query_incremental()97 inline spatial_query_incremental() 98 : m_translator(NULL) 99 // , m_pred() 100 , m_values(NULL) 101 , m_current() 102 {} 103 spatial_query_incremental(Translator const & t,Predicates const & p)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 operator ()(internal_node const & n)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 operator ()(leaf const & n)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 dereference() const125 const_reference dereference() const 126 { 127 BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable"); 128 return *m_current; 129 } 130 initialize(node_pointer root)131 void initialize(node_pointer root) 132 { 133 rtree::apply_visitor(*this, *root); 134 search_value(); 135 } 136 increment()137 void increment() 138 { 139 ++m_current; 140 search_value(); 141 } 142 search_value()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 is_end() const189 bool is_end() const 190 { 191 return 0 == m_values; 192 } 193 operator ==(spatial_query_incremental const & l,spatial_query_incremental const & r)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 215