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