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