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