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<permutable I, sentinel_for<I> S, class Proj = identity,
14// indirect_unary_predicate<projected<I, Proj>> Pred>
15// constexpr subrange<I>
16// partition(I first, S last, Pred pred, Proj proj = {}); // Since C++20
17//
18// template<forward_range R, class Proj = identity,
19// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
20// requires permutable<iterator_t<R>>
21// constexpr borrowed_subrange_t<R>
22// 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
33struct UnaryPred { bool operator()(int) const; };
34
35// Test constraints of the (iterator, sentinel) overload.
36// ======================================================
37
38template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
39concept HasPartitionIter =
40 requires(Iter&& iter, Sent&& sent, Pred&& pred) {
41 std::ranges::partition(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
42 };
43
44static_assert(HasPartitionIter<int*, int*, UnaryPred>);
45
46// !permutable<I>
47static_assert(!HasPartitionIter<PermutableNotForwardIterator>);
48static_assert(!HasPartitionIter<PermutableNotSwappable>);
49
50// !sentinel_for<S, I>
51static_assert(!HasPartitionIter<int*, SentinelForNotSemiregular>);
52static_assert(!HasPartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
53
54// !indirect_unary_predicate<projected<I, Proj>>
55static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
56static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
57
58// Test constraints of the (range) overload.
59// =========================================
60
61template <class Range, class Pred>
62concept HasPartitionRange =
63 requires(Range&& range, Pred&& pred) {
64 std::ranges::partition(std::forward<Range>(range), std::forward<Pred>(pred));
65 };
66
67template <class T>
68using R = UncheckedRange<T>;
69
70static_assert(HasPartitionRange<R<int*>, UnaryPred>);
71
72// !forward_range<R>
73static_assert(!HasPartitionRange<ForwardRangeNotDerivedFrom, UnaryPred>);
74static_assert(!HasPartitionRange<ForwardRangeNotIncrementable, UnaryPred>);
75
76// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
77static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
78static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
79
80// !permutable<iterator_t<R>>
81static_assert(!HasPartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
82static_assert(!HasPartitionRange<R<PermutableNotSwappable>, UnaryPred>);
83
84// `partition` isn't a stable algorithm so this function cannot test the exact output.
85template <class Iter, class Sent, std::size_t N, class Pred>
86constexpr void test_one(std::array<int, N> input, Pred pred, std::size_t partition_point) {
87 auto neg_pred = [&](int x) { return !pred(x); };
88
89 { // (iterator, sentinel) overload.
90 auto partitioned = input;
91 auto b = Iter(partitioned.data());
92 auto e = Sent(Iter(partitioned.data() + partitioned.size()));
93
94 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::partition(b, e, pred);
95
96 assert(base(result.begin()) == partitioned.data() + partition_point);
97 assert(base(result.end()) == partitioned.data() + partitioned.size());
98
99 assert(std::ranges::all_of(b, result.begin(), pred));
100 assert(std::ranges::all_of(result.begin(), e, neg_pred));
101 }
102
103 { // (range) overload.
104 auto partitioned = input;
105 auto b = Iter(partitioned.data());
106 auto e = Sent(Iter(partitioned.data() + partitioned.size()));
107 auto range = std::ranges::subrange(b, e);
108
109 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::partition(range, pred);
110
111 assert(base(result.begin()) == partitioned.data() + partition_point);
112 assert(base(result.end()) == partitioned.data() + partitioned.size());
113
114 assert(std::ranges::all_of(b, result.begin(), pred));
115 assert(std::ranges::all_of(result.begin(), e, neg_pred));
116 }
117}
118
119template <class Iter, class Sent>
120constexpr void test_iterators_2() {
121 auto is_odd = [](int x) { return x % 2 != 0; };
122
123 // Empty sequence.
124 test_one<Iter, Sent, 0>({}, is_odd, 0);
125 // 1-element sequence, the element satisfies the predicate.
126 test_one<Iter, Sent, 1>({1}, is_odd, 1);
127 // 1-element sequence, the element doesn't satisfy the predicate.
128 test_one<Iter, Sent, 1>({2}, is_odd, 0);
129 // 2-element sequence, not in order.
130 test_one<Iter, Sent, 2>({2, 1}, is_odd, 1);
131 // 2-element sequence, already in order.
132 test_one<Iter, Sent, 2>({1, 2}, is_odd, 1);
133 // 3-element sequence.
134 test_one<Iter, Sent, 3>({2, 1, 3}, is_odd, 2);
135 // Longer sequence.
136 test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, 4);
137 // Longer sequence with duplicates.
138 test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, 3);
139 // All elements are the same and satisfy the predicate.
140 test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3);
141 // All elements are the same and don't satisfy the predicate.
142 test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
143 // Already partitioned.
144 test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3);
145 // Reverse-partitioned.
146 test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3);
147 // Repeating pattern.
148 test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3);
149
150 auto is_negative = [](int x) { return x < 0; };
151 // Different comparator.
152 test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, 2);
153}
154
155template <class Iter>
156constexpr void test_iterators_1() {
157 test_iterators_2<Iter, Iter>();
158 test_iterators_2<Iter, sentinel_wrapper<Iter>>();
159}
160
161constexpr void test_iterators() {
162 test_iterators_1<forward_iterator<int*>>();
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
169constexpr bool test() {
170 test_iterators();
171
172 { // A custom projection works.
173 const std::array input = {1, -1};
174 auto is_negative = [](int x) { return x < 0; };
175 auto negate = [](int x) { return -x; };
176 const std::array expected_no_proj = {-1, 1};
177 const std::array expected_with_proj = {1, -1};
178
179 { // (iterator, sentinel) overload.
180 {
181 auto in = input;
182 std::ranges::partition(in.begin(), in.end(), is_negative);
183 assert(in == expected_no_proj);
184 }
185 {
186 auto in = input;
187 std::ranges::partition(in.begin(), in.end(), is_negative, negate);
188 assert(in == expected_with_proj);
189 }
190 }
191
192 { // (range) overload.
193 {
194 auto in = input;
195 std::ranges::partition(in, is_negative);
196 assert(in == expected_no_proj);
197 }
198 {
199 auto in = input;
200 std::ranges::partition(in, is_negative, negate);
201 assert(in == expected_with_proj);
202 }
203 }
204 }
205
206 return true;
207}
208
209int main(int, char**) {
210 test();
211 static_assert(test());
212
213 return 0;
214}
215

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