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