143 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++1410 11// <numeric>12 13// Became constexpr in C++2014// template<class InputIterator, class OutputIterator, class T, class BinaryOperation>15// OutputIterator16// inclusive_scan(InputIterator first, InputIterator last,17// OutputIterator result,18// BinaryOperation binary_op, T init); // C++1719 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 30template <class Iter1, class T, class Op>31TEST_CONSTEXPR_CXX20 void32test(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 place38 T *end = std::inclusive_scan(first, last, out, op, init);39 assert(std::equal(out, end, rFirst, rLast));40 41 // In place42 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 48template <class Iter>49TEST_CONSTEXPR_CXX20 void50test()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 sure57 static_assert(sa == sizeof(mRes) / sizeof(mRes[0])); // just to be sure58 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 65constexpr std::size_t triangle(size_t n) { return n*(n+1)/2; }66 67// Basic sanity68TEST_CONSTEXPR_CXX20 void69basic_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 typedef102 {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 119TEST_CONSTEXPR_CXX20 bool120test()121{122 basic_tests();123 124// All the iterator categories125 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 135int main(int, char**)136{137 test();138#if TEST_STD_VER > 17139 static_assert(test());140#endif141 return 0;142}143