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