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<forward_iterator I, sentinel_for<I> S, class Proj = identity,
15 // indirect_unary_predicate<projected<I, Proj>> Pred>
16 // constexpr I partition_point(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 // constexpr borrowed_iterator_t<R>
21 // partition_point(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 #include <utility>
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 HasPartitionPointIter =
40 requires(Iter&& iter, Sent&& sent, Pred&& pred) {
41 std::ranges::partition_point(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
42 };
43
44 static_assert(HasPartitionPointIter<int*, int*, UnaryPred>);
45
46 // !forward_iterator<I>
47 static_assert(!HasPartitionPointIter<ForwardIteratorNotDerivedFrom>);
48 static_assert(!HasPartitionPointIter<ForwardIteratorNotIncrementable>);
49
50 // !sentinel_for<S, I>
51 static_assert(!HasPartitionPointIter<int*, SentinelForNotSemiregular>);
52 static_assert(!HasPartitionPointIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
53
54 // !indirect_unary_predicate<projected<I, Proj>>
55 static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
56 static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
57
58 // Test constraints of the (range) overload.
59 // =========================================
60
61 template <class Range, class Pred>
62 concept HasPartitionPointRange =
63 requires(Range&& range, Pred&& pred) {
64 std::ranges::partition_point(std::forward<Range>(range), std::forward<Pred>(pred));
65 };
66
67 template <class T>
68 using R = UncheckedRange<T>;
69
70 static_assert(HasPartitionPointRange<R<int*>, UnaryPred>);
71
72 // !forward_range<R>
73 static_assert(!HasPartitionPointRange<ForwardRangeNotDerivedFrom, UnaryPred>);
74 static_assert(!HasPartitionPointRange<ForwardRangeNotIncrementable, UnaryPred>);
75
76 // !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
77 static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
78 static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
79
80 template <class Iter, class Sent, size_t N, class Pred>
test_one(std::array<int,N> input,Pred pred,size_t partition_point)81 constexpr void test_one(std::array<int, N> input, Pred pred, size_t partition_point) {
82 assert(std::ranges::is_partitioned(input, pred));
83
84 auto begin = Iter(input.data());
85 auto end = Sent(Iter(input.data() + input.size()));
86 auto neg_pred = [&](int x) { return !pred(x); };
87
88 { // (iterator, sentinel) overload.
89 std::same_as<Iter> decltype(auto) result = std::ranges::partition_point(begin, end, pred);
90
91 assert(base(result) == input.data() + partition_point);
92 assert(std::ranges::all_of(begin, result, pred));
93 assert(std::ranges::all_of(result, end, neg_pred));
94 }
95
96 { // (range) overload.
97 auto range = std::ranges::subrange(begin, end);
98 std::same_as<Iter> decltype(auto) result = std::ranges::partition_point(range, pred);
99
100 assert(base(result) == input.data() + partition_point);
101 assert(std::ranges::all_of(begin, result, pred));
102 assert(std::ranges::all_of(result, end, neg_pred));
103 }
104 }
105
106 template <class Iter, class Sent>
test_iterators_2()107 constexpr void test_iterators_2() {
108 auto is_odd = [](int x) { return x % 2 != 0; };
109
110 // Empty sequence.
111 test_one<Iter, Sent, 0>({}, is_odd, 0);
112 // 1-element sequence, the element satisfies the predicate.
113 test_one<Iter, Sent, 1>({1}, is_odd, 1);
114 // 1-element sequence, the element doesn't satisfy the predicate.
115 test_one<Iter, Sent, 1>({2}, is_odd, 0);
116 // 2-element sequence.
117 test_one<Iter, Sent, 2>({1, 2}, is_odd, 1);
118 // 3-element sequence.
119 test_one<Iter, Sent, 3>({3, 1, 2}, is_odd, 2);
120 // Longer sequence.
121 test_one<Iter, Sent, 8>({1, 3, 11, 5, 6, 2, 8, 4}, is_odd, 4);
122 // Longer sequence with duplicates.
123 test_one<Iter, Sent, 8>({1, 3, 3, 4, 6, 2, 8, 2}, is_odd, 3);
124 // All elements are the same and satisfy the predicate.
125 test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3);
126 // All elements are the same and don't satisfy the predicate.
127 test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
128 // All non-satisfying and all satisfying elements are the same.
129 test_one<Iter, Sent, 6>({1, 1, 1, 2, 2, 2}, is_odd, 3);
130
131 auto is_negative = [](int x) { return x < 0; };
132 // Different comparator.
133 test_one<Iter, Sent, 5>({-3, -6, 5, 7, 2}, is_negative, 2);
134 }
135
136 template <class Iter>
test_iterators_1()137 constexpr void test_iterators_1() {
138 test_iterators_2<Iter, Iter>();
139 test_iterators_2<Iter, sentinel_wrapper<Iter>>();
140 }
141
test_iterators()142 constexpr void test_iterators() {
143 test_iterators_1<forward_iterator<int*>>();
144 test_iterators_1<bidirectional_iterator<int*>>();
145 test_iterators_1<random_access_iterator<int*>>();
146 test_iterators_1<contiguous_iterator<int*>>();
147 test_iterators_1<int*>();
148 }
149
test()150 constexpr bool test() {
151 test_iterators();
152
153 { // A custom projection works.
154 const std::array in = {1, 3, 4, 6, 8};
155 auto is_odd = [](int x) { return x % 2 != 0; };
156 auto x2 = [](int x) { return x * 2; };
157 auto expected_no_proj = in.begin() + 2;
158 auto expected_with_proj = in.begin();
159
160 { // (iterator, sentinel) overload.
161 auto result_no_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd);
162 assert(result_no_proj == expected_no_proj);
163 auto result_with_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd, x2);
164 assert(result_with_proj == expected_with_proj);
165 }
166
167 { // (range) overload.
168 auto result_no_proj = std::ranges::partition_point(in, is_odd);
169 assert(result_no_proj == expected_no_proj);
170 auto result_with_proj = std::ranges::partition_point(in, is_odd, x2);
171 assert(result_with_proj == expected_with_proj);
172 }
173 }
174
175 return true;
176 }
177
main(int,char **)178 int main(int, char**) {
179 test();
180 static_assert(test());
181
182 return 0;
183 }
184