//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// UNSUPPORTED: c++03, c++11, c++14, c++17
// <algorithm>
// template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
// indirect_unary_predicate<projected<I, Proj>> Pred>
// constexpr I partition_point(I first, S last, Pred pred, Proj proj = {}); // Since C++20
//
// template<forward_range R, class Proj = identity,
// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
// constexpr borrowed_iterator_t<R>
// partition_point(R&& r, Pred pred, Proj proj = {}); // Since C++20
#include <algorithm>
#include <array>
#include <concepts>
#include <functional>
#include <ranges>
#include <utility>
#include "almost_satisfies_types.h"
#include "test_iterators.h"
struct UnaryPred { bool operator()(int) const; };
// Test constraints of the (iterator, sentinel) overload.
// ======================================================
template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
concept HasPartitionPointIter =
requires(Iter&& iter, Sent&& sent, Pred&& pred) {
std::ranges::partition_point(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
};
static_assert(HasPartitionPointIter<int*, int*, UnaryPred>);
// !forward_iterator<I>
static_assert(!HasPartitionPointIter<ForwardIteratorNotDerivedFrom>);
static_assert(!HasPartitionPointIter<ForwardIteratorNotIncrementable>);
// !sentinel_for<S, I>
static_assert(!HasPartitionPointIter<int*, SentinelForNotSemiregular>);
static_assert(!HasPartitionPointIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
// !indirect_unary_predicate<projected<I, Proj>>
static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
// Test constraints of the (range) overload.
// =========================================
template <class Range, class Pred>
concept HasPartitionPointRange =
requires(Range&& range, Pred&& pred) {
std::ranges::partition_point(std::forward<Range>(range), std::forward<Pred>(pred));
};
template <class T>
using R = UncheckedRange<T>;
static_assert(HasPartitionPointRange<R<int*>, UnaryPred>);
// !forward_range<R>
static_assert(!HasPartitionPointRange<ForwardRangeNotDerivedFrom, UnaryPred>);
static_assert(!HasPartitionPointRange<ForwardRangeNotIncrementable, UnaryPred>);
// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
template <class Iter, class Sent, std::size_t N, class Pred>
constexpr void test_one(std::array<int, N> input, Pred pred, std::size_t partition_point) {
assert(std::ranges::is_partitioned(input, pred));
auto begin = Iter(input.data());
auto end = Sent(Iter(input.data() + input.size()));
auto neg_pred = [&](int x) { return !pred(x); };
{ // (iterator, sentinel) overload.
std::same_as<Iter> decltype(auto) result = std::ranges::partition_point(begin, end, pred);
assert(base(result) == input.data() + partition_point);
assert(std::ranges::all_of(begin, result, pred));
assert(std::ranges::all_of(result, end, neg_pred));
}
{ // (range) overload.
auto range = std::ranges::subrange(begin, end);
std::same_as<Iter> decltype(auto) result = std::ranges::partition_point(range, pred);
assert(base(result) == input.data() + partition_point);
assert(std::ranges::all_of(begin, result, pred));
assert(std::ranges::all_of(result, end, neg_pred));
}
}
template <class Iter, class Sent>
constexpr void test_iterators_2() {
auto is_odd = [](int x) { return x % 2 != 0; };
// Empty sequence.
test_one<Iter, Sent, 0>({}, is_odd, 0);
// 1-element sequence, the element satisfies the predicate.
test_one<Iter, Sent, 1>({1}, is_odd, 1);
// 1-element sequence, the element doesn't satisfy the predicate.
test_one<Iter, Sent, 1>({2}, is_odd, 0);
// 2-element sequence.
test_one<Iter, Sent, 2>({1, 2}, is_odd, 1);
// 3-element sequence.
test_one<Iter, Sent, 3>({3, 1, 2}, is_odd, 2);
// Longer sequence.
test_one<Iter, Sent, 8>({1, 3, 11, 5, 6, 2, 8, 4}, is_odd, 4);
// Longer sequence with duplicates.
test_one<Iter, Sent, 8>({1, 3, 3, 4, 6, 2, 8, 2}, is_odd, 3);
// All elements are the same and satisfy the predicate.
test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3);
// All elements are the same and don't satisfy the predicate.
test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
// All non-satisfying and all satisfying elements are the same.
test_one<Iter, Sent, 6>({1, 1, 1, 2, 2, 2}, is_odd, 3);
auto is_negative = [](int x) { return x < 0; };
// Different comparator.
test_one<Iter, Sent, 5>({-3, -6, 5, 7, 2}, is_negative, 2);
}
template <class Iter>
constexpr void test_iterators_1() {
test_iterators_2<Iter, Iter>();
test_iterators_2<Iter, sentinel_wrapper<Iter>>();
}
constexpr void test_iterators() {
test_iterators_1<forward_iterator<int*>>();
test_iterators_1<bidirectional_iterator<int*>>();
test_iterators_1<random_access_iterator<int*>>();
test_iterators_1<contiguous_iterator<int*>>();
test_iterators_1<int*>();
}
constexpr bool test() {
test_iterators();
{ // A custom projection works.
const std::array in = {1, 3, 4, 6, 8};
auto is_odd = [](int x) { return x % 2 != 0; };
auto x2 = [](int x) { return x * 2; };
auto expected_no_proj = in.begin() + 2;
auto expected_with_proj = in.begin();
{ // (iterator, sentinel) overload.
auto result_no_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd);
assert(result_no_proj == expected_no_proj);
auto result_with_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd, x2);
assert(result_with_proj == expected_with_proj);
}
{ // (range) overload.
auto result_no_proj = std::ranges::partition_point(in, is_odd);
assert(result_no_proj == expected_no_proj);
auto result_with_proj = std::ranges::partition_point(in, is_odd, x2);
assert(result_with_proj == expected_with_proj);
}
}
return true;
}
int main(int, char**) {
test();
static_assert(test());
return 0;
}
Codebase Browser
llvm