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, c++17
10 
11 // <algorithm>
12 
13 // template<input_or_output_iterator O, copy_constructible F>
14 //   requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
15 //   constexpr O generate_n(O first, iter_difference_t<O> n, F gen);                                // Since C++20
16 
17 #include <algorithm>
18 #include <array>
19 #include <concepts>
20 #include <functional>
21 #include <ranges>
22 
23 #include "almost_satisfies_types.h"
24 #include "test_iterators.h"
25 
26 struct IntGen {
27   int operator()() const;
28 };
29 
30 struct UncopyableGen {
31   UncopyableGen(const UncopyableGen&) = delete;
32   int operator()() const;
33 };
34 static_assert(!std::copy_constructible<UncopyableGen>);
35 static_assert(std::invocable<UncopyableGen>);
36 
37 struct UninvocableGen {
38 };
39 static_assert(std::copy_constructible<UninvocableGen>);
40 static_assert(!std::invocable<UninvocableGen>);
41 
42 struct IntPtrGen {
43   int* operator()() const;
44 };
45 
46 // Test type constraints.
47 // ======================================================
48 
49 template <class Iter = int*, class Gen = IntGen>
50 concept HasGenerateNIter =
51     requires(Iter&& iter, Gen&& gen) {
52       std::ranges::generate_n(std::forward<Iter>(iter), 0, std::forward<Gen>(gen));
53     };
54 
55 static_assert(HasGenerateNIter<int*, IntGen>);
56 
57 // !input_or_output_iterator<O>
58 static_assert(!HasGenerateNIter<InputIteratorNotInputOrOutputIterator>);
59 
60 // !copy_constructible<F>
61 static_assert(!HasGenerateNIter<int*, UncopyableGen>);
62 
63 // !invocable<F&>
64 static_assert(!HasGenerateNIter<int*, UninvocableGen>);
65 
66 // !indirectly_writable<O, invoke_result_t<F&>>
67 static_assert(!HasGenerateNIter<int*, IntPtrGen>);
68 
69 template <class Iter, size_t N, class Gen>
70 constexpr void test_one(std::array<int, N> in, size_t n, Gen gen, std::array<int, N> expected) {
71   assert(n <= N);
72 
73   auto begin = Iter(in.data());
74 
75   std::same_as<Iter> decltype(auto) result = std::ranges::generate_n(std::move(begin), n, gen);
76   assert(base(result) == in.data() + n);
77   assert(in == expected);
78 }
79 
80 template <class Iter>
81 constexpr void test_iter() {
82   auto gen = [ctr = 1] () mutable { return ctr++; };
83 
84   // Empty sequence.
85   test_one<Iter, 0>({}, 0, gen, {});
86   // 1-element sequence, n = 0.
87   test_one<Iter>(std::array{-10}, 0, gen, {-10});
88   // 1-element sequence, n = 1.
89   test_one<Iter>(std::array{-10}, 1, gen, {1});
90   // Longer sequence, n = 3.
91   test_one<Iter>(std::array{-10, -20, -30, -40, -50}, 3, gen, {1, 2, 3, -40, -50});
92   // Longer sequence, n = 5.
93   test_one<Iter>(std::array<int, 5>{}, 5, gen, {1, 2, 3, 4, 5});
94 }
95 
96 constexpr void test_iterators() {
97   test_iter<cpp17_input_iterator<int*>>();
98   test_iter<cpp20_input_iterator<int*>>();
99   test_iter<cpp17_output_iterator<int*>>();
100   test_iter<cpp20_output_iterator<int*>>();
101   test_iter<forward_iterator<int*>>();
102   test_iter<bidirectional_iterator<int*>>();
103   test_iter<random_access_iterator<int*>>();
104   test_iter<contiguous_iterator<int*>>();
105   test_iter<int*>();
106 }
107 
108 constexpr bool test() {
109   test_iterators();
110 
111   { // Complexity: exactly N evaluations of `gen()` and assignments.
112     struct AssignedOnce {
113       bool assigned = false;
114       constexpr AssignedOnce& operator=(const AssignedOnce&) {
115         assert(!assigned);
116         assigned = true;
117         return *this;
118       }
119     };
120 
121     int gen_invocations = 0;
122     auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); };
123     constexpr size_t N1 = 10;
124     constexpr size_t N2 = N1 / 2;
125     std::array<AssignedOnce, N1> in;
126 
127     auto result = std::ranges::generate_n(in.begin(), N2, gen);
128     assert(std::ranges::all_of(std::ranges::subrange(in.begin(), result), &AssignedOnce::assigned));
129     assert(std::ranges::none_of(std::ranges::subrange(result, in.end()), &AssignedOnce::assigned));
130     assert(gen_invocations == N2);
131   }
132 
133 
134   return true;
135 }
136 
137 int main(int, char**) {
138   test();
139   static_assert(test());
140 
141   return 0;
142 }
143