ceph/src/boost/boost/geometry/index/detail/rtree/query_iterators.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree query iterators
   4 //
   5 // Copyright (c) 2011-2015 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_QUERY_ITERATORS_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
  13
  14 #include <boost/scoped_ptr.hpp>
  15
  16 //#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
  17
  18 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
  19
  20 template <typename Value, typename Allocators>
  21 struct end_query_iterator
  22 {
  23     typedef std::forward_iterator_tag iterator_category;
  24     typedef Value value_type;
  25     typedef typename Allocators::const_reference reference;
  26     typedef typename Allocators::difference_type difference_type;
  27     typedef typename Allocators::const_pointer pointer;
  28
  29     reference operator*() const
  30     {
  31         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not dereferencable");
  32         pointer p(0);
  33         return *p;
  34     }
  35
  36     const value_type * operator->() const
  37     {
  38         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not dereferencable");
  39         const value_type * p = 0;
  40         return p;
  41     }
  42
  43     end_query_iterator & operator++()
  44     {
  45         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not incrementable");
  46         return *this;
  47     }
  48
  49     end_query_iterator operator++(int)
  50     {
  51         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not incrementable");
  52         return *this;
  53     }
  54
  55     friend bool operator==(end_query_iterator const& /*l*/, end_query_iterator const& /*r*/)
  56     {
  57         return true;
  58     }
  59 };
  60
  61 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates>
  62 class spatial_query_iterator
  63 {
  64     typedef typename Options::parameters_type parameters_type;
  65     typedef visitors::spatial_query_incremental<Value, Options, Translator, Box, Allocators, Predicates> visitor_type;
  66     typedef typename visitor_type::node_pointer node_pointer;
  67
  68 public:
  69     typedef std::forward_iterator_tag iterator_category;
  70     typedef Value value_type;
  71     typedef typename Allocators::const_reference reference;
  72     typedef typename Allocators::difference_type difference_type;
  73     typedef typename Allocators::const_pointer pointer;
  74
  75     inline spatial_query_iterator()
  76     {}
  77
  78     inline spatial_query_iterator(parameters_type const& par, Translator const& t, Predicates const& p)
  79         : m_visitor(par, t, p)
  80     {}
  81
  82     inline spatial_query_iterator(node_pointer root, parameters_type const& par, Translator const& t, Predicates const& p)
  83         : m_visitor(par, t, p)
  84     {
  85         m_visitor.initialize(root);
  86     }
  87
  88     reference operator*() const
  89     {
  90         return m_visitor.dereference();
  91     }
  92
  93     const value_type * operator->() const
  94     {
  95         return boost::addressof(m_visitor.dereference());
  96     }
  97
  98     spatial_query_iterator & operator++()
  99     {
 100         m_visitor.increment();
 101         return *this;
 102     }
 103
 104     spatial_query_iterator operator++(int)
 105     {
 106         spatial_query_iterator temp = *this;
 107         this->operator++();
 108         return temp;
 109     }
 110
 111     friend bool operator==(spatial_query_iterator const& l, spatial_query_iterator const& r)
 112     {
 113         return l.m_visitor == r.m_visitor;
 114     }
 115
 116     friend bool operator==(spatial_query_iterator const& l, end_query_iterator<Value, Allocators> const& /*r*/)
 117     {
 118         return l.m_visitor.is_end();
 119     }
 120
 121     friend bool operator==(end_query_iterator<Value, Allocators> const& /*l*/, spatial_query_iterator const& r)
 122     {
 123         return r.m_visitor.is_end();
 124     }
 125
 126 private:
 127     visitor_type m_visitor;
 128 };
 129
 130 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, unsigned NearestPredicateIndex>
 131 class distance_query_iterator
 132 {
 133     typedef typename Options::parameters_type parameters_type;
 134     typedef visitors::distance_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type;
 135     typedef typename visitor_type::node_pointer node_pointer;
 136
 137 public:
 138     typedef std::forward_iterator_tag iterator_category;
 139     typedef Value value_type;
 140     typedef typename Allocators::const_reference reference;
 141     typedef typename Allocators::difference_type difference_type;
 142     typedef typename Allocators::const_pointer pointer;
 143
 144     inline distance_query_iterator()
 145     {}
 146
 147     inline distance_query_iterator(parameters_type const& par, Translator const& t, Predicates const& p)
 148         : m_visitor(par, t, p)
 149     {}
 150
 151     inline distance_query_iterator(node_pointer root, parameters_type const& par, Translator const& t, Predicates const& p)
 152         : m_visitor(par, t, p)
 153     {
 154         m_visitor.initialize(root);
 155     }
 156
 157     reference operator*() const
 158     {
 159         return m_visitor.dereference();
 160     }
 161
 162     const value_type * operator->() const
 163     {
 164         return boost::addressof(m_visitor.dereference());
 165     }
 166
 167     distance_query_iterator & operator++()
 168     {
 169         m_visitor.increment();
 170         return *this;
 171     }
 172
 173     distance_query_iterator operator++(int)
 174     {
 175         distance_query_iterator temp = *this;
 176         this->operator++();
 177         return temp;
 178     }
 179
 180     friend bool operator==(distance_query_iterator const& l, distance_query_iterator const& r)
 181     {
 182         return l.m_visitor == r.m_visitor;
 183     }
 184
 185     friend bool operator==(distance_query_iterator const& l, end_query_iterator<Value, Allocators> const& /*r*/)
 186     {
 187         return l.m_visitor.is_end();
 188     }
 189
 190     friend bool operator==(end_query_iterator<Value, Allocators> const& /*l*/, distance_query_iterator const& r)
 191     {
 192         return r.m_visitor.is_end();
 193     }
 194
 195 private:
 196     visitor_type m_visitor;
 197 };
 198
 199
 200 template <typename L, typename R>
 201 inline bool operator!=(L const& l, R const& r)
 202 {
 203     return !(l == r);
 204 }
 205
 206
 207 template <typename Value, typename Allocators>
 208 class query_iterator_base
 209 {
 210 public:
 211     typedef std::forward_iterator_tag iterator_category;
 212     typedef Value value_type;
 213     typedef typename Allocators::const_reference reference;
 214     typedef typename Allocators::difference_type difference_type;
 215     typedef typename Allocators::const_pointer pointer;
 216
 217     virtual ~query_iterator_base() {}
 218
 219     virtual query_iterator_base * clone() const = 0;
 220
 221     virtual bool is_end() const = 0;
 222     virtual reference dereference() const = 0;
 223     virtual void increment() = 0;
 224     virtual bool equals(query_iterator_base const&) const = 0;
 225 };
 226
 227 template <typename Value, typename Allocators, typename Iterator>
 228 class query_iterator_wrapper
 229     : public query_iterator_base<Value, Allocators>
 230 {
 231     typedef query_iterator_base<Value, Allocators> base_t;
 232
 233 public:
 234     typedef std::forward_iterator_tag iterator_category;
 235     typedef Value value_type;
 236     typedef typename Allocators::const_reference reference;
 237     typedef typename Allocators::difference_type difference_type;
 238     typedef typename Allocators::const_pointer pointer;
 239
 240     query_iterator_wrapper() : m_iterator() {}
 241     explicit query_iterator_wrapper(Iterator const& it) : m_iterator(it) {}
 242
 243     virtual base_t * clone() const { return new query_iterator_wrapper(m_iterator); }
 244
 245     virtual bool is_end() const { return m_iterator == end_query_iterator<Value, Allocators>(); }
 246     virtual reference dereference() const { return *m_iterator; }
 247     virtual void increment() { ++m_iterator; }
 248     virtual bool equals(base_t const& r) const
 249     {
 250         const query_iterator_wrapper * p = dynamic_cast<const query_iterator_wrapper *>(boost::addressof(r));
 251         BOOST_GEOMETRY_INDEX_ASSERT(p, "iterators can't be compared");
 252         return m_iterator == p->m_iterator;
 253     }
 254
 255 private:
 256     Iterator m_iterator;
 257 };
 258
 259
 260 template <typename Value, typename Allocators>
 261 class query_iterator
 262 {
 263     typedef query_iterator_base<Value, Allocators> iterator_base;
 264     typedef boost::scoped_ptr<iterator_base> iterator_ptr;
 265
 266 public:
 267     typedef std::forward_iterator_tag iterator_category;
 268     typedef Value value_type;
 269     typedef typename Allocators::const_reference reference;
 270     typedef typename Allocators::difference_type difference_type;
 271     typedef typename Allocators::const_pointer pointer;
 272
 273     query_iterator()
 274     {}
 275
 276     template <typename It>
 277     query_iterator(It const& it)
 278         : m_ptr(static_cast<iterator_base*>(
 279                     new query_iterator_wrapper<Value, Allocators, It>(it) ))
 280     {}
 281
 282     query_iterator(end_query_iterator<Value, Allocators> const& /*it*/)
 283     {}
 284
 285     query_iterator(query_iterator const& o)
 286         : m_ptr(o.m_ptr.get() ? o.m_ptr->clone() : 0)
 287     {}
 288
 289 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 290     query_iterator & operator=(query_iterator const& o)
 291     {
 292         if ( this != boost::addressof(o) )
 293         {
 294             m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
 295         }
 296         return *this;
 297     }
 298 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 299     query_iterator(query_iterator && o)
 300         : m_ptr(0)
 301     {
 302         m_ptr.swap(o.m_ptr);
 303     }
 304     query_iterator & operator=(query_iterator && o)
 305     {
 306         if ( this != boost::addressof(o) )
 307         {
 308             m_ptr.swap(o.m_ptr);
 309             o.m_ptr.reset();
 310         }
 311         return *this;
 312     }
 313 #endif
 314 #else // !BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 315 private:
 316     BOOST_COPYABLE_AND_MOVABLE(query_iterator)
 317 public:
 318     query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o)
 319     {
 320         if ( this != boost::addressof(o) )
 321         {
 322             m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
 323         }
 324         return *this;
 325     }
 326     query_iterator(BOOST_RV_REF(query_iterator) o)
 327         : m_ptr(0)
 328     {
 329         m_ptr.swap(o.m_ptr);
 330     }
 331     query_iterator & operator=(BOOST_RV_REF(query_iterator) o)
 332     {
 333         if ( this != boost::addressof(o) )
 334         {
 335             m_ptr.swap(o.m_ptr);
 336             o.m_ptr.reset();
 337         }
 338         return *this;
 339     }
 340 #endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 341
 342     reference operator*() const
 343     {
 344         return m_ptr->dereference();
 345     }
 346
 347     const value_type * operator->() const
 348     {
 349         return boost::addressof(m_ptr->dereference());
 350     }
 351
 352     query_iterator & operator++()
 353     {
 354         m_ptr->increment();
 355         return *this;
 356     }
 357
 358     query_iterator operator++(int)
 359     {
 360         query_iterator temp = *this;
 361         this->operator++();
 362         return temp;
 363     }
 364
 365     friend bool operator==(query_iterator const& l, query_iterator const& r)
 366     {
 367         if ( l.m_ptr.get() )
 368         {
 369             if ( r.m_ptr.get() )
 370                 return l.m_ptr->equals(*r.m_ptr);
 371             else
 372                 return l.m_ptr->is_end();
 373         }
 374         else
 375         {
 376             if ( r.m_ptr.get() )
 377                 return r.m_ptr->is_end();
 378             else
 379                 return true;
 380         }
 381     }
 382
 383 private:
 384     iterator_ptr m_ptr;
 385 };
 386
 387 }}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 388
 389 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP