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