libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 // UNSUPPORTED: c++03, c++11, c++14, c++17
  10
  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++20
  20 //
  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++20
  28
  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
  41 struct UnaryPred { bool operator()(int) const; };
  42
  43 // Test constraints of the (iterator, sentinel) overload.
  44 // ======================================================
  45
  46 template <class InIter = int*, class Sent = int*, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
  47 concept 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
  53 static_assert(HasPartitionCopyIter<int*, int*, int*, int*, UnaryPred>);
  54
  55 // !input_iterator<I>
  56 static_assert(!HasPartitionCopyIter<InputIteratorNotDerivedFrom>);
  57 static_assert(!HasPartitionCopyIter<InputIteratorNotIndirectlyReadable>);
  58 static_assert(!HasPartitionCopyIter<InputIteratorNotInputOrOutputIterator>);
  59
  60 // !sentinel_for<S, I>
  61 static_assert(!HasPartitionCopyIter<int*, SentinelForNotSemiregular>);
  62 static_assert(!HasPartitionCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
  63
  64 // !weakly_incrementable<O1>
  65 static_assert(!HasPartitionCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
  66
  67 // !weakly_incrementable<O2>
  68 static_assert(!HasPartitionCopyIter<int*, int*, int*, WeaklyIncrementableNotMovable>);
  69
  70 // !indirect_unary_predicate<projected<I, Proj>>
  71 static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
  72 static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
  73
  74 struct Uncopyable {
  75   Uncopyable(int&&);
  76   Uncopyable(const int&) = delete;
  77 };
  78 // !indirectly_copyable<I, O1>
  79 static_assert(!HasPartitionCopyIter<int*, int*, Uncopyable*>);
  80 // !indirectly_copyable<I, O2>
  81 static_assert(!HasPartitionCopyIter<int*, int*, int*, Uncopyable*>);
  82
  83 // Test constraints of the (range) overload.
  84 // =========================================
  85
  86 template <class InputRange, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
  87 concept 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
  93 template <class T>
  94 using R = UncheckedRange<T>;
  95
  96 static_assert(HasPartitionCopyRange<R<int*>, int*, int*, UnaryPred>);
  97
  98 // !input_iterator<I>
  99 static_assert(!HasPartitionCopyRange<InputRangeNotDerivedFrom>);
 100 static_assert(!HasPartitionCopyRange<InputRangeNotIndirectlyReadable>);
 101 static_assert(!HasPartitionCopyRange<InputRangeNotInputOrOutputIterator>);
 102
 103 // !weakly_incrementable<O1>
 104 static_assert(!HasPartitionCopyRange<R<int*>, WeaklyIncrementableNotMovable>);
 105
 106 // !weakly_incrementable<O2>
 107 static_assert(!HasPartitionCopyRange<R<int*>, int*, WeaklyIncrementableNotMovable>);
 108
 109 // !indirect_unary_predicate<projected<I, Proj>>
 110 static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotPredicate>);
 111 static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
 112
 113 // !indirectly_copyable<I, O1>
 114 static_assert(!HasPartitionCopyRange<R<int*>, Uncopyable*>);
 115 // !indirectly_copyable<I, O2>
 116 static_assert(!HasPartitionCopyRange<R<int*>, int*, Uncopyable*>);
 117
 118 static_assert(std::is_same_v<std::ranges::partition_copy_result<int, int, int>,
 119     std::ranges::in_out_out_result<int, int, int>>);
 120
 121 template <class Iter, class Sent, class OutIter1, class OutIter2, std::size_t N1, size_t N2, size_t N3, class Pred>
 122 constexpr 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.begin()), OutIter2(out2.begin()), 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.begin()), OutIter2(out2.begin()), 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
 162 template <class InIter, class Sent, class Out1, class Out2>
 163 constexpr 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
 198 template <class InIter, class Sent, class Out1>
 199 constexpr 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
 205 template <class InIter, class Sent>
 206 constexpr 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
 213 template <class InIter>
 214 constexpr 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
 221 constexpr void test_iterators() {
 222   // Note: deliberately testing with only the weakest and "strongest" iterator types to minimize combinatorial
 223   // explosion.
 224   test_iterators_in<cpp20_input_iterator<int*>>();
 225   test_iterators_in<int*>();
 226 }
 227
 228 constexpr 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
 300 int main(int, char**) {
 301   test();
 302   static_assert(test());
 303
 304   return 0;
 305 }