306 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 11// <algorithm>12 13// template<input_iterator I, sentinel_for<I> S,14// weakly_incrementable O1, weakly_incrementable O2,15// class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>16// requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>17// constexpr partition_copy_result<I, O1, O2>18// partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,19// Proj proj = {}); // Since C++2020//21// template<input_range R, weakly_incrementable O1, weakly_incrementable O2,22// class Proj = identity,23// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>24// requires indirectly_copyable<iterator_t<R>, O1> &&25// indirectly_copyable<iterator_t<R>, O2>26// constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2>27// partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); // Since C++2028 29#include <algorithm>30#include <array>31#include <concepts>32#include <functional>33#include <ranges>34#include <utility>35 36#include "almost_satisfies_types.h"37#include "counting_predicates.h"38#include "counting_projection.h"39#include "test_iterators.h"40 41struct UnaryPred { bool operator()(int) const; };42 43// Test constraints of the (iterator, sentinel) overload.44// ======================================================45 46template <class InIter = int*, class Sent = int*, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>47concept HasPartitionCopyIter =48 requires(InIter&& input, Sent&& sent, Output1&& output1, Output2&& output2, Pred&& pred) {49 std::ranges::partition_copy(std::forward<InIter>(input), std::forward<Sent>(sent),50 std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred));51 };52 53static_assert(HasPartitionCopyIter<int*, int*, int*, int*, UnaryPred>);54 55// !input_iterator<I>56static_assert(!HasPartitionCopyIter<InputIteratorNotDerivedFrom>);57static_assert(!HasPartitionCopyIter<InputIteratorNotIndirectlyReadable>);58static_assert(!HasPartitionCopyIter<InputIteratorNotInputOrOutputIterator>);59 60// !sentinel_for<S, I>61static_assert(!HasPartitionCopyIter<int*, SentinelForNotSemiregular>);62static_assert(!HasPartitionCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);63 64// !weakly_incrementable<O1>65static_assert(!HasPartitionCopyIter<int*, int*, WeaklyIncrementableNotMovable>);66 67// !weakly_incrementable<O2>68static_assert(!HasPartitionCopyIter<int*, int*, int*, WeaklyIncrementableNotMovable>);69 70// !indirect_unary_predicate<projected<I, Proj>>71static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);72static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);73 74struct Uncopyable {75 Uncopyable(int&&);76 Uncopyable(const int&) = delete;77};78// !indirectly_copyable<I, O1>79static_assert(!HasPartitionCopyIter<int*, int*, Uncopyable*>);80// !indirectly_copyable<I, O2>81static_assert(!HasPartitionCopyIter<int*, int*, int*, Uncopyable*>);82 83// Test constraints of the (range) overload.84// =========================================85 86template <class InputRange, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>87concept HasPartitionCopyRange =88 requires(InputRange&& input, Output1&& output1, Output2&& output2, Pred&& pred) {89 std::ranges::partition_copy(std::forward<InputRange>(input),90 std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred));91 };92 93template <class T>94using R = UncheckedRange<T>;95 96static_assert(HasPartitionCopyRange<R<int*>, int*, int*, UnaryPred>);97 98// !input_iterator<I>99static_assert(!HasPartitionCopyRange<InputRangeNotDerivedFrom>);100static_assert(!HasPartitionCopyRange<InputRangeNotIndirectlyReadable>);101static_assert(!HasPartitionCopyRange<InputRangeNotInputOrOutputIterator>);102 103// !weakly_incrementable<O1>104static_assert(!HasPartitionCopyRange<R<int*>, WeaklyIncrementableNotMovable>);105 106// !weakly_incrementable<O2>107static_assert(!HasPartitionCopyRange<R<int*>, int*, WeaklyIncrementableNotMovable>);108 109// !indirect_unary_predicate<projected<I, Proj>>110static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotPredicate>);111static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);112 113// !indirectly_copyable<I, O1>114static_assert(!HasPartitionCopyRange<R<int*>, Uncopyable*>);115// !indirectly_copyable<I, O2>116static_assert(!HasPartitionCopyRange<R<int*>, int*, Uncopyable*>);117 118static_assert(std::is_same_v<std::ranges::partition_copy_result<int, int, int>,119 std::ranges::in_out_out_result<int, int, int>>);120 121template <class Iter, class Sent, class OutIter1, class OutIter2, std::size_t N1, size_t N2, size_t N3, class Pred>122constexpr void test_one(std::array<int, N1> input, Pred pred, std::array<int, N2> expected_true,123 std::array<int, N3> expected_false) {124 static_assert(N2 + N3 == N1);125 using ResultT = std::ranges::partition_copy_result<Iter, OutIter1, OutIter2>;126 127 auto begin = input.data();128 auto end = input.data() + input.size();129 130 { // (iterator, sentinel) overload.131 std::array<int, N2> out1;132 std::array<int, N3> out2;133 134 std::same_as<ResultT> decltype(auto) result = std::ranges::partition_copy(135 Iter(begin), Sent(Iter(end)), OutIter1(out1.data()), OutIter2(out2.data()), pred);136 137 assert(base(result.in) == input.data() + input.size());138 assert(base(result.out1) == out1.data() + expected_true.size());139 assert(base(result.out2) == out2.data() + expected_false.size());140 141 assert(std::ranges::equal(out1, expected_true));142 assert(std::ranges::equal(out2, expected_false));143 }144 145 { // (range) overload.146 std::ranges::subrange range{Iter(begin), Sent(Iter(end))};147 std::array<int, N2> out1;148 std::array<int, N3> out2;149 150 std::same_as<ResultT> decltype(auto) result = std::ranges::partition_copy(151 range, OutIter1(out1.data()), OutIter2(out2.data()), pred);152 153 assert(base(result.in) == input.data() + input.size());154 assert(base(result.out1) == out1.data() + expected_true.size());155 assert(base(result.out2) == out2.data() + expected_false.size());156 157 assert(std::ranges::equal(out1, expected_true));158 assert(std::ranges::equal(out2, expected_false));159 }160}161 162template <class InIter, class Sent, class Out1, class Out2>163constexpr void test_iterators_in_sent_out1_out2() {164 auto is_odd = [](int x) { return x % 2 != 0; };165 166 // Empty sequence.167 test_one<InIter, Sent, Out1, Out2, 0, 0, 0>({}, is_odd, {}, {});168 // 1-element sequence, the element satisfies the predicate.169 test_one<InIter, Sent, Out1, Out2, 1, 1, 0>({1}, is_odd, {1}, {});170 // 1-element sequence, the element doesn't satisfy the predicate.171 test_one<InIter, Sent, Out1, Out2, 1, 0, 1>({2}, is_odd, {}, {2});172 // 2-element sequence, not in order.173 test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({2, 1}, is_odd, {1}, {2});174 // 2-element sequence, already in order.175 test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({1, 2}, is_odd, {1}, {2});176 // 3-element sequence.177 test_one<InIter, Sent, Out1, Out2, 3, 2, 1>({2, 1, 3}, is_odd, {1, 3}, {2});178 // Longer sequence.179 test_one<InIter, Sent, Out1, Out2, 8, 4, 4>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, {1, 3, 11, 5}, {2, 6, 8, 4});180 // Longer sequence with duplicates.181 test_one<InIter, Sent, Out1, Out2, 8, 3, 5>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, {1, 3, 1}, {2, 6, 2, 8, 6});182 // All elements are the same and satisfy the predicate.183 test_one<InIter, Sent, Out1, Out2, 3, 3, 0>({1, 1, 1}, is_odd, {1, 1, 1}, {});184 // All elements are the same and don't satisfy the predicate.185 test_one<InIter, Sent, Out1, Out2, 3, 0, 3>({2, 2, 2}, is_odd, {}, {2, 2, 2});186 // Already partitioned.187 test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 3, 5, 4, 6, 8}, is_odd, {1, 3, 5}, {4, 6, 8});188 // Reverse-partitioned.189 test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({4, 6, 8, 1, 3, 5}, is_odd, {1, 3, 5}, {4, 6, 8});190 // Repeating pattern.191 test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 2, 1, 2, 1, 2}, is_odd, {1, 1, 1}, {2, 2, 2});192 193 auto is_negative = [](int x) { return x < 0; };194 // Different comparator.195 test_one<InIter, Sent, Out1, Out2, 5, 2, 3>({-3, 5, 7, -6, 2}, is_negative, {-3, -6}, {5, 7, 2});196}197 198template <class InIter, class Sent, class Out1>199constexpr void test_iterators_in_sent_out1() {200 test_iterators_in_sent_out1_out2<InIter, Sent, Out1, cpp20_output_iterator<int*>>();201 test_iterators_in_sent_out1_out2<InIter, Sent, Out1, random_access_iterator<int*>>();202 test_iterators_in_sent_out1_out2<InIter, Sent, Out1, int*>();203}204 205template <class InIter, class Sent>206constexpr void test_iterators_in_sent() {207 test_iterators_in_sent_out1<InIter, Sent, cpp17_output_iterator<int*>>();208 test_iterators_in_sent_out1<InIter, Sent, cpp20_output_iterator<int*>>();209 test_iterators_in_sent_out1<InIter, Sent, random_access_iterator<int*>>();210 test_iterators_in_sent_out1<InIter, Sent, int*>();211}212 213template <class InIter>214constexpr void test_iterators_in() {215 if constexpr (std::sentinel_for<InIter, InIter>) {216 test_iterators_in_sent<InIter, InIter>();217 }218 test_iterators_in_sent<InIter, sentinel_wrapper<InIter>>();219}220 221constexpr void test_iterators() {222 // Note: deliberately testing with only the weakest and "strongest" iterator types to minimize combinatorial223 // explosion.224 test_iterators_in<cpp20_input_iterator<int*>>();225 test_iterators_in<int*>();226}227 228constexpr bool test() {229 test_iterators();230 231 { // A custom projection works.232 const std::array in = {1, 3, 9, -2, -5, -8};233 auto is_negative = [](int x) { return x < 0; };234 auto negate = [](int x) { return -x; };235 const std::array expected_negative = {-2, -5, -8};236 const std::array expected_positive = {1, 3, 9};237 238 { // (iterator, sentinel) overload.239 {240 std::array<int, 3> out1, out2;241 std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative);242 assert(out1 == expected_negative);243 assert(out2 == expected_positive);244 }245 {246 std::array<int, 3> out1, out2;247 std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative, negate);248 assert(out1 == expected_positive);249 assert(out2 == expected_negative);250 }251 }252 253 { // (range) overload.254 {255 std::array<int, 3> out1, out2;256 std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative);257 assert(out1 == expected_negative);258 assert(out2 == expected_positive);259 }260 {261 std::array<int, 3> out1, out2;262 std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative, negate);263 assert(out1 == expected_positive);264 assert(out2 == expected_negative);265 }266 }267 }268 269 { // Complexity: Exactly `last - first` applications of `pred` and `proj`.270 {271 const std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2};272 auto is_negative = [](int x) { return x < 0; };273 std::array<int, 6> out1;274 std::array<int, 8> out2;275 276 int pred_count = 0, proj_count = 0;277 counting_predicate pred(is_negative, pred_count);278 counting_projection proj(proj_count);279 auto expected = static_cast<int>(in.size());280 281 {282 std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), pred, proj);283 assert(pred_count == expected);284 assert(proj_count == expected);285 pred_count = proj_count = 0;286 }287 288 {289 std::ranges::partition_copy(in, out1.begin(), out2.begin(), pred, proj);290 assert(pred_count == expected);291 assert(proj_count == expected);292 pred_count = proj_count = 0;293 }294 }295 }296 297 return true;298}299 300int main(int, char**) {301 test();302 static_assert(test());303 304 return 0;305}306