libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy_if.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<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
  14 //          class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
  15 //   requires indirectly_copyable<I, O>
  16 //   constexpr remove_copy_if_result<I, O>
  17 //     remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});                        // Since C++20
  18 //
  19 // template<input_range R, weakly_incrementable O, class Proj = identity,
  20 //          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  21 //   requires indirectly_copyable<iterator_t<R>, O>
  22 //   constexpr remove_copy_if_result<borrowed_iterator_t<R>, O>
  23 //     remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});                                  // Since C++20
  24
  25 #include <algorithm>
  26 #include <array>
  27 #include <concepts>
  28 #include <functional>
  29 #include <ranges>
  30 #include <type_traits>
  31 #include <utility>
  32
  33 #include "almost_satisfies_types.h"
  34 #include "counting_predicates.h"
  35 #include "counting_projection.h"
  36 #include "test_iterators.h"
  37
  38 struct AlwaysTrue {
  39   constexpr bool operator()(auto&&...) const { return true; }
  40 };
  41
  42 template <
  43     class I,
  44     class S    = sentinel_wrapper<std::decay_t<I>>,
  45     class O    = int*,
  46     class Pred = AlwaysTrue>
  47 concept HasRemoveCopyIfIter =
  48   requires(I&& iter, S&& sent, O&& out, Pred&& pred) {
  49     std::ranges::remove_copy_if(std::forward<I>(iter), std::forward<S>(sent),
  50                                 std::forward<O>(out), std::forward<Pred>(pred));
  51 };
  52
  53 static_assert(HasRemoveCopyIfIter<int*, int*, int*>);
  54
  55 // !input_iterator<I>
  56 static_assert(!HasRemoveCopyIfIter<InputIteratorNotDerivedFrom>);
  57 static_assert(!HasRemoveCopyIfIter<cpp20_output_iterator<int*>>);
  58
  59 // !sentinel_for<S, I>
  60 static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
  61 static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotSemiregular>);
  62
  63 // !weakly_incrementable<O>
  64 static_assert(!HasRemoveCopyIfIter<int*, int*, WeaklyIncrementableNotMovable>);
  65
  66 // !indirect_unary_predicate<Pred, projected<I, Proj>>
  67 static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
  68 static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
  69
  70 // !indirectly_copyable<I, O>
  71 static_assert(!HasRemoveCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
  72 static_assert(!HasRemoveCopyIfIter<const int*, const int*, const int*>);
  73
  74 template < class R, class O = int*, class Pred = AlwaysTrue, class Proj = std::identity>
  75 concept HasRemoveCopyIfRange =
  76     requires(R&& r, O&& out, Pred&& pred, Proj&& proj) {
  77       std::ranges::remove_copy_if(
  78           std::forward<R>(r), std::forward<O>(out), std::forward<Pred>(pred), std::forward<Proj>(proj));
  79     };
  80
  81 template <class T>
  82 using R = UncheckedRange<T>;
  83
  84 static_assert(HasRemoveCopyIfRange<R<int*>>);
  85
  86 // !input_range<R>
  87 static_assert(!HasRemoveCopyIfRange<R<InputIteratorNotDerivedFrom>>);
  88 static_assert(!HasRemoveCopyIfRange<R<cpp20_output_iterator<int*>>>);
  89
  90 // !weakly_incrementable<O>
  91 static_assert(!HasRemoveCopyIfRange<R<int*>, WeaklyIncrementableNotMovable>);
  92
  93 // !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>>
  94 static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotPredicate>);
  95 static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotCopyConstructible>);
  96
  97 // !indirectly_copyable<iterator_t<R>, O>
  98 static_assert(!HasRemoveCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>);
  99 static_assert(!HasRemoveCopyIfRange<R<const int*>, const int*>);
 100
 101 template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2, class Pred>
 102 constexpr void testRemoveCopyIfImpl(std::array<int, N1> in, std::array<int, N2> expected, Pred pred) {
 103   using Sent = SentWrapper<InIter>;
 104   using Result = std::ranges::remove_copy_if_result<InIter, OutIter>;
 105
 106   // iterator overload
 107   {
 108     std::array<int, N2> out;
 109     std::same_as<Result> decltype(auto) result =
 110         std::ranges::remove_copy_if(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()}, pred);
 111     assert(std::ranges::equal(out, expected));
 112     assert(base(result.in) == in.data() + in.size());
 113     assert(base(result.out) == out.data() + out.size());
 114   }
 115
 116   // range overload
 117   {
 118     std::array<int, N2> out;
 119     std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};
 120     std::same_as<Result> decltype(auto) result =
 121         std::ranges::remove_copy_if(r, OutIter{out.data()}, pred);
 122     assert(std::ranges::equal(out, expected));
 123     assert(base(result.in) == in.data() + in.size());
 124     assert(base(result.out) == out.data() + out.size());
 125   }
 126 }
 127
 128 template <class InIter, class OutIter, template <class> class SentWrapper>
 129 constexpr void testImpl() {
 130   // remove multiple elements
 131   {
 132     std::array in{1, 2, 3, 2, 1};
 133     std::array expected{1, 3, 1};
 134     auto pred = [](int i) { return i == 2; };
 135     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 136   }
 137
 138   // remove single elements
 139   {
 140     std::array in{1, 2, 3, 2, 1};
 141     std::array expected{1, 2, 2, 1};
 142     auto pred = [](int i) { return i == 3; };
 143     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 144   }
 145
 146   // nothing removed
 147   {
 148     std::array in{1, 2, 3, 2, 1};
 149     std::array expected{1, 2, 3, 2, 1};
 150     auto pred = [](int) { return false; };
 151     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 152   }
 153
 154   // all removed
 155   {
 156     std::array in{1, 2, 3, 2, 1};
 157     std::array<int, 0> expected{};
 158     auto pred = [](int) { return true; };
 159     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 160   }
 161
 162   // remove first
 163   {
 164     std::array in{1, 2, 3, 2};
 165     std::array expected{2, 3, 2};
 166     auto pred = [](int i) { return i < 2; };
 167     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 168   }
 169
 170   // remove last
 171   {
 172     std::array in{1, 2, 3, 2, 5};
 173     std::array expected{1, 2, 3, 2};
 174     auto pred = [](int i) { return i > 3; };
 175     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 176   }
 177
 178   // stable
 179   {
 180     std::array in{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 181     std::array expected{6, 7, 8, 9, 10};
 182     auto pred = [](int i) { return i < 6; };
 183     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 184   }
 185
 186   // empty range
 187   {
 188     std::array<int, 0> in{};
 189     std::array<int, 0> expected{};
 190     auto pred = [](int) { return false; };
 191     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 192   }
 193
 194   // one element range
 195   {
 196     std::array in{1};
 197     std::array<int, 0> expected{};
 198     auto pred = [](int i) { return i == 1; };
 199     testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
 200   }
 201 }
 202
 203 template <class OutIter, template <class> class SentWrapper>
 204 constexpr void withAllPermutationsOfInIter() {
 205   testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>();
 206   testImpl<forward_iterator<int*>, OutIter, SentWrapper>();
 207   testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>();
 208   testImpl<random_access_iterator<int*>, OutIter, SentWrapper>();
 209   testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>();
 210   testImpl<int*, OutIter, SentWrapper>();
 211 }
 212
 213 template <template <class> class SentWrapper>
 214 constexpr void withAllPermutationsOfInIterOutIter() {
 215   withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
 216   withAllPermutationsOfInIter<int*, SentWrapper>();
 217 }
 218
 219 constexpr bool test() {
 220   withAllPermutationsOfInIterOutIter<std::type_identity_t>();
 221   withAllPermutationsOfInIterOutIter<sentinel_wrapper>();
 222
 223   // Test custom projection
 224   {
 225     struct Data {
 226       int data;
 227     };
 228
 229     std::array in{Data{4}, Data{8}, Data{12}, Data{12}};
 230     std::array expected{Data{4}, Data{12}, Data{12}};
 231
 232     const auto proj = &Data::data;
 233     const auto pred = [](int i) { return i == 8; };
 234
 235     const auto equals = [](const Data& x, const Data& y) { return x.data == y.data; };
 236     // iterator overload
 237     {
 238       std::array<Data, 3> out;
 239       auto result = std::ranges::remove_copy_if(in.begin(), in.end(), out.begin(), pred, proj);
 240       assert(std::ranges::equal(out, expected, equals));
 241       assert(result.in == in.end());
 242       assert(result.out == out.end());
 243     }
 244
 245     // range overload
 246     {
 247       std::array<Data, 3> out;
 248       auto result = std::ranges::remove_copy_if(in, out.begin(), pred, proj);
 249       assert(std::ranges::equal(out, expected, equals));
 250       assert(result.in == in.end());
 251       assert(result.out == out.end());
 252     }
 253   }
 254
 255   // Complexity: Exactly last - first applications of the corresponding predicate and any projection.
 256   {
 257     std::array in{4, 4, 5, 6};
 258     std::array expected{5, 6};
 259
 260     const auto pred = [](int i) { return i == 4; };
 261
 262     // iterator overload
 263     {
 264       int numberOfPred = 0;
 265       int numberOfProj = 0;
 266       std::array<int, 2> out;
 267       std::ranges::remove_copy_if(
 268           in.begin(), in.end(), out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj));
 269
 270       assert(numberOfPred == static_cast<int>(in.size()));
 271       assert(numberOfProj == static_cast<int>(in.size()));
 272
 273       assert(std::ranges::equal(out, expected));
 274     }
 275
 276     // range overload
 277     {
 278       int numberOfPred = 0;
 279       int numberOfProj = 0;
 280       std::array<int, 2> out;
 281       std::ranges::remove_copy_if(
 282           in, out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj));
 283       assert(numberOfPred == static_cast<int>(in.size()));
 284       assert(numberOfProj == static_cast<int>(in.size()));
 285       assert(std::ranges::equal(out, expected));
 286     }
 287   }
 288
 289   return true;
 290 }
 291
 292 int main(int, char**) {
 293   test();
 294   static_assert(test());
 295
 296   return 0;
 297 }