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++98, c++03, c++11, c++14
11 
12 // template<class InputIterator, class OutputIterator, class T>
13 //     OutputIterator exclusive_scan(InputIterator first, InputIterator last,
14 //                                   OutputIterator result, T init);
15 //
16 
17 #include <numeric>
18 #include <algorithm>
19 #include <cassert>
20 #include <functional>
21 #include <iterator>
22 #include <vector>
23 
24 #include "test_macros.h"
25 #include "test_iterators.h"
26 
27 template <class Iter1, class T, class Iter2>
28 void
29 test(Iter1 first, Iter1 last, T init, Iter2 rFirst, Iter2 rLast)
30 {
31     std::vector<typename std::iterator_traits<Iter1>::value_type> v;
32 
33 //  Not in place
34     std::exclusive_scan(first, last, std::back_inserter(v), init);
35     assert(std::equal(v.begin(), v.end(), rFirst, rLast));
36 
37 //  In place
38     v.clear();
39     v.assign(first, last);
40     std::exclusive_scan(v.begin(), v.end(), v.begin(), init);
41     assert(std::equal(v.begin(), v.end(), rFirst, rLast));
42 }
43 
44 
45 template <class Iter>
46 void
47 test()
48 {
49           int ia[]   = {1, 3, 5, 7,  9};
50     const int pRes[] = {0, 1, 4, 9, 16};
51     const unsigned sa = sizeof(ia) / sizeof(ia[0]);
52     static_assert(sa == sizeof(pRes) / sizeof(pRes[0]));       // just to be sure
53 
54     for (unsigned int i = 0; i < sa; ++i )
55         test(Iter(ia), Iter(ia + i), 0, pRes, pRes + i);
56 }
57 
58 size_t triangle(size_t n) { return n*(n+1)/2; }
59 
60 //  Basic sanity
61 void basic_tests()
62 {
63     {
64     std::vector<size_t> v(10);
65     std::fill(v.begin(), v.end(), 3);
66     std::exclusive_scan(v.begin(), v.end(), v.begin(), size_t{50});
67     for (size_t i = 0; i < v.size(); ++i)
68         assert(v[i] == 50 + i * 3);
69     }
70 
71     {
72     std::vector<size_t> v(10);
73     std::iota(v.begin(), v.end(), 0);
74     std::exclusive_scan(v.begin(), v.end(), v.begin(), size_t{30});
75     for (size_t i = 0; i < v.size(); ++i)
76         assert(v[i] == 30 + triangle(i-1));
77     }
78 
79     {
80     std::vector<size_t> v(10);
81     std::iota(v.begin(), v.end(), 1);
82     std::exclusive_scan(v.begin(), v.end(), v.begin(), size_t{40});
83     for (size_t i = 0; i < v.size(); ++i)
84         assert(v[i] == 40 + triangle(i));
85     }
86 
87 }
88 
89 int main(int, char**)
90 {
91     basic_tests();
92 
93 //  All the iterator categories
94     test<input_iterator        <const int*> >();
95     test<forward_iterator      <const int*> >();
96     test<bidirectional_iterator<const int*> >();
97     test<random_access_iterator<const int*> >();
98     test<const int*>();
99     test<      int*>();
100 
101   return 0;
102 }
103