1// Copyright David Abrahams and Thomas Becker 2000-2006.
2// Copyright Kohei Takahashi 2012-2014.
3//
4// Distributed under the Boost Software License, Version 1.0. (See
5// accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7
8#ifndef BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
9# define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_
10
11#include <stddef.h>
12#include <boost/iterator.hpp>
13#include <boost/iterator/iterator_traits.hpp>
14#include <boost/iterator/iterator_facade.hpp>
15#include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible
16#include <boost/iterator/iterator_categories.hpp>
17
18#include <boost/iterator/minimum_category.hpp>
19
20#include <utility> // for std::pair
21#include <boost/fusion/adapted/boost_tuple.hpp> // for backward compatibility
22
23#include <boost/type_traits/remove_reference.hpp>
24#include <boost/type_traits/remove_cv.hpp>
25
26#include <boost/mpl/at.hpp>
27#include <boost/mpl/fold.hpp>
28#include <boost/mpl/transform.hpp>
29#include <boost/mpl/placeholders.hpp>
30
31#include <boost/fusion/algorithm/iteration/for_each.hpp>
32#include <boost/fusion/algorithm/transformation/transform.hpp>
33#include <boost/fusion/sequence/convert.hpp>
34#include <boost/fusion/sequence/intrinsic/at_c.hpp>
35#include <boost/fusion/sequence/comparison/equal_to.hpp>
36#include <boost/fusion/support/tag_of_fwd.hpp>
37
38namespace boost {
39namespace iterators {
40
41 // Zip iterator forward declaration for zip_iterator_base
42 template<typename IteratorTuple>
43 class zip_iterator;
44
45 namespace detail
46 {
47
48 // Functors to be used with tuple algorithms
49 //
50 template<typename DiffType>
51 class advance_iterator
52 {
53 public:
54 advance_iterator(DiffType step) : m_step(step) {}
55
56 template<typename Iterator>
57 void operator()(Iterator& it) const
58 { it += m_step; }
59
60 private:
61 DiffType m_step;
62 };
63 //
64 struct increment_iterator
65 {
66 template<typename Iterator>
67 void operator()(Iterator& it) const
68 { ++it; }
69 };
70 //
71 struct decrement_iterator
72 {
73 template<typename Iterator>
74 void operator()(Iterator& it) const
75 { --it; }
76 };
77 //
78 struct dereference_iterator
79 {
80 template<typename>
81 struct result;
82
83 template<typename This, typename Iterator>
84 struct result<This(Iterator)>
85 {
86 typedef typename
87 remove_reference<typename remove_cv<Iterator>::type>::type
88 iterator;
89
90 typedef typename iterator_reference<iterator>::type type;
91 };
92
93 template<typename Iterator>
94 typename result<dereference_iterator(Iterator)>::type
95 operator()(Iterator const& it) const
96 { return *it; }
97 };
98
99 // Metafunction to obtain the type of the tuple whose element types
100 // are the reference types of an iterator tuple.
101 //
102 template<typename IteratorTuple>
103 struct tuple_of_references
104 : mpl::transform<
105 IteratorTuple,
106 iterator_reference<mpl::_1>
107 >
108 {
109 };
110
111 // Specialization for std::pair
112 template<typename Iterator1, typename Iterator2>
113 struct tuple_of_references<std::pair<Iterator1, Iterator2> >
114 {
115 typedef std::pair<
116 typename iterator_reference<Iterator1>::type
117 , typename iterator_reference<Iterator2>::type
118 > type;
119 };
120
121 // Metafunction to obtain the minimal traversal tag in a tuple
122 // of iterators.
123 //
124 template<typename IteratorTuple>
125 struct minimum_traversal_category_in_iterator_tuple
126 {
127 typedef typename mpl::transform<
128 IteratorTuple
129 , pure_traversal_tag<iterator_traversal<> >
130 >::type tuple_of_traversal_tags;
131
132 typedef typename mpl::fold<
133 tuple_of_traversal_tags
134 , random_access_traversal_tag
135 , minimum_category<>
136 >::type type;
137 };
138
139 template<typename Iterator1, typename Iterator2>
140 struct minimum_traversal_category_in_iterator_tuple<std::pair<Iterator1, Iterator2> >
141 {
142 typedef typename pure_traversal_tag<
143 typename iterator_traversal<Iterator1>::type
144 >::type iterator1_traversal;
145 typedef typename pure_traversal_tag<
146 typename iterator_traversal<Iterator2>::type
147 >::type iterator2_traversal;
148
149 typedef typename minimum_category<
150 iterator1_traversal
151 , typename minimum_category<
152 iterator2_traversal
153 , random_access_traversal_tag
154 >::type
155 >::type type;
156 };
157
158 ///////////////////////////////////////////////////////////////////
159 //
160 // Class zip_iterator_base
161 //
162 // Builds and exposes the iterator facade type from which the zip
163 // iterator will be derived.
164 //
165 template<typename IteratorTuple>
166 struct zip_iterator_base
167 {
168 private:
169 // Reference type is the type of the tuple obtained from the
170 // iterators' reference types.
171 typedef typename
172 detail::tuple_of_references<IteratorTuple>::type reference;
173
174 // Value type is the same as reference type.
175 typedef reference value_type;
176
177 // Difference type is the first iterator's difference type
178 typedef typename iterator_difference<
179 typename mpl::at_c<IteratorTuple, 0>::type
180 >::type difference_type;
181
182 // Traversal catetgory is the minimum traversal category in the
183 // iterator tuple.
184 typedef typename
185 detail::minimum_traversal_category_in_iterator_tuple<
186 IteratorTuple
187 >::type traversal_category;
188 public:
189
190 // The iterator facade type from which the zip iterator will
191 // be derived.
192 typedef iterator_facade<
193 zip_iterator<IteratorTuple>,
194 value_type,
195 traversal_category,
196 reference,
197 difference_type
198 > type;
199 };
200
201 template <>
202 struct zip_iterator_base<int>
203 {
204 typedef int type;
205 };
206
207 template <typename reference>
208 struct converter
209 {
210 template <typename Seq>
211 static reference call(Seq seq)
212 {
213 typedef typename fusion::traits::tag_of<reference>::type tag;
214 return fusion::convert<tag>(seq);
215 }
216 };
217
218 template <typename Reference1, typename Reference2>
219 struct converter<std::pair<Reference1, Reference2> >
220 {
221 typedef std::pair<Reference1, Reference2> reference;
222 template <typename Seq>
223 static reference call(Seq seq)
224 {
225 return reference(
226 fusion::at_c<0>(seq)
227 , fusion::at_c<1>(seq));
228 }
229 };
230 }
231
232 /////////////////////////////////////////////////////////////////////
233 //
234 // zip_iterator class definition
235 //
236 template<typename IteratorTuple>
237 class zip_iterator :
238 public detail::zip_iterator_base<IteratorTuple>::type
239 {
240
241 // Typedef super_t as our base class.
242 typedef typename
243 detail::zip_iterator_base<IteratorTuple>::type super_t;
244
245 // iterator_core_access is the iterator's best friend.
246 friend class iterator_core_access;
247
248 public:
249
250 // Construction
251 // ============
252
253 // Default constructor
254 zip_iterator() { }
255
256 // Constructor from iterator tuple
257 zip_iterator(IteratorTuple iterator_tuple)
258 : m_iterator_tuple(iterator_tuple)
259 { }
260
261 // Copy constructor
262 template<typename OtherIteratorTuple>
263 zip_iterator(
264 const zip_iterator<OtherIteratorTuple>& other,
265 typename enable_if_convertible<
266 OtherIteratorTuple,
267 IteratorTuple
268 >::type* = 0
269 ) : m_iterator_tuple(other.get_iterator_tuple())
270 {}
271
272 // Get method for the iterator tuple.
273 const IteratorTuple& get_iterator_tuple() const
274 { return m_iterator_tuple; }
275
276 private:
277
278 // Implementation of Iterator Operations
279 // =====================================
280
281 // Dereferencing returns a tuple built from the dereferenced
282 // iterators in the iterator tuple.
283 typename super_t::reference dereference() const
284 {
285 typedef typename super_t::reference reference;
286 typedef detail::converter<reference> gen;
287 return gen::call(fusion::transform(
288 get_iterator_tuple(),
289 detail::dereference_iterator()));
290 }
291
292 // Two zip iterators are equal if all iterators in the iterator
293 // tuple are equal. NOTE: It should be possible to implement this
294 // as
295 //
296 // return get_iterator_tuple() == other.get_iterator_tuple();
297 //
298 // but equality of tuples currently (7/2003) does not compile
299 // under several compilers. No point in bringing in a bunch
300 // of #ifdefs here.
301 //
302 template<typename OtherIteratorTuple>
303 bool equal(const zip_iterator<OtherIteratorTuple>& other) const
304 {
305 return fusion::equal_to(
306 get_iterator_tuple(),
307 other.get_iterator_tuple());
308 }
309
310 // Advancing a zip iterator means to advance all iterators in the
311 // iterator tuple.
312 void advance(typename super_t::difference_type n)
313 {
314 fusion::for_each(
315 m_iterator_tuple,
316 detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n));
317 }
318 // Incrementing a zip iterator means to increment all iterators in
319 // the iterator tuple.
320 void increment()
321 {
322 fusion::for_each(
323 m_iterator_tuple,
324 detail::increment_iterator());
325 }
326
327 // Decrementing a zip iterator means to decrement all iterators in
328 // the iterator tuple.
329 void decrement()
330 {
331 fusion::for_each(
332 m_iterator_tuple,
333 detail::decrement_iterator());
334 }
335
336 // Distance is calculated using the first iterator in the tuple.
337 template<typename OtherIteratorTuple>
338 typename super_t::difference_type distance_to(
339 const zip_iterator<OtherIteratorTuple>& other
340 ) const
341 {
342 return fusion::at_c<0>(other.get_iterator_tuple()) -
343 fusion::at_c<0>(this->get_iterator_tuple());
344 }
345
346 // Data Members
347 // ============
348
349 // The iterator tuple.
350 IteratorTuple m_iterator_tuple;
351
352 };
353
354 // Make function for zip iterator
355 //
356 template<typename IteratorTuple>
357 inline zip_iterator<IteratorTuple>
358 make_zip_iterator(IteratorTuple t)
359 { return zip_iterator<IteratorTuple>(t); }
360
361} // namespace iterators
362
363using iterators::zip_iterator;
364using iterators::make_zip_iterator;
365
366} // namespace boost
367
368#endif
369