1// -*- C++ -*-
2//===-- scan.pass.cpp -----------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10// UNSUPPORTED: c++03, c++11, c++14
11
12#include "support/pstl_test_config.h"
13
14#include <execution>
15#include <numeric>
16
17#include "support/utils.h"
18
19using namespace TestUtils;
20
21// We provide the no execution policy versions of the exclusive_scan and inclusive_scan due checking correctness result of the versions with execution policies.
22//TODO: to add a macro for availability of ver implementations
23template <class InputIterator, class OutputIterator, class T>
24OutputIterator
25exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init)
26{
27 for (; first != last; ++first, ++result)
28 {
29 *result = init;
30 init = init + *first;
31 }
32 return result;
33}
34
35template <class InputIterator, class OutputIterator, class T, class BinaryOperation>
36OutputIterator
37exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op)
38{
39 for (; first != last; ++first, ++result)
40 {
41 *result = init;
42 init = binary_op(init, *first);
43 }
44 return result;
45}
46
47// Note: N4582 is missing the ", class T". Issue was reported 2016-Apr-11 to cxxeditor@gmail.com
48template <class InputIterator, class OutputIterator, class BinaryOperation, class T>
49OutputIterator
50inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, T init)
51{
52 for (; first != last; ++first, ++result)
53 {
54 init = binary_op(init, *first);
55 *result = init;
56 }
57 return result;
58}
59
60template <class InputIterator, class OutputIterator, class BinaryOperation>
61OutputIterator
62inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op)
63{
64 if (first != last)
65 {
66 auto tmp = *first;
67 *result = tmp;
68 return inclusive_scan_serial(++first, last, ++result, binary_op, tmp);
69 }
70 else
71 {
72 return result;
73 }
74}
75
76template <class InputIterator, class OutputIterator>
77OutputIterator
78inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result)
79{
80 typedef typename std::iterator_traits<InputIterator>::value_type input_type;
81 return inclusive_scan_serial(first, last, result, std::plus<input_type>());
82}
83
84// Most of the framework required for testing inclusive and exclusive scan is identical,
85// so the tests for both are in this file. Which is being tested is controlled by the global
86// flag inclusive, which is set to each alternative by main().
87static bool inclusive;
88
89template <typename Iterator, typename Size, typename T>
90void
91check_and_reset(Iterator expected_first, Iterator out_first, Size n, T trash)
92{
93 EXPECT_EQ_N(expected_first, out_first, n,
94 inclusive ? "wrong result from inclusive_scan" : "wrong result from exclusive_scan");
95 std::fill_n(out_first, n, trash);
96}
97
98struct test_scan_with_plus
99{
100 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T>
101 void
102 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last,
103 Iterator3 expected_first, Iterator3, Size n, T init, T trash)
104 {
105 using namespace std;
106
107 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first)
108 : exclusive_scan_serial(in_first, in_last, expected_first, init);
109 (void)orr1;
110 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first)
111 : exclusive_scan(exec, in_first, in_last, out_first, init);
112 EXPECT_TRUE(out_last == orr,
113 inclusive ? "inclusive_scan returned wrong iterator" : "exclusive_scan returned wrong iterator");
114
115 check_and_reset(expected_first, out_first, n, trash);
116 fill(out_first, out_last, trash);
117 }
118};
119
120template <typename T, typename Convert>
121void
122test_with_plus(T init, T trash, Convert convert)
123{
124 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
125 {
126 Sequence<T> in(n, convert);
127 Sequence<T> expected(in);
128 Sequence<T> out(n, [&](int32_t) { return trash; });
129
130 invoke_on_all_policies(test_scan_with_plus(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(),
131 expected.end(), in.size(), init, trash);
132 invoke_on_all_policies(test_scan_with_plus(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(),
133 expected.end(), in.size(), init, trash);
134 }
135}
136struct test_scan_with_binary_op
137{
138 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T,
139 typename BinaryOp>
140 typename std::enable_if<!TestUtils::isReverse<Iterator1>::value, void>::type
141 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last,
142 Iterator3 expected_first, Iterator3, Size n, T init, BinaryOp binary_op, T trash)
143 {
144 using namespace std;
145
146 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first, binary_op, init)
147 : exclusive_scan_serial(in_first, in_last, expected_first, init, binary_op);
148 (void)orr1;
149 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first, binary_op, init)
150 : exclusive_scan(exec, in_first, in_last, out_first, init, binary_op);
151
152 EXPECT_TRUE(out_last == orr, "scan returned wrong iterator");
153 check_and_reset(expected_first, out_first, n, trash);
154 }
155
156 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T,
157 typename BinaryOp>
158 typename std::enable_if<TestUtils::isReverse<Iterator1>::value, void>::type
159 operator()(Policy&&, Iterator1, Iterator1, Iterator2, Iterator2, Iterator3, Iterator3, Size, T, BinaryOp, T)
160 {
161 }
162};
163
164template <typename In, typename Out, typename BinaryOp>
165void
166test_matrix(Out init, BinaryOp binary_op, Out trash)
167{
168 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
169 {
170 Sequence<In> in(n, [](size_t k) { return In(k, k + 1); });
171
172 Sequence<Out> out(n, [&](size_t) { return trash; });
173 Sequence<Out> expected(n, [&](size_t) { return trash; });
174
175 invoke_on_all_policies(test_scan_with_binary_op(), in.begin(), in.end(), out.begin(), out.end(),
176 expected.begin(), expected.end(), in.size(), init, binary_op, trash);
177 invoke_on_all_policies(test_scan_with_binary_op(), in.cbegin(), in.cend(), out.begin(), out.end(),
178 expected.begin(), expected.end(), in.size(), init, binary_op, trash);
179 }
180}
181
182int
183main()
184{
185 for (int32_t mode = 0; mode < 2; ++mode)
186 {
187 inclusive = mode != 0;
188#if !defined(_PSTL_ICC_19_TEST_SIMD_UDS_WINDOWS_RELEASE_BROKEN)
189 // Test with highly restricted type and associative but not commutative operation
190 test_matrix<Matrix2x2<int32_t>, Matrix2x2<int32_t>>(init: Matrix2x2<int32_t>(), binary_op: multiply_matrix<int32_t>,
191 trash: Matrix2x2<int32_t>(-666, 666));
192#endif
193
194 // Since the implict "+" forms of the scan delegate to the generic forms,
195 // there's little point in using a highly restricted type, so just use double.
196 test_with_plus<float64_t>(init: inclusive ? 0.0 : -1.0, trash: -666.0,
197 convert: [](uint32_t k) { return float64_t((k % 991 + 1) ^ (k % 997 + 2)); });
198 }
199 std::cout << done() << std::endl;
200 return 0;
201}
202

source code of pstl/test/std/numerics/numeric.ops/scan.pass.cpp