Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / iterator / zip_iterator.hpp
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
44 namespace 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