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