range/detail/any_iterator.hpp

0001 // Boost.Range library
0002 //
0003 //  Copyright Neil Groves 2010. Use, modification and
0004 //  distribution is subject to the Boost Software License, Version
0005 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 //  http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // For more information, see http://www.boost.org/libs/range/
0009 //
0010 #ifndef BOOST_RANGE_DETAIL_ANY_ITERATOR_HPP_INCLUDED
0011 #define BOOST_RANGE_DETAIL_ANY_ITERATOR_HPP_INCLUDED
0012
0013 #include <boost/mpl/and.hpp>
0014 #include <boost/mpl/or.hpp>
0015 #include <boost/mpl/not.hpp>
0016 #include <boost/iterator/iterator_facade.hpp>
0017 #include <boost/type_traits/is_const.hpp>
0018 #include <boost/type_traits/is_reference.hpp>
0019 #include <boost/type_traits/remove_reference.hpp>
0020 #include <boost/range/detail/any_iterator_buffer.hpp>
0021 #include <boost/range/detail/any_iterator_interface.hpp>
0022 #include <boost/range/detail/any_iterator_wrapper.hpp>
0023 #include <boost/utility/enable_if.hpp>
0024
0025 namespace boost
0026 {
0027     namespace range_detail
0028     {
0029         // metafunction to determine if T is a const reference
0030         template<class T>
0031         struct is_const_reference
0032         {
0033             typedef typename mpl::and_<
0034                 typename is_reference<T>::type,
0035                 typename is_const<
0036                     typename remove_reference<T>::type
0037                 >::type
0038             >::type type;
0039         };
0040
0041         // metafunction to determine if T is a mutable reference
0042         template<class T>
0043         struct is_mutable_reference
0044         {
0045             typedef typename mpl::and_<
0046                 typename is_reference<T>::type,
0047                 typename mpl::not_<
0048                     typename is_const<
0049                         typename remove_reference<T>::type
0050                     >::type
0051                 >::type
0052             >::type type;
0053         };
0054
0055         // metafunction to evaluate if a source 'reference' can be
0056         // converted to a target 'reference' as a value.
0057         //
0058         // This is true, when the target reference type is actually
0059         // not a reference, and the source reference is convertible
0060         // to the target type.
0061         template<class SourceReference, class TargetReference>
0062         struct is_convertible_to_value_as_reference
0063         {
0064             typedef typename mpl::and_<
0065                 typename mpl::not_<
0066                     typename is_reference<TargetReference>::type
0067                 >::type
0068               , typename is_convertible<
0069                     SourceReference
0070                   , TargetReference
0071                 >::type
0072             >::type type;
0073         };
0074
0075         template<
0076             class Value
0077           , class Traversal
0078           , class Reference
0079           , class Difference
0080           , class Buffer = any_iterator_default_buffer
0081         >
0082         class any_iterator;
0083
0084         // metafunction to determine if SomeIterator is an
0085         // any_iterator.
0086         //
0087         // This is the general implementation which evaluates to false.
0088         template<class SomeIterator>
0089         struct is_any_iterator
0090             : mpl::bool_<false>
0091         {
0092         };
0093
0094         // specialization of is_any_iterator to return true for
0095         // any_iterator classes regardless of template parameters.
0096         template<
0097             class Value
0098           , class Traversal
0099           , class Reference
0100           , class Difference
0101           , class Buffer
0102         >
0103         struct is_any_iterator<
0104             any_iterator<
0105                 Value
0106               , Traversal
0107               , Reference
0108               , Difference
0109               , Buffer
0110             >
0111         >
0112             : mpl::bool_<true>
0113         {
0114         };
0115     } // namespace range_detail
0116
0117     namespace iterators
0118     {
0119     namespace detail
0120     {
0121         // Rationale:
0122         // These are specialized since the iterator_facade versions lack
0123         // the requisite typedefs to allow wrapping to determine the types
0124         // if a user copy constructs from a postfix increment.
0125
0126         template<
0127             class Value
0128           , class Traversal
0129           , class Reference
0130           , class Difference
0131           , class Buffer
0132         >
0133         class postfix_increment_proxy<
0134                     range_detail::any_iterator<
0135                         Value
0136                       , Traversal
0137                       , Reference
0138                       , Difference
0139                       , Buffer
0140                     >
0141                 >
0142         {
0143             typedef range_detail::any_iterator<
0144                 Value
0145               , Traversal
0146               , Reference
0147               , Difference
0148               , Buffer
0149             > any_iterator_type;
0150
0151         public:
0152             typedef Value value_type;
0153             typedef typename std::iterator_traits<any_iterator_type>::iterator_category iterator_category;
0154             typedef Difference difference_type;
0155             typedef typename iterator_pointer<any_iterator_type>::type pointer;
0156             typedef Reference reference;
0157
0158             explicit postfix_increment_proxy(any_iterator_type const& x)
0159                 : stored_value(*x)
0160             {}
0161
0162             value_type&
0163             operator*() const
0164             {
0165                 return this->stored_value;
0166             }
0167         private:
0168             mutable value_type stored_value;
0169         };
0170
0171         template<
0172             class Value
0173           , class Traversal
0174           , class Reference
0175           , class Difference
0176           , class Buffer
0177         >
0178         class writable_postfix_increment_proxy<
0179                     range_detail::any_iterator<
0180                         Value
0181                       , Traversal
0182                       , Reference
0183                       , Difference
0184                       , Buffer
0185                     >
0186                 >
0187         {
0188             typedef range_detail::any_iterator<
0189                         Value
0190                       , Traversal
0191                       , Reference
0192                       , Difference
0193                       , Buffer
0194                     > any_iterator_type;
0195          public:
0196             typedef Value value_type;
0197             typedef typename std::iterator_traits<any_iterator_type>::iterator_category iterator_category;
0198             typedef Difference difference_type;
0199             typedef typename iterator_pointer<any_iterator_type>::type pointer;
0200             typedef Reference reference;
0201
0202             explicit writable_postfix_increment_proxy(any_iterator_type const& x)
0203               : stored_value(*x)
0204               , stored_iterator(x)
0205             {}
0206
0207             // Dereferencing must return a proxy so that both *r++ = o and
0208             // value_type(*r++) can work.  In this case, *r is the same as
0209             // *r++, and the conversion operator below is used to ensure
0210             // readability.
0211             writable_postfix_increment_proxy const&
0212             operator*() const
0213             {
0214                 return *this;
0215             }
0216
0217             // Provides readability of *r++
0218             operator value_type&() const
0219             {
0220                 return stored_value;
0221             }
0222
0223             // Provides writability of *r++
0224             template <class T>
0225             T const& operator=(T const& x) const
0226             {
0227                 *this->stored_iterator = x;
0228                 return x;
0229             }
0230
0231             // This overload just in case only non-const objects are writable
0232             template <class T>
0233             T& operator=(T& x) const
0234             {
0235                 *this->stored_iterator = x;
0236                 return x;
0237             }
0238
0239             // Provides X(r++)
0240             operator any_iterator_type const&() const
0241             {
0242                 return stored_iterator;
0243             }
0244
0245          private:
0246             mutable value_type stored_value;
0247             any_iterator_type stored_iterator;
0248         };
0249
0250     } //namespace detail
0251     } //namespace iterators
0252
0253     namespace range_detail
0254     {
0255         template<
0256             class Value
0257           , class Traversal
0258           , class Reference
0259           , class Difference
0260           , class Buffer
0261         >
0262         class any_iterator
0263             : public iterator_facade<
0264                         any_iterator<
0265                             Value
0266                           , Traversal
0267                           , Reference
0268                           , Difference
0269                           , Buffer
0270                         >
0271                     , Value
0272                     , Traversal
0273                     , Reference
0274                     , Difference
0275                 >
0276         {
0277             template<
0278                 class OtherValue
0279               , class OtherTraversal
0280               , class OtherReference
0281               , class OtherDifference
0282               , class OtherBuffer
0283             >
0284             friend class any_iterator;
0285
0286             struct enabler {};
0287             struct disabler {};
0288
0289             typedef typename any_iterator_interface_type_generator<
0290                 Traversal
0291               , Reference
0292               , Difference
0293               , Buffer
0294             >::type abstract_base_type;
0295
0296             typedef iterator_facade<
0297                         any_iterator<
0298                             Value
0299                           , Traversal
0300                           , Reference
0301                           , Difference
0302                           , Buffer
0303                         >
0304                       , Value
0305                       , Traversal
0306                       , Reference
0307                       , Difference
0308                   > base_type;
0309
0310             typedef Buffer buffer_type;
0311
0312         public:
0313             typedef typename base_type::value_type value_type;
0314             typedef typename base_type::reference reference;
0315             typedef typename base_type::difference_type difference_type;
0316
0317             // Default constructor
0318             any_iterator()
0319                 : m_impl(0) {}
0320
0321             // Simple copy construction without conversion
0322             any_iterator(const any_iterator& other)
0323                 : base_type(other)
0324                 , m_impl(other.m_impl
0325                             ? other.m_impl->clone(m_buffer)
0326                             : 0)
0327             {
0328             }
0329
0330             // Simple assignment operator without conversion
0331             any_iterator& operator=(const any_iterator& other)
0332             {
0333                 if (this != &other)
0334                 {
0335                     if (m_impl)
0336                         m_impl->~abstract_base_type();
0337                     m_buffer.deallocate();
0338                     m_impl = 0;
0339                     if (other.m_impl)
0340                         m_impl = other.m_impl->clone(m_buffer);
0341                 }
0342                 return *this;
0343             }
0344
0345             // Implicit conversion from another any_iterator where the
0346             // conversion is from a non-const reference to a const reference
0347             template<
0348                 class OtherValue
0349               , class OtherTraversal
0350               , class OtherReference
0351               , class OtherDifference
0352             >
0353             any_iterator(const any_iterator<
0354                                 OtherValue,
0355                                 OtherTraversal,
0356                                 OtherReference,
0357                                 OtherDifference,
0358                                 Buffer
0359                             >& other,
0360                          typename ::boost::enable_if<
0361                             typename mpl::and_<
0362                                 typename is_mutable_reference<OtherReference>::type,
0363                                 typename is_const_reference<Reference>::type
0364                             >::type,
0365                             enabler
0366                         >::type* = 0
0367                     )
0368                 : m_impl(other.m_impl
0369                             ? other.m_impl->clone_const_ref(m_buffer)
0370                          : 0
0371                         )
0372             {
0373             }
0374
0375             // Implicit conversion from another any_iterator where the
0376             // reference types of the source and the target are references
0377             // that are either both const, or both non-const.
0378             template<
0379                 class OtherValue
0380               , class OtherTraversal
0381               , class OtherReference
0382               , class OtherDifference
0383             >
0384             any_iterator(const any_iterator<
0385                                 OtherValue
0386                               , OtherTraversal
0387                               , OtherReference
0388                               , OtherDifference
0389                               , Buffer
0390                             >& other,
0391                          typename ::boost::enable_if<
0392                             typename mpl::or_<
0393                                 typename mpl::and_<
0394                                     typename is_mutable_reference<OtherReference>::type,
0395                                     typename is_mutable_reference<Reference>::type
0396                                 >::type,
0397                                 typename mpl::and_<
0398                                     typename is_const_reference<OtherReference>::type,
0399                                     typename is_const_reference<Reference>::type
0400                                 >::type
0401                             >::type,
0402                             enabler
0403                         >::type* = 0
0404                         )
0405                 : m_impl(other.m_impl
0406                             ? other.m_impl->clone(m_buffer)
0407                          : 0
0408                         )
0409             {
0410             }
0411
0412             // Implicit conversion to an any_iterator that uses a value for
0413             // the reference type.
0414             template<
0415                 class OtherValue
0416               , class OtherTraversal
0417               , class OtherReference
0418               , class OtherDifference
0419             >
0420             any_iterator(const any_iterator<
0421                                 OtherValue
0422                               , OtherTraversal
0423                               , OtherReference
0424                               , OtherDifference
0425                               , Buffer
0426                             >& other,
0427                         typename ::boost::enable_if<
0428                             typename is_convertible_to_value_as_reference<
0429                                         OtherReference
0430                                       , Reference
0431                                     >::type,
0432                             enabler
0433                         >::type* = 0
0434                         )
0435                 : m_impl(other.m_impl
0436                             ? other.m_impl->clone_reference_as_value(m_buffer)
0437                             : 0
0438                             )
0439             {
0440             }
0441
0442             any_iterator clone() const
0443             {
0444                 any_iterator result;
0445                 if (m_impl)
0446                     result.m_impl = m_impl->clone(result.m_buffer);
0447                 return result;
0448             }
0449
0450             any_iterator<
0451                 Value
0452               , Traversal
0453               , typename abstract_base_type::const_reference
0454               , Difference
0455               , Buffer
0456             >
0457             clone_const_ref() const
0458             {
0459                 typedef any_iterator<
0460                     Value
0461                   , Traversal
0462                   , typename abstract_base_type::const_reference
0463                   , Difference
0464                   , Buffer
0465                 > result_type;
0466
0467                 result_type result;
0468
0469                 if (m_impl)
0470                     result.m_impl = m_impl->clone_const_ref(result.m_buffer);
0471
0472                 return result;
0473             }
0474
0475             // implicit conversion and construction from type-erasure-compatible
0476             // iterators
0477             template<class WrappedIterator>
0478             explicit any_iterator(
0479                 const WrappedIterator& wrapped_iterator,
0480                 typename disable_if<
0481                     typename is_any_iterator<WrappedIterator>::type
0482                   , disabler
0483                 >::type* = 0
0484                 )
0485             {
0486                 typedef typename any_iterator_wrapper_type_generator<
0487                             WrappedIterator
0488                           , Traversal
0489                           , Reference
0490                           , Difference
0491                           , Buffer
0492                         >::type wrapper_type;
0493
0494                 void* ptr = m_buffer.allocate(sizeof(wrapper_type));
0495                 m_impl = new(ptr) wrapper_type(wrapped_iterator);
0496             }
0497
0498             ~any_iterator()
0499             {
0500                 // manually run the destructor, the deallocation is automatically
0501                 // handled by the any_iterator_small_buffer base class.
0502                 if (m_impl)
0503                     m_impl->~abstract_base_type();
0504             }
0505
0506         private:
0507             friend class ::boost::iterator_core_access;
0508
0509             Reference dereference() const
0510             {
0511                 BOOST_ASSERT( m_impl );
0512                 return m_impl->dereference();
0513             }
0514
0515             bool equal(const any_iterator& other) const
0516             {
0517                 return (m_impl == other.m_impl)
0518                     || (m_impl && other.m_impl && m_impl->equal(*other.m_impl));
0519             }
0520
0521             void increment()
0522             {
0523                 BOOST_ASSERT( m_impl );
0524                 m_impl->increment();
0525             }
0526
0527             void decrement()
0528             {
0529                 BOOST_ASSERT( m_impl );
0530                 m_impl->decrement();
0531             }
0532
0533             Difference distance_to(const any_iterator& other) const
0534             {
0535                 return m_impl && other.m_impl
0536                     ? m_impl->distance_to(*other.m_impl)
0537                     : 0;
0538             }
0539
0540             void advance(Difference offset)
0541             {
0542                 BOOST_ASSERT( m_impl );
0543                 m_impl->advance(offset);
0544             }
0545
0546             any_iterator& swap(any_iterator& other)
0547             {
0548                 BOOST_ASSERT( this != &other );
0549                 // grab a temporary copy of the other iterator
0550                 any_iterator tmp(other);
0551
0552                 // deallocate the other iterator, taking care to obey the
0553                 // class-invariants in-case of exceptions later
0554                 if (other.m_impl)
0555                 {
0556                     other.m_impl->~abstract_base_type();
0557                     other.m_buffer.deallocate();
0558                     other.m_impl = 0;
0559                 }
0560
0561                 // If this is a non-null iterator then we need to put
0562                 // a clone of this iterators implementation into the other
0563                 // iterator.
0564                 // We can't just swap because of the small buffer optimization.
0565                 if (m_impl)
0566                 {
0567                     other.m_impl = m_impl->clone(other.m_buffer);
0568                     m_impl->~abstract_base_type();
0569                     m_buffer.deallocate();
0570                     m_impl = 0;
0571                 }
0572
0573                 // assign to this instance a clone of the temporarily held
0574                 // tmp which represents the input other parameter at the
0575                 // start of execution of this function.
0576                 if (tmp.m_impl)
0577                     m_impl = tmp.m_impl->clone(m_buffer);
0578
0579                 return *this;
0580             }
0581
0582             buffer_type m_buffer;
0583             abstract_base_type* m_impl;
0584         };
0585
0586     } // namespace range_detail
0587 } // namespace boost
0588
0589 #endif // include guard