boost/iterator/zip_iterator.hpp

// (C) Copyright David Abrahams and Thomas Becker 2000. Permission to
// copy, use, modify, sell and distribute this software is granted
// provided this copyright notice appears in all copies. This software
// is provided "as is" without express or implied warranty, and with
// no claim as to its suitability for any purpose.
//
// Compilers Tested:
// =================
// Metrowerks Codewarrior Pro 7.2, 8.3
// gcc 2.95.3
// gcc 3.2
// Microsoft VC 6sp5 (test fails due to some compiler bug)
// Microsoft VC 7 (works)
// Microsoft VC 7.1
// Intel 5
// Intel 6
// Intel 7.1
// Intel 8
// Borland 5.5.1 (broken due to lack of support from Boost.Tuples)

#ifndef BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
# define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_

#include <stddef.h>
#include <boost/iterator.hpp>
#include <boost/iterator/iterator_traits.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible
#include <boost/iterator/iterator_categories.hpp>
#include <boost/detail/iterator.hpp>

#include <boost/iterator/detail/minimum_category.hpp>

#include <boost/tuple/tuple.hpp>

#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/lambda.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/aux_/lambda_support.hpp>

namespace boost {

  // Zip iterator forward declaration for zip_iterator_base
  template<typename IteratorTuple>
  class zip_iterator;

  // One important design goal of the zip_iterator is to isolate all
  // functionality whose implementation relies on the current tuple
  // implementation. This goal has been achieved as follows: Inside
  // the namespace detail there is a namespace tuple_impl_specific.
  // This namespace encapsulates all functionality that is specific
  // to the current Boost tuple implementation. More precisely, the
  // namespace tuple_impl_specific provides the following tuple
  // algorithms and meta-algorithms for the current Boost tuple
  // implementation:
  //
  // tuple_meta_transform
  // tuple_meta_accumulate
  // tuple_transform
  // tuple_for_each
  //
  // If the tuple implementation changes, all that needs to be
  // replaced is the implementation of these four (meta-)algorithms.

  namespace detail
  {

    // Functors to be used with tuple algorithms
    //
    template<typename DiffType>
    class advance_iterator
    {
    public:
      advance_iterator(DiffType step) : m_step(step) {}

      template<typename Iterator>
      void operator()(Iterator& it) const
      { it += m_step; }

    private:
      DiffType m_step;
    };
    //
    struct increment_iterator
    {
      template<typename Iterator>
      void operator()(Iterator& it)
      { ++it; }
    };
    //
    struct decrement_iterator
    {
      template<typename Iterator>
      void operator()(Iterator& it)
      { --it; }
    };
    //
    struct dereference_iterator
    {
      template<typename Iterator>
      struct apply
      {
        typedef typename
          iterator_traits<Iterator>::reference
        type;
      };

      template<typename Iterator>
        typename apply<Iterator>::type operator()(Iterator const& it)
      { return *it; }
    };


    // The namespace tuple_impl_specific provides two meta-
    // algorithms and two algorithms for tuples.
    //
    namespace tuple_impl_specific
    {
      // Meta-transform algorithm for tuples
      //
      template<typename Tuple, class UnaryMetaFun>
      struct tuple_meta_transform;

      template<typename Tuple, class UnaryMetaFun>
      struct tuple_meta_transform_impl
      {
          typedef tuples::cons<
              typename mpl::apply1<
                  typename mpl::lambda<UnaryMetaFun>::type
                , typename Tuple::head_type
              >::type
            , typename tuple_meta_transform<
                  typename Tuple::tail_type
                , UnaryMetaFun
              >::type
          > type;
      };

      template<typename Tuple, class UnaryMetaFun>
      struct tuple_meta_transform
        : mpl::eval_if<
              boost::is_same<Tuple, tuples::null_type>
            , mpl::identity<tuples::null_type>
            , tuple_meta_transform_impl<Tuple, UnaryMetaFun>
        >
      {
      };

      // Meta-accumulate algorithm for tuples. Note: The template
      // parameter StartType corresponds to the initial value in
      // ordinary accumulation.
      //
      template<class Tuple, class BinaryMetaFun, class StartType>
      struct tuple_meta_accumulate;

