boost/iterator/zip_iterator.hpp
// Copyright David Abrahams and Thomas Becker 2000-2006. Distributed // under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #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, < 1300) mpl::or_< #endif boost::is_same<Tuple, tuples::null_type> #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) , 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. // inline 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 , pure_traversal_tag<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, < 1300) // 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