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