source: NonGTP/Boost/boost/iterator/zip_iterator.hpp @ 857

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