ceph/src/boost/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp

   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
  37     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
  41     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
  62     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
 117     inline spatial_query_incremental()
 118         : m_translator(NULL)
 119 //        , m_pred()
 120         , m_values(NULL)
 121         , m_current()
 122 //        , m_strategy()
 123     {}
 124
 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
 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
 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
 147     const_reference dereference() const
 148     {
 149         BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
 150         return *m_current;
 151     }
 152
 153     void initialize(node_pointer root)
 154     {
 155         rtree::apply_visitor(*this, *root);
 156         search_value();
 157     }
 158
 159     void increment()
 160     {
 161         ++m_current;
 162         search_value();
 163     }
 164
 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
 221     bool is_end() const
 222     {
 223         return 0 == m_values;
 224     }
 225
 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