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// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
14// indirect_unary_predicate<projected<I, Proj>> Pred>
15// requires permutable<I>
16// subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {}); // Since C++20
17//
18// template<bidirectional_range R, class Proj = identity,
19// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
20// requires permutable<iterator_t<R>>
21// borrowed_subrange_t<R> stable_partition(R&& r, Pred pred, Proj proj = {}); // Since C++20
22
23#include <algorithm>
24#include <array>
25#include <concepts>
26#include <functional>
27#include <ranges>
28
29#include "almost_satisfies_types.h"
30#include "test_iterators.h"
31
32struct UnaryPred { bool operator()(int) const; };
33
34// Test constraints of the (iterator, sentinel) overload.
35// ======================================================
36
37template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
38concept HasStablePartitionIter =
39 requires(Iter&& iter, Sent&& sent, Pred&& pred) {
40 std::ranges::stable_partition(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
41 };
42
43static_assert(HasStablePartitionIter<int*, int*, UnaryPred>);
44
45// !bidirectional_iterator<I>
46static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDerivedFrom>);
47static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDecrementable>);
48
49// !sentinel_for<S, I>
50static_assert(!HasStablePartitionIter<int*, SentinelForNotSemiregular>);
51static_assert(!HasStablePartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
52
53// !indirect_unary_predicate<projected<I, Proj>>
54static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
55static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
56
57// !permutable<I>
58static_assert(!HasStablePartitionIter<PermutableNotForwardIterator>);
59static_assert(!HasStablePartitionIter<PermutableNotSwappable>);
60
61// Test constraints of the (range) overload.
62// =========================================
63
64template <class Range, class Pred>
65concept HasStablePartitionRange =
66 requires(Range&& range, Pred&& pred) {
67 std::ranges::stable_partition(std::forward<Range>(range), std::forward<Pred>(pred));
68 };
69
70template <class T>
71using R = UncheckedRange<T>;
72
73static_assert(HasStablePartitionRange<R<int*>, UnaryPred>);
74
75// !bidirectional_range<R>
76static_assert(!HasStablePartitionRange<BidirectionalRangeNotDerivedFrom, UnaryPred>);
77static_assert(!HasStablePartitionRange<BidirectionalRangeNotDecrementable, UnaryPred>);
78
79// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
80static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
81static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
82
83// !permutable<iterator_t<R>>
84static_assert(!HasStablePartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
85static_assert(!HasStablePartitionRange<R<PermutableNotSwappable>, UnaryPred>);
86
87template <class Iter, class Sent, std::size_t N, class Pred>
88void test_one(std::array<int, N> input, Pred pred, std::size_t partition_point, std::array<int, N> expected) {
89 auto neg_pred = [&](int x) { return !pred(x); };
90
91 { // (iterator, sentinel) overload.
92 auto partitioned = input;
93 auto b = Iter(partitioned.data());
94 auto e = Sent(Iter(partitioned.data() + partitioned.size()));
95
96 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::stable_partition(b, e, pred);
97
98 assert(partitioned == expected);
99 assert(base(result.begin()) == partitioned.data() + partition_point);
100 assert(base(result.end()) == partitioned.data() + partitioned.size());
101
102 assert(std::ranges::all_of(b, result.begin(), pred));
103 assert(std::ranges::all_of(result.begin(), e, neg_pred));
104 }
105
106 { // (range) overload.
107 auto partitioned = input;
108 auto b = Iter(partitioned.data());
109 auto e = Sent(Iter(partitioned.data() + partitioned.size()));
110 auto range = std::ranges::subrange(b, e);
111
112 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::stable_partition(range, pred);
113
114 assert(partitioned == expected);
115 assert(base(result.begin()) == partitioned.data() + partition_point);
116 assert(base(result.end()) == partitioned.data() + partitioned.size());
117
118 assert(std::ranges::all_of(b, result.begin(), pred));
119 assert(std::ranges::all_of(result.begin(), e, neg_pred));
120 }
121}
122
123template <class Iter, class Sent>
124void test_iterators_2() {
125 auto is_odd = [](int x) { return x % 2 != 0; };
126
127 // Empty sequence.
128 test_one<Iter, Sent, 0>({}, is_odd, 0, {});
129 // 1-element sequence, the element satisfies the predicate.
130 test_one<Iter, Sent, 1>({1}, is_odd, 1, {1});
131 // 1-element sequence, the element doesn't satisfy the predicate.
132 test_one<Iter, Sent, 1>({2}, is_odd, 0, {2});
133 // 2-element sequence, not in order.
134 test_one<Iter, Sent, 2>({2, 1}, is_odd, 1, {1, 2});
135 // 2-element sequence, already in order.
136 test_one<Iter, Sent, 2>({1, 2}, is_odd, 1, {1, 2});
137 // 3-element sequence.
138 test_one<Iter, Sent, 3>({2, 1, 3}, is_odd, 2, {1, 3, 2});
139 // Longer sequence.
140 test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, 4, {1, 3, 11, 5, 2, 6, 8, 4});
141 // Longer sequence with duplicates.
142 test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, 3, {1, 3, 1, 2, 6, 2, 8, 6});
143 // All elements are the same and satisfy the predicate.
144 test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3, {1, 1, 1});
145 // All elements are the same and don't satisfy the predicate.
146 test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0, {2, 2, 2});
147 // Already partitioned.
148 test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3, {1, 3, 5, 4, 6, 8});
149 // Reverse-partitioned.
150 test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3, {1, 3, 5, 4, 6, 8});
151 // Repeating pattern.
152 test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3, {1, 1, 1, 2, 2, 2});
153
154 auto is_negative = [](int x) { return x < 0; };
155 // Different comparator.
156 test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, 2, {-3, -6, 5, 7, 2});
157}
158
159template <class Iter>
160void test_iterators_1() {
161 test_iterators_2<Iter, Iter>();
162 test_iterators_2<Iter, sentinel_wrapper<Iter>>();
163}
164
165void test_iterators() {
166 test_iterators_1<bidirectional_iterator<int*>>();
167 test_iterators_1<random_access_iterator<int*>>();
168 test_iterators_1<contiguous_iterator<int*>>();
169 test_iterators_1<int*>();
170}
171
172void test() {
173 test_iterators();
174
175 { // The algorithm is stable (equivalent elements remain in the same order).
176 struct OrderedValue {
177 int value;
178 double original_order;
179 bool operator==(const OrderedValue&) const = default;
180 };
181
182 auto is_odd = [](OrderedValue x) { return x.value % 2 != 0; };
183
184 using V = OrderedValue;
185 using Array = std::array<V, 20>;
186 Array orig_in = {
187 V{.value: 10, .original_order: 2.1}, {.value: 12, .original_order: 2.2}, {.value: 3, .original_order: 1.1}, {.value: 5, .original_order: 1.2}, {.value: 3, .original_order: 1.3}, {.value: 3, .original_order: 1.4}, {.value: 11, .original_order: 1.5}, {.value: 12, .original_order: 2.3}, {.value: 4, .original_order: 2.4}, {.value: 4, .original_order: 2.5},
188 {.value: 4, .original_order: 2.6}, {.value: 1, .original_order: 1.6}, {.value: 6, .original_order: 2.7}, {.value: 3, .original_order: 1.7}, {.value: 10, .original_order: 2.8}, {.value: 8, .original_order: 2.9}, {.value: 12, .original_order: 2.10}, {.value: 1, .original_order: 1.8}, {.value: 1, .original_order: 1.9}, {.value: 5, .original_order: 1.10}
189 };
190 Array expected = {
191 V{.value: 3, .original_order: 1.1}, {.value: 5, .original_order: 1.2}, {.value: 3, .original_order: 1.3}, {.value: 3, .original_order: 1.4}, {.value: 11, .original_order: 1.5}, {.value: 1, .original_order: 1.6}, {.value: 3, .original_order: 1.7}, {.value: 1, .original_order: 1.8}, {.value: 1, .original_order: 1.9}, {.value: 5, .original_order: 1.10},
192 {.value: 10, .original_order: 2.1}, {.value: 12, .original_order: 2.2}, {.value: 12, .original_order: 2.3}, {.value: 4, .original_order: 2.4}, {.value: 4, .original_order: 2.5}, {.value: 4, .original_order: 2.6}, {.value: 6, .original_order: 2.7}, {.value: 10, .original_order: 2.8}, {.value: 8, .original_order: 2.9}, {.value: 12, .original_order: 2.10}
193 };
194
195 {
196 auto in = orig_in;
197 std::ranges::stable_partition(in.begin(), in.end(), is_odd);
198 assert(in == expected);
199 }
200
201 {
202 auto in = orig_in;
203 std::ranges::stable_partition(in, is_odd);
204 assert(in == expected);
205 }
206 }
207
208 { // A custom projection works.
209 const std::array input = {1, -1};
210 auto is_negative = [](int x) { return x < 0; };
211 auto negate = [](int x) { return -x; };
212 const std::array expected_no_proj = {-1, 1};
213 const std::array expected_with_proj = {1, -1};
214
215 { // (iterator, sentinel) overload.
216 {
217 auto in = input;
218 std::ranges::partition(in.begin(), in.end(), is_negative);
219 assert(in == expected_no_proj);
220 }
221 {
222 auto in = input;
223 std::ranges::partition(in.begin(), in.end(), is_negative, negate);
224 assert(in == expected_with_proj);
225 }
226 }
227
228 { // (range) overload.
229 {
230 auto in = input;
231 std::ranges::partition(in, is_negative);
232 assert(in == expected_no_proj);
233 }
234 {
235 auto in = input;
236 std::ranges::partition(in, is_negative, negate);
237 assert(in == expected_with_proj);
238 }
239 }
240 }
241}
242
243int main(int, char**) {
244 test();
245 // Note: `stable_partition` is not `constexpr`.
246
247 return 0;
248}
249

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp