boost/iterator/zip_iterator.hpp

   1 // Copyright David Abrahams and Thomas Becker 2000-2006. Distributed
   2 // under the Boost Software License, Version 1.0. (See accompanying
   3 // file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #ifndef BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
   7 # define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
   8
   9 #include <stddef.h>
  10 #include <boost/iterator.hpp>
  11 #include <boost/iterator/iterator_traits.hpp>
  12 #include <boost/iterator/iterator_facade.hpp>
  13 #include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible
  14 #include <boost/iterator/iterator_categories.hpp>
  15 #include <boost/detail/iterator.hpp>
  16
  17 #include <boost/iterator/detail/minimum_category.hpp>
  18
  19 #include <boost/tuple/tuple.hpp>
  20
  21 #include <boost/type_traits/is_same.hpp>
  22 #include <boost/mpl/and.hpp>
  23 #include <boost/mpl/apply.hpp>
  24 #include <boost/mpl/eval_if.hpp>
  25 #include <boost/mpl/lambda.hpp>
  26 #include <boost/mpl/placeholders.hpp>
  27 #include <boost/mpl/aux_/lambda_support.hpp>
  28
  29 namespace boost {
  30
  31   // Zip iterator forward declaration for zip_iterator_base
  32   template<typename IteratorTuple>
  33   class zip_iterator;
  34
  35   // One important design goal of the zip_iterator is to isolate all
  36   // functionality whose implementation relies on the current tuple
  37   // implementation. This goal has been achieved as follows: Inside
  38   // the namespace detail there is a namespace tuple_impl_specific.
  39   // This namespace encapsulates all functionality that is specific
  40   // to the current Boost tuple implementation. More precisely, the
  41   // namespace tuple_impl_specific provides the following tuple
  42   // algorithms and meta-algorithms for the current Boost tuple
  43   // implementation:
  44   //
  45   // tuple_meta_transform
  46   // tuple_meta_accumulate
  47   // tuple_transform
  48   // tuple_for_each
  49   //
  50   // If the tuple implementation changes, all that needs to be
  51   // replaced is the implementation of these four (meta-)algorithms.
  52
  53   namespace detail
  54   {
  55
  56     // Functors to be used with tuple algorithms
  57     //
  58     template<typename DiffType>
  59     class advance_iterator
  60     {
  61     public:
  62       advance_iterator(DiffType step) : m_step(step) {}
  63
  64       template<typename Iterator>
  65       void operator()(Iterator& it) const
  66       { it += m_step; }
  67
  68     private:
  69       DiffType m_step;
  70     };
  71     //
  72     struct increment_iterator
  73     {
  74       template<typename Iterator>
  75       void operator()(Iterator& it)
  76       { ++it; }
  77     };
  78     //
  79     struct decrement_iterator
  80     {
  81       template<typename Iterator>
  82       void operator()(Iterator& it)
  83       { --it; }
  84     };
  85     //
  86     struct dereference_iterator
  87     {
  88       template<typename Iterator>
  89       struct apply
  90       {
  91         typedef typename
  92           iterator_traits<Iterator>::reference
  93         type;
  94       };
  95
  96       template<typename Iterator>
  97         typename apply<Iterator>::type operator()(Iterator const& it)
  98       { return *it; }
  99     };
 100
 101
 102     // The namespace tuple_impl_specific provides two meta-
 103     // algorithms and two algorithms for tuples.
 104     //
 105     namespace tuple_impl_specific
 106     {
 107       // Meta-transform algorithm for tuples
 108       //
 109       template<typename Tuple, class UnaryMetaFun>
 110       struct tuple_meta_transform;
 111
 112       template<typename Tuple, class UnaryMetaFun>
 113       struct tuple_meta_transform_impl
 114       {
 115           typedef tuples::cons<
 116               typename mpl::apply1<
 117                   typename mpl::lambda<UnaryMetaFun>::type
 118                 , typename Tuple::head_type
 119               >::type
 120             , typename tuple_meta_transform<
 121                   typename Tuple::tail_type
 122                 , UnaryMetaFun
 123               >::type
 124           > type;
 125       };
 126
 127       template<typename Tuple, class UnaryMetaFun>
 128       struct tuple_meta_transform
 129         : mpl::eval_if<
 130               boost::is_same<Tuple, tuples::null_type>
 131             , mpl::identity<tuples::null_type>
 132             , tuple_meta_transform_impl<Tuple, UnaryMetaFun>
 133         >
 134       {
 135       };
 136
 137       // Meta-accumulate algorithm for tuples. Note: The template
 138       // parameter StartType corresponds to the initial value in
 139       // ordinary accumulation.
 140       //
 141       template<class Tuple, class BinaryMetaFun, class StartType>
 142       struct tuple_meta_accumulate;
 143
 144       template<
 145           typename Tuple
 146         , class BinaryMetaFun
 147         , typename StartType
 148       >
 149       struct tuple_meta_accumulate_impl
 150       {
 151          typedef typename mpl::apply2<
 152              typename mpl::lambda<BinaryMetaFun>::type
 153            , typename Tuple::head_type
 154            , typename tuple_meta_accumulate<
 155                  typename Tuple::tail_type
 156                , BinaryMetaFun
 157                , StartType
 158              >::type
 159          >::type type;
 160       };
 161
 162       template<
 163           typename Tuple
 164         , class BinaryMetaFun
 165         , typename StartType
 166       >
 167       struct tuple_meta_accumulate
 168         : mpl::eval_if<
 169 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 170               mpl::or_<
 171 #endif
 172                   boost::is_same<Tuple, tuples::null_type>
 173 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 174                 , boost::is_same<Tuple,int>
 175               >
 176 #endif
 177             , mpl::identity<StartType>
 178             , tuple_meta_accumulate_impl<
 179                   Tuple
 180                 , BinaryMetaFun
 181                 , StartType
 182               >
 183           >
 184       {
 185       };
 186
 187 #if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)                            \
 188     || (                                                                    \
 189       BOOST_WORKAROUND(BOOST_INTEL_CXX_VERSION, != 0) && defined(_MSC_VER)  \
 190     )
 191 // Not sure why intel's partial ordering fails in this case, but I'm
 192 // assuming int's an MSVC bug-compatibility feature.
 193
 194 # define BOOST_TUPLE_ALGO_DISPATCH
 195 # define BOOST_TUPLE_ALGO(algo) algo##_impl
 196 # define BOOST_TUPLE_ALGO_TERMINATOR , int
 197 # define BOOST_TUPLE_ALGO_RECURSE , ...
 198 #else
 199 # define BOOST_TUPLE_ALGO(algo) algo
 200 # define BOOST_TUPLE_ALGO_TERMINATOR
 201 # define BOOST_TUPLE_ALGO_RECURSE
 202 #endif
 203
 204       // transform algorithm for tuples. The template parameter Fun
 205       // must be a unary functor which is also a unary metafunction
 206       // class that computes its return type based on its argument
 207       // type. For example:
 208       //
 209       // struct to_ptr
 210       // {
 211       //     template <class Arg>
 212       //     struct apply
 213       //     {
 214       //          typedef Arg* type;
 215       //     }
 216       //
 217       //     template <class Arg>
 218       //     Arg* operator()(Arg x);
 219       // };
 220       template<typename Fun>
 221       tuples::null_type BOOST_TUPLE_ALGO(tuple_transform)
 222           (tuples::null_type const&, Fun BOOST_TUPLE_ALGO_TERMINATOR)
 223       { return tuples::null_type(); }
 224
 225       template<typename Tuple, typename Fun>
 226       typename tuple_meta_transform<
 227           Tuple
 228         , Fun
 229       >::type
 230
 231       BOOST_TUPLE_ALGO(tuple_transform)(
 232         const Tuple& t,
 233         Fun f
 234         BOOST_TUPLE_ALGO_RECURSE
 235       )
 236       {
 237           typedef typename tuple_meta_transform<
 238               BOOST_DEDUCED_TYPENAME Tuple::tail_type
 239             , Fun
 240           >::type transformed_tail_type;
 241
 242         return tuples::cons<
 243             BOOST_DEDUCED_TYPENAME mpl::apply1<
 244                 Fun, BOOST_DEDUCED_TYPENAME Tuple::head_type
 245              >::type
 246            , transformed_tail_type
 247         >(
 248             f(boost::tuples::get<0>(t)), tuple_transform(t.get_tail(), f)
 249         );
 250       }
 251
 252 #ifdef BOOST_TUPLE_ALGO_DISPATCH
 253       template<typename Tuple, typename Fun>
 254       typename tuple_meta_transform<
 255           Tuple
 256         , Fun
 257       >::type
 258
 259       tuple_transform(
 260         const Tuple& t,
 261         Fun f
 262       )
 263       {
 264           return tuple_transform_impl(t, f, 1);
 265       }
 266 #endif
 267
 268       // for_each algorithm for tuples.
 269       //
 270       template<typename Fun>
 271       Fun BOOST_TUPLE_ALGO(tuple_for_each)(
 272           tuples::null_type
 273         , Fun f BOOST_TUPLE_ALGO_TERMINATOR
 274       )
 275       { return f; }
 276
 277
 278       template<typename Tuple, typename Fun>
 279       Fun BOOST_TUPLE_ALGO(tuple_for_each)(
 280           Tuple& t
 281         , Fun f BOOST_TUPLE_ALGO_RECURSE)
 282       {
 283           f( t.get_head() );
 284           return tuple_for_each(t.get_tail(), f);
 285       }
 286
 287 #ifdef BOOST_TUPLE_ALGO_DISPATCH
 288       template<typename Tuple, typename Fun>
 289       Fun
 290       tuple_for_each(
 291         Tuple& t,
 292         Fun f
 293       )
 294       {
 295           return tuple_for_each_impl(t, f, 1);
 296       }
 297 #endif
 298
 299       // Equality of tuples. NOTE: "==" for tuples currently (7/2003)
 300       // has problems under some compilers, so I just do my own.
 301       // No point in bringing in a bunch of #ifdefs here. This is
 302       // going to go away with the next tuple implementation anyway.
 303       //
 304       inline bool tuple_equal(tuples::null_type, tuples::null_type)
 305       { return true; }
 306
 307       template<typename Tuple1, typename Tuple2>
 308         bool tuple_equal(
 309             Tuple1 const& t1,
 310             Tuple2 const& t2
 311         )
 312       {
 313           return t1.get_head() == t2.get_head() &&
 314           tuple_equal(t1.get_tail(), t2.get_tail());
 315       }
 316     }
 317     //
 318     // end namespace tuple_impl_specific
 319
 320     template<typename Iterator>
 321     struct iterator_reference
 322     {
 323         typedef typename iterator_traits<Iterator>::reference type;
 324     };
 325
 326 #ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT
 327     // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work
 328     // out well.  Instantiating the nested apply template also
 329     // requires instantiating iterator_traits on the
 330     // placeholder. Instead we just specialize it as a metafunction
 331     // class.
 332     template<>
 333     struct iterator_reference<mpl::_1>
 334     {
 335         template <class T>
 336         struct apply : iterator_reference<T> {};
 337     };
 338 #endif
 339
 340     // Metafunction to obtain the type of the tuple whose element types
 341     // are the reference types of an iterator tuple.
 342     //
 343     template<typename IteratorTuple>
 344     struct tuple_of_references
 345       : tuple_impl_specific::tuple_meta_transform<
 346             IteratorTuple,
 347             iterator_reference<mpl::_1>
 348           >
 349     {
 350     };
 351
 352     // Metafunction to obtain the minimal traversal tag in a tuple
 353     // of iterators.
 354     //
 355     template<typename IteratorTuple>
 356     struct minimum_traversal_category_in_iterator_tuple
 357     {
 358       typedef typename tuple_impl_specific::tuple_meta_transform<
 359           IteratorTuple
 360         , iterator_traversal<>
 361       >::type tuple_of_traversal_tags;
 362
 363       typedef typename tuple_impl_specific::tuple_meta_accumulate<
 364           tuple_of_traversal_tags
 365         , minimum_category<>
 366         , random_access_traversal_tag
 367       >::type type;
 368     };
 369
 370 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // ETI workaround
 371       template <>
 372       struct minimum_traversal_category_in_iterator_tuple<int>
 373       {
 374           typedef int type;
 375       };
 376 #endif
 377
 378       // We need to call tuple_meta_accumulate with mpl::and_ as the
 379       // accumulating functor. To this end, we need to wrap it into
 380       // a struct that has exactly two arguments (that is, template
 381       // parameters) and not five, like mpl::and_ does.
 382       //
 383       template<typename Arg1, typename Arg2>
 384       struct and_with_two_args
 385         : mpl::and_<Arg1, Arg2>
 386       {
 387       };
 388
 389 # ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT
 390   // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work
 391   // out well.  In this case I think it's an MPL bug
 392       template<>
 393       struct and_with_two_args<mpl::_1,mpl::_2>
 394       {
 395           template <class A1, class A2>
 396           struct apply : mpl::and_<A1,A2>
 397           {};
 398       };
 399 # endif
 400
 401     ///////////////////////////////////////////////////////////////////
 402     //
 403     // Class zip_iterator_base
 404     //
 405     // Builds and exposes the iterator facade type from which the zip
 406     // iterator will be derived.
 407     //
 408     template<typename IteratorTuple>
 409     struct zip_iterator_base
 410     {
 411      private:
 412         // Reference type is the type of the tuple obtained from the
 413         // iterators' reference types.
 414         typedef typename
 415         detail::tuple_of_references<IteratorTuple>::type reference;
 416
 417         // Value type is the same as reference type.
 418         typedef reference value_type;
 419
 420         // Difference type is the first iterator's difference type
 421         typedef typename iterator_traits<
 422             typename tuples::element<0, IteratorTuple>::type
 423             >::difference_type difference_type;
 424
 425         // Traversal catetgory is the minimum traversal category in the
 426         // iterator tuple.
 427         typedef typename
 428         detail::minimum_traversal_category_in_iterator_tuple<
 429             IteratorTuple
 430         >::type traversal_category;
 431      public:
 432
 433         // The iterator facade type from which the zip iterator will
 434         // be derived.
 435         typedef iterator_facade<
 436             zip_iterator<IteratorTuple>,
 437             value_type,
 438             traversal_category,
 439             reference,
 440             difference_type
 441         > type;
 442     };
 443
 444     template <>
 445     struct zip_iterator_base<int>
 446     {
 447         typedef int type;
 448     };
 449   }
 450
 451   /////////////////////////////////////////////////////////////////////
 452   //
 453   // zip_iterator class definition
 454   //
 455   template<typename IteratorTuple>
 456   class zip_iterator :
 457     public detail::zip_iterator_base<IteratorTuple>::type
 458   {
 459
 460    // Typedef super_t as our base class.
 461    typedef typename
 462      detail::zip_iterator_base<IteratorTuple>::type super_t;
 463
 464    // iterator_core_access is the iterator's best friend.
 465    friend class iterator_core_access;
 466
 467   public:
 468
 469     // Construction
 470     // ============
 471
 472     // Default constructor
 473     zip_iterator() { }
 474
 475     // Constructor from iterator tuple
 476     zip_iterator(IteratorTuple iterator_tuple)
 477       : m_iterator_tuple(iterator_tuple)
 478     { }
 479
 480     // Copy constructor
 481     template<typename OtherIteratorTuple>
 482     zip_iterator(
 483        const zip_iterator<OtherIteratorTuple>& other,
 484        typename enable_if_convertible<
 485          OtherIteratorTuple,
 486          IteratorTuple
 487          >::type* = 0
 488     ) : m_iterator_tuple(other.get_iterator_tuple())
 489     {}
 490
 491     // Get method for the iterator tuple.
 492     const IteratorTuple& get_iterator_tuple() const
 493     { return m_iterator_tuple; }
 494
 495   private:
 496
 497     // Implementation of Iterator Operations
 498     // =====================================
 499
 500     // Dereferencing returns a tuple built from the dereferenced
 501     // iterators in the iterator tuple.
 502     typename super_t::reference dereference() const
 503     {
 504       return detail::tuple_impl_specific::tuple_transform(
 505         get_iterator_tuple(),
 506         detail::dereference_iterator()
 507        );
 508     }
 509
 510     // Two zip iterators are equal if all iterators in the iterator
 511     // tuple are equal. NOTE: It should be possible to implement this
 512     // as
 513     //
 514     // return get_iterator_tuple() == other.get_iterator_tuple();
 515     //
 516     // but equality of tuples currently (7/2003) does not compile
 517     // under several compilers. No point in bringing in a bunch
 518     // of #ifdefs here.
 519     //
 520     template<typename OtherIteratorTuple>
 521     bool equal(const zip_iterator<OtherIteratorTuple>& other) const
 522     {
 523       return detail::tuple_impl_specific::tuple_equal(
 524         get_iterator_tuple(),
 525         other.get_iterator_tuple()
 526         );
 527     }
 528
 529     // Advancing a zip iterator means to advance all iterators in the
 530     // iterator tuple.
 531     void advance(typename super_t::difference_type n)
 532     {
 533       detail::tuple_impl_specific::tuple_for_each(
 534           m_iterator_tuple,
 535           detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n)
 536           );
 537     }
 538     // Incrementing a zip iterator means to increment all iterators in
 539     // the iterator tuple.
 540     void increment()
 541     {
 542       detail::tuple_impl_specific::tuple_for_each(
 543         m_iterator_tuple,
 544         detail::increment_iterator()
 545         );
 546     }
 547
 548     // Decrementing a zip iterator means to decrement all iterators in
 549     // the iterator tuple.
 550     void decrement()
 551     {
 552       detail::tuple_impl_specific::tuple_for_each(
 553         m_iterator_tuple,
 554         detail::decrement_iterator()
 555         );
 556     }
 557
 558     // Distance is calculated using the first iterator in the tuple.
 559     template<typename OtherIteratorTuple>
 560       typename super_t::difference_type distance_to(
 561         const zip_iterator<OtherIteratorTuple>& other
 562         ) const
 563     {
 564         return boost::tuples::get<0>(other.get_iterator_tuple()) -
 565             boost::tuples::get<0>(this->get_iterator_tuple());
 566     }
 567
 568     // Data Members
 569     // ============
 570
 571     // The iterator tuple.
 572     IteratorTuple m_iterator_tuple;
 573
 574   };
 575
 576   // Make function for zip iterator
 577   //
 578   template<typename IteratorTuple>
 579   zip_iterator<IteratorTuple>
 580   make_zip_iterator(IteratorTuple t)
 581   { return zip_iterator<IteratorTuple>(t); }
 582
 583 }
 584
 585 #endif