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