include/tbb/iterators.h

0001 /*
0002     Copyright (c) 2017-2020 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_iterators_H
0018 #define __TBB_iterators_H
0019
0020 #include <iterator>
0021 #include <limits>
0022
0023 #include "tbb_config.h"
0024 #include "tbb_stddef.h"
0025
0026 #if __TBB_CPP11_PRESENT
0027
0028 #include <type_traits>
0029
0030 namespace tbb {
0031
0032 template <typename IntType>
0033 class counting_iterator {
0034     __TBB_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer, "Cannot instantiate counting_iterator with a non-integer type");
0035 public:
0036     typedef typename std::make_signed<IntType>::type difference_type;
0037     typedef IntType value_type;
0038     typedef const IntType* pointer;
0039     typedef const IntType& reference;
0040     typedef std::random_access_iterator_tag iterator_category;
0041
0042     counting_iterator() : my_counter() {}
0043     explicit counting_iterator(IntType init) : my_counter(init) {}
0044
0045     reference operator*() const { return my_counter; }
0046     value_type operator[](difference_type i) const { return *(*this + i); }
0047
0048     difference_type operator-(const counting_iterator& it) const { return my_counter - it.my_counter; }
0049
0050     counting_iterator& operator+=(difference_type forward) { my_counter += forward; return *this; }
0051     counting_iterator& operator-=(difference_type backward) { return *this += -backward; }
0052     counting_iterator& operator++() { return *this += 1; }
0053     counting_iterator& operator--() { return *this -= 1; }
0054
0055     counting_iterator operator++(int) {
0056         counting_iterator it(*this);
0057         ++(*this);
0058         return it;
0059     }
0060     counting_iterator operator--(int) {
0061         counting_iterator it(*this);
0062         --(*this);
0063         return it;
0064     }
0065
0066     counting_iterator operator-(difference_type backward) const { return counting_iterator(my_counter - backward); }
0067     counting_iterator operator+(difference_type forward) const { return counting_iterator(my_counter + forward); }
0068     friend counting_iterator operator+(difference_type forward, const counting_iterator it) { return it + forward; }
0069
0070     bool operator==(const counting_iterator& it) const { return *this - it == 0; }
0071     bool operator!=(const counting_iterator& it) const { return !(*this == it); }
0072     bool operator<(const counting_iterator& it) const {return *this - it < 0; }
0073     bool operator>(const counting_iterator& it) const { return it < *this; }
0074     bool operator<=(const counting_iterator& it) const { return !(*this > it); }
0075     bool operator>=(const counting_iterator& it) const { return !(*this < it); }
0076
0077 private:
0078     IntType my_counter;
0079 };
0080 } //namespace tbb
0081
0082
0083 #include <tuple>
0084
0085 #include "internal/_template_helpers.h" // index_sequence, make_index_sequence
0086
0087 namespace tbb {
0088 namespace internal {
0089
0090 template<size_t N>
0091 struct tuple_util {
0092     template<typename TupleType, typename DifferenceType>
0093     static void increment(TupleType& it, DifferenceType forward) {
0094         std::get<N-1>(it) += forward;
0095         tuple_util<N-1>::increment(it, forward);
0096     }
0097     template<typename TupleType, typename DifferenceType>
0098     static bool check_sync(const TupleType& it1, const TupleType& it2, DifferenceType val) {
0099         if(std::get<N-1>(it1) - std::get<N-1>(it2) != val)
0100             return false;
0101         return tuple_util<N-1>::check_sync(it1, it2, val);
0102     }
0103 };
0104
0105 template<>
0106 struct tuple_util<0> {
0107     template<typename TupleType, typename DifferenceType>
0108     static void increment(TupleType&, DifferenceType) {}
0109     template<typename TupleType, typename DifferenceType>
0110     static bool check_sync(const TupleType&, const TupleType&, DifferenceType) { return true;}
0111 };
0112
0113 template <typename TupleReturnType>
0114 struct make_references {
0115     template <typename TupleType, std::size_t... Is>
0116     TupleReturnType operator()(const TupleType& t, tbb::internal::index_sequence<Is...>) {
0117         return std::tie( *std::get<Is>(t)... );
0118     }
0119 };
0120
0121 // A simple wrapper over a tuple of references.
0122 // The class is designed to hold a temporary tuple of reference
0123 // after dereferencing a zip_iterator; in particular, it is needed
0124 // to swap these rvalue tuples. Any other usage is not supported.
0125 template<typename... T>
0126 struct tuplewrapper : public std::tuple<typename std::enable_if<std::is_reference<T>::value, T&&>::type...> {
0127     // In the context of this class, T is a reference, so T&& is a "forwarding reference"
0128     typedef std::tuple<T&&...> base_type;
0129     // Construct from the result of std::tie
0130     tuplewrapper(const base_type& in) : base_type(in) {}
0131 #if __INTEL_COMPILER
0132     // ICC cannot generate copy ctor & assignment
0133     tuplewrapper(const tuplewrapper& rhs) : base_type(rhs) {}
0134     tuplewrapper& operator=(const tuplewrapper& rhs) {
0135         *this = base_type(rhs);
0136         return *this;
0137     }
0138 #endif
0139     // Assign any tuple convertible to std::tuple<T&&...>: *it = a_tuple;
0140     template<typename... U>
0141     tuplewrapper& operator=(const std::tuple<U...>& other) {
0142         base_type::operator=(other);
0143         return *this;
0144     }
0145 #if _LIBCPP_VERSION
0146     // (Necessary for libc++ tuples) Convert to a tuple of values: v = *it;
0147     operator std::tuple<typename std::remove_reference<T>::type...>() { return base_type(*this); }
0148 #endif
0149     // Swap rvalue tuples: swap(*it1,*it2);
0150     friend void swap(tuplewrapper&& a, tuplewrapper&& b) {
0151         std::swap<T&&...>(a,b);
0152     }
0153 };
0154
0155 } //namespace internal
0156
0157 template <typename... Types>
0158 class zip_iterator {
0159     __TBB_STATIC_ASSERT(sizeof...(Types)>0, "Cannot instantiate zip_iterator with empty template parameter pack");
0160     static const std::size_t num_types = sizeof...(Types);
0161     typedef std::tuple<Types...> it_types;
0162 public:
0163     typedef typename std::make_signed<std::size_t>::type difference_type;
0164     typedef std::tuple<typename std::iterator_traits<Types>::value_type...> value_type;
0165 #if __INTEL_COMPILER && __INTEL_COMPILER < 1800 && _MSC_VER
0166     typedef std::tuple<typename std::iterator_traits<Types>::reference...> reference;
0167 #else
0168     typedef tbb::internal::tuplewrapper<typename std::iterator_traits<Types>::reference...> reference;
0169 #endif
0170     typedef std::tuple<typename std::iterator_traits<Types>::pointer...> pointer;
0171     typedef std::random_access_iterator_tag iterator_category;
0172
0173     zip_iterator() : my_it() {}
0174     explicit zip_iterator(Types... args) : my_it(std::make_tuple(args...)) {}
0175     zip_iterator(const zip_iterator& input) : my_it(input.my_it) {}
0176     zip_iterator& operator=(const zip_iterator& input) {
0177         my_it = input.my_it;
0178         return *this;
0179     }
0180
0181     reference operator*() const {
0182         return tbb::internal::make_references<reference>()(my_it, tbb::internal::make_index_sequence<num_types>());
0183     }
0184     reference operator[](difference_type i) const { return *(*this + i); }
0185
0186     difference_type operator-(const zip_iterator& it) const {
0187         __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)),
0188                      "Components of zip_iterator are not synchronous");
0189         return std::get<0>(my_it) - std::get<0>(it.my_it);
0190     }
0191
0192     zip_iterator& operator+=(difference_type forward) {
0193         internal::tuple_util<num_types>::increment(my_it, forward);
0194         return *this;
0195     }
0196     zip_iterator& operator-=(difference_type backward) { return *this += -backward; }
0197     zip_iterator& operator++() { return *this += 1; }
0198     zip_iterator& operator--() { return *this -= 1; }
0199
0200     zip_iterator operator++(int) {
0201         zip_iterator it(*this);
0202         ++(*this);
0203         return it;
0204     }
0205     zip_iterator operator--(int) {
0206         zip_iterator it(*this);
0207         --(*this);
0208         return it;
0209     }
0210
0211     zip_iterator operator-(difference_type backward) const {
0212         zip_iterator it(*this);
0213         return it -= backward;
0214     }
0215     zip_iterator operator+(difference_type forward) const {
0216         zip_iterator it(*this);
0217         return it += forward;
0218     }
0219     friend zip_iterator operator+(difference_type forward, const zip_iterator& it) { return it + forward; }
0220
0221     bool operator==(const zip_iterator& it) const {
0222         return *this - it == 0;
0223     }
0224     it_types base() const { return my_it; }
0225
0226     bool operator!=(const zip_iterator& it) const { return !(*this == it); }
0227     bool operator<(const zip_iterator& it) const { return *this - it < 0; }
0228     bool operator>(const zip_iterator& it) const { return it < *this; }
0229     bool operator<=(const zip_iterator& it) const { return !(*this > it); }
0230     bool operator>=(const zip_iterator& it) const { return !(*this < it); }
0231 private:
0232     it_types my_it;
0233 };
0234
0235 template<typename... T>
0236 zip_iterator<T...> make_zip_iterator(T... args) { return zip_iterator<T...>(args...); }
0237
0238 template <typename UnaryFunc, typename Iter>
0239 class transform_iterator {
0240 public:
0241     typedef typename std::iterator_traits<Iter>::value_type value_type;
0242     typedef typename std::iterator_traits<Iter>::difference_type difference_type;
0243 #if __TBB_CPP17_INVOKE_RESULT_PRESENT
0244     typedef typename std::invoke_result<UnaryFunc, typename std::iterator_traits<Iter>::reference>::type reference;
0245 #else
0246     typedef typename std::result_of<UnaryFunc(typename std::iterator_traits<Iter>::reference)>::type reference;
0247 #endif
0248     typedef typename std::iterator_traits<Iter>::pointer pointer;
0249     typedef typename std::random_access_iterator_tag iterator_category;
0250
0251     transform_iterator(Iter it, UnaryFunc unary_func) : my_it(it), my_unary_func(unary_func) {
0252         __TBB_STATIC_ASSERT((std::is_same<typename std::iterator_traits<Iter>::iterator_category,
0253                              std::random_access_iterator_tag>::value), "Random access iterator required.");
0254     }
0255     transform_iterator(const transform_iterator& input) : my_it(input.my_it), my_unary_func(input.my_unary_func) { }
0256     transform_iterator& operator=(const transform_iterator& input) {
0257         my_it = input.my_it;
0258         return *this;
0259     }
0260     reference operator*() const {
0261         return my_unary_func(*my_it);
0262     }
0263     reference operator[](difference_type i) const {
0264         return *(*this + i);
0265     }
0266     transform_iterator& operator++() {
0267         ++my_it;
0268         return *this;
0269     }
0270     transform_iterator& operator--() {
0271         --my_it;
0272         return *this;
0273     }
0274     transform_iterator operator++(int) {
0275         transform_iterator it(*this);
0276         ++(*this);
0277         return it;
0278     }
0279     transform_iterator operator--(int) {
0280         transform_iterator it(*this);
0281         --(*this);
0282         return it;
0283     }
0284     transform_iterator operator+(difference_type forward) const {
0285         return { my_it + forward, my_unary_func };
0286     }
0287     transform_iterator operator-(difference_type backward) const {
0288         return { my_it - backward, my_unary_func };
0289     }
0290     transform_iterator& operator+=(difference_type forward) {
0291         my_it += forward;
0292         return *this;
0293     }
0294     transform_iterator& operator-=(difference_type backward) {
0295         my_it -= backward;
0296         return *this;
0297     }
0298     friend transform_iterator operator+(difference_type forward, const transform_iterator& it) {
0299         return it + forward;
0300     }
0301     difference_type operator-(const transform_iterator& it) const {
0302         return my_it - it.my_it;
0303     }
0304     bool operator==(const transform_iterator& it) const { return *this - it == 0; }
0305     bool operator!=(const transform_iterator& it) const { return !(*this == it); }
0306     bool operator<(const transform_iterator& it) const { return *this - it < 0; }
0307     bool operator>(const transform_iterator& it) const { return it < *this; }
0308     bool operator<=(const transform_iterator& it) const { return !(*this > it); }
0309     bool operator>=(const transform_iterator& it) const { return !(*this < it); }
0310
0311     Iter base() const { return my_it; }
0312 private:
0313     Iter my_it;
0314     const UnaryFunc my_unary_func;
0315 };
0316
0317 template<typename UnaryFunc, typename Iter>
0318 transform_iterator<UnaryFunc, Iter> make_transform_iterator(Iter it, UnaryFunc unary_func) {
0319     return transform_iterator<UnaryFunc, Iter>(it, unary_func);
0320 }
0321
0322 } //namespace tbb
0323
0324 #endif //__TBB_CPP11_PRESENT
0325
0326 #endif /* __TBB_iterators_H */