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