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