      template<
          typename Tuple
        , class BinaryMetaFun
        , typename StartType
      >
      struct tuple_meta_accumulate_impl
      {
         typedef typename mpl::apply2<
             typename mpl::lambda<BinaryMetaFun>::type
           , typename Tuple::head_type
           , typename tuple_meta_accumulate<
                 typename Tuple::tail_type
               , BinaryMetaFun
               , StartType
             >::type
         >::type type;
      };

      template<
          typename Tuple
        , class BinaryMetaFun
        , typename StartType
      >
      struct tuple_meta_accumulate
        : mpl::eval_if<
#if BOOST_WORKAROUND(BOOST_MSVC, == 1200)
              mpl::or_<
#endif
                  boost::is_same<Tuple, tuples::null_type>
#if BOOST_WORKAROUND(BOOST_MSVC, == 1200)
                , boost::is_same<Tuple,int>
              >
#endif
            , mpl::identity<StartType>
            , tuple_meta_accumulate_impl<
                  Tuple
                , BinaryMetaFun
                , StartType
              >
          >
      {
      };

#if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)                            \
    || (                                                                    \
      BOOST_WORKAROUND(BOOST_INTEL_CXX_VERSION, != 0) && defined(_MSC_VER)  \
    )
// Not sure why intel's partial ordering fails in this case, but I'm
// assuming int's an MSVC bug-compatibility feature.

# define BOOST_TUPLE_ALGO_DISPATCH
# define BOOST_TUPLE_ALGO(algo) algo##_impl
# define BOOST_TUPLE_ALGO_TERMINATOR , int
# define BOOST_TUPLE_ALGO_RECURSE , ...
#else
# define BOOST_TUPLE_ALGO(algo) algo
# define BOOST_TUPLE_ALGO_TERMINATOR
# define BOOST_TUPLE_ALGO_RECURSE
#endif

      // transform algorithm for tuples. The template parameter Fun
      // must be a unary functor which is also a unary metafunction
      // class that computes its return type based on its argument
      // type. For example:
      //
      // struct to_ptr
      // {
      //     template <class Arg>
      //     struct apply
      //     {
      //          typedef Arg* type;
      //     }
      //
      //     template <class Arg>
      //     Arg* operator()(Arg x);
      // };
      template<typename Fun>
      tuples::null_type BOOST_TUPLE_ALGO(tuple_transform)
          (tuples::null_type const&, Fun BOOST_TUPLE_ALGO_TERMINATOR)
      { return tuples::null_type(); }

      template<typename Tuple, typename Fun>
      typename tuple_meta_transform<
          Tuple
        , Fun
      >::type

      BOOST_TUPLE_ALGO(tuple_transform)(
        const Tuple& t,
        Fun f
        BOOST_TUPLE_ALGO_RECURSE
      )
      {
          typedef typename tuple_meta_transform<
              BOOST_DEDUCED_TYPENAME Tuple::tail_type
            , Fun
          >::type transformed_tail_type;

        return tuples::cons<
            BOOST_DEDUCED_TYPENAME mpl::apply1<
                Fun, BOOST_DEDUCED_TYPENAME Tuple::head_type
             >::type
           , transformed_tail_type
        >(
            f(boost::tuples::get<0>(t)), tuple_transform(t.get_tail(), f)
        );
      }

#ifdef BOOST_TUPLE_ALGO_DISPATCH
      template<typename Tuple, typename Fun>
      typename tuple_meta_transform<
          Tuple
        , Fun
      >::type

      tuple_transform(
        const Tuple& t,
        Fun f
      )
      {
          return tuple_transform_impl(t, f, 1);
      }
#endif

      // for_each algorithm for tuples.
      //
      template<typename Fun>
      Fun BOOST_TUPLE_ALGO(tuple_for_each)(
          tuples::null_type
        , Fun f BOOST_TUPLE_ALGO_TERMINATOR
      )
      { return f; }


