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>
test_one(std::array<int,N> input,Pred pred,size_t partition_point,std::array<int,N> expected)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>
test_iterators_2()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   auto is_negative = [](int x) { return x < 0; };
156   // Different comparator.
157   test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, 2, {-3, -6, 5, 7, 2});
158 }
159 
160 template <class Iter>
test_iterators_1()161 void test_iterators_1() {
162   test_iterators_2<Iter, Iter>();
163   test_iterators_2<Iter, sentinel_wrapper<Iter>>();
164 }
165 
test_iterators()166 void test_iterators() {
167   test_iterators_1<bidirectional_iterator<int*>>();
168   test_iterators_1<random_access_iterator<int*>>();
169   test_iterators_1<contiguous_iterator<int*>>();
170   test_iterators_1<int*>();
171 }
172 
test()173 void test() {
174   test_iterators();
175 
176   { // The algorithm is stable (equivalent elements remain in the same order).
177     struct OrderedValue {
178       int value;
179       double original_order;
180       bool operator==(const OrderedValue&) const = default;
181     };
182 
183     auto is_odd = [](OrderedValue x) { return x.value % 2 != 0; };
184 
185     using V = OrderedValue;
186     using Array = std::array<V, 20>;
187     Array orig_in = {
188       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},
189       {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}
190     };
191     Array expected = {
192       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},
193       {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}
194     };
195 
196     {
197       auto in = orig_in;
198       std::ranges::stable_partition(in.begin(), in.end(), is_odd);
199       assert(in == expected);
200     }
201 
202     {
203       auto in = orig_in;
204       std::ranges::stable_partition(in, is_odd);
205       assert(in == expected);
206     }
207   }
208 
209   { // A custom projection works.
210     const std::array input = {1, -1};
211     auto is_negative = [](int x) { return x < 0; };
212     auto negate = [](int x) { return -x; };
213     const std::array expected_no_proj = {-1, 1};
214     const std::array expected_with_proj = {1, -1};
215 
216     { // (iterator, sentinel) overload.
217       {
218         auto in = input;
219         std::ranges::partition(in.begin(), in.end(), is_negative);
220         assert(in == expected_no_proj);
221       }
222       {
223         auto in = input;
224         std::ranges::partition(in.begin(), in.end(), is_negative, negate);
225         assert(in == expected_with_proj);
226       }
227     }
228 
229     { // (range) overload.
230       {
231         auto in = input;
232         std::ranges::partition(in, is_negative);
233         assert(in == expected_no_proj);
234       }
235       {
236         auto in = input;
237         std::ranges::partition(in, is_negative, negate);
238         assert(in == expected_with_proj);
239       }
240     }
241   }
242 }
243 
main(int,char **)244 int main(int, char**) {
245   test();
246   // Note: `stable_partition` is not `constexpr`.
247 
248   return 0;
249 }
250