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