183 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<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++2016//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++2021 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 32struct UnaryPred { bool operator()(int) const; };33 34// Test constraints of the (iterator, sentinel) overload.35// ======================================================36 37template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>38concept 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 43static_assert(HasPartitionPointIter<int*, int*, UnaryPred>);44 45// !forward_iterator<I>46static_assert(!HasPartitionPointIter<ForwardIteratorNotDerivedFrom>);47static_assert(!HasPartitionPointIter<ForwardIteratorNotIncrementable>);48 49// !sentinel_for<S, I>50static_assert(!HasPartitionPointIter<int*, SentinelForNotSemiregular>);51static_assert(!HasPartitionPointIter<int*, SentinelForNotWeaklyEqualityComparableWith>);52 53// !indirect_unary_predicate<projected<I, Proj>>54static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotPredicate>);55static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);56 57// Test constraints of the (range) overload.58// =========================================59 60template <class Range, class Pred>61concept HasPartitionPointRange =62 requires(Range&& range, Pred&& pred) {63 std::ranges::partition_point(std::forward<Range>(range), std::forward<Pred>(pred));64 };65 66template <class T>67using R = UncheckedRange<T>;68 69static_assert(HasPartitionPointRange<R<int*>, UnaryPred>);70 71// !forward_range<R>72static_assert(!HasPartitionPointRange<ForwardRangeNotDerivedFrom, UnaryPred>);73static_assert(!HasPartitionPointRange<ForwardRangeNotIncrementable, UnaryPred>);74 75// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>76static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotPredicate>);77static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);78 79template <class Iter, class Sent, std::size_t N, class Pred>80constexpr 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 105template <class Iter, class Sent>106constexpr 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 135template <class Iter>136constexpr void test_iterators_1() {137 test_iterators_2<Iter, Iter>();138 test_iterators_2<Iter, sentinel_wrapper<Iter>>();139}140 141constexpr 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 149constexpr 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 177int main(int, char**) {178 test();179 static_assert(test());180 181 return 0;182}183