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