boost/iterator/zip_iterator.hpp

0001 // Copyright David Abrahams and Thomas Becker 2000-2006.
0002 // Copyright Kohei Takahashi 2012-2014.
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007
0008 #ifndef BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
0009 # define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
0010
0011 #include <stddef.h>
0012 #include <boost/iterator/iterator_traits.hpp>
0013 #include <boost/iterator/iterator_facade.hpp>
0014 #include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible
0015 #include <boost/iterator/iterator_categories.hpp>
0016
0017 #include <boost/iterator/minimum_category.hpp>
0018
0019 #include <utility> // for std::pair
0020 #include <boost/fusion/adapted/boost_tuple.hpp> // for backward compatibility
0021
0022 #include <boost/type_traits/remove_reference.hpp>
0023 #include <boost/type_traits/remove_cv.hpp>
0024
0025 #include <boost/mpl/at.hpp>
0026 #include <boost/mpl/fold.hpp>
0027 #include <boost/mpl/transform.hpp>
0028 #include <boost/mpl/placeholders.hpp>
0029
0030 #include <boost/fusion/algorithm/iteration/for_each.hpp>
0031 #include <boost/fusion/algorithm/transformation/transform.hpp>
0032 #include <boost/fusion/sequence/convert.hpp>
0033 #include <boost/fusion/sequence/intrinsic/at_c.hpp>
0034 #include <boost/fusion/sequence/comparison/equal_to.hpp>
0035 #include <boost/fusion/support/tag_of_fwd.hpp>
0036
0037 namespace boost {
0038 namespace iterators {
0039
0040   // Zip iterator forward declaration for zip_iterator_base
0041   template<typename IteratorTuple>
0042   class zip_iterator;
0043
0044   namespace detail
0045   {
0046
0047     // Functors to be used with tuple algorithms
0048     //
0049     template<typename DiffType>
0050     class advance_iterator
0051     {
0052     public:
0053       advance_iterator(DiffType step) : m_step(step) {}
0054
0055       template<typename Iterator>
0056       void operator()(Iterator& it) const
0057       { it += m_step; }
0058
0059     private:
0060       DiffType m_step;
0061     };
0062     //
0063     struct increment_iterator
0064     {
0065       template<typename Iterator>
0066       void operator()(Iterator& it) const
0067       { ++it; }
0068     };
0069     //
0070     struct decrement_iterator
0071     {
0072       template<typename Iterator>
0073       void operator()(Iterator& it) const
0074       { --it; }
0075     };
0076     //
0077     struct dereference_iterator
0078     {
0079       template<typename>
0080       struct result;
0081
0082       template<typename This, typename Iterator>
0083       struct result<This(Iterator)>
0084       {
0085         typedef typename
0086           remove_cv<typename remove_reference<Iterator>::type>::type
0087         iterator;
0088
0089         typedef typename iterator_reference<iterator>::type type;
0090       };
0091
0092       template<typename Iterator>
0093         typename result<dereference_iterator(Iterator)>::type
0094         operator()(Iterator const& it) const
0095       { return *it; }
0096     };
0097
0098     // Metafunction to obtain the type of the tuple whose element types
0099     // are the reference types of an iterator tuple.
0100     //
0101     template<typename IteratorTuple>
0102     struct tuple_of_references
0103       : mpl::transform<
0104             IteratorTuple,
0105             iterator_reference<mpl::_1>
0106           >
0107     {
0108     };
0109
0110     // Specialization for std::pair
0111     template<typename Iterator1, typename Iterator2>
0112     struct tuple_of_references<std::pair<Iterator1, Iterator2> >
0113     {
0114         typedef std::pair<
0115             typename iterator_reference<Iterator1>::type
0116           , typename iterator_reference<Iterator2>::type
0117         > type;
0118     };
0119
0120     // Metafunction to obtain the minimal traversal tag in a tuple
0121     // of iterators.
0122     //
0123     template<typename IteratorTuple>
0124     struct minimum_traversal_category_in_iterator_tuple
0125     {
0126       typedef typename mpl::transform<
0127           IteratorTuple
0128         , pure_traversal_tag<iterator_traversal<> >
0129       >::type tuple_of_traversal_tags;
0130
0131       typedef typename mpl::fold<
0132           tuple_of_traversal_tags
0133         , random_access_traversal_tag
0134         , minimum_category<>
0135       >::type type;
0136     };
0137
0138     template<typename Iterator1, typename Iterator2>
0139     struct minimum_traversal_category_in_iterator_tuple<std::pair<Iterator1, Iterator2> >
0140     {
0141         typedef typename pure_traversal_tag<
0142             typename iterator_traversal<Iterator1>::type
0143         >::type iterator1_traversal;
0144         typedef typename pure_traversal_tag<
0145             typename iterator_traversal<Iterator2>::type
0146         >::type iterator2_traversal;
0147
0148         typedef typename minimum_category<
0149             iterator1_traversal
0150           , typename minimum_category<
0151                 iterator2_traversal
0152               , random_access_traversal_tag
0153             >::type
0154         >::type type;
0155     };
0156
0157     ///////////////////////////////////////////////////////////////////
0158     //
0159     // Class zip_iterator_base
0160     //
0161     // Builds and exposes the iterator facade type from which the zip
0162     // iterator will be derived.
0163     //
0164     template<typename IteratorTuple>
0165     struct zip_iterator_base
0166     {
0167      private:
0168         // Reference type is the type of the tuple obtained from the
0169         // iterators' reference types.
0170         typedef typename
0171         detail::tuple_of_references<IteratorTuple>::type reference;
0172
0173         // Value type is the same as reference type.
0174         typedef reference value_type;
0175
0176         // Difference type is the first iterator's difference type
0177         typedef typename iterator_difference<
0178             typename mpl::at_c<IteratorTuple, 0>::type
0179         >::type difference_type;
0180
0181         // Traversal catetgory is the minimum traversal category in the
0182         // iterator tuple.
0183         typedef typename
0184         detail::minimum_traversal_category_in_iterator_tuple<
0185             IteratorTuple
0186         >::type traversal_category;
0187      public:
0188
0189         // The iterator facade type from which the zip iterator will
0190         // be derived.
0191         typedef iterator_facade<
0192             zip_iterator<IteratorTuple>,
0193             value_type,
0194             traversal_category,
0195             reference,
0196             difference_type
0197         > type;
0198     };
0199
0200     template <>
0201     struct zip_iterator_base<int>
0202     {
0203         typedef int type;
0204     };
0205
0206     template <typename reference>
0207     struct converter
0208     {
0209         template <typename Seq>
0210         static reference call(Seq seq)
0211         {
0212             typedef typename fusion::traits::tag_of<reference>::type tag;
0213             return fusion::convert<tag>(seq);
0214         }
0215     };
0216
0217     template <typename Reference1, typename Reference2>
0218     struct converter<std::pair<Reference1, Reference2> >
0219     {
0220         typedef std::pair<Reference1, Reference2> reference;
0221         template <typename Seq>
0222         static reference call(Seq seq)
0223         {
0224             return reference(
0225                 fusion::at_c<0>(seq)
0226               , fusion::at_c<1>(seq));
0227         }
0228     };
0229   }
0230
0231   /////////////////////////////////////////////////////////////////////
0232   //
0233   // zip_iterator class definition
0234   //
0235   template<typename IteratorTuple>
0236   class zip_iterator :
0237     public detail::zip_iterator_base<IteratorTuple>::type
0238   {
0239
0240    // Typedef super_t as our base class.
0241    typedef typename
0242      detail::zip_iterator_base<IteratorTuple>::type super_t;
0243
0244    // iterator_core_access is the iterator's best friend.
0245    friend class iterator_core_access;
0246
0247   public:
0248
0249     // Construction
0250     // ============
0251
0252     // Default constructor
0253     zip_iterator() { }
0254
0255     // Constructor from iterator tuple
0256     zip_iterator(IteratorTuple iterator_tuple)
0257       : m_iterator_tuple(iterator_tuple)
0258     { }
0259
0260     // Copy constructor
0261     template<typename OtherIteratorTuple>
0262     zip_iterator(
0263        const zip_iterator<OtherIteratorTuple>& other,
0264        typename enable_if_convertible<
0265          OtherIteratorTuple,
0266          IteratorTuple
0267          >::type* = 0
0268     ) : m_iterator_tuple(other.get_iterator_tuple())
0269     {}
0270
0271     // Get method for the iterator tuple.
0272     const IteratorTuple& get_iterator_tuple() const
0273     { return m_iterator_tuple; }
0274
0275   private:
0276
0277     // Implementation of Iterator Operations
0278     // =====================================
0279
0280     // Dereferencing returns a tuple built from the dereferenced
0281     // iterators in the iterator tuple.
0282     typename super_t::reference dereference() const
0283     {
0284         typedef typename super_t::reference reference;
0285         typedef detail::converter<reference> gen;
0286         return gen::call(fusion::transform(
0287           get_iterator_tuple(),
0288           detail::dereference_iterator()));
0289     }
0290
0291     // Two zip iterators are equal if all iterators in the iterator
0292     // tuple are equal. NOTE: It should be possible to implement this
0293     // as
0294     //
0295     // return get_iterator_tuple() == other.get_iterator_tuple();
0296     //
0297     // but equality of tuples currently (7/2003) does not compile
0298     // under several compilers. No point in bringing in a bunch
0299     // of #ifdefs here.
0300     //
0301     template<typename OtherIteratorTuple>
0302     bool equal(const zip_iterator<OtherIteratorTuple>& other) const
0303     {
0304         return fusion::equal_to(
0305           get_iterator_tuple(),
0306           other.get_iterator_tuple());
0307     }
0308
0309     // Advancing a zip iterator means to advance all iterators in the
0310     // iterator tuple.
0311     void advance(typename super_t::difference_type n)
0312     {
0313         fusion::for_each(
0314           m_iterator_tuple,
0315           detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n));
0316     }
0317     // Incrementing a zip iterator means to increment all iterators in
0318     // the iterator tuple.
0319     void increment()
0320     {
0321         fusion::for_each(
0322           m_iterator_tuple,
0323           detail::increment_iterator());
0324     }
0325
0326     // Decrementing a zip iterator means to decrement all iterators in
0327     // the iterator tuple.
0328     void decrement()
0329     {
0330         fusion::for_each(
0331           m_iterator_tuple,
0332           detail::decrement_iterator());
0333     }
0334
0335     // Distance is calculated using the first iterator in the tuple.
0336     template<typename OtherIteratorTuple>
0337       typename super_t::difference_type distance_to(
0338         const zip_iterator<OtherIteratorTuple>& other
0339         ) const
0340     {
0341         return fusion::at_c<0>(other.get_iterator_tuple()) -
0342             fusion::at_c<0>(this->get_iterator_tuple());
0343     }
0344
0345     // Data Members
0346     // ============
0347
0348     // The iterator tuple.
0349     IteratorTuple m_iterator_tuple;
0350
0351   };
0352
0353   // Make function for zip iterator
0354   //
0355   template<typename IteratorTuple>
0356   inline zip_iterator<IteratorTuple>
0357   make_zip_iterator(IteratorTuple t)
0358   { return zip_iterator<IteratorTuple>(t); }
0359
0360 } // namespace iterators
0361
0362 using iterators::zip_iterator;
0363 using iterators::make_zip_iterator;
0364
0365 } // namespace boost
0366
0367 #endif