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_iterator I, sentinel_for<I> S, class T, output_iterator<const T&> O,
15 // class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
16 // requires indirectly_copyable<I, O>
17 // constexpr replace_copy_if_result<I, O>
18 // replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
19 // Proj proj = {}); // Since C++20
20 //
21 // template<input_range R, class T, output_iterator<const T&> O, class Proj = identity,
22 // indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
23 // requires indirectly_copyable<iterator_t<R>, O>
24 // constexpr replace_copy_if_result<borrowed_iterator_t<R>, O>
25 // replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
26 // Proj proj = {}); // Since C++20
27
28 #include <algorithm>
29 #include <array>
30 #include <concepts>
31 #include <functional>
32 #include <ranges>
33 #include <utility>
34
35 #include "almost_satisfies_types.h"
36 #include "counting_predicates.h"
37 #include "counting_projection.h"
38 #include "test_iterators.h"
39
40 struct FalsePredicate {
operator ()FalsePredicate41 constexpr bool operator()(int) { return false; }
42 };
43
44 template <class Iter, class Sent = sentinel_wrapper<Iter>, class OutIter = int*>
45 concept HasReplaceCopyIfIter = requires(Iter&& first, Sent&& last, OutIter&& result) {
46 std::ranges::replace_copy_if(
47 std::forward<Iter>(first), std::forward<Sent>(last), std::forward<OutIter>(result), FalsePredicate{}, 0);
48 };
49
50 static_assert(HasReplaceCopyIfIter<int*>);
51
52 // !input_iterator<I>
53 static_assert(!HasReplaceCopyIfIter<InputIteratorNotDerivedFrom>);
54 static_assert(!HasReplaceCopyIfIter<InputIteratorNotIndirectlyReadable>);
55 static_assert(!HasReplaceCopyIfIter<InputIteratorNotInputOrOutputIterator>);
56
57 // !sentinel_for<S, I>
58 static_assert(!HasReplaceCopyIfIter<int*, SentinelForNotSemiregular>);
59 static_assert(!HasReplaceCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
60
61 // !output_iterator<O, const T2&>
62 static_assert(!HasReplaceCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
63 static_assert(!HasReplaceCopyIfIter<int*, int*, OutputIteratorNotInputOrOutputIterator>);
64
65 // !indirect_unary_predicate<Pred, projected<I, Proj>> Pred>
66 static_assert(!HasReplaceCopyIfIter<IndirectUnaryPredicateNotCopyConstructible>);
67 static_assert(!HasReplaceCopyIfIter<IndirectUnaryPredicateNotPredicate>);
68
69 // !indirectly_copyable<I, O>
70 static_assert(!HasReplaceCopyIfIter<int*, int*, int**>);
71
72 template <class Range, class OutIter = int*>
73 concept HasReplaceCopyIfRange = requires(Range&& range, OutIter&& result) {
74 std::ranges::replace_copy_if(std::forward<Range>(range), std::forward<OutIter>(result), FalsePredicate{}, 0);
75 };
76
77 template <class T>
78 using R = UncheckedRange<T>;
79
80 static_assert(HasReplaceCopyIfRange<R<int*>>);
81
82 // !input_range<R>
83 static_assert(!HasReplaceCopyIfRange<InputRangeNotDerivedFrom>);
84 static_assert(!HasReplaceCopyIfRange<InputRangeNotIndirectlyReadable>);
85 static_assert(!HasReplaceCopyIfRange<InputRangeNotInputOrOutputIterator>);
86 static_assert(!HasReplaceCopyIfRange<InputRangeNotSentinelSemiregular>);
87 static_assert(!HasReplaceCopyIfRange<InputRangeNotSentinelEqualityComparableWith>);
88
89 // !output_iterator<O, const T2&>
90 static_assert(!HasReplaceCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>);
91 static_assert(!HasReplaceCopyIfRange<R<int*>, OutputIteratorNotInputOrOutputIterator>);
92
93 // !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>> Pred>
94 static_assert(!HasReplaceCopyIfRange<R<IndirectUnaryPredicateNotPredicate>>);
95
96 // !indirectly_copyable<iterator_t<R>, O>
97 static_assert(!HasReplaceCopyIfRange<R<int*>, int**>);
98
99 template <int N>
100 struct Data {
101 std::array<int, N> input;
102 int cutoff;
103 int new_value;
104 std::array<int, N> expected;
105 };
106
107 template <class InIter, class Sent, class OutIter, int N>
test(Data<N> d)108 constexpr void test(Data<N> d) {
109 { // iterator overload
110 std::array<int, N> output;
111
112 auto first = InIter(d.input.data());
113 auto last = Sent(InIter(d.input.data() + d.input.size()));
114 auto result = OutIter(output.data());
115
116 auto pred = [&](int i) { return i < d.cutoff; };
117
118 std::same_as<std::ranges::replace_copy_if_result<InIter, OutIter>> decltype(auto) ret =
119 std::ranges::replace_copy_if(std::move(first), std::move(last), std::move(result), pred, d.new_value);
120 assert(base(ret.in) == d.input.data() + d.input.size());
121 assert(base(ret.out) == output.data() + output.size());
122 assert(d.expected == output);
123 }
124
125 { // range overload
126 std::array<int, N> output;
127
128 auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())));
129 auto result = OutIter(output.data());
130
131 auto pred = [&](int i) { return i < d.cutoff; };
132
133 std::same_as<std::ranges::replace_copy_if_result<InIter, OutIter>> decltype(auto) ret =
134 std::ranges::replace_copy_if(range, result, pred, d.new_value);
135 assert(base(ret.in) == d.input.data() + d.input.size());
136 assert(base(ret.out) == output.data() + output.size());
137 assert(d.expected == output);
138 }
139 }
140
141 template <class InIter, class Sent, class OutIter>
tests()142 constexpr void tests() {
143 // simple test
144 test<InIter, Sent, OutIter, 4>({.input = {1, 2, 3, 4}, .cutoff = 2, .new_value = 5, .expected = {5, 2, 3, 4}});
145 // empty range
146 test<InIter, Sent, OutIter, 0>({.input = {}, .cutoff = 2, .new_value = 5, .expected = {}});
147 // all elements match
148 test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .cutoff = 2, .new_value = 2, .expected = {2, 2, 2, 2}});
149 // no element matches
150 test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .cutoff = 1, .new_value = 3, .expected = {1, 1, 1, 1}});
151 // more elements
152 test<InIter, Sent, OutIter, 7>(
153 {.input = {1, 2, 3, 4, 5, 6, 7}, .cutoff = 3, .new_value = 3, .expected = {3, 3, 3, 4, 5, 6, 7}});
154 // single element - match
155 test<InIter, Sent, OutIter, 1>({.input = {1}, .cutoff = 2, .new_value = 5, .expected = {5}});
156 // single element - no match
157 test<InIter, Sent, OutIter, 1>({.input = {2}, .cutoff = 2, .new_value = 5, .expected = {2}});
158 }
159
160 template <class InIter, class Sent>
test_output_iterators()161 constexpr void test_output_iterators() {
162 tests<InIter, Sent, cpp17_output_iterator<int*>>();
163 tests<InIter, Sent, forward_iterator<int*>>();
164 tests<InIter, Sent, bidirectional_iterator<int*>>();
165 tests<InIter, Sent, random_access_iterator<int*>>();
166 tests<InIter, Sent, contiguous_iterator<int*>>();
167 tests<InIter, Sent, int*>();
168 }
169
170 template <class InIter>
test_sentinels()171 constexpr void test_sentinels() {
172 test_output_iterators<InIter, InIter>();
173 test_output_iterators<InIter, sentinel_wrapper<InIter>>();
174 test_output_iterators<InIter, sized_sentinel<InIter>>();
175 }
176
test()177 constexpr bool test() {
178 test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
179 test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
180 test_sentinels<forward_iterator<int*>>();
181 test_sentinels<bidirectional_iterator<int*>>();
182 test_sentinels<random_access_iterator<int*>>();
183 test_sentinels<contiguous_iterator<int*>>();
184 test_sentinels<int*>();
185 test_sentinels<const int*>();
186
187 { // check that a custom projection works
188 struct S {
189 int i;
190 };
191
192 { // iterator overload
193 S a[] = {{1}, {2}, {3}, {4}};
194 S b[4];
195 auto ret = std::ranges::replace_copy_if(std::begin(a), std::end(a), std::begin(b), FalsePredicate{}, S{2}, &S::i);
196 assert(ret.in == std::end(a));
197 assert(ret.out == std::end(b));
198 assert(std::ranges::equal(a, b, {}, &S::i, &S::i));
199 }
200
201 { // range overload
202 S a[] = {{1}, {2}, {3}, {4}};
203 S b[4];
204 auto ret = std::ranges::replace_copy_if(a, std::begin(b), FalsePredicate{}, S{2}, &S::i);
205 assert(ret.in == std::end(a));
206 assert(ret.out == std::end(b));
207 assert(std::ranges::equal(a, b, {}, &S::i, &S::i));
208 }
209 }
210
211 { // Complexity: exactly `last - first` applications of the corresponding predicate and any projection.
212 { // iterator overload
213 int pred_count = 0;
214 int proj_count = 0;
215 int a[] = {1, 2, 3, 4};
216 int b[4];
217
218 std::ranges::replace_copy_if(
219 std::begin(a), std::end(a), std::begin(b),
220 counting_predicate(FalsePredicate{}, pred_count), 0, counting_projection(proj_count));
221 assert(pred_count == 4);
222 assert(proj_count == 4);
223 }
224
225 { // range overload
226 int pred_count = 0;
227 int proj_count = 0;
228 int a[] = {1, 2, 3, 4};
229 int b[4];
230
231 std::ranges::replace_copy_if(a, std::begin(b),
232 counting_predicate(FalsePredicate{}, pred_count), 0, counting_projection(proj_count));
233 assert(pred_count == 4);
234 assert(proj_count == 4);
235 }
236 }
237
238 { // using different types for the old and new values works
239 struct S {
240 constexpr operator int() const { return 1; }
241 };
242 {
243 int a[] = {0, 0, 2, 3};
244 int b[4];
245 std::ranges::replace_copy_if(std::begin(a), std::end(a), std::begin(b), [](int i) { return i < 2; }, S{});
246 assert(std::ranges::equal(b, std::array{1, 1, 2, 3}));
247 }
248
249 {
250 int a[] = {0, 0, 2, 3};
251 int b[4];
252 std::ranges::replace_copy_if(a, std::begin(b), [](int i) { return i < 2; }, S{});
253 assert(std::ranges::equal(b, std::array{1, 1, 2, 3}));
254 }
255 }
256
257 return true;
258 }
259
main(int,char **)260 int main(int, char**) {
261 test();
262 static_assert(test());
263
264 return 0;
265 }
266