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