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

   1 // Boost.Geometry Index
   2 //
   3 // R-tree query iterators
   4 //
   5 // Copyright (c) 2011-2013 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 #define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL
  15 //#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION
  16 //#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
  17 //#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
  18
  19 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
  20
  21 template <typename Value, typename Allocators>
  22 struct end_query_iterator
  23 {
  24     typedef std::input_iterator_tag iterator_category;
  25     typedef Value value_type;
  26     typedef typename Allocators::const_reference reference;
  27     typedef typename Allocators::difference_type difference_type;
  28     typedef typename Allocators::const_pointer pointer;
  29
  30     reference operator*() const
  31     {
  32         BOOST_ASSERT_MSG(false, "iterator not dereferencable");
  33         pointer p(0);
  34         return *p;
  35     }
  36
  37     const value_type * operator->() const
  38     {
  39         BOOST_ASSERT_MSG(false, "iterator not dereferencable");
  40         const value_type * p = 0;
  41         return p;
  42     }
  43
  44     end_query_iterator & operator++()
  45     {
  46         BOOST_ASSERT_MSG(false, "iterator not incrementable");
  47         return *this;
  48     }
  49
  50     end_query_iterator operator++(int)
  51     {
  52         BOOST_ASSERT_MSG(false, "iterator not incrementable");
  53         return *this;
  54     }
  55
  56     friend bool operator==(end_query_iterator const& /*l*/, end_query_iterator const& /*r*/)
  57     {
  58         return true;
  59     }
  60 };
  61
  62 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates>
  63 class spatial_query_iterator
  64 {
  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::input_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(Translator const& t, Predicates const& p)
  76         : m_visitor(t, p)
  77     {}
  78
  79     inline spatial_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
  80         : m_visitor(t, p)
  81     {
  82         m_visitor.initialize(root);
  83     }
  84
  85     reference operator*() const
  86     {
  87         return m_visitor.dereference();
  88     }
  89
  90     const value_type * operator->() const
  91     {
  92         return boost::addressof(m_visitor.dereference());
  93     }
  94
  95     spatial_query_iterator & operator++()
  96     {
  97         m_visitor.increment();
  98         return *this;
  99     }
 100
 101     spatial_query_iterator operator++(int)
 102     {
 103         spatial_query_iterator temp = *this;
 104         this->operator++();
 105         return temp;
 106     }
 107
 108     friend bool operator==(spatial_query_iterator const& l, spatial_query_iterator const& r)
 109     {
 110         return l.m_visitor == r.m_visitor;
 111     }
 112
 113     friend bool operator==(spatial_query_iterator const& l, end_query_iterator<Value, Allocators> const& /*r*/)
 114     {
 115         return l.m_visitor.is_end();
 116     }
 117
 118     friend bool operator==(end_query_iterator<Value, Allocators> const& /*l*/, spatial_query_iterator const& r)
 119     {
 120         return r.m_visitor.is_end();
 121     }
 122
 123 private:
 124     visitor_type m_visitor;
 125 };
 126
 127 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, unsigned NearestPredicateIndex>
 128 class distance_query_iterator
 129 {
 130     typedef visitors::distance_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type;
 131     typedef typename visitor_type::node_pointer node_pointer;
 132
 133 public:
 134     typedef std::input_iterator_tag iterator_category;
 135     typedef Value value_type;
 136     typedef typename Allocators::const_reference reference;
 137     typedef typename Allocators::difference_type difference_type;
 138     typedef typename Allocators::const_pointer pointer;
 139
 140     inline distance_query_iterator(Translator const& t, Predicates const& p)
 141         : m_visitor(t, p)
 142     {}
 143
 144     inline distance_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
 145         : m_visitor(t, p)
 146     {
 147         m_visitor.initialize(root);
 148     }
 149
 150     reference operator*() const
 151     {
 152         return m_visitor.dereference();
 153     }
 154
 155     const value_type * operator->() const
 156     {
 157         return boost::addressof(m_visitor.dereference());
 158     }
 159
 160     distance_query_iterator & operator++()
 161     {
 162         m_visitor.increment();
 163         return *this;
 164     }
 165
 166     distance_query_iterator operator++(int)
 167     {
 168         distance_query_iterator temp = *this;
 169         this->operator++();
 170         return temp;
 171     }
 172
 173     friend bool operator==(distance_query_iterator const& l, distance_query_iterator const& r)
 174     {
 175         return l.m_visitor == r.m_visitor;
 176     }
 177
 178     friend bool operator==(distance_query_iterator const& l, end_query_iterator<Value, Allocators> const& /*r*/)
 179     {
 180         return l.m_visitor.is_end();
 181     }
 182
 183     friend bool operator==(end_query_iterator<Value, Allocators> const& /*l*/, distance_query_iterator const& r)
 184     {
 185         return r.m_visitor.is_end();
 186     }
 187
 188 private:
 189     visitor_type m_visitor;
 190 };
 191
 192 template <typename L, typename R>
 193 inline bool operator!=(L const& l, R const& r)
 194 {
 195     return !(l == r);
 196 }
 197
 198 }}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 199
 200 #if defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL) || defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION)
 201
 202 #if defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL)
 203
 204 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 205
 206 template <typename Value, typename Allocators>
 207 class query_iterator_base
 208 {
 209 public:
 210     typedef std::input_iterator_tag iterator_category;
 211     typedef Value value_type;
 212     typedef typename Allocators::const_reference reference;
 213     typedef typename Allocators::difference_type difference_type;
 214     typedef typename Allocators::const_pointer pointer;
 215
 216     virtual ~query_iterator_base() {}
 217
 218     virtual query_iterator_base * clone() const = 0;
 219
 220     virtual bool is_end() const = 0;
 221     virtual reference dereference() const = 0;
 222     virtual void increment() = 0;
 223     virtual bool equals(query_iterator_base const&) const = 0;
 224 };
 225
 226 template <typename Value, typename Allocators, typename Iterator>
 227 class query_iterator_wrapper
 228     : public query_iterator_base<Value, Allocators>
 229 {
 230     typedef query_iterator_base<Value, Allocators> base_t;
 231
 232 public:
 233     typedef std::input_iterator_tag iterator_category;
 234     typedef Value value_type;
 235     typedef typename Allocators::const_reference reference;
 236     typedef typename Allocators::difference_type difference_type;
 237     typedef typename Allocators::const_pointer pointer;
 238
 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_ASSERT_MSG(p, "those iterators can't be compared");
 250         return m_iterator == p->m_iterator;
 251     }
 252
 253 private:
 254     Iterator m_iterator;
 255 };
 256
 257 #elif defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION)
 258
 259 #include <boost/function.hpp>
 260 #include <boost/bind.hpp>
 261
 262 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 263
 264 template <typename Value, typename Allocators>
 265 class query_iterator_base
 266 {
 267 public:
 268     typedef std::input_iterator_tag iterator_category;
 269     typedef Value value_type;
 270     typedef typename Allocators::const_reference reference;
 271     typedef typename Allocators::difference_type difference_type;
 272     typedef typename Allocators::const_pointer pointer;
 273
 274     virtual ~query_iterator_base() {}
 275
 276     boost::function<query_iterator_base*()> clone;
 277     boost::function<bool()> is_end;
 278     boost::function<reference()> dereference;
 279     boost::function<void()> increment;
 280     boost::function<bool(query_iterator_base const&)> equals;
 281 };
 282
 283 template <typename Value, typename Allocators, typename Iterator>
 284 class query_iterator_wrapper
 285     : public query_iterator_base<Value, Allocators>
 286 {
 287     typedef query_iterator_base<Value, Allocators> base_t;
 288
 289 public:
 290     typedef std::input_iterator_tag iterator_category;
 291     typedef Value value_type;
 292     typedef typename Allocators::const_reference reference;
 293     typedef typename Allocators::difference_type difference_type;
 294     typedef typename Allocators::const_pointer pointer;
 295
 296     explicit query_iterator_wrapper(Iterator const& it)
 297         : m_iterator(it)
 298     {
 299         base_t::clone = boost::bind(&query_iterator_wrapper::clone_, this);
 300         base_t::is_end = boost::bind(&query_iterator_wrapper::is_end_, this);
 301         base_t::dereference = boost::bind(&query_iterator_wrapper::dereference_, this);
 302         base_t::increment = boost::bind(&query_iterator_wrapper::increment_, this);
 303         base_t::equals = boost::bind(&query_iterator_wrapper::equals_, this, _1);
 304     }
 305
 306 private:
 307     base_t * clone_() const { return new query_iterator_wrapper(m_iterator); }
 308
 309     bool is_end_() const { return m_iterator == end_query_iterator<Value, Allocators>(); }
 310     reference dereference_() const { return *m_iterator; }
 311     void increment_() { ++m_iterator; }
 312     bool equals_(base_t const& r) const
 313     {
 314         const query_iterator_wrapper * p = dynamic_cast<const query_iterator_wrapper *>(boost::addressof(r));
 315         BOOST_ASSERT_MSG(p, "those iterators can't be compared");
 316         return m_iterator == p->m_iterator;
 317     }
 318
 319 private:
 320     Iterator m_iterator;
 321 };
 322
 323 #endif
 324
 325 template <typename Value, typename Allocators>
 326 class query_iterator
 327 {
 328     typedef query_iterator_base<Value, Allocators> iterator_base;
 329     typedef std::auto_ptr<iterator_base> iterator_ptr;
 330
 331 public:
 332     typedef std::input_iterator_tag iterator_category;
 333     typedef Value value_type;
 334     typedef typename Allocators::const_reference reference;
 335     typedef typename Allocators::difference_type difference_type;
 336     typedef typename Allocators::const_pointer pointer;
 337
 338     query_iterator() {}
 339
 340     template <typename It>
 341     query_iterator(It const& it)
 342         : m_ptr(static_cast<iterator_base*>(
 343                     new query_iterator_wrapper<Value, Allocators, It>(it) ))
 344     {}
 345
 346     query_iterator(end_query_iterator<Value, Allocators> const& /*it*/)
 347     {}
 348
 349     query_iterator(query_iterator const& o)
 350         : m_ptr(o.m_ptr.get() ? o.m_ptr->clone() : 0)
 351     {}
 352
 353 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 354     query_iterator & operator=(query_iterator const& o)
 355     {
 356         m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
 357         return *this;
 358     }
 359 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 360     query_iterator(query_iterator && o)
 361         : m_ptr(o.m_ptr.get())
 362     {
 363         o.m_ptr.release();
 364     }
 365     query_iterator & operator=(query_iterator && o)
 366     {
 367         if ( this != boost::addressof(o) )
 368         {
 369             m_ptr.reset(o.m_ptr.get());
 370             o.m_ptr.release();
 371         }
 372         return *this;
 373     }
 374 #endif
 375 #else // !BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 376 private:
 377     BOOST_COPYABLE_AND_MOVABLE(query_iterator)
 378 public:
 379     query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o)
 380     {
 381         m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
 382         return *this;
 383     }
 384     query_iterator(BOOST_RV_REF(query_iterator) o)
 385         : m_ptr(o.m_ptr.get())
 386     {
 387         o.m_ptr.release();
 388     }
 389     query_iterator & operator=(BOOST_RV_REF(query_iterator) o)
 390     {
 391         if ( this != boost::addressof(o) )
 392         {
 393             m_ptr.reset(o.m_ptr.get());
 394             o.m_ptr.release();
 395         }
 396         return *this;
 397     }
 398 #endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 399
 400     reference operator*() const
 401     {
 402         return m_ptr->dereference();
 403     }
 404
 405     const value_type * operator->() const
 406     {
 407         return boost::addressof(m_ptr->dereference());
 408     }
 409
 410     query_iterator & operator++()
 411     {
 412         m_ptr->increment();
 413         return *this;
 414     }
 415
 416     query_iterator operator++(int)
 417     {
 418         query_iterator temp = *this;
 419         this->operator++();
 420         return temp;
 421     }
 422
 423     friend bool operator==(query_iterator const& l, query_iterator const& r)
 424     {
 425         if ( l.m_ptr.get() )
 426         {
 427             if ( r.m_ptr.get() )
 428                 return l.m_ptr->equals(*r.m_ptr);
 429             else
 430                 return l.m_ptr->is_end();
 431         }
 432         else
 433         {
 434             if ( r.m_ptr.get() )
 435                 return r.m_ptr->is_end();
 436             else
 437                 return true;
 438         }
 439     }
 440
 441 private:
 442     iterator_ptr m_ptr;
 443 };
 444
 445 }}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 446
 447 #elif defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE)
 448
 449 #include <boost/type_erasure/any.hpp>
 450 #include <boost/type_erasure/operators.hpp>
 451 #include <boost/type_erasure/is_empty.hpp>
 452
 453 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 454
 455 template<typename T, typename Value, typename Allocators>
 456 struct single_pass_iterator_concept :
 457     ::boost::mpl::vector<
 458         ::boost::type_erasure::copy_constructible<T>,
 459         ::boost::type_erasure::equality_comparable<T>,
 460         ::boost::type_erasure::dereferenceable<typename Allocators::const_reference, T>,
 461         ::boost::type_erasure::assignable<T>,
 462         ::boost::type_erasure::incrementable<T>,
 463         ::boost::type_erasure::equality_comparable<T, end_query_iterator<Value, Allocators> >,
 464         ::boost::type_erasure::relaxed // default ctor
 465     >
 466 {};
 467
 468 template <typename Value, typename Allocators>
 469 struct single_pass_iterator_type
 470 {
 471     typedef ::boost::type_erasure::any<
 472         single_pass_iterator_concept<
 473             ::boost::type_erasure::_self, Value, Allocators
 474         >
 475     > type;
 476 };
 477
 478 }}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 479
 480 namespace boost { namespace type_erasure {
 481
 482 template<typename T, typename Value, typename Allocators, typename Base>
 483 struct concept_interface<
 484     ::boost::geometry::index::detail::rtree::single_pass_iterator_concept<
 485         T, Value, Allocators
 486     >, Base, T>
 487     : Base
 488 {
 489     typedef Value value_type;
 490     typedef typename Allocators::const_reference reference;
 491     typedef typename Allocators::const_pointer pointer;
 492     typedef typename Allocators::difference_type difference_type;
 493     typedef ::std::input_iterator_tag iterator_category;
 494 };
 495
 496 }} // boost::type_erasure
 497
 498 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 499
 500 template <typename Value, typename Allocators>
 501 class query_iterator
 502 {
 503 public:
 504     typedef std::input_iterator_tag iterator_category;
 505     typedef Value value_type;
 506     typedef typename Allocators::const_reference reference;
 507     typedef typename Allocators::difference_type difference_type;
 508     typedef typename Allocators::const_pointer pointer;
 509
 510 private:
 511     typedef typename rtree::single_pass_iterator_type<Value, Allocators>::type iterator_type;
 512
 513 public:
 514
 515     query_iterator() {}
 516
 517     template <typename It>
 518     query_iterator(It const& it)
 519         : m_iterator(it)
 520     {}
 521
 522     query_iterator(end_query_iterator<Value, Allocators> const& /*it*/)
 523     {}
 524
 525 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 526 private:
 527     BOOST_COPYABLE_AND_MOVABLE(query_iterator)
 528 public:
 529     query_iterator(query_iterator const& o)
 530         : m_iterator(o.m_iterator)
 531     {}
 532     query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o)
 533     {
 534         m_iterator = o.m_iterator;
 535         return *this;
 536     }
 537     query_iterator(BOOST_RV_REF(query_iterator) o)
 538         : m_iterator(boost::move(o.m_iterator))
 539     {}
 540     query_iterator & operator=(BOOST_RV_REF(query_iterator) o)
 541     {
 542         if ( this != boost::addressof(o) )
 543         {
 544             m_iterator = boost::move(o.m_iterator);
 545         }
 546         return *this;
 547     }
 548 #endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 549
 550     reference operator*() const
 551     {
 552         return *m_iterator;
 553     }
 554
 555     const value_type * operator->() const
 556     {
 557         return boost::addressof(*m_iterator);
 558     }
 559
 560     query_iterator & operator++()
 561     {
 562         ++m_iterator;
 563         return *this;
 564     }
 565
 566     query_iterator operator++(int)
 567     {
 568         query_iterator temp = *this;
 569         ++m_iterator;
 570         return temp;
 571     }
 572
 573     friend bool operator==(query_iterator const& l, query_iterator const& r)
 574     {
 575         if ( !::boost::type_erasure::is_empty(l.m_iterator) )
 576         {
 577             if ( !::boost::type_erasure::is_empty(r.m_iterator) )
 578                 return l.m_iterator == r.m_iterator;
 579             else
 580                 return l.m_iterator == end_query_iterator<Value, Allocators>();
 581         }
 582         else
 583         {
 584             if ( !::boost::type_erasure::is_empty(r.m_iterator) )
 585                 return r.m_iterator == end_query_iterator<Value, Allocators>();
 586             else
 587                 return true;
 588         }
 589     }
 590
 591 private:
 592     iterator_type m_iterator;
 593 };
 594
 595 }}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 596
 597 #endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
 598
 599 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP