Chris@16: // Copyright David Abrahams and Thomas Becker 2000-2006. Distributed
Chris@16: // under the Boost Software License, Version 1.0. (See accompanying
Chris@16: // file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
Chris@16: # define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
Chris@16: 
Chris@16: #include <stddef.h>
Chris@16: #include <boost/iterator.hpp>
Chris@16: #include <boost/iterator/iterator_traits.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible
Chris@16: #include <boost/iterator/iterator_categories.hpp>
Chris@16: #include <boost/detail/iterator.hpp>
Chris@16: 
Chris@101: #include <boost/iterator/minimum_category.hpp>
Chris@16: 
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: 
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/mpl/and.hpp>
Chris@16: #include <boost/mpl/apply.hpp>
Chris@16: #include <boost/mpl/eval_if.hpp>
Chris@16: #include <boost/mpl/lambda.hpp>
Chris@16: #include <boost/mpl/placeholders.hpp>
Chris@16: #include <boost/mpl/aux_/lambda_support.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@101: namespace iterators {
Chris@16: 
Chris@16:   // Zip iterator forward declaration for zip_iterator_base
Chris@16:   template<typename IteratorTuple>
Chris@16:   class zip_iterator;
Chris@16: 
Chris@16:   // One important design goal of the zip_iterator is to isolate all
Chris@16:   // functionality whose implementation relies on the current tuple
Chris@16:   // implementation. This goal has been achieved as follows: Inside
Chris@16:   // the namespace detail there is a namespace tuple_impl_specific.
Chris@16:   // This namespace encapsulates all functionality that is specific
Chris@16:   // to the current Boost tuple implementation. More precisely, the
Chris@16:   // namespace tuple_impl_specific provides the following tuple
Chris@16:   // algorithms and meta-algorithms for the current Boost tuple
Chris@16:   // implementation:
Chris@16:   //
Chris@16:   // tuple_meta_transform
Chris@16:   // tuple_meta_accumulate
Chris@16:   // tuple_transform
Chris@16:   // tuple_for_each
Chris@16:   //
Chris@16:   // If the tuple implementation changes, all that needs to be
Chris@16:   // replaced is the implementation of these four (meta-)algorithms.
Chris@16: 
Chris@16:   namespace detail
Chris@16:   {
Chris@16: 
Chris@16:     // Functors to be used with tuple algorithms
Chris@16:     //
Chris@16:     template<typename DiffType>
Chris@16:     class advance_iterator
Chris@16:     {
Chris@16:     public:
Chris@16:       advance_iterator(DiffType step) : m_step(step) {}
Chris@101: 
Chris@16:       template<typename Iterator>
Chris@16:       void operator()(Iterator& it) const
Chris@16:       { it += m_step; }
Chris@16: 
Chris@16:     private:
Chris@16:       DiffType m_step;
Chris@16:     };
Chris@16:     //
Chris@16:     struct increment_iterator
Chris@16:     {
Chris@16:       template<typename Iterator>
Chris@16:       void operator()(Iterator& it)
Chris@16:       { ++it; }
Chris@16:     };
Chris@16:     //
Chris@16:     struct decrement_iterator
Chris@16:     {
Chris@16:       template<typename Iterator>
Chris@16:       void operator()(Iterator& it)
Chris@16:       { --it; }
Chris@16:     };
Chris@16:     //
Chris@16:     struct dereference_iterator
Chris@16:     {
Chris@16:       template<typename Iterator>
Chris@16:       struct apply
Chris@101:       {
Chris@16:         typedef typename
Chris@101:           boost::detail::iterator_traits<Iterator>::reference
Chris@16:         type;
Chris@16:       };
Chris@16: 
Chris@16:       template<typename Iterator>
Chris@16:         typename apply<Iterator>::type operator()(Iterator const& it)
Chris@16:       { return *it; }
Chris@16:     };
Chris@101: 
Chris@16: 
Chris@16:     // The namespace tuple_impl_specific provides two meta-
Chris@16:     // algorithms and two algorithms for tuples.
Chris@16:     //
Chris@16:     namespace tuple_impl_specific
Chris@16:     {
Chris@16:       // Meta-transform algorithm for tuples
Chris@16:       //
Chris@16:       template<typename Tuple, class UnaryMetaFun>
Chris@16:       struct tuple_meta_transform;
Chris@101: 
Chris@16:       template<typename Tuple, class UnaryMetaFun>
Chris@16:       struct tuple_meta_transform_impl
Chris@16:       {
Chris@16:           typedef tuples::cons<
Chris@16:               typename mpl::apply1<
Chris@16:                   typename mpl::lambda<UnaryMetaFun>::type
Chris@16:                 , typename Tuple::head_type
Chris@16:               >::type
Chris@16:             , typename tuple_meta_transform<
Chris@16:                   typename Tuple::tail_type
Chris@101:                 , UnaryMetaFun
Chris@16:               >::type
Chris@16:           > type;
Chris@16:       };
Chris@16: 
Chris@16:       template<typename Tuple, class UnaryMetaFun>
Chris@16:       struct tuple_meta_transform
Chris@16:         : mpl::eval_if<
Chris@16:               boost::is_same<Tuple, tuples::null_type>
Chris@16:             , mpl::identity<tuples::null_type>
Chris@16:             , tuple_meta_transform_impl<Tuple, UnaryMetaFun>
Chris@16:         >
Chris@16:       {
Chris@16:       };
Chris@101: 
Chris@101:       // Meta-accumulate algorithm for tuples. Note: The template
Chris@101:       // parameter StartType corresponds to the initial value in
Chris@16:       // ordinary accumulation.
Chris@16:       //
Chris@16:       template<class Tuple, class BinaryMetaFun, class StartType>
Chris@16:       struct tuple_meta_accumulate;
Chris@101: 
Chris@16:       template<
Chris@16:           typename Tuple
Chris@16:         , class BinaryMetaFun
Chris@16:         , typename StartType
Chris@16:       >
Chris@16:       struct tuple_meta_accumulate_impl
Chris@16:       {
Chris@16:          typedef typename mpl::apply2<
Chris@16:              typename mpl::lambda<BinaryMetaFun>::type
Chris@16:            , typename Tuple::head_type
Chris@16:            , typename tuple_meta_accumulate<
Chris@16:                  typename Tuple::tail_type
Chris@16:                , BinaryMetaFun
Chris@101:                , StartType
Chris@16:              >::type
Chris@16:          >::type type;
Chris@16:       };
Chris@16: 
Chris@16:       template<
Chris@16:           typename Tuple
Chris@16:         , class BinaryMetaFun
Chris@16:         , typename StartType
Chris@16:       >
Chris@16:       struct tuple_meta_accumulate
Chris@16:         : mpl::eval_if<
Chris@16:                   boost::is_same<Tuple, tuples::null_type>
Chris@16:             , mpl::identity<StartType>
Chris@16:             , tuple_meta_accumulate_impl<
Chris@16:                   Tuple
Chris@16:                 , BinaryMetaFun
Chris@16:                 , StartType
Chris@16:               >
Chris@16:           >
Chris@16:       {
Chris@101:       };
Chris@16: 
Chris@16: #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)                            \
Chris@16:     || (                                                                    \
Chris@16:       BOOST_WORKAROUND(BOOST_INTEL_CXX_VERSION, != 0) && defined(_MSC_VER)  \
Chris@16:     )
Chris@16: // Not sure why intel's partial ordering fails in this case, but I'm
Chris@16: // assuming int's an MSVC bug-compatibility feature.
Chris@101: 
Chris@16: # define BOOST_TUPLE_ALGO_DISPATCH
Chris@16: # define BOOST_TUPLE_ALGO(algo) algo##_impl
Chris@16: # define BOOST_TUPLE_ALGO_TERMINATOR , int
Chris@16: # define BOOST_TUPLE_ALGO_RECURSE , ...
Chris@101: #else
Chris@16: # define BOOST_TUPLE_ALGO(algo) algo
Chris@16: # define BOOST_TUPLE_ALGO_TERMINATOR
Chris@16: # define BOOST_TUPLE_ALGO_RECURSE
Chris@16: #endif
Chris@101: 
Chris@16:       // transform algorithm for tuples. The template parameter Fun
Chris@16:       // must be a unary functor which is also a unary metafunction
Chris@16:       // class that computes its return type based on its argument
Chris@16:       // type. For example:
Chris@16:       //
Chris@16:       // struct to_ptr
Chris@16:       // {
Chris@16:       //     template <class Arg>
Chris@16:       //     struct apply
Chris@16:       //     {
Chris@16:       //          typedef Arg* type;
Chris@16:       //     }
Chris@16:       //
Chris@16:       //     template <class Arg>
Chris@16:       //     Arg* operator()(Arg x);
Chris@16:       // };
Chris@16:       template<typename Fun>
Chris@101:       inline tuples::null_type BOOST_TUPLE_ALGO(tuple_transform)
Chris@16:           (tuples::null_type const&, Fun BOOST_TUPLE_ALGO_TERMINATOR)
Chris@16:       { return tuples::null_type(); }
Chris@16: 
Chris@16:       template<typename Tuple, typename Fun>
Chris@101:       inline typename tuple_meta_transform<
Chris@16:           Tuple
Chris@16:         , Fun
Chris@16:       >::type
Chris@101: 
Chris@16:       BOOST_TUPLE_ALGO(tuple_transform)(
Chris@101:         const Tuple& t,
Chris@16:         Fun f
Chris@16:         BOOST_TUPLE_ALGO_RECURSE
Chris@16:       )
Chris@101:       {
Chris@16:           typedef typename tuple_meta_transform<
Chris@16:               BOOST_DEDUCED_TYPENAME Tuple::tail_type
Chris@16:             , Fun
Chris@16:           >::type transformed_tail_type;
Chris@16: 
Chris@16:         return tuples::cons<
Chris@16:             BOOST_DEDUCED_TYPENAME mpl::apply1<
Chris@16:                 Fun, BOOST_DEDUCED_TYPENAME Tuple::head_type
Chris@16:              >::type
Chris@16:            , transformed_tail_type
Chris@101:         >(
Chris@16:             f(boost::tuples::get<0>(t)), tuple_transform(t.get_tail(), f)
Chris@16:         );
Chris@16:       }
Chris@16: 
Chris@16: #ifdef BOOST_TUPLE_ALGO_DISPATCH
Chris@16:       template<typename Tuple, typename Fun>
Chris@101:       inline typename tuple_meta_transform<
Chris@16:           Tuple
Chris@16:         , Fun
Chris@16:       >::type
Chris@101: 
Chris@16:       tuple_transform(
Chris@101:         const Tuple& t,
Chris@16:         Fun f
Chris@16:       )
Chris@16:       {
Chris@16:           return tuple_transform_impl(t, f, 1);
Chris@16:       }
Chris@16: #endif
Chris@101: 
Chris@16:       // for_each algorithm for tuples.
Chris@16:       //
Chris@16:       template<typename Fun>
Chris@101:       inline Fun BOOST_TUPLE_ALGO(tuple_for_each)(
Chris@16:           tuples::null_type
Chris@16:         , Fun f BOOST_TUPLE_ALGO_TERMINATOR
Chris@16:       )
Chris@16:       { return f; }
Chris@16: 
Chris@101: 
Chris@16:       template<typename Tuple, typename Fun>
Chris@101:       inline Fun BOOST_TUPLE_ALGO(tuple_for_each)(
Chris@16:           Tuple& t
Chris@16:         , Fun f BOOST_TUPLE_ALGO_RECURSE)
Chris@101:       {
Chris@16:           f( t.get_head() );
Chris@16:           return tuple_for_each(t.get_tail(), f);
Chris@16:       }
Chris@101: 
Chris@16: #ifdef BOOST_TUPLE_ALGO_DISPATCH
Chris@16:       template<typename Tuple, typename Fun>
Chris@101:       inline Fun
Chris@16:       tuple_for_each(
Chris@101:         Tuple& t,
Chris@16:         Fun f
Chris@16:       )
Chris@16:       {
Chris@16:           return tuple_for_each_impl(t, f, 1);
Chris@16:       }
Chris@16: #endif
Chris@101: 
Chris@16:       // Equality of tuples. NOTE: "==" for tuples currently (7/2003)
Chris@16:       // has problems under some compilers, so I just do my own.
Chris@16:       // No point in bringing in a bunch of #ifdefs here. This is
Chris@16:       // going to go away with the next tuple implementation anyway.
Chris@16:       //
Chris@16:       inline bool tuple_equal(tuples::null_type, tuples::null_type)
Chris@16:       { return true; }
Chris@16: 
Chris@16:       template<typename Tuple1, typename Tuple2>
Chris@101:       inline bool tuple_equal(Tuple1 const& t1, Tuple2 const& t2)
Chris@101:       {
Chris@101:           return t1.get_head() == t2.get_head() &&
Chris@16:           tuple_equal(t1.get_tail(), t2.get_tail());
Chris@16:       }
Chris@16:     }
Chris@16:     //
Chris@16:     // end namespace tuple_impl_specific
Chris@16: 
Chris@16:     template<typename Iterator>
Chris@16:     struct iterator_reference
Chris@16:     {
Chris@101:         typedef typename boost::detail::iterator_traits<Iterator>::reference type;
Chris@16:     };
Chris@16: 
Chris@16: #ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT
Chris@16:     // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work
Chris@16:     // out well.  Instantiating the nested apply template also
Chris@16:     // requires instantiating iterator_traits on the
Chris@16:     // placeholder. Instead we just specialize it as a metafunction
Chris@16:     // class.
Chris@16:     template<>
Chris@16:     struct iterator_reference<mpl::_1>
Chris@16:     {
Chris@16:         template <class T>
Chris@16:         struct apply : iterator_reference<T> {};
Chris@16:     };
Chris@16: #endif
Chris@101: 
Chris@16:     // Metafunction to obtain the type of the tuple whose element types
Chris@16:     // are the reference types of an iterator tuple.
Chris@16:     //
Chris@16:     template<typename IteratorTuple>
Chris@16:     struct tuple_of_references
Chris@16:       : tuple_impl_specific::tuple_meta_transform<
Chris@101:             IteratorTuple,
Chris@16:             iterator_reference<mpl::_1>
Chris@16:           >
Chris@16:     {
Chris@16:     };
Chris@16: 
Chris@16:     // Metafunction to obtain the minimal traversal tag in a tuple
Chris@16:     // of iterators.
Chris@16:     //
Chris@16:     template<typename IteratorTuple>
Chris@16:     struct minimum_traversal_category_in_iterator_tuple
Chris@16:     {
Chris@16:       typedef typename tuple_impl_specific::tuple_meta_transform<
Chris@16:           IteratorTuple
Chris@16:         , pure_traversal_tag<iterator_traversal<> >
Chris@16:       >::type tuple_of_traversal_tags;
Chris@101: 
Chris@16:       typedef typename tuple_impl_specific::tuple_meta_accumulate<
Chris@16:           tuple_of_traversal_tags
Chris@16:         , minimum_category<>
Chris@16:         , random_access_traversal_tag
Chris@16:       >::type type;
Chris@16:     };
Chris@16: 
Chris@16:       // We need to call tuple_meta_accumulate with mpl::and_ as the
Chris@16:       // accumulating functor. To this end, we need to wrap it into
Chris@16:       // a struct that has exactly two arguments (that is, template
Chris@16:       // parameters) and not five, like mpl::and_ does.
Chris@16:       //
Chris@16:       template<typename Arg1, typename Arg2>
Chris@16:       struct and_with_two_args
Chris@16:         : mpl::and_<Arg1, Arg2>
Chris@16:       {
Chris@16:       };
Chris@101: 
Chris@16: # ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT
Chris@16:   // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work
Chris@16:   // out well.  In this case I think it's an MPL bug
Chris@16:       template<>
Chris@16:       struct and_with_two_args<mpl::_1,mpl::_2>
Chris@16:       {
Chris@16:           template <class A1, class A2>
Chris@16:           struct apply : mpl::and_<A1,A2>
Chris@16:           {};
Chris@16:       };
Chris@101: # endif
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     // Class zip_iterator_base
Chris@16:     //
Chris@101:     // Builds and exposes the iterator facade type from which the zip
Chris@16:     // iterator will be derived.
Chris@16:     //
Chris@16:     template<typename IteratorTuple>
Chris@16:     struct zip_iterator_base
Chris@16:     {
Chris@16:      private:
Chris@16:         // Reference type is the type of the tuple obtained from the
Chris@16:         // iterators' reference types.
Chris@101:         typedef typename
Chris@16:         detail::tuple_of_references<IteratorTuple>::type reference;
Chris@101: 
Chris@16:         // Value type is the same as reference type.
Chris@16:         typedef reference value_type;
Chris@101: 
Chris@16:         // Difference type is the first iterator's difference type
Chris@101:         typedef typename boost::detail::iterator_traits<
Chris@16:             typename tuples::element<0, IteratorTuple>::type
Chris@16:             >::difference_type difference_type;
Chris@101: 
Chris@101:         // Traversal catetgory is the minimum traversal category in the
Chris@16:         // iterator tuple.
Chris@101:         typedef typename
Chris@16:         detail::minimum_traversal_category_in_iterator_tuple<
Chris@16:             IteratorTuple
Chris@16:         >::type traversal_category;
Chris@16:      public:
Chris@101: 
Chris@16:         // The iterator facade type from which the zip iterator will
Chris@16:         // be derived.
Chris@16:         typedef iterator_facade<
Chris@16:             zip_iterator<IteratorTuple>,
Chris@101:             value_type,
Chris@16:             traversal_category,
Chris@16:             reference,
Chris@16:             difference_type
Chris@16:         > type;
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct zip_iterator_base<int>
Chris@16:     {
Chris@16:         typedef int type;
Chris@16:     };
Chris@16:   }
Chris@101: 
Chris@16:   /////////////////////////////////////////////////////////////////////
Chris@16:   //
Chris@16:   // zip_iterator class definition
Chris@16:   //
Chris@16:   template<typename IteratorTuple>
Chris@101:   class zip_iterator :
Chris@16:     public detail::zip_iterator_base<IteratorTuple>::type
Chris@101:   {
Chris@16: 
Chris@101:    // Typedef super_t as our base class.
Chris@101:    typedef typename
Chris@16:      detail::zip_iterator_base<IteratorTuple>::type super_t;
Chris@16: 
Chris@16:    // iterator_core_access is the iterator's best friend.
Chris@16:    friend class iterator_core_access;
Chris@16: 
Chris@16:   public:
Chris@101: 
Chris@16:     // Construction
Chris@16:     // ============
Chris@101: 
Chris@16:     // Default constructor
Chris@16:     zip_iterator() { }
Chris@16: 
Chris@16:     // Constructor from iterator tuple
Chris@101:     zip_iterator(IteratorTuple iterator_tuple)
Chris@101:       : m_iterator_tuple(iterator_tuple)
Chris@16:     { }
Chris@16: 
Chris@16:     // Copy constructor
Chris@16:     template<typename OtherIteratorTuple>
Chris@16:     zip_iterator(
Chris@16:        const zip_iterator<OtherIteratorTuple>& other,
Chris@16:        typename enable_if_convertible<
Chris@16:          OtherIteratorTuple,
Chris@16:          IteratorTuple
Chris@16:          >::type* = 0
Chris@16:     ) : m_iterator_tuple(other.get_iterator_tuple())
Chris@16:     {}
Chris@16: 
Chris@16:     // Get method for the iterator tuple.
Chris@16:     const IteratorTuple& get_iterator_tuple() const
Chris@16:     { return m_iterator_tuple; }
Chris@16: 
Chris@16:   private:
Chris@101: 
Chris@16:     // Implementation of Iterator Operations
Chris@16:     // =====================================
Chris@101: 
Chris@16:     // Dereferencing returns a tuple built from the dereferenced
Chris@16:     // iterators in the iterator tuple.
Chris@16:     typename super_t::reference dereference() const
Chris@101:     {
Chris@101:       return detail::tuple_impl_specific::tuple_transform(
Chris@16:         get_iterator_tuple(),
Chris@16:         detail::dereference_iterator()
Chris@16:        );
Chris@16:     }
Chris@16: 
Chris@16:     // Two zip iterators are equal if all iterators in the iterator
Chris@16:     // tuple are equal. NOTE: It should be possible to implement this
Chris@16:     // as
Chris@16:     //
Chris@16:     // return get_iterator_tuple() == other.get_iterator_tuple();
Chris@16:     //
Chris@16:     // but equality of tuples currently (7/2003) does not compile
Chris@16:     // under several compilers. No point in bringing in a bunch
Chris@16:     // of #ifdefs here.
Chris@16:     //
Chris@101:     template<typename OtherIteratorTuple>
Chris@16:     bool equal(const zip_iterator<OtherIteratorTuple>& other) const
Chris@16:     {
Chris@16:       return detail::tuple_impl_specific::tuple_equal(
Chris@16:         get_iterator_tuple(),
Chris@16:         other.get_iterator_tuple()
Chris@16:         );
Chris@16:     }
Chris@16: 
Chris@16:     // Advancing a zip iterator means to advance all iterators in the
Chris@16:     // iterator tuple.
Chris@16:     void advance(typename super_t::difference_type n)
Chris@101:     {
Chris@16:       detail::tuple_impl_specific::tuple_for_each(
Chris@16:           m_iterator_tuple,
Chris@16:           detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n)
Chris@16:           );
Chris@16:     }
Chris@16:     // Incrementing a zip iterator means to increment all iterators in
Chris@16:     // the iterator tuple.
Chris@16:     void increment()
Chris@101:     {
Chris@16:       detail::tuple_impl_specific::tuple_for_each(
Chris@16:         m_iterator_tuple,
Chris@16:         detail::increment_iterator()
Chris@16:         );
Chris@16:     }
Chris@101: 
Chris@16:     // Decrementing a zip iterator means to decrement all iterators in
Chris@16:     // the iterator tuple.
Chris@16:     void decrement()
Chris@101:     {
Chris@16:       detail::tuple_impl_specific::tuple_for_each(
Chris@16:         m_iterator_tuple,
Chris@16:         detail::decrement_iterator()
Chris@16:         );
Chris@16:     }
Chris@101: 
Chris@16:     // Distance is calculated using the first iterator in the tuple.
Chris@16:     template<typename OtherIteratorTuple>
Chris@16:       typename super_t::difference_type distance_to(
Chris@16:         const zip_iterator<OtherIteratorTuple>& other
Chris@16:         ) const
Chris@101:     {
Chris@101:         return boost::tuples::get<0>(other.get_iterator_tuple()) -
Chris@16:             boost::tuples::get<0>(this->get_iterator_tuple());
Chris@16:     }
Chris@101: 
Chris@16:     // Data Members
Chris@16:     // ============
Chris@101: 
Chris@16:     // The iterator tuple.
Chris@16:     IteratorTuple m_iterator_tuple;
Chris@101: 
Chris@16:   };
Chris@16: 
Chris@16:   // Make function for zip iterator
Chris@16:   //
Chris@101:   template<typename IteratorTuple>
Chris@101:   inline zip_iterator<IteratorTuple>
Chris@16:   make_zip_iterator(IteratorTuple t)
Chris@16:   { return zip_iterator<IteratorTuple>(t); }
Chris@16: 
Chris@101: } // namespace iterators
Chris@101: 
Chris@101: using iterators::zip_iterator;
Chris@101: using iterators::make_zip_iterator;
Chris@101: 
Chris@101: } // namespace boost
Chris@16: 
Chris@16: #endif