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<permutable I, sentinel_for<I> S, class Proj = identity,
15 //          indirect_unary_predicate<projected<I, Proj>> Pred>
16 //   constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
17 // template<forward_range R, class Proj = identity,
18 //          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
19 //   requires permutable<iterator_t<R>>
20 //   constexpr borrowed_subrange_t<R>
21 //     ranges::remove_if(R&& r, Pred pred, Proj proj = {});
22 
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <ranges>
27 
28 #include "almost_satisfies_types.h"
29 #include "boolean_testable.h"
30 #include "test_iterators.h"
31 
32 struct FalsePredicate {
33   bool operator()(int) { return false; }
34 };
35 
36 template <class Iter, class Sent = sentinel_wrapper<Iter>>
37 concept HasRemoveIfIt = requires(Iter first, Sent last) { std::ranges::remove_if(first, last, FalsePredicate{}); };
38 
39 static_assert(HasRemoveIfIt<int*>);
40 static_assert(!HasRemoveIfIt<PermutableNotForwardIterator>);
41 static_assert(!HasRemoveIfIt<PermutableNotSwappable>);
42 static_assert(!HasRemoveIfIt<int*, SentinelForNotSemiregular>);
43 static_assert(!HasRemoveIfIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
44 static_assert(!HasRemoveIfIt<int**>); // not indirect_unary_predicate
45 
46 template <class Range>
47 concept HasRemoveIfR = requires(Range range) { std::ranges::remove_if(range, FalsePredicate{}); };
48 
49 static_assert(HasRemoveIfR<UncheckedRange<int*>>);
50 static_assert(!HasRemoveIfR<PermutableRangeNotForwardIterator>);
51 static_assert(!HasRemoveIfR<PermutableRangeNotSwappable>);
52 static_assert(!HasRemoveIfR<SentinelForNotSemiregular>);
53 static_assert(!HasRemoveIfR<SentinelForNotWeaklyEqualityComparableWith>);
54 static_assert(!HasRemoveIfR<UncheckedRange<int**>>); // not indirect_unary_predicate
55 
56 template <int N, int M>
57 struct Data {
58   std::array<int, N> input;
59   std::array<int, M> expected;
60   int cutoff;
61 };
62 
63 template <class Iter, class Sent, int N, int M>
64 constexpr void test(Data<N, M> d) {
65   { // iterator overload
66     auto input = d.input;
67 
68     auto first = Iter(input.data());
69     auto last  = Sent(Iter(input.data() + input.size()));
70 
71     std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =
72         std::ranges::remove_if(std::move(first), std::move(last), [&](int i) { return i < d.cutoff; });
73 
74     assert(base(ret.begin()) == input.data() + M);
75     assert(base(ret.end()) == input.data() + N);
76     assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));
77   }
78 
79   { // range overload
80     auto input = d.input;
81     auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));
82 
83     std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove_if(range, [&](int i) {
84       return i < d.cutoff;
85     });
86 
87     assert(base(ret.begin()) == input.data() + M);
88     assert(base(ret.end()) == input.data() + N);
89     assert(std::ranges::equal(base(input.begin()), base(ret.begin()), d.expected.begin(), d.expected.end()));
90   }
91 }
92 
93 template <class Iter, class Sent>
94 constexpr void tests() {
95   // simple test
96   test<Iter, Sent, 6, 2>({.input = {1, 2, 3, 4, 5, 6}, .expected = {5, 6}, .cutoff = 5});
97   // empty range
98   test<Iter, Sent, 0, 0>({});
99   // single element range - no match
100   test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .cutoff = 1});
101   // single element range - match
102   test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .cutoff = 2});
103   // two element range
104   test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .cutoff = 2});
105   // all elements match
106   test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .cutoff = 2});
107   // no elements match
108   test<Iter, Sent, 5, 5>({.input = {1, 1, 1, 1, 1}, .expected = {1, 1, 1, 1, 1}, .cutoff = 0});
109   // the relative order of elements isn't changed
110   test<Iter, Sent, 8, 7>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {2, 3, 2, 3, 4, 2, 5}, .cutoff = 2});
111   // multiple matches in a row
112   test<Iter, Sent, 5, 3>({.input = {1, 2, 2, 2, 1}, .expected = {2, 2, 2}, .cutoff = 2});
113   // only the last element matches
114   test<Iter, Sent, 3, 2>({.input = {2, 2, 1}, .expected = {2, 2}, .cutoff = 2});
115   // only the last element doesn't match
116   test<Iter, Sent, 3, 1>({.input = {1, 1, 2}, .expected = {2}, .cutoff = 2});
117 }
118 
119 template <class Iter>
120 constexpr void test_sentinels() {
121   tests<Iter, Iter>();
122   tests<Iter, sentinel_wrapper<Iter>>();
123   tests<Iter, sized_sentinel<Iter>>();
124 }
125 
126 constexpr void test_iterators() {
127   test_sentinels<forward_iterator<int*>>();
128   test_sentinels<bidirectional_iterator<int*>>();
129   test_sentinels<random_access_iterator<int*>>();
130   test_sentinels<contiguous_iterator<int*>>();
131   test_sentinels<int*>();
132 }
133 
134 constexpr bool test() {
135   test_iterators();
136 
137   { // check that ranges::dangling is returned
138     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
139         std::ranges::remove_if(std::array{1, 2, 3, 4}, [](int i) { return i < 0; });
140   }
141 
142   {// check complexity requirements
143 
144    // This is https://llvm.org/PR56382 - clang-format behaves weird if function-local structs are used
145    // clang-format off
146     {
147       int comp_count = 0;
148       auto comp = [&](int i) {
149         ++comp_count;
150         return i == 0;
151       };
152       int proj_count = 0;
153       auto proj      = [&](int i) {
154         ++proj_count;
155         return i;
156       };
157       int a[]  = {1, 2, 3, 4};
158       auto ret = std::ranges::remove_if(std::begin(a), std::end(a), comp, proj);
159       assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
160       assert(comp_count == 4);
161       assert(proj_count == 4);
162     }
163     {
164       int comp_count = 0;
165       auto comp      = [&](int i) {
166         ++comp_count;
167         return i == 0;
168       };
169       int proj_count = 0;
170       auto proj      = [&](int i) {
171         ++proj_count;
172         return i;
173       };
174       int a[]  = {1, 2, 3, 4};
175       auto ret = std::ranges::remove_if(a, comp, proj);
176       assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
177       assert(comp_count == 4);
178       assert(proj_count == 4);
179     }
180   }
181 
182   { // check that std::invoke is used
183     struct S {
184       constexpr S& identity() { return *this; }
185       constexpr bool predicate() const { return true; }
186     };
187     {
188       S a[4]   = {};
189       auto ret = std::ranges::remove_if(std::begin(a), std::end(a), &S::predicate, &S::identity);
190       assert(ret.begin() == std::begin(a));
191       assert(ret.end() == std::end(a));
192     }
193     {
194       S a[4]   = {};
195       auto ret = std::ranges::remove_if(a, &S::predicate, &S::identity);
196       assert(ret.begin() == std::begin(a));
197       assert(ret.end() == std::end(a));
198     }
199   }
200 
201   {
202     // check that the implicit conversion to bool works
203     {
204       int a[]  = {1, 2, 3, 4};
205       auto ret = std::ranges::remove_if(a, a + 4, [](const int& i) { return BooleanTestable{i == 3}; });
206       assert(ret.begin() == a + 3);
207     }
208     {
209       int a[]  = {1, 2, 3, 4};
210       auto ret = std::ranges::remove_if(a, [](const int& b) { return BooleanTestable{b == 3}; });
211       assert(ret.begin() == a + 3);
212     }
213   }
214 
215   return true;
216 }
217 // clang-format on
218 
219 int main(int, char**) {
220   test();
221   static_assert(test());
222 
223   return 0;
224 }
225