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 
32 struct UnaryPred { bool operator()(int) const; };
33 
34 // Test constraints of the (iterator, sentinel) overload.
35 // ======================================================
36 
37 template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
38 concept 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 
43 static_assert(HasStablePartitionIter<int*, int*, UnaryPred>);
44 
45 // !bidirectional_iterator<I>
46 static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDerivedFrom>);
47 static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDecrementable>);
48 
49 // !sentinel_for<S, I>
50 static_assert(!HasStablePartitionIter<int*, SentinelForNotSemiregular>);
51 static_assert(!HasStablePartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
52 
53 // !indirect_unary_predicate<projected<I, Proj>>
54 static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
55 static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
56 
57 // !permutable<I>
58 static_assert(!HasStablePartitionIter<PermutableNotForwardIterator>);
59 static_assert(!HasStablePartitionIter<PermutableNotSwappable>);
60 
61 // Test constraints of the (range) overload.
62 // =========================================
63 
64 template <class Range, class Pred>
65 concept HasStablePartitionRange =
66     requires(Range&& range, Pred&& pred) {
67       std::ranges::stable_partition(std::forward<Range>(range), std::forward<Pred>(pred));
68     };
69 
70 template <class T>
71 using R = UncheckedRange<T>;
72 
73 static_assert(HasStablePartitionRange<R<int*>, UnaryPred>);
74 
75 // !bidirectional_range<R>
76 static_assert(!HasStablePartitionRange<BidirectionalRangeNotDerivedFrom, UnaryPred>);
77 static_assert(!HasStablePartitionRange<BidirectionalRangeNotDecrementable, UnaryPred>);
78 
79 // !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
80 static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
81 static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
82 
83 // !permutable<iterator_t<R>>
84 static_assert(!HasStablePartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
85 static_assert(!HasStablePartitionRange<R<PermutableNotSwappable>, UnaryPred>);
86 
87 template <class Iter, class Sent, size_t N, class Pred>
88 void test_one(std::array<int, N> input, Pred pred, 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 
123 template <class Iter, class Sent>
124 void 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 
159 template <class Iter>
160 void test_iterators_1() {
161   test_iterators_2<Iter, Iter>();
162   test_iterators_2<Iter, sentinel_wrapper<Iter>>();
163 }
164 
165 void 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 
172 void 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{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},
188       {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}
189     };
190     Array expected = {
191       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},
192       {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}
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 
243 int main(int, char**) {
244   test();
245   // Note: `stable_partition` is not `constexpr`.
246 
247   return 0;
248 }
249