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