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 // <numeric>
10 // UNSUPPORTED: c++03, c++11, c++14
11 // UNSUPPORTED: clang-8
12 // UNSUPPORTED: gcc-9
13
14 // Became constexpr in C++20
15 // template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
16 // OutputIterator
17 // inclusive_scan(InputIterator first, InputIterator last,
18 // OutputIterator result,
19 // BinaryOperation binary_op); // C++17
20
21 #include <numeric>
22 #include <algorithm>
23 #include <array>
24 #include <cassert>
25 #include <functional>
26 #include <iterator>
27 #include <vector>
28
29 #include "test_macros.h"
30 #include "test_iterators.h"
31 // FIXME Remove constexpr vector workaround introduced in D90569
32 #if TEST_STD_VER > 17
33 #include <span>
34 #endif
35
36 template <class Iter1, class Op, class Iter2>
37 TEST_CONSTEXPR_CXX20 void
test(Iter1 first,Iter1 last,Op op,Iter2 rFirst,Iter2 rLast)38 test(Iter1 first, Iter1 last, Op op, Iter2 rFirst, Iter2 rLast)
39 {
40 // C++17 doesn't test constexpr so can use a vector.
41 // C++20 can use vector in constexpr evaluation, but both libc++ and MSVC
42 // don't have the support yet. In these cases use a std::span for the test.
43 // FIXME Remove constexpr vector workaround introduced in D90569
44 size_t size = std::distance(first, last);
45 #if TEST_STD_VER < 20 || \
46 (defined(__cpp_lib_constexpr_vector) && __cpp_lib_constexpr_vector >= 201907L)
47
48 std::vector<typename std::iterator_traits<Iter1>::value_type> v(size);
49 #else
50 assert((size <= 5) && "Increment the size of the array");
51 typename std::iterator_traits<Iter1>::value_type b[5];
52 std::span<typename std::iterator_traits<Iter1>::value_type> v{b, size};
53 #endif
54
55 // Not in place
56 std::inclusive_scan(first, last, v.begin(), op);
57 assert(std::equal(v.begin(), v.end(), rFirst, rLast));
58
59 // In place
60 std::copy(first, last, v.begin());
61 std::inclusive_scan(v.begin(), v.end(), v.begin(), op);
62 assert(std::equal(v.begin(), v.end(), rFirst, rLast));
63 }
64
65
66 template <class Iter>
67 TEST_CONSTEXPR_CXX20 void
test()68 test()
69 {
70 int ia[] = {1, 3, 5, 7, 9};
71 const int pRes[] = {1, 4, 9, 16, 25};
72 const int mRes[] = {1, 3, 15, 105, 945};
73 const unsigned sa = sizeof(ia) / sizeof(ia[0]);
74 static_assert(sa == sizeof(pRes) / sizeof(pRes[0])); // just to be sure
75 static_assert(sa == sizeof(mRes) / sizeof(mRes[0])); // just to be sure
76
77 for (unsigned int i = 0; i < sa; ++i ) {
78 test(Iter(ia), Iter(ia + i), std::plus<>(), pRes, pRes + i);
79 test(Iter(ia), Iter(ia + i), std::multiplies<>(), mRes, mRes + i);
80 }
81 }
82
triangle(size_t n)83 constexpr size_t triangle(size_t n) { return n*(n+1)/2; }
84
85 // Basic sanity
86 TEST_CONSTEXPR_CXX20 void
basic_tests()87 basic_tests()
88 {
89 {
90 std::array<size_t, 10> v;
91 std::fill(v.begin(), v.end(), 3);
92 std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>());
93 for (size_t i = 0; i < v.size(); ++i)
94 assert(v[i] == (i+1) * 3);
95 }
96
97 {
98 std::array<size_t, 10> v;
99 std::iota(v.begin(), v.end(), 0);
100 std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>());
101 for (size_t i = 0; i < v.size(); ++i)
102 assert(v[i] == triangle(i));
103 }
104
105 {
106 std::array<size_t, 10> v;
107 std::iota(v.begin(), v.end(), 1);
108 std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>());
109 for (size_t i = 0; i < v.size(); ++i)
110 assert(v[i] == triangle(i + 1));
111 }
112
113 {
114 // C++17 doesn't test constexpr so can use a vector.
115 // C++20 can use vector in constexpr evaluation, but both libc++ and MSVC
116 // don't have the support yet. In these cases use a std::span for the test.
117 // FIXME Remove constexpr vector workaround introduced in D90569
118 #if TEST_STD_VER < 20 || \
119 (defined(__cpp_lib_constexpr_vector) && __cpp_lib_constexpr_vector >= 201907L)
120 std::vector<size_t> v, res;
121 std::inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::plus<>());
122 #else
123 std::array<size_t, 0> v, res;
124 std::inclusive_scan(v.begin(), v.end(), res.begin(), std::plus<>());
125 #endif
126 assert(res.empty());
127 }
128 }
129
130 TEST_CONSTEXPR_CXX20 bool
test()131 test()
132 {
133 basic_tests();
134
135 // All the iterator categories
136 test<input_iterator <const int*> >();
137 test<forward_iterator <const int*> >();
138 test<bidirectional_iterator<const int*> >();
139 test<random_access_iterator<const int*> >();
140 test<const int*>();
141 test< int*>();
142
143 return true;
144 }
145
main(int,char **)146 int main(int, char**)
147 {
148 test();
149 #if TEST_STD_VER > 17
150 static_assert(test());
151 #endif
152 return 0;
153 }
154