      template<typename Tuple, typename Fun>
      Fun BOOST_TUPLE_ALGO(tuple_for_each)(
          Tuple& t
        , Fun f BOOST_TUPLE_ALGO_RECURSE)
      {
          f( t.get_head() );
          return tuple_for_each(t.get_tail(), f);
      }

#ifdef BOOST_TUPLE_ALGO_DISPATCH
      template<typename Tuple, typename Fun>
      Fun
      tuple_for_each(
        Tuple& t,
        Fun f
      )
      {
          return tuple_for_each_impl(t, f, 1);
      }
#endif

      // Equality of tuples. NOTE: "==" for tuples currently (7/2003)
      // has problems under some compilers, so I just do my own.
      // No point in bringing in a bunch of #ifdefs here. This is
      // going to go away with the next tuple implementation anyway.
      //
      bool tuple_equal(tuples::null_type, tuples::null_type)
      { return true; }

      template<typename Tuple1, typename Tuple2>
        bool tuple_equal(
            Tuple1 const& t1,
            Tuple2 const& t2
        )
      {
          return t1.get_head() == t2.get_head() &&
          tuple_equal(t1.get_tail(), t2.get_tail());
      }
    }
    //
    // end namespace tuple_impl_specific

    template<typename Iterator>
    struct iterator_reference
    {
        typedef typename iterator_traits<Iterator>::reference type;
    };

#ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT
    // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work
    // out well.  Instantiating the nested apply template also
    // requires instantiating iterator_traits on the
    // placeholder. Instead we just specialize it as a metafunction
    // class.
    template<>
    struct iterator_reference<mpl::_1>
    {
        template <class T>
        struct apply : iterator_reference<T> {};
    };
#endif

    // Metafunction to obtain the type of the tuple whose element types
    // are the reference types of an iterator tuple.
    //
    template<typename IteratorTuple>
    struct tuple_of_references
      : tuple_impl_specific::tuple_meta_transform<
            IteratorTuple,
            iterator_reference<mpl::_1>
          >
    {
    };

    // Metafunction to obtain the minimal traversal tag in a tuple
    // of iterators.
    //
    template<typename IteratorTuple>
    struct minimum_traversal_category_in_iterator_tuple
    {
      typedef typename tuple_impl_specific::tuple_meta_transform<
          IteratorTuple
        , iterator_traversal<>
      >::type tuple_of_traversal_tags;

      typedef typename tuple_impl_specific::tuple_meta_accumulate<
          tuple_of_traversal_tags
        , minimum_category<>
        , random_access_traversal_tag
      >::type type;
    };

#if BOOST_WORKAROUND(BOOST_MSVC, == 1200) // ETI workaround
      template <>
      struct minimum_traversal_category_in_iterator_tuple<int>
      {
          typedef int type;
      };
#endif

      // We need to call tuple_meta_accumulate with mpl::and_ as the
      // accumulating functor. To this end, we need to wrap it into
      // a struct that has exactly two arguments (that is, template
      // parameters) and not five, like mpl::and_ does.
      //
      template<typename Arg1, typename Arg2>
      struct and_with_two_args
        : mpl::and_<Arg1, Arg2>
      {
      };

# ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT
  // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work
  // out well.  In this case I think it's an MPL bug
      template<>
      struct and_with_two_args<mpl::_1,mpl::_2>
      {
          template <class A1, class A2>
          struct apply : mpl::and_<A1,A2>
          {};
      };
# endif

    ///////////////////////////////////////////////////////////////////
    //
    // Class zip_iterator_base
    //
    // Builds and exposes the iterator facade type from which the zip
    // iterator will be derived.
    //
    template<typename IteratorTuple>
    struct zip_iterator_base
    {
     private:
        // Reference type is the type of the tuple obtained from the
        // iterators' reference types.
        typedef typename
        detail::tuple_of_references<IteratorTuple>::type reference;

        // Value type is the same as reference type.
        typedef reference value_type;

        // Difference type is the first iterator's difference type
        typedef typename iterator_traits<
            typename tuples::element<0, IteratorTuple>::type
            >::difference_type difference_type;

