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