255 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// 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++2018//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++2027 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 39template <class Iter, class Sent = sentinel_wrapper<Iter>, class OutIter = int*>40concept 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 46static_assert(HasReplaceCopyIter<int*>);47 48// !input_iterator<I>49static_assert(!HasReplaceCopyIter<InputIteratorNotDerivedFrom>);50static_assert(!HasReplaceCopyIter<InputIteratorNotIndirectlyReadable>);51static_assert(!HasReplaceCopyIter<InputIteratorNotInputOrOutputIterator>);52 53// !sentinel_for<S, I>54static_assert(!HasReplaceCopyIter<int*, SentinelForNotSemiregular>);55static_assert(!HasReplaceCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);56 57// !output_iterator<O, const T2&>58static_assert(!HasReplaceCopyIter<int*, int*, OutputIteratorNotIndirectlyWritable>);59static_assert(!HasReplaceCopyIter<int*, int*, OutputIteratorNotInputOrOutputIterator>);60 61// !indirectly_copyable<I, O>62static_assert(!HasReplaceCopyIter<int*, int*, int**>);63 64// !indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>65static_assert(!HasReplaceCopyIter<IndirectBinaryPredicateNotIndirectlyReadable>);66 67template <class Range, class OutIter = int*>68concept HasReplaceCopyRange = requires(Range&& range, OutIter&& result) {69 std::ranges::replace_copy(std::forward<Range>(range), std::forward<OutIter>(result), 0, 0);70};71 72template <class T>73using R = UncheckedRange<T>;74 75static_assert(HasReplaceCopyRange<R<int*>>);76 77// !input_range<R>78static_assert(!HasReplaceCopyRange<InputRangeNotDerivedFrom>);79static_assert(!HasReplaceCopyRange<InputRangeNotIndirectlyReadable>);80static_assert(!HasReplaceCopyRange<InputRangeNotInputOrOutputIterator>);81static_assert(!HasReplaceCopyRange<InputRangeNotSentinelSemiregular>);82static_assert(!HasReplaceCopyRange<InputRangeNotSentinelEqualityComparableWith>);83 84// !output_iterator<O, const T2&>85static_assert(!HasReplaceCopyRange<R<int*>, OutputIteratorNotIndirectlyWritable>);86static_assert(!HasReplaceCopyRange<R<int*>, OutputIteratorNotInputOrOutputIterator>);87 88// !indirectly_copyable<iterator_t<R>, O>89static_assert(!HasReplaceCopyRange<R<int*>, R<int**>>);90 91// !indirect_binary_predicate<ranges::equal_to, projected<iterator_t<T>, Proj>, const T1*>92static_assert(!HasReplaceCopyRange<R<IndirectBinaryPredicateNotIndirectlyReadable>>);93 94template <int N>95struct Data {96 std::array<int, N> input;97 int old_value;98 int new_value;99 std::array<int, N> expected;100};101 102template <class InIter, class Sent, class OutIter, int N>103constexpr void test(Data<N> d) {104 { // iterator overload105 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 overload119 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 132template <class InIter, class Sent, class OutIter>133constexpr void tests() {134 // simple test135 test<InIter, Sent, OutIter, 4>({.input = {1, 2, 3, 4}, .old_value = 2, .new_value = 5, .expected = {1, 5, 3, 4}});136 // empty range137 test<InIter, Sent, OutIter, 0>({.input = {}, .old_value = 2, .new_value = 5, .expected = {}});138 // all elements match139 test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .old_value = 1, .new_value = 2, .expected = {2, 2, 2, 2}});140 // no element matches141 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 - match143 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 match145 test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .old_value = 2, .new_value = 2, .expected = {1, 1, 1, 1}});146 // more elements147 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 - match150 test<InIter, Sent, OutIter, 1>({.input = {1}, .old_value = 1, .new_value = 5, .expected = {5}});151 // single element - no match152 test<InIter, Sent, OutIter, 1>({.input = {2}, .old_value = 1, .new_value = 5, .expected = {2}});153}154 155template <class InIter, class Sent>156constexpr 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 165template <class InIter>166constexpr 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 172constexpr 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 works183 struct S {184 int i;185 };186 187 { // iterator overload188 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 overload196 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 overload206 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 overload215 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 works224 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 249int main(int, char**) {250 test();251 static_assert(test());252 253 return 0;254}255