libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.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<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
  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 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
  44 static_assert(HasPartitionIter<int*, int*, UnaryPred>);
  45
  46 // !permutable<I>
  47 static_assert(!HasPartitionIter<PermutableNotForwardIterator>);
  48 static_assert(!HasPartitionIter<PermutableNotSwappable>);
  49
  50 // !sentinel_for<S, I>
  51 static_assert(!HasPartitionIter<int*, SentinelForNotSemiregular>);
  52 static_assert(!HasPartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
  53
  54 // !indirect_unary_predicate<projected<I, Proj>>
  55 static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
  56 static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
  57
  58 // Test constraints of the (range) overload.
  59 // =========================================
  60
  61 template <class Range, class Pred>
  62 concept HasPartitionRange =
  63     requires(Range&& range, Pred&& pred) {
  64       std::ranges::partition(std::forward<Range>(range), std::forward<Pred>(pred));
  65     };
  66
  67 template <class T>
  68 using R = UncheckedRange<T>;
  69
  70 static_assert(HasPartitionRange<R<int*>, UnaryPred>);
  71
  72 // !forward_range<R>
  73 static_assert(!HasPartitionRange<ForwardRangeNotDerivedFrom, UnaryPred>);
  74 static_assert(!HasPartitionRange<ForwardRangeNotIncrementable, UnaryPred>);
  75
  76 // !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  77 static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
  78 static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
  79
  80 // !permutable<iterator_t<R>>
  81 static_assert(!HasPartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
  82 static_assert(!HasPartitionRange<R<PermutableNotSwappable>, UnaryPred>);
  83
  84 // `partition` isn't a stable algorithm so this function cannot test the exact output.
  85 template <class Iter, class Sent, std::size_t N, class Pred>
  86 constexpr 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
 119 template <class Iter, class Sent>
 120 constexpr 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
 155 template <class Iter>
 156 constexpr void test_iterators_1() {
 157   test_iterators_2<Iter, Iter>();
 158   test_iterators_2<Iter, sentinel_wrapper<Iter>>();
 159 }
 160
 161 constexpr 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
 169 constexpr 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
 209 int main(int, char**) {
 210   test();
 211   static_assert(test());
 212
 213   return 0;
 214 }