1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
3 //
4 // Distributed under the Boost Software License, Version 1.0
5 // See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt
7 //
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
10
11 #ifndef BOOST_COMPUTE_ITERATOR_ZIP_ITERATOR_HPP
12 #define BOOST_COMPUTE_ITERATOR_ZIP_ITERATOR_HPP
13
14 #include <cstddef>
15 #include <iterator>
16
17 #include <boost/config.hpp>
18 #include <boost/fusion/algorithm/iteration/for_each.hpp>
19 #include <boost/iterator/iterator_facade.hpp>
20 #include <boost/mpl/back_inserter.hpp>
21 #include <boost/mpl/transform.hpp>
22 #include <boost/mpl/vector.hpp>
23 #include <boost/preprocessor/repetition.hpp>
24 #include <boost/tuple/tuple.hpp>
25 #include <boost/tuple/tuple_comparison.hpp>
26
27 #include <boost/compute/config.hpp>
28 #include <boost/compute/functional.hpp>
29 #include <boost/compute/detail/meta_kernel.hpp>
30 #include <boost/compute/detail/mpl_vector_to_tuple.hpp>
31 #include <boost/compute/types/tuple.hpp>
32 #include <boost/compute/type_traits/is_device_iterator.hpp>
33 #include <boost/compute/type_traits/type_name.hpp>
34
35 namespace boost {
36 namespace compute {
37
38 // forward declaration for zip_iterator
39 template<class IteratorTuple>
40 class zip_iterator;
41
42 namespace detail {
43
44 namespace mpl = boost::mpl;
45
46 // meta-function returning the value_type for an iterator
47 template<class Iterator>
48 struct make_iterator_value_type
49 {
50 typedef typename std::iterator_traits<Iterator>::value_type type;
51 };
52
53 // meta-function returning the value_type for a zip_iterator
54 template<class IteratorTuple>
55 struct make_zip_iterator_value_type
56 {
57 typedef typename
58 detail::mpl_vector_to_tuple<
59 typename mpl::transform<
60 IteratorTuple,
61 make_iterator_value_type<mpl::_1>,
62 mpl::back_inserter<mpl::vector<> >
63 >::type
64 >::type type;
65 };
66
67 // helper class which defines the iterator_facade super-class
68 // type for zip_iterator
69 template<class IteratorTuple>
70 class zip_iterator_base
71 {
72 public:
73 typedef ::boost::iterator_facade<
74 ::boost::compute::zip_iterator<IteratorTuple>,
75 typename make_zip_iterator_value_type<IteratorTuple>::type,
76 ::std::random_access_iterator_tag,
77 typename make_zip_iterator_value_type<IteratorTuple>::type
78 > type;
79 };
80
81 template<class IteratorTuple, class IndexExpr>
82 struct zip_iterator_index_expr
83 {
84 typedef typename
85 make_zip_iterator_value_type<IteratorTuple>::type
86 result_type;
87
zip_iterator_index_exprboost::compute::detail::zip_iterator_index_expr88 zip_iterator_index_expr(const IteratorTuple &iterators,
89 const IndexExpr &index_expr)
90 : m_iterators(iterators),
91 m_index_expr(index_expr)
92 {
93 }
94
95 const IteratorTuple m_iterators;
96 const IndexExpr m_index_expr;
97 };
98
99 /// \internal_
100 #define BOOST_COMPUTE_PRINT_ELEM(z, n, unused) \
101 BOOST_PP_EXPR_IF(n, << ", ") \
102 << boost::get<n>(expr.m_iterators)[expr.m_index_expr]
103
104 /// \internal_
105 #define BOOST_COMPUTE_PRINT_ZIP_IDX(z, n, unused) \
106 template<BOOST_PP_ENUM_PARAMS(n, class Iterator), class IndexExpr> \
107 inline meta_kernel& operator<<( \
108 meta_kernel &kernel, \
109 const zip_iterator_index_expr< \
110 boost::tuple<BOOST_PP_ENUM_PARAMS(n, Iterator)>, \
111 IndexExpr \
112 > &expr) \
113 { \
114 typedef typename \
115 boost::tuple<BOOST_PP_ENUM_PARAMS(n, Iterator)> \
116 tuple_type; \
117 typedef typename \
118 make_zip_iterator_value_type<tuple_type>::type \
119 value_type; \
120 kernel.inject_type<value_type>(); \
121 return kernel \
122 << "(" << type_name<value_type>() << ")" \
123 << "{ " \
124 BOOST_PP_REPEAT(n, BOOST_COMPUTE_PRINT_ELEM, ~) \
125 << "}"; \
126 }
127
128 BOOST_PP_REPEAT_FROM_TO(1, BOOST_COMPUTE_MAX_ARITY, BOOST_COMPUTE_PRINT_ZIP_IDX, ~)
129
130 #undef BOOST_COMPUTE_PRINT_ZIP_IDX
131 #undef BOOST_COMPUTE_PRINT_ELEM
132
133 struct iterator_advancer
134 {
iterator_advancerboost::compute::detail::iterator_advancer135 iterator_advancer(size_t n)
136 : m_distance(n)
137 {
138 }
139
140 template<class Iterator>
operator ()boost::compute::detail::iterator_advancer141 void operator()(Iterator &i) const
142 {
143 std::advance(i, m_distance);
144 }
145
146 size_t m_distance;
147 };
148
149 template<class Iterator>
increment_iterator(Iterator & i)150 void increment_iterator(Iterator &i)
151 {
152 i++;
153 }
154
155 template<class Iterator>
decrement_iterator(Iterator & i)156 void decrement_iterator(Iterator &i)
157 {
158 i--;
159 }
160
161 } // end detail namespace
162
163 /// \class zip_iterator
164 /// \brief A zip iterator adaptor.
165 ///
166 /// The zip_iterator class combines values from multiple input iterators. When
167 /// dereferenced it returns a tuple containing each value at the current
168 /// position in each input range.
169 ///
170 /// \see make_zip_iterator()
171 template<class IteratorTuple>
172 class zip_iterator : public detail::zip_iterator_base<IteratorTuple>::type
173 {
174 public:
175 typedef typename
176 detail::zip_iterator_base<IteratorTuple>::type
177 super_type;
178 typedef typename super_type::value_type value_type;
179 typedef typename super_type::reference reference;
180 typedef typename super_type::difference_type difference_type;
181 typedef IteratorTuple iterator_tuple;
182
zip_iterator(IteratorTuple iterators)183 zip_iterator(IteratorTuple iterators)
184 : m_iterators(iterators)
185 {
186 }
187
zip_iterator(const zip_iterator<IteratorTuple> & other)188 zip_iterator(const zip_iterator<IteratorTuple> &other)
189 : m_iterators(other.m_iterators)
190 {
191 }
192
193 zip_iterator<IteratorTuple>&
operator =(const zip_iterator<IteratorTuple> & other)194 operator=(const zip_iterator<IteratorTuple> &other)
195 {
196 if(this != &other){
197 super_type::operator=(other);
198
199 m_iterators = other.m_iterators;
200 }
201
202 return *this;
203 }
204
~zip_iterator()205 ~zip_iterator()
206 {
207 }
208
get_iterator_tuple() const209 const IteratorTuple& get_iterator_tuple() const
210 {
211 return m_iterators;
212 }
213
214 template<class IndexExpression>
215 detail::zip_iterator_index_expr<IteratorTuple, IndexExpression>
operator [](const IndexExpression & expr) const216 operator[](const IndexExpression &expr) const
217 {
218 return detail::zip_iterator_index_expr<IteratorTuple,
219 IndexExpression>(m_iterators,
220 expr);
221 }
222
223 private:
224 friend class ::boost::iterator_core_access;
225
dereference() const226 reference dereference() const
227 {
228 return reference();
229 }
230
equal(const zip_iterator<IteratorTuple> & other) const231 bool equal(const zip_iterator<IteratorTuple> &other) const
232 {
233 return m_iterators == other.m_iterators;
234 }
235
increment()236 void increment()
237 {
238 boost::fusion::for_each(m_iterators, detail::increment_iterator);
239 }
240
decrement()241 void decrement()
242 {
243 boost::fusion::for_each(m_iterators, detail::decrement_iterator);
244 }
245
advance(difference_type n)246 void advance(difference_type n)
247 {
248 boost::fusion::for_each(m_iterators, detail::iterator_advancer(n));
249 }
250
distance_to(const zip_iterator<IteratorTuple> & other) const251 difference_type distance_to(const zip_iterator<IteratorTuple> &other) const
252 {
253 return std::distance(boost::get<0>(m_iterators),
254 boost::get<0>(other.m_iterators));
255 }
256
257 private:
258 IteratorTuple m_iterators;
259 };
260
261 /// Creates a zip_iterator for \p iterators.
262 ///
263 /// \param iterators a tuple of input iterators to zip together
264 ///
265 /// \return a \c zip_iterator for \p iterators
266 ///
267 /// For example, to zip together iterators from three vectors (\c a, \c b, and
268 /// \p c):
269 /// \code
270 /// auto zipped = boost::compute::make_zip_iterator(
271 /// boost::make_tuple(a.begin(), b.begin(), c.begin())
272 /// );
273 /// \endcode
274 template<class IteratorTuple>
275 inline zip_iterator<IteratorTuple>
make_zip_iterator(IteratorTuple iterators)276 make_zip_iterator(IteratorTuple iterators)
277 {
278 return zip_iterator<IteratorTuple>(iterators);
279 }
280
281 /// \internal_ (is_device_iterator specialization for zip_iterator)
282 template<class IteratorTuple>
283 struct is_device_iterator<zip_iterator<IteratorTuple> > : boost::true_type {};
284
285 namespace detail {
286
287 // get<N>() specialization for zip_iterator
288 /// \internal_
289 #define BOOST_COMPUTE_ZIP_GET_N(z, n, unused) \
290 template<size_t N, class IteratorTuple, class IndexExpr, \
291 BOOST_PP_ENUM_PARAMS(n, class T)> \
292 inline meta_kernel& \
293 operator<<(meta_kernel &kernel, \
294 const invoked_get< \
295 N, \
296 zip_iterator_index_expr<IteratorTuple, IndexExpr>, \
297 boost::tuple<BOOST_PP_ENUM_PARAMS(n, T)> \
298 > &expr) \
299 { \
300 typedef typename boost::tuple<BOOST_PP_ENUM_PARAMS(n, T)> Tuple; \
301 typedef typename boost::tuples::element<N, Tuple>::type T; \
302 BOOST_STATIC_ASSERT(N < size_t(boost::tuples::length<Tuple>::value)); \
303 kernel.inject_type<T>(); \
304 return kernel \
305 << boost::get<N>(expr.m_arg.m_iterators)[expr.m_arg.m_index_expr]; \
306 }
307
308 BOOST_PP_REPEAT_FROM_TO(1, BOOST_COMPUTE_MAX_ARITY, BOOST_COMPUTE_ZIP_GET_N, ~)
309
310 #undef BOOST_COMPUTE_ZIP_GET_N
311
312 } // end detail namespace
313 } // end compute namespace
314 } // end boost namespace
315
316 #endif // BOOST_COMPUTE_ITERATOR_ZIP_ITERATOR_HPP
317