src/test/test_iterators.cpp

   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 #include "tbb/tbb_config.h"
  18
  19 #if __TBB_CPP11_PRESENT
  20
  21 #include "tbb/iterators.h"
  22 #include "tbb/tbb_stddef.h"
  23
  24 #include <vector>
  25 #include <iostream>
  26 #include <algorithm>
  27 #include <numeric>
  28 #include <type_traits>
  29
  30 #include "harness.h"
  31
  32 //common checks of a random access iterator functionality
  33 template <typename RandomIt>
  34 void test_random_iterator(const RandomIt& it) {
  35     // check that RandomIt has all necessary publicly accessible member types
  36     {
  37         auto t1 = typename RandomIt::difference_type{};
  38         auto t2 = typename RandomIt::value_type{};
  39         typename RandomIt::reference ref = *it;
  40         tbb::internal::suppress_unused_warning(ref);
  41         auto t3 = typename RandomIt::pointer{};
  42         typename RandomIt::iterator_category{};
  43     }
  44
  45     ASSERT(  it == it,      "== returned false negative");
  46     ASSERT(!(it == it + 1), "== returned false positive");
  47     ASSERT(  it != it + 1,  "!= returned false negative");
  48     ASSERT(!(it != it),     "!= returned false positive");
  49
  50     ASSERT(*it == *it, "wrong result with operator*");
  51
  52     RandomIt it1 = it;
  53     ASSERT(it1 == it, "iterator is not copy constructible");
  54     RandomIt it2 = RandomIt(it);
  55     ASSERT(it2 == it, "iterator is not move constructible");
  56
  57     ++it1;
  58     ASSERT(it1 == it + 1, "wrong result with prefix operator++");
  59
  60     using std::swap;
  61     swap(it1, it2);
  62     ASSERT((it1 == it) && (it2 == it + 1), "iterator is not swappable");
  63
  64     it2 = it;
  65     ASSERT(it2 == it, "iterator is not copy assignable");
  66
  67     ++it2;
  68     it2 = RandomIt(it);
  69     ASSERT(it2 == it, "iterator is not move assignable");
  70
  71     it1 = it;
  72     ASSERT((it1++ == it) && (it1 == it + 1), "wrong result with postfix operator++");
  73
  74     it1 = it + 1;
  75     ASSERT(--it1 == it, "wrong result with prefix operator--");
  76
  77     it1 = it + 1;
  78     ASSERT((it1-- == it + 1) && (it1 == it), "wrong result with postfix operator--");
  79
  80     it1 += 1;
  81     ASSERT(it1 == it + 1, "wrong result with operator+=");
  82
  83     it1 -= 1;
  84     ASSERT(it1 == it, "wrong result with operator-=");
  85
  86     ASSERT(1 + it == it + 1, "n + iterator != iterator + n");
  87
  88     ASSERT((it + 1) - 1 == it, "wrong result with operator-(difference_type)");
  89
  90     ASSERT((it + 1) - it == 1, "wrong result with iterator subtraction");
  91
  92     ASSERT(it[1] == *(it + 1), "wrong result with operator[]");
  93
  94     ASSERT(it < it + 1, "operator< returned false negative");
  95     ASSERT(!(it < it),  "operator< returned false positive");
  96
  97     ASSERT(it + 1 > it, "operator> returned false negative");
  98     ASSERT(!(it > it),  "operator> returned false positive");
  99
 100     ASSERT(it <= it + 1,    "operator<= returned false negative");
 101     ASSERT(it <= it,        "operator<= returned false negative");
 102     ASSERT(!(it + 1 <= it), "operator<= returned false positive");
 103
 104     ASSERT(1 + it >= it,    "operator>= returned false negative");
 105     ASSERT(    it >= it,    "operator>= returned false negative");
 106     ASSERT(!(it >= it + 1), "operator>= returned false positive");
 107 }
 108
 109 struct test_counting_iterator {
 110     template <typename T, typename IntType>
 111     void operator()( std::vector<T>& in, IntType begin, IntType end, const T& value) {
 112         ASSERT((0 <= begin) && (begin <= end) && (end <= IntType(in.size())),
 113         "incorrect test_counting_iterator 'begin' and/or 'end' argument values");
 114
 115         //test that counting_iterator is default constructible
 116         tbb::counting_iterator<IntType> b;
 117
 118         b = tbb::counting_iterator<IntType>(begin);
 119         auto e = tbb::counting_iterator<IntType>(end);
 120
 121         //checks in using
 122         std::for_each(b, e, [&in, &value](IntType i) { in[i] = value; });
 123
 124         auto res = std::all_of(in.begin(), in.begin() + begin, [&value](const T& a) {return a!=value;});
 125         ASSERT(res, "wrong result with counting_iterator in vector's begin portion");
 126
 127         res = std::all_of(in.begin() + begin, in.begin() + end, [&value](const T& a) {return a==value;});
 128         ASSERT(res, "wrong result with counting_iterator in vector's main portion");
 129
 130         res = std::all_of(in.begin() + end, in.end(), [&value](const T& a) {return a!=value;});
 131         ASSERT(res, "wrong result with counting_iterator in vector's end portion");
 132
 133         //explicit checks of the counting iterator specific
 134         ASSERT(b[0]==begin, "wrong result with operator[] for an iterator");
 135         ASSERT(*(b + 1) == begin+1, "wrong result with operator+ for an iterator");
 136         ASSERT(*(b+=1) == begin+1, "wrong result with operator+= for an iterator");
 137     }
 138 };
 139
 140 struct sort_fun{
 141     template<typename T1, typename T2>
 142     bool operator()(T1 a1, T2 a2) const {
 143         return std::get<0>(a1) < std::get<0>(a2);
 144     }
 145 };
 146
 147 template <typename InputIterator>
 148 void test_explicit_move(InputIterator i, InputIterator j) {
 149     using value_type = typename std::iterator_traits<InputIterator>::value_type;
 150     value_type t(std::move(*i));
 151     *i = std::move(*j);
 152     *j = std::move(t);
 153 }
 154
 155 struct test_zip_iterator {
 156     template <typename T1, typename T2>
 157     void operator()(std::vector<T1>& in1, std::vector<T2>& in2) {
 158         //test that zip_iterator is default constructible
 159         tbb::zip_iterator<decltype(in1.begin()), decltype(in2.begin())> b;
 160
 161         b = tbb::make_zip_iterator(in1.begin(), in2.begin());
 162         auto e = tbb::make_zip_iterator(in1.end(), in2.end());
 163
 164         ASSERT( (b+1) != e, "size of input sequence insufficient for test" );
 165
 166         //simple check for-loop.
 167         {
 168         std::for_each(b, e, [](const std::tuple<T1&, T2&>& a) { std::get<0>(a) = 1, std::get<1>(a) = 1;});
 169         auto res = std::all_of(b, e, [](const std::tuple<T1&, T2&>& a) {return std::get<0>(a) == 1 && std::get<1>(a) == 1;});
 170         ASSERT(res, "wrong result sequence assignment to (1,1) with zip_iterator iterator");
 171         }
 172
 173         //check swapping de-referenced iterators (required by sort algorithm)
 174         {
 175         using std::swap;
 176         auto t = std::make_tuple(T1(3), T2(2));
 177         *b = t;
 178         t = *(b+1);
 179         ASSERT( std::get<0>(t) == 1 && std::get<1>(t) == 1, "wrong result of assignment from zip_iterator");
 180         swap(*b, *(b+1));
 181         ASSERT( std::get<0>(*b) == 1 && std::get<1>(*b) == 1, "wrong result swapping zip-iterator");
 182         ASSERT( std::get<0>(*(b+1)) == 3 && std::get<1>(*(b+1)) == 2, "wrong result swapping zip-iterator");
 183         // Test leaves sequence un-sorted.
 184         }
 185
 186         //sort sequences by first stream.
 187         {
 188         // sanity check if sequence is un-sorted.
 189         auto res = std::is_sorted(b, e, sort_fun());
 190         ASSERT(!res, "input sequence to be sorted is already sorted! Test might lead to false positives.");
 191         std::sort(tbb::make_zip_iterator(in1.begin(), in2.begin()),
 192                   tbb::make_zip_iterator(in1.end(), in2.end()),
 193                   sort_fun());
 194         res = std::is_sorted(b, e, sort_fun());
 195         ASSERT(res, "wrong result sorting sequence using zip-iterator");
 196             // TODO: Add simple check: comparison with sort_fun().
 197         }
 198         test_explicit_move(b, b+1);
 199         auto iter_base = b.base();
 200         static_assert(std::is_same<decltype(iter_base),
 201             std::tuple<decltype(in1.begin()), decltype(in2.begin())>>::value, "base returned wrong type");
 202         ASSERT(std::get<0>(iter_base) == in1.begin(), "wrong result from base (get<0>)");
 203         ASSERT(std::get<1>(iter_base) == in2.begin(), "wrong result from base (get<1>)");
 204
 205         test_random_iterator(b);
 206     }
 207 };
 208
 209 template <typename VecIt1, typename VecIt2>
 210 void test_transform_effect(VecIt1 first1, VecIt1 last1, VecIt2 first2) {
 211     auto triple = [](typename std::iterator_traits<VecIt1>::value_type const& val) {
 212         return typename std::iterator_traits<VecIt2>::value_type (3 * val);
 213     };
 214
 215     std::copy(
 216         tbb::make_transform_iterator(first1, triple),
 217         tbb::make_transform_iterator(last1,  triple),
 218         first2
 219     );
 220
 221     for (typename std::iterator_traits<VecIt1>::difference_type i = 0; i < last1 - first1; ++i)
 222         if ( first2[i] != (typename std::iterator_traits<VecIt2>::value_type) triple(first1[i]) ) {
 223             std::cout << "wrong effect with transform iterator" << std::endl;
 224             exit(1);
 225         }
 226 }
 227
 228 struct test_transform_iterator {
 229     template <typename T1, typename T2>
 230     void operator()(std::vector<T1>& in1, std::vector<T2>& in2) {
 231         std::iota(in1.begin(), in1.end(), T1(0));
 232
 233         test_transform_effect(in1.begin(),  in1.end(),  in2.begin());
 234         test_transform_effect(in1.cbegin(), in1.cend(), in2.begin());
 235
 236         auto new_transform_iterator = tbb::make_transform_iterator(in2.begin(), [](T2& x) { return x + 1; });
 237         test_random_iterator(new_transform_iterator);
 238     }
 239 };
 240
 241 template <typename T, typename IntType>
 242 void test_iterator_by_type(IntType n) {
 243
 244     const IntType beg = 0;
 245     const IntType end = n;
 246
 247     std::vector<T> in(n, T(0));
 248     std::vector<IntType> in2(n, IntType(0));
 249
 250     test_counting_iterator()(in, beg,     end,     /*value*/ T(-1));
 251     test_counting_iterator()(in, beg+123, end-321, /*value*/ T(42));
 252     test_random_iterator(tbb::counting_iterator<IntType>(beg));
 253
 254     test_zip_iterator()(in, in2);
 255     test_transform_iterator()(in, in2);
 256 }
 257
 258 int TestMain() {
 259
 260     const auto n1 = 1000;
 261     const auto n2 = 100000;
 262
 263     test_iterator_by_type<int16_t, int16_t>(n1);
 264     test_iterator_by_type<int16_t, int64_t>(n2);
 265
 266     test_iterator_by_type<double, int16_t>(n1);
 267     test_iterator_by_type<double, int64_t>(n2);
 268
 269     return Harness::Done;
 270 }
 271
 272 #else
 273
 274 #include "harness.h"
 275
 276 int TestMain () {
 277     return Harness::Skipped;
 278 }
 279
 280 #endif /* __TBB_CPP11_PRESENT && __TBB_CPP11_DECLTYPE_PRESENT */