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