boost/boost/iterator/zip_iterator.hpp

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