        // Traversal catetgory is the minimum traversal category in the
        // iterator tuple.
        typedef typename
        detail::minimum_traversal_category_in_iterator_tuple<
            IteratorTuple
        >::type traversal_category;
     public:

        // The iterator facade type from which the zip iterator will
        // be derived.
        typedef iterator_facade<
            zip_iterator<IteratorTuple>,
            value_type,
            traversal_category,
            reference,
            difference_type
        > type;
    };

    template <>
    struct zip_iterator_base<int>
    {
        typedef int type;
    };
  }

  /////////////////////////////////////////////////////////////////////
  //
  // zip_iterator class definition
  //
  template<typename IteratorTuple>
  class zip_iterator :
    public detail::zip_iterator_base<IteratorTuple>::type
  {

   // Typedef super_t as our base class.
   typedef typename
     detail::zip_iterator_base<IteratorTuple>::type super_t;

   // iterator_core_access is the iterator's best friend.
   friend class iterator_core_access;

  public:

    // Construction
    // ============

    // Default constructor
    zip_iterator() { }

    // Constructor from iterator tuple
    zip_iterator(IteratorTuple iterator_tuple)
      : m_iterator_tuple(iterator_tuple)
    { }

    // Copy constructor
    template<typename OtherIteratorTuple>
    zip_iterator(
       const zip_iterator<OtherIteratorTuple>& other,
       typename enable_if_convertible<
         OtherIteratorTuple,
         IteratorTuple
         >::type* = 0
    ) : m_iterator_tuple(other.get_iterator_tuple())
    {}

    // Get method for the iterator tuple.
    const IteratorTuple& get_iterator_tuple() const
    { return m_iterator_tuple; }

  private:

    // Implementation of Iterator Operations
    // =====================================

    // Dereferencing returns a tuple built from the dereferenced
    // iterators in the iterator tuple.
    typename super_t::reference dereference() const
    {
      return detail::tuple_impl_specific::tuple_transform(
        get_iterator_tuple(),
        detail::dereference_iterator()
       );
    }

    // Two zip iterators are equal if all iterators in the iterator
    // tuple are equal. NOTE: It should be possible to implement this
    // as
    //
    // return get_iterator_tuple() == other.get_iterator_tuple();
    //
    // but equality of tuples currently (7/2003) does not compile
    // under several compilers. No point in bringing in a bunch
    // of #ifdefs here.
    //
    template<typename OtherIteratorTuple>
    bool equal(const zip_iterator<OtherIteratorTuple>& other) const
    {
      return detail::tuple_impl_specific::tuple_equal(
        get_iterator_tuple(),
        other.get_iterator_tuple()
        );
    }

    // Advancing a zip iterator means to advance all iterators in the
    // iterator tuple.
    void advance(typename super_t::difference_type n)
    {
      detail::tuple_impl_specific::tuple_for_each(
          m_iterator_tuple,
          detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n)
          );
    }
    // Incrementing a zip iterator means to increment all iterators in
    // the iterator tuple.
    void increment()
    {
      detail::tuple_impl_specific::tuple_for_each(
        m_iterator_tuple,
        detail::increment_iterator()
        );
    }

    // Decrementing a zip iterator means to decrement all iterators in
    // the iterator tuple.
    void decrement()
    {
      detail::tuple_impl_specific::tuple_for_each(
        m_iterator_tuple,
        detail::decrement_iterator()
        );
    }

    // Distance is calculated using the first iterator in the tuple.
    template<typename OtherIteratorTuple>
      typename super_t::difference_type distance_to(
        const zip_iterator<OtherIteratorTuple>& other
        ) const
    {
        return boost::tuples::get<0>(other.get_iterator_tuple()) -
            boost::tuples::get<0>(this->get_iterator_tuple());
    }

    // Data Members
    // ============

    // The iterator tuple.
    IteratorTuple m_iterator_tuple;

  };

  // Make function for zip iterator
  //
  template<typename IteratorTuple>
  zip_iterator<IteratorTuple>
  make_zip_iterator(IteratorTuple t)
  { return zip_iterator<IteratorTuple>(t); }

}

#endif