1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // UNSUPPORTED: c++03, c++11, c++14
10
11 // <numeric>
12
13 // Became constexpr in C++20
14 // template<class InputIterator, class OutputIterator, class T,
15 // class BinaryOperation, class UnaryOperation>
16 // OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last,
17 // OutputIterator result, T init,
18 // BinaryOperation binary_op,
19 // UnaryOperation unary_op);
20
21
22 #include <numeric>
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <functional>
27 #include <iterator>
28
29 #include "test_macros.h"
30 #include "test_iterators.h"
31
32 struct add_one {
33 template <typename T>
operator ()add_one34 constexpr auto operator()(T x) const noexcept {
35 return static_cast<T>(x + 1);
36 }
37 };
38
39 template <class Iter1, class BOp, class UOp, class T>
40 TEST_CONSTEXPR_CXX20 void
test(Iter1 first,Iter1 last,BOp bop,UOp uop,T init,const T * rFirst,const T * rLast)41 test(Iter1 first, Iter1 last, BOp bop, UOp uop, T init, const T *rFirst, const T *rLast)
42 {
43 assert((rLast - rFirst) <= 5); // or else increase the size of "out"
44 T out[5];
45
46 // Not in place
47 T *end = std::transform_exclusive_scan(first, last, out, init, bop, uop);
48 assert(std::equal(out, end, rFirst, rLast));
49
50 // In place
51 std::copy(first, last, out);
52 end = std::transform_exclusive_scan(out, end, out, init, bop, uop);
53 assert(std::equal(out, end, rFirst, rLast));
54 }
55
56 template <class Iter>
57 TEST_CONSTEXPR_CXX20 void
test()58 test()
59 {
60 int ia[] = { 1, 3, 5, 7, 9 };
61 const int pResI0[] = { 0, 2, 6, 12, 20 }; // with add_one
62 const int mResI0[] = { 0, 0, 0, 0, 0 };
63 const int pResN0[] = { 0, -1, -4, -9, -16 }; // with negate
64 const int mResN0[] = { 0, 0, 0, 0, 0 };
65 const int pResI2[] = { 2, 4, 8, 14, 22 }; // with add_one
66 const int mResI2[] = { 2, 4, 16, 96, 768 };
67 const int pResN2[] = { 2, 1, -2, -7, -14 }; // with negate
68 const int mResN2[] = { 2, -2, 6, -30, 210 };
69 const unsigned sa = sizeof(ia) / sizeof(ia[0]);
70 static_assert(sa == sizeof(pResI0) / sizeof(pResI0[0])); // just to be sure
71 static_assert(sa == sizeof(mResI0) / sizeof(mResI0[0])); // just to be sure
72 static_assert(sa == sizeof(pResN0) / sizeof(pResN0[0])); // just to be sure
73 static_assert(sa == sizeof(mResN0) / sizeof(mResN0[0])); // just to be sure
74 static_assert(sa == sizeof(pResI2) / sizeof(pResI2[0])); // just to be sure
75 static_assert(sa == sizeof(mResI2) / sizeof(mResI2[0])); // just to be sure
76 static_assert(sa == sizeof(pResN2) / sizeof(pResN2[0])); // just to be sure
77 static_assert(sa == sizeof(mResN2) / sizeof(mResN2[0])); // just to be sure
78
79 for (unsigned int i = 0; i < sa; ++i ) {
80 test(Iter(ia), Iter(ia + i), std::plus<>(), add_one{}, 0, pResI0, pResI0 + i);
81 test(Iter(ia), Iter(ia + i), std::multiplies<>(), add_one{}, 0, mResI0, mResI0 + i);
82 test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), 0, pResN0, pResN0 + i);
83 test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), 0, mResN0, mResN0 + i);
84 test(Iter(ia), Iter(ia + i), std::plus<>(), add_one{}, 2, pResI2, pResI2 + i);
85 test(Iter(ia), Iter(ia + i), std::multiplies<>(), add_one{}, 2, mResI2, mResI2 + i);
86 test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), 2, pResN2, pResN2 + i);
87 test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), 2, mResN2, mResN2 + i);
88 }
89 }
90
triangle(size_t n)91 constexpr std::size_t triangle(size_t n) { return n*(n+1)/2; }
92
93 // Basic sanity
94 TEST_CONSTEXPR_CXX20 void
basic_tests()95 basic_tests()
96 {
97 {
98 std::array<std::size_t, 10> v;
99 std::fill(v.begin(), v.end(), 3);
100 std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), std::size_t{50}, std::plus<>(), add_one{});
101 for (std::size_t i = 0; i < v.size(); ++i)
102 assert(v[i] == 50 + i * 4);
103 }
104
105 {
106 std::array<std::size_t, 10> v;
107 std::iota(v.begin(), v.end(), 0);
108 std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), std::size_t{30}, std::plus<>(), add_one{});
109 for (std::size_t i = 0; i < v.size(); ++i)
110 assert(v[i] == 30 + triangle(i - 1) + i);
111 }
112
113 {
114 std::array<std::size_t, 10> v;
115 std::iota(v.begin(), v.end(), 1);
116 std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), std::size_t{40}, std::plus<>(), add_one{});
117 for (std::size_t i = 0; i < v.size(); ++i)
118 assert(v[i] == 40 + triangle(i) + i);
119 }
120
121 {
122 std::array<std::size_t, 0> v, res;
123 std::transform_exclusive_scan(v.begin(), v.end(), res.begin(), std::size_t{40}, std::plus<>(), add_one{});
124 assert(res.empty());
125 }
126
127 // Make sure that the calculations are done using the init typedef
128 {
129 std::array<unsigned char, 10> v;
130 std::iota(v.begin(), v.end(), static_cast<unsigned char>(1));
131 std::array<std::size_t, 10> res;
132 std::transform_exclusive_scan(v.begin(), v.end(), res.begin(), std::size_t{1}, std::multiplies<>(), add_one{});
133
134 assert(res.size() == 10);
135 std::size_t j = 1;
136 assert(res[0] == 1);
137 for (std::size_t i = 1; i < res.size(); ++i)
138 {
139 j *= i + 1;
140 assert(res[i] == j);
141 }
142 }
143 }
144
145 TEST_CONSTEXPR_CXX20 bool
test()146 test()
147 {
148 basic_tests();
149
150 // All the iterator categories
151 test<cpp17_input_iterator <const int*> >();
152 test<forward_iterator <const int*> >();
153 test<bidirectional_iterator<const int*> >();
154 test<random_access_iterator<const int*> >();
155 test<const int*>();
156 test< int*>();
157
158 return true;
159 }
160
main(int,char **)161 int main(int, char**)
162 {
163 test();
164 #if TEST_STD_VER > 17
165 static_assert(test());
166 #endif
167 return 0;
168 }
169