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 // <algorithm>
10 
11 // UNSUPPORTED: c++03, c++11, c++14, c++17
12 
13 // template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
14 //   requires indirectly_writable<I, const T2&> &&
15 //            indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
16 //   constexpr I
17 //     ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});
18 // template<input_range R, class T1, class T2, class Proj = identity>
19 //   requires indirectly_writable<iterator_t<R>, const T2&> &&
20 //            indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
21 //   constexpr borrowed_iterator_t<R>
22 //     ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});
23 
24 #include <algorithm>
25 #include <array>
26 #include <cassert>
27 #include <ranges>
28 
29 #include "almost_satisfies_types.h"
30 #include "boolean_testable.h"
31 #include "test_iterators.h"
32 
33 template <class Iter, class Sent = sentinel_wrapper<Iter>>
34 concept HasReplaceIt = requires(Iter iter, Sent sent) { std::ranges::replace(iter, sent, 0, 0); };
35 
36 static_assert(HasReplaceIt<int*>);
37 static_assert(!HasReplaceIt<InputIteratorNotDerivedFrom>);
38 static_assert(!HasReplaceIt<InputIteratorNotIndirectlyReadable>);
39 static_assert(!HasReplaceIt<InputIteratorNotInputOrOutputIterator>);
40 static_assert(!HasReplaceIt<int*, SentinelForNotSemiregular>);
41 static_assert(!HasReplaceIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
42 static_assert(!HasReplaceIt<int**>); // not indirectly_writable
43 static_assert(!HasReplaceIt<IndirectBinaryPredicateNotIndirectlyReadable>);
44 
45 template <class Range>
46 concept HasReplaceR = requires(Range range) { std::ranges::replace(range, 0, 0); };
47 
48 static_assert(HasReplaceR<UncheckedRange<int*>>);
49 static_assert(!HasReplaceR<InputRangeNotDerivedFrom>);
50 static_assert(!HasReplaceR<InputRangeNotIndirectlyReadable>);
51 static_assert(!HasReplaceR<InputRangeNotInputOrOutputIterator>);
52 static_assert(!HasReplaceR<InputRangeNotSentinelSemiregular>);
53 static_assert(!HasReplaceR<InputRangeNotSentinelEqualityComparableWith>);
54 static_assert(!HasReplaceR<UncheckedRange<int**>>); // not indirectly_writable
55 static_assert(!HasReplaceR<InputRangeIndirectBinaryPredicateNotIndirectlyReadable>);
56 
57 template <int N>
58 struct Data {
59   std::array<int, N> input;
60   int oldval;
61   int newval;
62   std::array<int, N> expected;
63 };
64 
65 template <class Iter, class Sent, int N>
66 constexpr void test(Data<N> d) {
67   {
68     auto a = d.input;
69     std::same_as<Iter> decltype(auto) ret = std::ranges::replace(Iter(a.data()), Sent(Iter(a.data() + N)),
70                                                                  d.oldval,
71                                                                  d.newval);
72     assert(base(ret) == a.data() + N);
73     assert(a == d.expected);
74   }
75   {
76     auto a = d.input;
77     auto range = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data() + N)));
78     std::same_as<Iter> decltype(auto) ret = std::ranges::replace(range, d.oldval, d.newval);
79     assert(base(ret) == a.data() + N);
80     assert(a == d.expected);
81   }
82 }
83 
84 template <class Iter, class Sent = Iter>
85 constexpr void test_iterators() {
86   // simple test
87   test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .oldval = 2, .newval = 23, .expected = {1, 23, 3, 4}});
88   // no match
89   test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .oldval = 5, .newval = 23, .expected = {1, 2, 3, 4}});
90   // all match
91   test<Iter, Sent, 4>({.input = {1, 1, 1, 1}, .oldval = 1, .newval = 23, .expected = {23, 23, 23, 23}});
92   // empty range
93   test<Iter, Sent, 0>({.input = {}, .oldval = 1, .newval = 23, .expected = {}});
94   // single element range
95   test<Iter, Sent, 1>({.input = {1}, .oldval = 1, .newval = 2, .expected = {2}});
96 }
97 
98 constexpr bool test() {
99   test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
100   test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
101   test_iterators<forward_iterator<int*>>();
102   test_iterators<bidirectional_iterator<int*>>();
103   test_iterators<random_access_iterator<int*>>();
104   test_iterators<contiguous_iterator<int*>>();
105   test_iterators<int*>();
106 
107   { // check that the projection is used
108     struct S {
109       constexpr S(int i_) : i(i_) {}
110       int i;
111     };
112     {
113       S a[] = {1, 2, 3, 4};
114       std::ranges::replace(a, a + 4, 3, S{0}, &S::i);
115     }
116     {
117       S a[] = {1, 2, 3, 4};
118       std::ranges::replace(a, 3, S{0}, &S::i);
119     }
120   }
121 
122   { // check that std::invoke is used
123     struct S {
124       constexpr S(int i_) : i(i_) {}
125       constexpr bool operator==(const S&) const = default;
126       constexpr const S& identity() const { return *this; }
127       int i;
128     };
129     {
130       S a[] = {1, 2, 3, 4};
131       auto ret = std::ranges::replace(std::begin(a), std::end(a), S{1}, S{2}, &S::identity);
132       assert(ret == a + 4);
133     }
134     {
135       S a[] = {1, 2, 3, 4};
136       auto ret = std::ranges::replace(a, S{1}, S{2}, &S::identity);
137       assert(ret == a + 4);
138     }
139   }
140 
141   { // check that the implicit conversion to bool works
142     {
143       StrictComparable<int> a[] = {1, 2, 2, 4};
144       auto ret = std::ranges::replace(std::begin(a), std::end(a), 1, 2);
145       assert(ret == std::end(a));
146     }
147     {
148       StrictComparable<int> a[] = {1, 2, 2, 4};
149       auto ret = std::ranges::replace(a, 1, 2);
150       assert(ret == std::end(a));
151     }
152   }
153 
154   { // check that T1 and T2 can be different types
155     {
156       StrictComparable<int> a[] = {1, 2, 2, 4};
157       auto ret = std::ranges::replace(std::begin(a), std::end(a), '\0', 2ull);
158       assert(ret == std::end(a));
159     }
160     {
161       StrictComparable<int> a[] = {1, 2, 2, 4};
162       auto ret = std::ranges::replace(a, '\0', 2ull);
163       assert(ret == std::end(a));
164     }
165   }
166 
167   { // check that std::ranges::dangling is returned
168     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
169         std::ranges::replace(std::array {1, 2, 3, 4}, 1, 1);
170   }
171 
172   { // check that the complexity requirements are met
173     {
174       auto projectionCount = 0;
175       auto proj = [&](int i) { ++projectionCount; return i; };
176       int a[] = {1, 2, 3, 4, 5};
177       auto ret = std::ranges::replace(std::begin(a), std::end(a), 1, 2, proj);
178       assert(ret == a + 5);
179       assert(projectionCount == 5);
180     }
181     {
182       auto projectionCount = 0;
183       auto proj = [&](int i) { ++projectionCount; return i; };
184       int a[] = {1, 2, 3, 4, 5};
185       auto ret = std::ranges::replace(a, 1, 2, proj);
186       assert(ret == a + 5);
187       assert(projectionCount == 5);
188     }
189   }
190 
191   return true;
192 }
193 
194 int main(int, char**) {
195   test();
196   static_assert(test());
197 
198   return 0;
199 }
200