detail/rtree/query_iterators.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree query iterators
0004 //
0005 // Copyright (c) 2011-2023 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2021.
0008 // Modifications copyright (c) 2019-2021 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
0017
0018 #include <memory>
0019
0020 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0021 #include <boost/geometry/index/detail/rtree/visitors/distance_query.hpp>
0022 #include <boost/geometry/index/detail/rtree/visitors/spatial_query.hpp>
0023
0024 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
0025
0026 template <typename Value, typename Allocators>
0027 struct end_query_iterator
0028 {
0029     typedef std::forward_iterator_tag iterator_category;
0030     typedef Value value_type;
0031     typedef typename Allocators::const_reference reference;
0032     typedef typename Allocators::difference_type difference_type;
0033     typedef typename Allocators::const_pointer pointer;
0034
0035     reference operator*() const
0036     {
0037         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not dereferencable");
0038         pointer p(0);
0039         return *p;
0040     }
0041
0042     const value_type * operator->() const
0043     {
0044         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not dereferencable");
0045         const value_type * p = 0;
0046         return p;
0047     }
0048
0049     end_query_iterator & operator++()
0050     {
0051         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not incrementable");
0052         return *this;
0053     }
0054
0055     end_query_iterator operator++(int)
0056     {
0057         BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not incrementable");
0058         return *this;
0059     }
0060
0061     friend bool operator==(end_query_iterator const& /*l*/, end_query_iterator const& /*r*/)
0062     {
0063         return true;
0064     }
0065 };
0066
0067 template <typename MembersHolder, typename Predicates>
0068 class spatial_query_iterator
0069 {
0070     typedef typename MembersHolder::allocators_type allocators_type;
0071
0072 public:
0073     typedef std::forward_iterator_tag iterator_category;
0074     typedef typename MembersHolder::value_type value_type;
0075     typedef typename allocators_type::const_reference reference;
0076     typedef typename allocators_type::difference_type difference_type;
0077     typedef typename allocators_type::const_pointer pointer;
0078
0079     spatial_query_iterator() = default;
0080
0081     explicit spatial_query_iterator(Predicates const& pred)
0082         : m_impl(pred)
0083     {}
0084
0085     spatial_query_iterator(MembersHolder const& members, Predicates const& pred)
0086         : m_impl(members, pred)
0087     {
0088         m_impl.initialize(members);
0089     }
0090
0091     reference operator*() const
0092     {
0093         return m_impl.dereference();
0094     }
0095
0096     const value_type * operator->() const
0097     {
0098         return boost::addressof(m_impl.dereference());
0099     }
0100
0101     spatial_query_iterator & operator++()
0102     {
0103         m_impl.increment();
0104         return *this;
0105     }
0106
0107     spatial_query_iterator operator++(int)
0108     {
0109         spatial_query_iterator temp = *this;
0110         this->operator++();
0111         return temp;
0112     }
0113
0114     friend bool operator==(spatial_query_iterator const& l, spatial_query_iterator const& r)
0115     {
0116         return l.m_impl == r.m_impl;
0117     }
0118
0119     friend bool operator==(spatial_query_iterator const& l, end_query_iterator<value_type, allocators_type> const& /*r*/)
0120     {
0121         return l.m_impl.is_end();
0122     }
0123
0124     friend bool operator==(end_query_iterator<value_type, allocators_type> const& /*l*/, spatial_query_iterator const& r)
0125     {
0126         return r.m_impl.is_end();
0127     }
0128
0129 private:
0130     visitors::spatial_query_incremental<MembersHolder, Predicates> m_impl;
0131 };
0132
0133 template <typename MembersHolder, typename Predicates>
0134 class distance_query_iterator
0135 {
0136     typedef typename MembersHolder::allocators_type allocators_type;
0137
0138 public:
0139     typedef std::forward_iterator_tag iterator_category;
0140     typedef typename MembersHolder::value_type value_type;
0141     typedef typename allocators_type::const_reference reference;
0142     typedef typename allocators_type::difference_type difference_type;
0143     typedef typename allocators_type::const_pointer pointer;
0144
0145     distance_query_iterator() = default;
0146
0147     explicit distance_query_iterator(Predicates const& pred)
0148         : m_impl(pred)
0149     {}
0150
0151     distance_query_iterator(MembersHolder const& members, Predicates const& pred)
0152         : m_impl(members, pred)
0153     {
0154         m_impl.initialize(members);
0155     }
0156
0157     reference operator*() const
0158     {
0159         return m_impl.dereference();
0160     }
0161
0162     const value_type * operator->() const
0163     {
0164         return boost::addressof(m_impl.dereference());
0165     }
0166
0167     distance_query_iterator & operator++()
0168     {
0169         m_impl.increment();
0170         return *this;
0171     }
0172
0173     distance_query_iterator operator++(int)
0174     {
0175         distance_query_iterator temp = *this;
0176         this->operator++();
0177         return temp;
0178     }
0179
0180     friend bool operator==(distance_query_iterator const& l, distance_query_iterator const& r)
0181     {
0182         return l.m_impl == r.m_impl;
0183     }
0184
0185     friend bool operator==(distance_query_iterator const& l, end_query_iterator<value_type, allocators_type> const& /*r*/)
0186     {
0187         return l.m_impl.is_end();
0188     }
0189
0190     friend bool operator==(end_query_iterator<value_type, allocators_type> const& /*l*/, distance_query_iterator const& r)
0191     {
0192         return r.m_impl.is_end();
0193     }
0194
0195 private:
0196     visitors::distance_query_incremental<MembersHolder, Predicates> m_impl;
0197 };
0198
0199
0200 template <typename L, typename R>
0201 inline bool operator!=(L const& l, R const& r)
0202 {
0203     return !(l == r);
0204 }
0205
0206
0207 template <typename Value, typename Allocators>
0208 class query_iterator_base
0209 {
0210 public:
0211     typedef std::forward_iterator_tag iterator_category;
0212     typedef Value value_type;
0213     typedef typename Allocators::const_reference reference;
0214     typedef typename Allocators::difference_type difference_type;
0215     typedef typename Allocators::const_pointer pointer;
0216
0217     virtual ~query_iterator_base() {}
0218
0219     virtual query_iterator_base * clone() const = 0;
0220
0221     virtual bool is_end() const = 0;
0222     virtual reference dereference() const = 0;
0223     virtual void increment() = 0;
0224     virtual bool equals(query_iterator_base const&) const = 0;
0225 };
0226
0227 template <typename Value, typename Allocators, typename Iterator>
0228 class query_iterator_wrapper
0229     : public query_iterator_base<Value, Allocators>
0230 {
0231     typedef query_iterator_base<Value, Allocators> base_t;
0232
0233 public:
0234     typedef std::forward_iterator_tag iterator_category;
0235     typedef Value value_type;
0236     typedef typename Allocators::const_reference reference;
0237     typedef typename Allocators::difference_type difference_type;
0238     typedef typename Allocators::const_pointer pointer;
0239
0240     query_iterator_wrapper() : m_iterator() {}
0241     explicit query_iterator_wrapper(Iterator const& it) : m_iterator(it) {}
0242
0243     virtual base_t * clone() const { return new query_iterator_wrapper(m_iterator); }
0244
0245     virtual bool is_end() const { return m_iterator == end_query_iterator<Value, Allocators>(); }
0246     virtual reference dereference() const { return *m_iterator; }
0247     virtual void increment() { ++m_iterator; }
0248     virtual bool equals(base_t const& r) const
0249     {
0250         const query_iterator_wrapper * p = dynamic_cast<const query_iterator_wrapper *>(boost::addressof(r));
0251         BOOST_GEOMETRY_INDEX_ASSERT(p, "iterators can't be compared");
0252         return m_iterator == p->m_iterator;
0253     }
0254
0255 private:
0256     Iterator m_iterator;
0257 };
0258
0259
0260 template <typename Value, typename Allocators>
0261 class query_iterator
0262 {
0263     typedef query_iterator_base<Value, Allocators> iterator_base;
0264     typedef std::unique_ptr<iterator_base> iterator_ptr;
0265
0266 public:
0267     typedef std::forward_iterator_tag iterator_category;
0268     typedef Value value_type;
0269     typedef typename Allocators::const_reference reference;
0270     typedef typename Allocators::difference_type difference_type;
0271     typedef typename Allocators::const_pointer pointer;
0272
0273     query_iterator() = default;
0274
0275     template <typename It>
0276     query_iterator(It const& it)
0277         : m_ptr(static_cast<iterator_base*>(
0278                     new query_iterator_wrapper<Value, Allocators, It>(it) ))
0279     {}
0280
0281     query_iterator(end_query_iterator<Value, Allocators> const& /*it*/)
0282     {}
0283
0284     query_iterator(query_iterator const& o)
0285         : m_ptr(o.m_ptr.get() ? o.m_ptr->clone() : 0)
0286     {}
0287
0288     query_iterator(query_iterator&&) = default;
0289
0290     query_iterator & operator=(query_iterator const& o)
0291     {
0292         if ( this != boost::addressof(o) )
0293         {
0294             m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
0295         }
0296         return *this;
0297     }
0298
0299     query_iterator& operator=(query_iterator &&) = default;
0300
0301     reference operator*() const
0302     {
0303         return m_ptr->dereference();
0304     }
0305
0306     const value_type * operator->() const
0307     {
0308         return boost::addressof(m_ptr->dereference());
0309     }
0310
0311     query_iterator & operator++()
0312     {
0313         m_ptr->increment();
0314         return *this;
0315     }
0316
0317     query_iterator operator++(int)
0318     {
0319         query_iterator temp = *this;
0320         this->operator++();
0321         return temp;
0322     }
0323
0324     friend bool operator==(query_iterator const& l, query_iterator const& r)
0325     {
0326         if ( l.m_ptr.get() )
0327         {
0328             if ( r.m_ptr.get() )
0329                 return l.m_ptr->equals(*r.m_ptr);
0330             else
0331                 return l.m_ptr->is_end();
0332         }
0333         else
0334         {
0335             if ( r.m_ptr.get() )
0336                 return r.m_ptr->is_end();
0337             else
0338                 return true;
0339         }
0340     }
0341
0342 private:
0343     iterator_ptr m_ptr;
0344 };
0345
0346 }}}}}} // namespace boost::geometry::index::detail::rtree::iterators
0347
0348 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP