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