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

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