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