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