256 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<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,14// indirect_unary_predicate<projected<I, Proj>> Pred>15// requires permutable<I>16// constexpr subrange<I> // constexpr since C++2617// stable_partition(I first, S last, Pred pred, Proj proj = {}); // Since C++2018//19// template<bidirectional_range R, class Proj = identity,20// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>21// requires permutable<iterator_t<R>>22// constexpr borrowed_subrange_t<R> // constexpr since C++2623// stable_partition(R&& r, Pred pred, Proj proj = {}); // Since C++2024 25#include <algorithm>26#include <array>27#include <concepts>28#include <functional>29#include <ranges>30 31#include "almost_satisfies_types.h"32#include "test_iterators.h"33 34struct UnaryPred { bool operator()(int) const; };35 36// Test constraints of the (iterator, sentinel) overload.37// ======================================================38 39template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>40concept HasStablePartitionIter =41 requires(Iter&& iter, Sent&& sent, Pred&& pred) {42 std::ranges::stable_partition(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));43 };44 45static_assert(HasStablePartitionIter<int*, int*, UnaryPred>);46 47// !bidirectional_iterator<I>48static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDerivedFrom>);49static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDecrementable>);50 51// !sentinel_for<S, I>52static_assert(!HasStablePartitionIter<int*, SentinelForNotSemiregular>);53static_assert(!HasStablePartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);54 55// !indirect_unary_predicate<projected<I, Proj>>56static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);57static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);58 59// !permutable<I>60static_assert(!HasStablePartitionIter<PermutableNotForwardIterator>);61static_assert(!HasStablePartitionIter<PermutableNotSwappable>);62 63// Test constraints of the (range) overload.64// =========================================65 66template <class Range, class Pred>67concept HasStablePartitionRange =68 requires(Range&& range, Pred&& pred) {69 std::ranges::stable_partition(std::forward<Range>(range), std::forward<Pred>(pred));70 };71 72template <class T>73using R = UncheckedRange<T>;74 75static_assert(HasStablePartitionRange<R<int*>, UnaryPred>);76 77// !bidirectional_range<R>78static_assert(!HasStablePartitionRange<BidirectionalRangeNotDerivedFrom, UnaryPred>);79static_assert(!HasStablePartitionRange<BidirectionalRangeNotDecrementable, UnaryPred>);80 81// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>82static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);83static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);84 85// !permutable<iterator_t<R>>86static_assert(!HasStablePartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);87static_assert(!HasStablePartitionRange<R<PermutableNotSwappable>, UnaryPred>);88 89template <class Iter, class Sent, std::size_t N, class Pred>90TEST_CONSTEXPR_CXX26 void91test_one(std::array<int, N> input, Pred pred, std::size_t partition_point, std::array<int, N> expected) {92 auto neg_pred = [&](int x) { return !pred(x); };93 94 { // (iterator, sentinel) overload.95 auto partitioned = input;96 auto b = Iter(partitioned.data());97 auto e = Sent(Iter(partitioned.data() + partitioned.size()));98 99 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::stable_partition(b, e, pred);100 101 assert(partitioned == expected);102 assert(base(result.begin()) == partitioned.data() + partition_point);103 assert(base(result.end()) == partitioned.data() + partitioned.size());104 105 assert(std::ranges::all_of(b, result.begin(), pred));106 assert(std::ranges::all_of(result.begin(), e, neg_pred));107 }108 109 { // (range) overload.110 auto partitioned = input;111 auto b = Iter(partitioned.data());112 auto e = Sent(Iter(partitioned.data() + partitioned.size()));113 auto range = std::ranges::subrange(b, e);114 115 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::stable_partition(range, pred);116 117 assert(partitioned == expected);118 assert(base(result.begin()) == partitioned.data() + partition_point);119 assert(base(result.end()) == partitioned.data() + partitioned.size());120 121 assert(std::ranges::all_of(b, result.begin(), pred));122 assert(std::ranges::all_of(result.begin(), e, neg_pred));123 }124}125 126template <class Iter, class Sent>127TEST_CONSTEXPR_CXX26 void test_iterators_2() {128 auto is_odd = [](int x) { return x % 2 != 0; };129 130 // Empty sequence.131 test_one<Iter, Sent, 0>({}, is_odd, 0, {});132 // 1-element sequence, the element satisfies the predicate.133 test_one<Iter, Sent, 1>({1}, is_odd, 1, {1});134 // 1-element sequence, the element doesn't satisfy the predicate.135 test_one<Iter, Sent, 1>({2}, is_odd, 0, {2});136 // 2-element sequence, not in order.137 test_one<Iter, Sent, 2>({2, 1}, is_odd, 1, {1, 2});138 // 2-element sequence, already in order.139 test_one<Iter, Sent, 2>({1, 2}, is_odd, 1, {1, 2});140 // 3-element sequence.141 test_one<Iter, Sent, 3>({2, 1, 3}, is_odd, 2, {1, 3, 2});142 // Longer sequence.143 test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, 4, {1, 3, 11, 5, 2, 6, 8, 4});144 // Longer sequence with duplicates.145 test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, 3, {1, 3, 1, 2, 6, 2, 8, 6});146 // All elements are the same and satisfy the predicate.147 test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3, {1, 1, 1});148 // All elements are the same and don't satisfy the predicate.149 test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0, {2, 2, 2});150 // Already partitioned.151 test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3, {1, 3, 5, 4, 6, 8});152 // Reverse-partitioned.153 test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3, {1, 3, 5, 4, 6, 8});154 // Repeating pattern.155 test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3, {1, 1, 1, 2, 2, 2});156 157 auto is_negative = [](int x) { return x < 0; };158 // Different comparator.159 test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, 2, {-3, -6, 5, 7, 2});160}161 162template <class Iter>163TEST_CONSTEXPR_CXX26 void test_iterators_1() {164 test_iterators_2<Iter, Iter>();165 test_iterators_2<Iter, sentinel_wrapper<Iter>>();166}167 168TEST_CONSTEXPR_CXX26 void test_iterators() {169 test_iterators_1<bidirectional_iterator<int*>>();170 test_iterators_1<random_access_iterator<int*>>();171 test_iterators_1<contiguous_iterator<int*>>();172 test_iterators_1<int*>();173}174 175TEST_CONSTEXPR_CXX26 bool test() {176 test_iterators();177 178 { // The algorithm is stable (equivalent elements remain in the same order).179 struct OrderedValue {180 int value;181 double original_order;182 bool operator==(const OrderedValue&) const = default;183 };184 185 auto is_odd = [](OrderedValue x) { return x.value % 2 != 0; };186 187 using V = OrderedValue;188 using Array = std::array<V, 20>;189 Array orig_in = {190 V{10, 2.1}, {12, 2.2}, {3, 1.1}, {5, 1.2}, {3, 1.3}, {3, 1.4}, {11, 1.5}, {12, 2.3}, {4, 2.4}, {4, 2.5},191 {4, 2.6}, {1, 1.6}, {6, 2.7}, {3, 1.7}, {10, 2.8}, {8, 2.9}, {12, 2.10}, {1, 1.8}, {1, 1.9}, {5, 1.10}192 };193 Array expected = {194 V{3, 1.1}, {5, 1.2}, {3, 1.3}, {3, 1.4}, {11, 1.5}, {1, 1.6}, {3, 1.7}, {1, 1.8}, {1, 1.9}, {5, 1.10},195 {10, 2.1}, {12, 2.2}, {12, 2.3}, {4, 2.4}, {4, 2.5}, {4, 2.6}, {6, 2.7}, {10, 2.8}, {8, 2.9}, {12, 2.10}196 };197 198 {199 auto in = orig_in;200 std::ranges::stable_partition(in.begin(), in.end(), is_odd);201 assert(in == expected);202 }203 204 {205 auto in = orig_in;206 std::ranges::stable_partition(in, is_odd);207 assert(in == expected);208 }209 }210 211 { // A custom projection works.212 const std::array input = {1, -1};213 auto is_negative = [](int x) { return x < 0; };214 auto negate = [](int x) { return -x; };215 const std::array expected_no_proj = {-1, 1};216 const std::array expected_with_proj = {1, -1};217 218 { // (iterator, sentinel) overload.219 {220 auto in = input;221 std::ranges::partition(in.begin(), in.end(), is_negative);222 assert(in == expected_no_proj);223 }224 {225 auto in = input;226 std::ranges::partition(in.begin(), in.end(), is_negative, negate);227 assert(in == expected_with_proj);228 }229 }230 231 { // (range) overload.232 {233 auto in = input;234 std::ranges::partition(in, is_negative);235 assert(in == expected_no_proj);236 }237 {238 auto in = input;239 std::ranges::partition(in, is_negative, negate);240 assert(in == expected_with_proj);241 }242 }243 }244 245 return true;246}247 248int main(int, char**) {249 test();250#if TEST_STD_VER >= 26251 static_assert(test());252#endif253 254 return 0;255}256