1 //===----------------------------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // <numeric> 11 // UNSUPPORTED: c++98, c++03, c++11, c++14 12 13 // template<class InputIterator, class OutputIterator, class T, class BinaryOperation> 14 // OutputIterator 15 // inclusive_scan(InputIterator first, InputIterator last, 16 // OutputIterator result, 17 // BinaryOperation binary_op, T init); // C++17 18 19 #include <numeric> 20 #include <vector> 21 #include <cassert> 22 23 #include "test_iterators.h" 24 25 template <class Iter1, class T, class Op, class Iter2> 26 void 27 test(Iter1 first, Iter1 last, Op op, T init, Iter2 rFirst, Iter2 rLast) 28 { 29 std::vector<typename std::iterator_traits<Iter1>::value_type> v; 30 31 // Not in place 32 std::inclusive_scan(first, last, std::back_inserter(v), op, init); 33 assert(std::equal(v.begin(), v.end(), rFirst, rLast)); 34 35 // In place 36 v.clear(); 37 v.assign(first, last); 38 std::inclusive_scan(v.begin(), v.end(), v.begin(), op, init); 39 assert(std::equal(v.begin(), v.end(), rFirst, rLast)); 40 } 41 42 43 template <class Iter> 44 void 45 test() 46 { 47 int ia[] = {1, 3, 5, 7, 9}; 48 const int pRes[] = {1, 4, 9, 16, 25}; 49 const int mRes[] = {1, 3, 15, 105, 945}; 50 const unsigned sa = sizeof(ia) / sizeof(ia[0]); 51 static_assert(sa == sizeof(pRes) / sizeof(pRes[0])); // just to be sure 52 static_assert(sa == sizeof(mRes) / sizeof(mRes[0])); // just to be sure 53 54 for (unsigned int i = 0; i < sa; ++i ) { 55 test(Iter(ia), Iter(ia + i), std::plus<>(), 0, pRes, pRes + i); 56 test(Iter(ia), Iter(ia + i), std::multiplies<>(), 1, mRes, mRes + i); 57 } 58 } 59 60 int triangle(int n) { return n*(n+1)/2; } 61 62 // Basic sanity 63 void basic_tests() 64 { 65 { 66 std::vector<int> v(10); 67 std::fill(v.begin(), v.end(), 3); 68 std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), 50); 69 for (size_t i = 0; i < v.size(); ++i) 70 assert(v[i] == 50 + (int)(i+1) * 3); 71 } 72 73 { 74 std::vector<int> v(10); 75 std::iota(v.begin(), v.end(), 0); 76 std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), 40); 77 for (size_t i = 0; i < v.size(); ++i) 78 assert(v[i] == 40 + triangle(i)); 79 } 80 81 { 82 std::vector<int> v(10); 83 std::iota(v.begin(), v.end(), 1); 84 std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), 30); 85 for (size_t i = 0; i < v.size(); ++i) 86 assert(v[i] == 30 + triangle(i + 1)); 87 } 88 89 { 90 std::vector<int> v, res; 91 std::inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::plus<>(), 40); 92 assert(res.empty()); 93 } 94 95 // Make sure that the calculations are done using the init typedef 96 { 97 std::vector<unsigned char> v(10); 98 std::iota(v.begin(), v.end(), 1); 99 std::vector<int> res; 100 std::inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::multiplies<>(), 1); 101 102 assert(res.size() == 10); 103 int j = 1; 104 assert(res[0] == 1); 105 for (size_t i = 1; i < v.size(); ++i) 106 { 107 j *= i + 1; 108 assert(res[i] == j); 109 } 110 } 111 } 112 113 114 int main() 115 { 116 117 basic_tests(); 118 119 // All the iterator categories 120 test<input_iterator <const int*> >(); 121 test<forward_iterator <const int*> >(); 122 test<bidirectional_iterator<const int*> >(); 123 test<random_access_iterator<const int*> >(); 124 test<const int*>(); 125 test< int*>(); 126 127 } 128