libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_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, class T, output_iterator<const T&> O,
  14 //          class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
  15 //   requires indirectly_copyable<I, O>
  16 //   constexpr replace_copy_if_result<I, O>
  17 //     replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
  18 //                     Proj proj = {});                                                             // Since C++20
  19 //
  20 // template<input_range R, class T, output_iterator<const T&> O, class Proj = identity,
  21 //          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  22 //   requires indirectly_copyable<iterator_t<R>, O>
  23 //   constexpr replace_copy_if_result<borrowed_iterator_t<R>, O>
  24 //     replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
  25 //                     Proj proj = {});                                                             // Since C++20
  26
  27 #include <algorithm>
  28 #include <array>
  29 #include <concepts>
  30 #include <functional>
  31 #include <ranges>
  32 #include <utility>
  33
  34 #include "almost_satisfies_types.h"
  35 #include "counting_predicates.h"
  36 #include "counting_projection.h"
  37 #include "test_iterators.h"
  38
  39 struct FalsePredicate {
  40   constexpr bool operator()(int) { return false; }
  41 };
  42
  43 template <class Iter, class Sent = sentinel_wrapper<Iter>, class OutIter = int*>
  44 concept HasReplaceCopyIfIter = requires(Iter&& first, Sent&& last, OutIter&& result) {
  45   std::ranges::replace_copy_if(
  46       std::forward<Iter>(first), std::forward<Sent>(last), std::forward<OutIter>(result), FalsePredicate{}, 0);
  47 };
  48
  49 static_assert(HasReplaceCopyIfIter<int*>);
  50
  51 // !input_iterator<I>
  52 static_assert(!HasReplaceCopyIfIter<InputIteratorNotDerivedFrom>);
  53 static_assert(!HasReplaceCopyIfIter<InputIteratorNotIndirectlyReadable>);
  54 static_assert(!HasReplaceCopyIfIter<InputIteratorNotInputOrOutputIterator>);
  55
  56 // !sentinel_for<S, I>
  57 static_assert(!HasReplaceCopyIfIter<int*, SentinelForNotSemiregular>);
  58 static_assert(!HasReplaceCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
  59
  60 // !output_iterator<O, const T2&>
  61 static_assert(!HasReplaceCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
  62 static_assert(!HasReplaceCopyIfIter<int*, int*, OutputIteratorNotInputOrOutputIterator>);
  63
  64 // !indirect_unary_predicate<Pred, projected<I, Proj>> Pred>
  65 static_assert(!HasReplaceCopyIfIter<IndirectUnaryPredicateNotCopyConstructible>);
  66 static_assert(!HasReplaceCopyIfIter<IndirectUnaryPredicateNotPredicate>);
  67
  68 // !indirectly_copyable<I, O>
  69 static_assert(!HasReplaceCopyIfIter<int*, int*, int**>);
  70
  71 template <class Range, class OutIter = int*>
  72 concept HasReplaceCopyIfRange = requires(Range&& range, OutIter&& result) {
  73   std::ranges::replace_copy_if(std::forward<Range>(range), std::forward<OutIter>(result), FalsePredicate{}, 0);
  74 };
  75
  76 template <class T>
  77 using R = UncheckedRange<T>;
  78
  79 static_assert(HasReplaceCopyIfRange<R<int*>>);
  80
  81 // !input_range<R>
  82 static_assert(!HasReplaceCopyIfRange<InputRangeNotDerivedFrom>);
  83 static_assert(!HasReplaceCopyIfRange<InputRangeNotIndirectlyReadable>);
  84 static_assert(!HasReplaceCopyIfRange<InputRangeNotInputOrOutputIterator>);
  85 static_assert(!HasReplaceCopyIfRange<InputRangeNotSentinelSemiregular>);
  86 static_assert(!HasReplaceCopyIfRange<InputRangeNotSentinelEqualityComparableWith>);
  87
  88 // !output_iterator<O, const T2&>
  89 static_assert(!HasReplaceCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>);
  90 static_assert(!HasReplaceCopyIfRange<R<int*>, OutputIteratorNotInputOrOutputIterator>);
  91
  92 // !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>> Pred>
  93 static_assert(!HasReplaceCopyIfRange<R<IndirectUnaryPredicateNotPredicate>>);
  94
  95 // !indirectly_copyable<iterator_t<R>, O>
  96 static_assert(!HasReplaceCopyIfRange<R<int*>, int**>);
  97
  98 template <int N>
  99 struct Data {
 100   std::array<int, N> input;
 101   int cutoff;
 102   int new_value;
 103   std::array<int, N> expected;
 104 };
 105
 106 template <class InIter, class Sent, class OutIter, int N>
 107 constexpr void test(Data<N> d) {
 108   { // iterator overload
 109     std::array<int, N> output;
 110
 111     auto first  = InIter(d.input.data());
 112     auto last   = Sent(InIter(d.input.data() + d.input.size()));
 113     auto result = OutIter(output.data());
 114
 115     auto pred = [&](int i) { return i < d.cutoff; };
 116
 117     std::same_as<std::ranges::replace_copy_if_result<InIter, OutIter>> decltype(auto) ret =
 118         std::ranges::replace_copy_if(std::move(first), std::move(last), std::move(result), pred, d.new_value);
 119     assert(base(ret.in) == d.input.data() + d.input.size());
 120     assert(base(ret.out) == output.data() + output.size());
 121     assert(d.expected == output);
 122   }
 123
 124   { // range overload
 125     std::array<int, N> output;
 126
 127     auto range  = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())));
 128     auto result = OutIter(output.data());
 129
 130     auto pred = [&](int i) { return i < d.cutoff; };
 131
 132     std::same_as<std::ranges::replace_copy_if_result<InIter, OutIter>> decltype(auto) ret =
 133         std::ranges::replace_copy_if(range, result, pred, d.new_value);
 134     assert(base(ret.in) == d.input.data() + d.input.size());
 135     assert(base(ret.out) == output.data() + output.size());
 136     assert(d.expected == output);
 137   }
 138 }
 139
 140 template <class InIter, class Sent, class OutIter>
 141 constexpr void tests() {
 142   // simple test
 143   test<InIter, Sent, OutIter, 4>({.input = {1, 2, 3, 4}, .cutoff = 2, .new_value = 5, .expected = {5, 2, 3, 4}});
 144   // empty range
 145   test<InIter, Sent, OutIter, 0>({.input = {}, .cutoff = 2, .new_value = 5, .expected = {}});
 146   // all elements match
 147   test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .cutoff = 2, .new_value = 2, .expected = {2, 2, 2, 2}});
 148   // no element matches
 149   test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .cutoff = 1, .new_value = 3, .expected = {1, 1, 1, 1}});
 150   // more elements
 151   test<InIter, Sent, OutIter, 7>(
 152       {.input = {1, 2, 3, 4, 5, 6, 7}, .cutoff = 3, .new_value = 3, .expected = {3, 3, 3, 4, 5, 6, 7}});
 153   // single element - match
 154   test<InIter, Sent, OutIter, 1>({.input = {1}, .cutoff = 2, .new_value = 5, .expected = {5}});
 155   // single element - no match
 156   test<InIter, Sent, OutIter, 1>({.input = {2}, .cutoff = 2, .new_value = 5, .expected = {2}});
 157 }
 158
 159 template <class InIter, class Sent>
 160 constexpr void test_output_iterators() {
 161   tests<InIter, Sent, cpp17_output_iterator<int*>>();
 162   tests<InIter, Sent, forward_iterator<int*>>();
 163   tests<InIter, Sent, bidirectional_iterator<int*>>();
 164   tests<InIter, Sent, random_access_iterator<int*>>();
 165   tests<InIter, Sent, contiguous_iterator<int*>>();
 166   tests<InIter, Sent, int*>();
 167 }
 168
 169 template <class InIter>
 170 constexpr void test_sentinels() {
 171   test_output_iterators<InIter, InIter>();
 172   test_output_iterators<InIter, sentinel_wrapper<InIter>>();
 173   test_output_iterators<InIter, sized_sentinel<InIter>>();
 174 }
 175
 176 constexpr bool test() {
 177   test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
 178   test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
 179   test_sentinels<forward_iterator<int*>>();
 180   test_sentinels<bidirectional_iterator<int*>>();
 181   test_sentinels<random_access_iterator<int*>>();
 182   test_sentinels<contiguous_iterator<int*>>();
 183   test_sentinels<int*>();
 184   test_sentinels<const int*>();
 185
 186   { // check that a custom projection works
 187     struct S {
 188       int i;
 189     };
 190
 191     { // iterator overload
 192       S a[] = {{1}, {2}, {3}, {4}};
 193       S b[4];
 194       auto ret = std::ranges::replace_copy_if(std::begin(a), std::end(a), std::begin(b), FalsePredicate{}, S{2}, &S::i);
 195       assert(ret.in == std::end(a));
 196       assert(ret.out == std::end(b));
 197       assert(std::ranges::equal(a, b, {}, &S::i, &S::i));
 198     }
 199
 200     { // range overload
 201       S a[] = {{1}, {2}, {3}, {4}};
 202       S b[4];
 203       auto ret = std::ranges::replace_copy_if(a, std::begin(b), FalsePredicate{}, S{2}, &S::i);
 204       assert(ret.in == std::end(a));
 205       assert(ret.out == std::end(b));
 206       assert(std::ranges::equal(a, b, {}, &S::i, &S::i));
 207     }
 208   }
 209
 210   {   // Complexity: exactly `last - first` applications of the corresponding predicate and any projection.
 211     { // iterator overload
 212       int pred_count = 0;
 213       int proj_count = 0;
 214       int a[] = {1, 2, 3, 4};
 215       int b[4];
 216
 217       std::ranges::replace_copy_if(
 218           std::begin(a), std::end(a), std::begin(b),
 219           counting_predicate(FalsePredicate{}, pred_count), 0, counting_projection(proj_count));
 220       assert(pred_count == 4);
 221       assert(proj_count == 4);
 222     }
 223
 224     { // range overload
 225       int pred_count = 0;
 226       int proj_count = 0;
 227       int a[] = {1, 2, 3, 4};
 228       int b[4];
 229
 230       std::ranges::replace_copy_if(a, std::begin(b),
 231           counting_predicate(FalsePredicate{}, pred_count), 0, counting_projection(proj_count));
 232       assert(pred_count == 4);
 233       assert(proj_count == 4);
 234     }
 235   }
 236
 237   { // using different types for the old and new values works
 238     struct S {
 239       constexpr operator int() const { return 1; }
 240     };
 241     {
 242       int a[] = {0, 0, 2, 3};
 243       int b[4];
 244       std::ranges::replace_copy_if(std::begin(a), std::end(a), std::begin(b), [](int i) { return i < 2; }, S{});
 245       assert(std::ranges::equal(b, std::array{1, 1, 2, 3}));
 246     }
 247
 248     {
 249       int a[] = {0, 0, 2, 3};
 250       int b[4];
 251       std::ranges::replace_copy_if(a, std::begin(b), [](int i) { return i < 2; }, S{});
 252       assert(std::ranges::equal(b, std::array{1, 1, 2, 3}));
 253     }
 254   }
 255
 256   return true;
 257 }
 258
 259 int main(int, char**) {
 260   test();
 261   static_assert(test());
 262
 263   return 0;
 264 }