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