1/*
2 Copyright (c) 2017-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17#ifndef __TBB_iterators_H
18#define __TBB_iterators_H
19
20#include <iterator>
21#include <limits>
22
23#include "tbb_config.h"
24#include "tbb_stddef.h"
25
26#if __TBB_CPP11_PRESENT
27
28#include <type_traits>
29
30namespace tbb {
31
32template <typename IntType>
33class counting_iterator {
34 __TBB_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer, "Cannot instantiate counting_iterator with a non-integer type");
35public:
36 typedef typename std::make_signed<IntType>::type difference_type;
37 typedef IntType value_type;
38 typedef const IntType* pointer;
39 typedef const IntType& reference;
40 typedef std::random_access_iterator_tag iterator_category;
41
42 counting_iterator() : my_counter() {}
43 explicit counting_iterator(IntType init) : my_counter(init) {}
44
45 reference operator*() const { return my_counter; }
46 value_type operator[](difference_type i) const { return *(*this + i); }
47
48 difference_type operator-(const counting_iterator& it) const { return my_counter - it.my_counter; }
49
50 counting_iterator& operator+=(difference_type forward) { my_counter += forward; return *this; }
51 counting_iterator& operator-=(difference_type backward) { return *this += -backward; }
52 counting_iterator& operator++() { return *this += 1; }
53 counting_iterator& operator--() { return *this -= 1; }
54
55 counting_iterator operator++(int) {
56 counting_iterator it(*this);
57 ++(*this);
58 return it;
59 }
60 counting_iterator operator--(int) {
61 counting_iterator it(*this);
62 --(*this);
63 return it;
64 }
65
66 counting_iterator operator-(difference_type backward) const { return counting_iterator(my_counter - backward); }
67 counting_iterator operator+(difference_type forward) const { return counting_iterator(my_counter + forward); }
68 friend counting_iterator operator+(difference_type forward, const counting_iterator it) { return it + forward; }
69
70 bool operator==(const counting_iterator& it) const { return *this - it == 0; }
71 bool operator!=(const counting_iterator& it) const { return !(*this == it); }
72 bool operator<(const counting_iterator& it) const {return *this - it < 0; }
73 bool operator>(const counting_iterator& it) const { return it < *this; }
74 bool operator<=(const counting_iterator& it) const { return !(*this > it); }
75 bool operator>=(const counting_iterator& it) const { return !(*this < it); }
76
77private:
78 IntType my_counter;
79};
80} //namespace tbb
81
82
83#include <tuple>
84
85#include "internal/_template_helpers.h" // index_sequence, make_index_sequence
86
87namespace tbb {
88namespace internal {
89
90template<size_t N>
91struct tuple_util {
92 template<typename TupleType, typename DifferenceType>
93 static void increment(TupleType& it, DifferenceType forward) {
94 std::get<N-1>(it) += forward;
95 tuple_util<N-1>::increment(it, forward);
96 }
97 template<typename TupleType, typename DifferenceType>
98 static bool check_sync(const TupleType& it1, const TupleType& it2, DifferenceType val) {
99 if(std::get<N-1>(it1) - std::get<N-1>(it2) != val)
100 return false;
101 return tuple_util<N-1>::check_sync(it1, it2, val);
102 }
103};
104
105template<>
106struct tuple_util<0> {
107 template<typename TupleType, typename DifferenceType>
108 static void increment(TupleType&, DifferenceType) {}
109 template<typename TupleType, typename DifferenceType>
110 static bool check_sync(const TupleType&, const TupleType&, DifferenceType) { return true;}
111};
112
113template <typename TupleReturnType>
114struct make_references {
115 template <typename TupleType, std::size_t... Is>
116 TupleReturnType operator()(const TupleType& t, tbb::internal::index_sequence<Is...>) {
117 return std::tie( *std::get<Is>(t)... );
118 }
119};
120
121// A simple wrapper over a tuple of references.
122// The class is designed to hold a temporary tuple of reference
123// after dereferencing a zip_iterator; in particular, it is needed
124// to swap these rvalue tuples. Any other usage is not supported.
125template<typename... T>
126struct tuplewrapper : public std::tuple<typename std::enable_if<std::is_reference<T>::value, T&&>::type...> {
127 // In the context of this class, T is a reference, so T&& is a "forwarding reference"
128 typedef std::tuple<T&&...> base_type;
129 // Construct from the result of std::tie
130 tuplewrapper(const base_type& in) : base_type(in) {}
131#if __INTEL_COMPILER
132 // ICC cannot generate copy ctor & assignment
133 tuplewrapper(const tuplewrapper& rhs) : base_type(rhs) {}
134 tuplewrapper& operator=(const tuplewrapper& rhs) {
135 *this = base_type(rhs);
136 return *this;
137 }
138#endif
139 // Assign any tuple convertible to std::tuple<T&&...>: *it = a_tuple;
140 template<typename... U>
141 tuplewrapper& operator=(const std::tuple<U...>& other) {
142 base_type::operator=(other);
143 return *this;
144 }
145#if _LIBCPP_VERSION
146 // (Necessary for libc++ tuples) Convert to a tuple of values: v = *it;
147 operator std::tuple<typename std::remove_reference<T>::type...>() { return base_type(*this); }
148#endif
149 // Swap rvalue tuples: swap(*it1,*it2);
150 friend void swap(tuplewrapper&& a, tuplewrapper&& b) {
151 std::swap<T&&...>(a,b);
152 }
153};
154
155} //namespace internal
156
157template <typename... Types>
158class zip_iterator {
159 __TBB_STATIC_ASSERT(sizeof...(Types), "Cannot instantiate zip_iterator with empty template parameter pack");
160 static const std::size_t num_types = sizeof...(Types);
161 typedef std::tuple<Types...> it_types;
162public:
163 typedef typename std::make_signed<std::size_t>::type difference_type;
164 typedef std::tuple<typename std::iterator_traits<Types>::value_type...> value_type;
165#if __INTEL_COMPILER && __INTEL_COMPILER < 1800 && _MSC_VER
166 typedef std::tuple<typename std::iterator_traits<Types>::reference...> reference;
167#else
168 typedef tbb::internal::tuplewrapper<typename std::iterator_traits<Types>::reference...> reference;
169#endif
170 typedef std::tuple<typename std::iterator_traits<Types>::pointer...> pointer;
171 typedef std::random_access_iterator_tag iterator_category;
172
173 zip_iterator() : my_it() {}
174 explicit zip_iterator(Types... args) : my_it(std::make_tuple(args...)) {}
175 zip_iterator(const zip_iterator& input) : my_it(input.my_it) {}
176 zip_iterator& operator=(const zip_iterator& input) {
177 my_it = input.my_it;
178 return *this;
179 }
180
181 reference operator*() const {
182 return tbb::internal::make_references<reference>()(my_it, tbb::internal::make_index_sequence<num_types>());
183 }
184 reference operator[](difference_type i) const { return *(*this + i); }
185
186 difference_type operator-(const zip_iterator& it) const {
187 __TBB_ASSERT(internal::tuple_util<num_types>::check_sync(my_it, it.my_it, std::get<0>(my_it) - std::get<0>(it.my_it)),
188 "Components of zip_iterator are not synchronous");
189 return std::get<0>(my_it) - std::get<0>(it.my_it);
190 }
191
192 zip_iterator& operator+=(difference_type forward) {
193 internal::tuple_util<num_types>::increment(my_it, forward);
194 return *this;
195 }
196 zip_iterator& operator-=(difference_type backward) { return *this += -backward; }
197 zip_iterator& operator++() { return *this += 1; }
198 zip_iterator& operator--() { return *this -= 1; }
199
200 zip_iterator operator++(int) {
201 zip_iterator it(*this);
202 ++(*this);
203 return it;
204 }
205 zip_iterator operator--(int) {
206 zip_iterator it(*this);
207 --(*this);
208 return it;
209 }
210
211 zip_iterator operator-(difference_type backward) const {
212 zip_iterator it(*this);
213 return it -= backward;
214 }
215 zip_iterator operator+(difference_type forward) const {
216 zip_iterator it(*this);
217 return it += forward;
218 }
219 friend zip_iterator operator+(difference_type forward, const zip_iterator& it) { return it + forward; }
220
221 bool operator==(const zip_iterator& it) const {
222 return *this - it == 0;
223 }
224 it_types base() const { return my_it; }
225
226 bool operator!=(const zip_iterator& it) const { return !(*this == it); }
227 bool operator<(const zip_iterator& it) const { return *this - it < 0; }
228 bool operator>(const zip_iterator& it) const { return it < *this; }
229 bool operator<=(const zip_iterator& it) const { return !(*this > it); }
230 bool operator>=(const zip_iterator& it) const { return !(*this < it); }
231private:
232 it_types my_it;
233};
234
235template<typename... T>
236zip_iterator<T...> make_zip_iterator(T... args) { return zip_iterator<T...>(args...); }
237
238template <typename UnaryFunc, typename Iter>
239class transform_iterator {
240public:
241 typedef typename std::iterator_traits<Iter>::value_type value_type;
242 typedef typename std::iterator_traits<Iter>::difference_type difference_type;
243#if __TBB_CPP17_INVOKE_RESULT_PRESENT
244 typedef typename std::invoke_result<UnaryFunc, typename std::iterator_traits<Iter>::reference>::type reference;
245#else
246 typedef typename std::result_of<UnaryFunc(typename std::iterator_traits<Iter>::reference)>::type reference;
247#endif
248 typedef typename std::iterator_traits<Iter>::pointer pointer;
249 typedef typename std::random_access_iterator_tag iterator_category;
250
251 transform_iterator(Iter it, UnaryFunc unary_func) : my_it(it), my_unary_func(unary_func) {
252 __TBB_STATIC_ASSERT((std::is_same<typename std::iterator_traits<Iter>::iterator_category,
253 std::random_access_iterator_tag>::value), "Random access iterator required.");
254 }
255 transform_iterator(const transform_iterator& input) : my_it(input.my_it), my_unary_func(input.my_unary_func) { }
256 transform_iterator& operator=(const transform_iterator& input) {
257 my_it = input.my_it;
258 return *this;
259 }
260 reference operator*() const {
261 return my_unary_func(*my_it);
262 }
263 reference operator[](difference_type i) const {
264 return *(*this + i);
265 }
266 transform_iterator& operator++() {
267 ++my_it;
268 return *this;
269 }
270 transform_iterator& operator--() {
271 --my_it;
272 return *this;
273 }
274 transform_iterator operator++(int) {
275 transform_iterator it(*this);
276 ++(*this);
277 return it;
278 }
279 transform_iterator operator--(int) {
280 transform_iterator it(*this);
281 --(*this);
282 return it;
283 }
284 transform_iterator operator+(difference_type forward) const {
285 return { my_it + forward, my_unary_func };
286 }
287 transform_iterator operator-(difference_type backward) const {
288 return { my_it - backward, my_unary_func };
289 }
290 transform_iterator& operator+=(difference_type forward) {
291 my_it += forward;
292 return *this;
293 }
294 transform_iterator& operator-=(difference_type backward) {
295 my_it -= backward;
296 return *this;
297 }
298 friend transform_iterator operator+(difference_type forward, const transform_iterator& it) {
299 return it + forward;
300 }
301 difference_type operator-(const transform_iterator& it) const {
302 return my_it - it.my_it;
303 }
304 bool operator==(const transform_iterator& it) const { return *this - it == 0; }
305 bool operator!=(const transform_iterator& it) const { return !(*this == it); }
306 bool operator<(const transform_iterator& it) const { return *this - it < 0; }
307 bool operator>(const transform_iterator& it) const { return it < *this; }
308 bool operator<=(const transform_iterator& it) const { return !(*this > it); }
309 bool operator>=(const transform_iterator& it) const { return !(*this < it); }
310
311 Iter base() const { return my_it; }
312private:
313 Iter my_it;
314 const UnaryFunc my_unary_func;
315};
316
317template<typename UnaryFunc, typename Iter>
318transform_iterator<UnaryFunc, Iter> make_transform_iterator(Iter it, UnaryFunc unary_func) {
319 return transform_iterator<UnaryFunc, Iter>(it, unary_func);
320}
321
322} //namespace tbb
323
324#endif //__TBB_CPP11_PRESENT
325
326#endif /* __TBB_iterators_H */
327