diff options
author | Nikolas Klauser <nikolasklauser@berlin.de> | 2022-08-02 22:25:00 -0700 |
---|---|---|
committer | Tom Stellard <tstellar@redhat.com> | 2022-08-05 01:04:08 -0700 |
commit | 40c79a4d5180273c9cc265adf715d225a9cc7d33 (patch) | |
tree | 3055079c41bb418da7772d5dfd83fbc5dc7903ee | |
parent | e38e97d804e64507fcc0a123038fceb4aab5590c (diff) |
[libc++][ranges] Implement `ranges::replace_copy{,_if}`.
Co-authored-by: Konstantin Varlamov <varconst@apple.com>
Differential Revision: https://reviews.llvm.org/D129806
(cherry picked from commit 93172c1c2b10066628c85c9ff78eb882222fb304)
15 files changed, 569 insertions, 90 deletions
diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 4299410089df..131f698ee859 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -51,8 +51,8 @@ Write,remove_copy,Nikolas Klauser,`D130599 <https://llvm.org/D130599>`_,✅ Write,remove_copy_if,Nikolas Klauser,`D130599 <https://llvm.org/D130599>`_,✅ Write,replace,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅ Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅ -Write,replace_copy,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review -Write,replace_copy_if,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review +Write,replace_copy,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,✅ +Write,replace_copy_if,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,✅ Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅ Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅ Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅ diff --git a/libcxx/include/__algorithm/ranges_replace_copy.h b/libcxx/include/__algorithm/ranges_replace_copy.h index 19ef635d6f15..7d59dbe7dbed 100644 --- a/libcxx/include/__algorithm/ranges_replace_copy.h +++ b/libcxx/include/__algorithm/ranges_replace_copy.h @@ -10,19 +10,16 @@ #define _LIBCPP___ALGORITHM_RANGES_REPLACE_COPY_H #include <__algorithm/in_out_result.h> -#include <__algorithm/make_projected.h> -#include <__algorithm/replace_copy.h> +#include <__algorithm/ranges_replace_copy_if.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> #include <__functional/ranges_operations.h> #include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> #include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> -#include <__utility/forward.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -40,35 +37,45 @@ using replace_copy_result = in_out_result<_InIter, _OutIter>; namespace __replace_copy { -struct __fn { - - template <input_iterator _InIter, sentinel_for<_InIter> _Sent, class _Type1, class _Type2, - output_iterator<const _Type2&> _OutIter, class _Proj = identity> - requires indirectly_copyable<_InIter, _OutIter> && - indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type1*> - _LIBCPP_HIDE_FROM_ABI constexpr - replace_copy_result<_InIter, _OutIter> - operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type1& __old_value, const _Type2& __new_value, + struct __fn { + template <input_iterator _InIter, + sentinel_for<_InIter> _Sent, + class _OldType, + class _NewType, + output_iterator<const _NewType&> _OutIter, + class _Proj = identity> + requires indirectly_copyable<_InIter, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _OldType*> + _LIBCPP_HIDE_FROM_ABI constexpr replace_copy_result<_InIter, _OutIter> + operator()(_InIter __first, + _Sent __last, + _OutIter __result, + const _OldType& __old_value, + const _NewType& __new_value, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__old_value; (void)__new_value; (void)__proj; - return {}; - } - - template <input_range _Range, class _Type1, class _Type2, output_iterator<const _Type2&> _OutIter, - class _Proj = identity> - requires indirectly_copyable<iterator_t<_Range>, _OutIter> && - indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type1*> - _LIBCPP_HIDE_FROM_ABI constexpr - replace_copy_result<borrowed_iterator_t<_Range>, _OutIter> - operator()(_Range&& __range, _OutIter __result, const _Type1& __old_value, const _Type2& __new_value, + auto __pred = [&](const auto& __value) { return __value == __old_value; }; + return ranges::__replace_copy_if_impl( + std::move(__first), std::move(__last), std::move(__result), __pred, __new_value, __proj); + } + + template <input_range _Range, + class _OldType, + class _NewType, + output_iterator<const _NewType&> _OutIter, + class _Proj = identity> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _OldType*> + _LIBCPP_HIDE_FROM_ABI constexpr replace_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, + _OutIter __result, + const _OldType& __old_value, + const _NewType& __new_value, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__old_value; (void)__new_value; (void)__proj; - return {}; - } - -}; + auto __pred = [&](const auto& __value) { return __value == __old_value; }; + return ranges::__replace_copy_if_impl( + ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __new_value, __proj); + } + }; } // namespace __replace_copy diff --git a/libcxx/include/__algorithm/ranges_replace_copy_if.h b/libcxx/include/__algorithm/ranges_replace_copy_if.h index 2a908e2057af..7602e8a14487 100644 --- a/libcxx/include/__algorithm/ranges_replace_copy_if.h +++ b/libcxx/include/__algorithm/ranges_replace_copy_if.h @@ -10,19 +10,14 @@ #define _LIBCPP___ALGORITHM_RANGES_REPLACE_COPY_IF_H #include <__algorithm/in_out_result.h> -#include <__algorithm/make_projected.h> -#include <__algorithm/replace_copy_if.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> -#include <__functional/ranges_operations.h> #include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> #include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> -#include <__utility/forward.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -38,34 +33,51 @@ namespace ranges { template <class _InIter, class _OutIter> using replace_copy_if_result = in_out_result<_InIter, _OutIter>; -namespace __replace_copy_if { - -struct __fn { - - template <input_iterator _InIter, sentinel_for<_InIter> _Sent, class _Type, output_iterator<const _Type&> _OutIter, - class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> - requires indirectly_copyable<_InIter, _OutIter> - _LIBCPP_HIDE_FROM_ABI constexpr - replace_copy_if_result<_InIter, _OutIter> - operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, const _Type& __new_value, - _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__pred; (void)__new_value; (void)__proj; - return {}; +template <class _InIter, class _Sent, class _OutIter, class _Pred, class _Type, class _Proj> +_LIBCPP_HIDE_FROM_ABI constexpr replace_copy_if_result<_InIter, _OutIter> __replace_copy_if_impl( + _InIter __first, _Sent __last, _OutIter __result, _Pred& __pred, const _Type& __new_value, _Proj& __proj) { + while (__first != __last) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + *__result = __new_value; + else + *__result = *__first; + + ++__first; + ++__result; } - template <input_range _Range, class _Type, output_iterator<const _Type&> _OutIter, class _Proj = identity, - indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> - requires indirectly_copyable<iterator_t<_Range>, _OutIter> - _LIBCPP_HIDE_FROM_ABI constexpr - replace_copy_if_result<borrowed_iterator_t<_Range>, _OutIter> - operator()(_Range&& __range, _OutIter __result, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__pred; (void)__new_value; (void)__proj; - return {}; - } + return {std::move(__first), std::move(__result)}; +} + +namespace __replace_copy_if { -}; + struct __fn { + template <input_iterator _InIter, + sentinel_for<_InIter> _Sent, + class _Type, + output_iterator<const _Type&> _OutIter, + class _Proj = identity, + indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr replace_copy_if_result<_InIter, _OutIter> operator()( + _InIter __first, _Sent __last, _OutIter __result, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) + const { + return ranges::__replace_copy_if_impl( + std::move(__first), std::move(__last), std::move(__result), __pred, __new_value, __proj); + } + + template <input_range _Range, + class _Type, + output_iterator<const _Type&> _OutIter, + class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const { + return ranges::__replace_copy_if_impl( + ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __new_value, __proj); + } + }; } // namespace __replace_copy_if diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index b4e1b82350f2..0a4077837a99 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -944,6 +944,43 @@ namespace ranges { constexpr remove_copy_if_result<borrowed_iterator_t<R>, O> remove_copy_if(R&& r, O result, Pred pred, Proj proj = {}); // Since C++20 + template<class I, class O> + using replace_copy_result = in_out_result<I, O>; // Since C++20 + + template<input_iterator I, sentinel_for<I> S, class T1, class T2, + output_iterator<const T2&> O, class Proj = identity> + requires indirectly_copyable<I, O> && + indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> + constexpr replace_copy_result<I, O> + replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value, + Proj proj = {}); // Since C++20 + + template<input_range R, class T1, class T2, output_iterator<const T2&> O, + class Proj = identity> + requires indirectly_copyable<iterator_t<R>, O> && + indirect_binary_predicate<ranges::equal_to, + projected<iterator_t<R>, Proj>, const T1*> + constexpr replace_copy_result<borrowed_iterator_t<R>, O> + replace_copy(R&& r, O result, const T1& old_value, const T2& new_value, + Proj proj = {}); // Since C++20 + + template<class I, class O> + using replace_copy_if_result = in_out_result<I, O>; // Since C++20 + + template<input_iterator I, sentinel_for<I> S, class T, output_iterator<const T&> O, + class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> + requires indirectly_copyable<I, O> + constexpr replace_copy_if_result<I, O> + replace_copy_if(I first, S last, O result, Pred pred, const T& new_value, + Proj proj = {}); // Since C++20 + + template<input_range R, class T, output_iterator<const T&> O, class Proj = identity, + indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> + requires indirectly_copyable<iterator_t<R>, O> + constexpr replace_copy_if_result<borrowed_iterator_t<R>, O> + replace_copy_if(R&& r, O result, Pred pred, const T& new_value, + Proj proj = {}); // Since C++20 + } constexpr bool // constexpr in C++20 @@ -1730,6 +1767,8 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/ranges_remove_copy_if.h> #include <__algorithm/ranges_remove_if.h> #include <__algorithm/ranges_replace.h> +#include <__algorithm/ranges_replace_copy.h> +#include <__algorithm/ranges_replace_copy_if.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_reverse_copy.h> diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp index b809db91e42e..3959d48288e2 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -191,8 +191,8 @@ constexpr bool all_the_algorithms() (void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0); - //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0); + (void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0); + (void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0); (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0); (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0); (void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp index 687d4fa18d66..ed6277e9eb86 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -178,10 +178,10 @@ constexpr bool all_the_algorithms() (void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0); (void)std::ranges::remove_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::remove_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::replace_copy(first, last, first2, value, T(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::replace_copy(a, first2, value, T(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::replace_copy(first, last, first2, value, T(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::replace_copy(a, first2, value, T(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::replace_copy_if(a, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0); (void)std::ranges::replace(first, last, value, T(), Proj(&copies)); assert(copies == 0); (void)std::ranges::replace(a, value, T(), Proj(&copies)); assert(copies == 0); (void)std::ranges::replace_if(first, last, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy.pass.cpp index b1a82e394774..511bc118ea03 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy.pass.cpp @@ -26,23 +26,223 @@ // replace_copy(R&& r, O result, const T1& old_value, const T2& new_value, // Proj proj = {}); // Since C++20 -// TODO: synopsis - #include <algorithm> #include <array> #include <concepts> #include <functional> #include <ranges> +#include <utility> #include "almost_satisfies_types.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template <class Iter, class Sent = sentinel_wrapper<Iter>, class OutIter = int*> +concept HasReplaceCopyIter = + requires(Iter&& first, Sent&& last, OutIter&& result) { + std::ranges::replace_copy( + std::forward<Iter>(first), std::forward<Sent>(last), std::forward<OutIter>(result), 0, 0); +}; + +static_assert(HasReplaceCopyIter<int*>); + +// !input_iterator<I> +static_assert(!HasReplaceCopyIter<InputIteratorNotDerivedFrom>); +static_assert(!HasReplaceCopyIter<InputIteratorNotIndirectlyReadable>); +static_assert(!HasReplaceCopyIter<InputIteratorNotInputOrOutputIterator>); + +// !sentinel_for<S, I> +static_assert(!HasReplaceCopyIter<int*, SentinelForNotSemiregular>); +static_assert(!HasReplaceCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>); + +// !output_iterator<O, const T2&> +static_assert(!HasReplaceCopyIter<int*, int*, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasReplaceCopyIter<int*, int*, OutputIteratorNotInputOrOutputIterator>); + +// !indirectly_copyable<I, O> +static_assert(!HasReplaceCopyIter<int*, int*, int**>); + +// !indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> +static_assert(!HasReplaceCopyIter<IndirectBinaryPredicateNotIndirectlyReadable>); + +template <class Range, class OutIter = int*> +concept HasReplaceCopyRange = requires(Range&& range, OutIter&& result) { + std::ranges::replace_copy(std::forward<Range>(range), std::forward<OutIter>(result), 0, 0); +}; + +template <class T> +using R = UncheckedRange<T>; + +static_assert(HasReplaceCopyRange<R<int*>>); + +// !input_range<R> +static_assert(!HasReplaceCopyRange<InputRangeNotDerivedFrom>); +static_assert(!HasReplaceCopyRange<InputRangeNotIndirectlyReadable>); +static_assert(!HasReplaceCopyRange<InputRangeNotInputOrOutputIterator>); +static_assert(!HasReplaceCopyRange<InputRangeNotSentinelSemiregular>); +static_assert(!HasReplaceCopyRange<InputRangeNotSentinelEqualityComparableWith>); + +// !output_iterator<O, const T2&> +static_assert(!HasReplaceCopyRange<R<int*>, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasReplaceCopyRange<R<int*>, OutputIteratorNotInputOrOutputIterator>); + +// !indirectly_copyable<iterator_t<R>, O> +static_assert(!HasReplaceCopyRange<R<int*>, R<int**>>); + +// !indirect_binary_predicate<ranges::equal_to, projected<iterator_t<T>, Proj>, const T1*> +static_assert(!HasReplaceCopyRange<R<IndirectBinaryPredicateNotIndirectlyReadable>>); + +template <int N> +struct Data { + std::array<int, N> input; + int old_value; + int new_value; + std::array<int, N> expected; +}; + +template <class InIter, class Sent, class OutIter, int N> +constexpr void test(Data<N> d) { + { // iterator overload + std::array<int, N> output; + + auto first = InIter(d.input.data()); + auto last = Sent(InIter(d.input.data() + d.input.size())); + auto result = OutIter(output.data()); + + std::same_as<std::ranges::replace_copy_result<InIter, OutIter>> decltype(auto) ret = + std::ranges::replace_copy(std::move(first), std::move(last), std::move(result), d.old_value, d.new_value); + assert(base(ret.in) == d.input.data() + d.input.size()); + assert(base(ret.out) == output.data() + output.size()); + assert(d.expected == output); + } + + { // range overload + std::array<int, N> output; + + auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size()))); + auto result = OutIter(output.data()); + + std::same_as<std::ranges::replace_copy_result<InIter, OutIter>> decltype(auto) ret = + std::ranges::replace_copy(range, result, d.old_value, d.new_value); + assert(base(ret.in) == d.input.data() + d.input.size()); + assert(base(ret.out) == output.data() + output.size()); + assert(d.expected == output); + } +} + +template <class InIter, class Sent, class OutIter> +constexpr void tests() { + // simple test + test<InIter, Sent, OutIter, 4>({.input = {1, 2, 3, 4}, .old_value = 2, .new_value = 5, .expected = {1, 5, 3, 4}}); + // empty range + test<InIter, Sent, OutIter, 0>({.input = {}, .old_value = 2, .new_value = 5, .expected = {}}); + // all elements match + test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .old_value = 1, .new_value = 2, .expected = {2, 2, 2, 2}}); + // no element matches + test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .old_value = 2, .new_value = 3, .expected = {1, 1, 1, 1}}); + // old_value and new_value are identical - match + test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .old_value = 1, .new_value = 1, .expected = {1, 1, 1, 1}}); + // old_value and new_value are identical - no match + test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .old_value = 2, .new_value = 2, .expected = {1, 1, 1, 1}}); + // more elements + test<InIter, Sent, OutIter, 7>( + {.input = {1, 2, 3, 4, 5, 6, 7}, .old_value = 2, .new_value = 3, .expected = {1, 3, 3, 4, 5, 6, 7}}); + // single element - match + test<InIter, Sent, OutIter, 1>({.input = {1}, .old_value = 1, .new_value = 5, .expected = {5}}); + // single element - no match + test<InIter, Sent, OutIter, 1>({.input = {2}, .old_value = 1, .new_value = 5, .expected = {2}}); +} + +template <class InIter, class Sent> +constexpr void test_output_iterators() { + tests<InIter, Sent, cpp17_output_iterator<int*>>(); + tests<InIter, Sent, forward_iterator<int*>>(); + tests<InIter, Sent, bidirectional_iterator<int*>>(); + tests<InIter, Sent, random_access_iterator<int*>>(); + tests<InIter, Sent, contiguous_iterator<int*>>(); + tests<InIter, Sent, int*>(); +} + +template <class InIter> +constexpr void test_sentinels() { + test_output_iterators<InIter, InIter>(); + test_output_iterators<InIter, sentinel_wrapper<InIter>>(); + test_output_iterators<InIter, sized_sentinel<InIter>>(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); + test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); + test_sentinels<forward_iterator<int*>>(); + test_sentinels<bidirectional_iterator<int*>>(); + test_sentinels<random_access_iterator<int*>>(); + test_sentinels<contiguous_iterator<int*>>(); + test_sentinels<int*>(); + test_sentinels<const int*>(); + + { // check that a custom projection works + struct S { + int i; + }; + + { // iterator overload + S a[] = {{1}, {2}, {3}, {4}}; + S b[4]; + auto ret = std::ranges::replace_copy(std::begin(a), std::end(a), std::begin(b), 1, S{2}, &S::i); + assert(ret.in == std::end(a)); + assert(ret.out == std::end(b)); + } + + { // range overload + S a[] = {{1}, {2}, {3}, {4}}; + S b[4]; + auto ret = std::ranges::replace_copy(a, std::begin(b), 1, S{2}, &S::i); + assert(ret.in == std::end(a)); + assert(ret.out == std::end(b)); + } + } + + { // Complexity: exactly `last - first` applications of the corresponding predicate and any projection. + { // iterator overload + int proj_count = 0; + int a[] = {1, 2, 3, 4}; + int b[4]; + std::ranges::replace_copy( + std::begin(a), std::end(a), std::begin(b), 0, 0, counting_projection(proj_count)); + assert(proj_count == 4); + } + + { // range overload + int proj_count = 0; + int a[] = {1, 2, 3, 4}; + int b[4]; + std::ranges::replace_copy(a, std::begin(b), 0, 0, counting_projection(proj_count)); + assert(proj_count == 4); + } + } + + { // using different types for the old and new values works + struct S { + constexpr operator int() const { return 0; } + constexpr bool operator==(const S&) const = default; + constexpr bool operator==(int i) const { return i == 0; } + }; + struct T { + constexpr operator int() const { return 1; } + }; + { + int a[] = {0, 1, 2, 3}; + int b[4]; + std::ranges::replace_copy(std::begin(a), std::end(a), std::begin(b), S{}, T{}); + assert(std::ranges::equal(b, std::array{1, 1, 2, 3})); + } + { + int a[] = {0, 1, 2, 3}; + int b[4]; + std::ranges::replace_copy(a, std::begin(b), S{}, T{}); + assert(std::ranges::equal(b, std::array{1, 1, 2, 3})); + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy_if.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy_if.pass.cpp index d24853884b92..3cbe6da19437 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy_if.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges_replace_copy_if.pass.cpp @@ -30,16 +30,229 @@ #include <concepts> #include <functional> #include <ranges> +#include <utility> #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct FalsePredicate { + constexpr bool operator()(int) { return false; } +}; + +template <class Iter, class Sent = sentinel_wrapper<Iter>, class OutIter = int*> +concept HasReplaceCopyIfIter = requires(Iter&& first, Sent&& last, OutIter&& result) { + std::ranges::replace_copy_if( + std::forward<Iter>(first), std::forward<Sent>(last), std::forward<OutIter>(result), FalsePredicate{}, 0); +}; + +static_assert(HasReplaceCopyIfIter<int*>); + +// !input_iterator<I> +static_assert(!HasReplaceCopyIfIter<InputIteratorNotDerivedFrom>); +static_assert(!HasReplaceCopyIfIter<InputIteratorNotIndirectlyReadable>); +static_assert(!HasReplaceCopyIfIter<InputIteratorNotInputOrOutputIterator>); + +// !sentinel_for<S, I> +static_assert(!HasReplaceCopyIfIter<int*, SentinelForNotSemiregular>); +static_assert(!HasReplaceCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>); + +// !output_iterator<O, const T2&> +static_assert(!HasReplaceCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasReplaceCopyIfIter<int*, int*, OutputIteratorNotInputOrOutputIterator>); + +// !indirect_unary_predicate<Pred, projected<I, Proj>> Pred> +static_assert(!HasReplaceCopyIfIter<IndirectUnaryPredicateNotCopyConstructible>); +static_assert(!HasReplaceCopyIfIter<IndirectUnaryPredicateNotPredicate>); + +// !indirectly_copyable<I, O> +static_assert(!HasReplaceCopyIfIter<int*, int*, int**>); + +template <class Range, class OutIter = int*> +concept HasReplaceCopyIfRange = requires(Range&& range, OutIter&& result) { + std::ranges::replace_copy_if(std::forward<Range>(range), std::forward<OutIter>(result), FalsePredicate{}, 0); +}; + +template <class T> +using R = UncheckedRange<T>; + +static_assert(HasReplaceCopyIfRange<R<int*>>); + +// !input_range<R> +static_assert(!HasReplaceCopyIfRange<InputRangeNotDerivedFrom>); +static_assert(!HasReplaceCopyIfRange<InputRangeNotIndirectlyReadable>); +static_assert(!HasReplaceCopyIfRange<InputRangeNotInputOrOutputIterator>); +static_assert(!HasReplaceCopyIfRange<InputRangeNotSentinelSemiregular>); +static_assert(!HasReplaceCopyIfRange<InputRangeNotSentinelEqualityComparableWith>); + +// !output_iterator<O, const T2&> +static_assert(!HasReplaceCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasReplaceCopyIfRange<R<int*>, OutputIteratorNotInputOrOutputIterator>); + +// !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>> Pred> +static_assert(!HasReplaceCopyIfRange<R<IndirectUnaryPredicateNotPredicate>>); + +// !indirectly_copyable<iterator_t<R>, O> +static_assert(!HasReplaceCopyIfRange<R<int*>, int**>); + +template <int N> +struct Data { + std::array<int, N> input; + int cutoff; + int new_value; + std::array<int, N> expected; +}; + +template <class InIter, class Sent, class OutIter, int N> +constexpr void test(Data<N> d) { + { // iterator overload + std::array<int, N> output; + + auto first = InIter(d.input.data()); + auto last = Sent(InIter(d.input.data() + d.input.size())); + auto result = OutIter(output.data()); + + auto pred = [&](int i) { return i < d.cutoff; }; + + std::same_as<std::ranges::replace_copy_if_result<InIter, OutIter>> decltype(auto) ret = + std::ranges::replace_copy_if(std::move(first), std::move(last), std::move(result), pred, d.new_value); + assert(base(ret.in) == d.input.data() + d.input.size()); + assert(base(ret.out) == output.data() + output.size()); + assert(d.expected == output); + } + + { // range overload + std::array<int, N> output; + + auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size()))); + auto result = OutIter(output.data()); + + auto pred = [&](int i) { return i < d.cutoff; }; + + std::same_as<std::ranges::replace_copy_if_result<InIter, OutIter>> decltype(auto) ret = + std::ranges::replace_copy_if(range, result, pred, d.new_value); + assert(base(ret.in) == d.input.data() + d.input.size()); + assert(base(ret.out) == output.data() + output.size()); + assert(d.expected == output); + } +} + +template <class InIter, class Sent, class OutIter> +constexpr void tests() { + // simple test + test<InIter, Sent, OutIter, 4>({.input = {1, 2, 3, 4}, .cutoff = 2, .new_value = 5, .expected = {5, 2, 3, 4}}); + // empty range + test<InIter, Sent, OutIter, 0>({.input = {}, .cutoff = 2, .new_value = 5, .expected = {}}); + // all elements match + test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .cutoff = 2, .new_value = 2, .expected = {2, 2, 2, 2}}); + // no element matches + test<InIter, Sent, OutIter, 4>({.input = {1, 1, 1, 1}, .cutoff = 1, .new_value = 3, .expected = {1, 1, 1, 1}}); + // more elements + test<InIter, Sent, OutIter, 7>( + {.input = {1, 2, 3, 4, 5, 6, 7}, .cutoff = 3, .new_value = 3, .expected = {3, 3, 3, 4, 5, 6, 7}}); + // single element - match + test<InIter, Sent, OutIter, 1>({.input = {1}, .cutoff = 2, .new_value = 5, .expected = {5}}); + // single element - no match + test<InIter, Sent, OutIter, 1>({.input = {2}, .cutoff = 2, .new_value = 5, .expected = {2}}); +} + +template <class InIter, class Sent> +constexpr void test_output_iterators() { + tests<InIter, Sent, cpp17_output_iterator<int*>>(); + tests<InIter, Sent, forward_iterator<int*>>(); + tests<InIter, Sent, bidirectional_iterator<int*>>(); + tests<InIter, Sent, random_access_iterator<int*>>(); + tests<InIter, Sent, contiguous_iterator<int*>>(); + tests<InIter, Sent, int*>(); +} + +template <class InIter> +constexpr void test_sentinels() { + test_output_iterators<InIter, InIter>(); + test_output_iterators<InIter, sentinel_wrapper<InIter>>(); + test_output_iterators<InIter, sized_sentinel<InIter>>(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); + test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); + test_sentinels<forward_iterator<int*>>(); + test_sentinels<bidirectional_iterator<int*>>(); + test_sentinels<random_access_iterator<int*>>(); + test_sentinels<contiguous_iterator<int*>>(); + test_sentinels<int*>(); + test_sentinels<const int*>(); + + { // check that a custom projection works + struct S { + int i; + }; + + { // iterator overload + S a[] = {{1}, {2}, {3}, {4}}; + S b[4]; + auto ret = std::ranges::replace_copy_if(std::begin(a), std::end(a), std::begin(b), FalsePredicate{}, S{2}, &S::i); + assert(ret.in == std::end(a)); + assert(ret.out == std::end(b)); + assert(std::ranges::equal(a, b, {}, &S::i, &S::i)); + } + + { // range overload + S a[] = {{1}, {2}, {3}, {4}}; + S b[4]; + auto ret = std::ranges::replace_copy_if(a, std::begin(b), FalsePredicate{}, S{2}, &S::i); + assert(ret.in == std::end(a)); + assert(ret.out == std::end(b)); + assert(std::ranges::equal(a, b, {}, &S::i, &S::i)); + } + } + + { // Complexity: exactly `last - first` applications of the corresponding predicate and any projection. + { // iterator overload + int pred_count = 0; + int proj_count = 0; + int a[] = {1, 2, 3, 4}; + int b[4]; + + std::ranges::replace_copy_if( + std::begin(a), std::end(a), std::begin(b), + counting_predicate(FalsePredicate{}, pred_count), 0, counting_projection(proj_count)); + assert(pred_count == 4); + assert(proj_count == 4); + } + + { // range overload + int pred_count = 0; + int proj_count = 0; + int a[] = {1, 2, 3, 4}; + int b[4]; + + std::ranges::replace_copy_if(a, std::begin(b), + counting_predicate(FalsePredicate{}, pred_count), 0, counting_projection(proj_count)); + assert(pred_count == 4); + assert(proj_count == 4); + } + } + + { // using different types for the old and new values works + struct S { + constexpr operator int() const { return 1; } + }; + { + int a[] = {0, 0, 2, 3}; + int b[4]; + std::ranges::replace_copy_if(std::begin(a), std::end(a), std::begin(b), [](int i) { return i < 2; }, S{}); + assert(std::ranges::equal(b, std::array{1, 1, 2, 3})); + } + + { + int a[] = {0, 0, 2, 3}; + int b[4]; + std::ranges::replace_copy_if(a, std::begin(b), [](int i) { return i < 2; }, S{}); + assert(std::ranges::equal(b, std::array{1, 1, 2, 3})); + } + } return true; } diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp index 6a0fa1ac0b03..5c8a1031997a 100644 --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -34,8 +34,8 @@ static_assert(std::is_same_v<in_out_result<int, long>, move_backward_result<int, static_assert(std::is_same_v<in_out_result<int, long>, partial_sort_copy_result<int, long>>); static_assert(std::is_same_v<in_out_result<int, long>, remove_copy_result<int, long>>); static_assert(std::is_same_v<in_out_result<int, long>, remove_copy_if_result<int, long>>); -// static_assert(std::is_same_v<in_out_result<int, long>, replace_copy_result<int, long>>); -// static_assert(std::is_same_v<in_out_result<int, long>, replace_copy_if_result<int, long>>); +static_assert(std::is_same_v<in_out_result<int, long>, replace_copy_result<int, long>>); +static_assert(std::is_same_v<in_out_result<int, long>, replace_copy_if_result<int, long>>); // static_assert(std::is_same_v<in_out_result<int, long>, reverse_copy_result<int, long>>); // static_assert(std::is_same_v<in_out_result<int, long>, rotate_copy_result<int, long>>); static_assert(std::is_same_v<in_out_result<int, long>, set_difference_result<int, long>>); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp index de2ed6920b06..5335b842fc53 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -80,6 +80,8 @@ constexpr bool test_all() { using std::ranges::partition_copy_result; using std::ranges::remove_copy_result; using std::ranges::remove_copy_if_result; + using std::ranges::replace_copy_result; + using std::ranges::replace_copy_if_result; using std::ranges::reverse_copy_result; using std::ranges::rotate_copy_result; using std::ranges::set_difference_result; @@ -148,8 +150,8 @@ constexpr bool test_all() { dangling_1st<remove_copy_if_result<dangling, int*>>(std::ranges::remove_copy_if, in, out, unary_pred); dangling_1st(std::ranges::replace, in, x, x); dangling_1st(std::ranges::replace_if, in, std::identity{}, x); - //dangling_1st(std::ranges::replace_copy, in, out, x, x); - //dangling_1st(std::ranges::replace_copy_if, in, out, x, x); + dangling_1st<replace_copy_result<dangling, int*>>(std::ranges::replace_copy, in, out, x, x); + dangling_1st<replace_copy_if_result<dangling, int*>>(std::ranges::replace_copy_if, in, out, unary_pred, x); dangling_1st<swap_ranges_result<dangling, int*>>(std::ranges::swap_ranges, in, in2); dangling_2nd<swap_ranges_result<int*, dangling>>(std::ranges::swap_ranges, in, in2); dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp index 37d454ca4979..9ad1273880e1 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp @@ -114,7 +114,7 @@ constexpr bool test_all() { test(std::ranges::copy_if, in, out, unary_pred); test(std::ranges::remove_copy_if, in, out, unary_pred); test(std::ranges::replace_if, in, unary_pred, x); - //test(std::ranges::replace_copy_if, in, out, unary_pred, x); + test(std::ranges::replace_copy_if, in, out, unary_pred, x); test(std::ranges::unique_copy, in, out, binary_pred); test(std::ranges::partition_copy, in, out, out2, unary_pred); test(std::ranges::partial_sort_copy, in, in2, binary_pred); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp index 120c0bc7e225..12d764aaf6d0 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -134,8 +134,8 @@ constexpr bool test_all() { // `replace*` algorithms only use the projection to compare the elements, not to write them. test(std::ranges::replace, in, x, a, &Bar::val); test(std::ranges::replace_if, in, &Foo::unary_pred, a, &Bar::val); - //test(std::ranges::replace_copy, in, out, x, a, &Bar::val); - //test(std::ranges::replace_copy_if, in, out, pred, a, &Bar::val); + test(std::ranges::replace_copy, in, out, x, a, &Bar::val); + test(std::ranges::replace_copy_if, in, out, &Foo::unary_pred, a, &Bar::val); // `swap_ranges` has neither a projection nor a predicate. // `reverse_copy` has neither a projection nor a predicate. // `rotate_copy` has neither a projection nor a predicate. diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp index 332a562ff366..b5dd483d6f71 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -128,8 +128,8 @@ constexpr void run_tests() { test(std::ranges::remove_copy_if, in, out, unary_pred); test(std::ranges::replace, in, x, x); test(std::ranges::replace_if, in, unary_pred, x); - //test(std::ranges::replace_copy, in, out, x, x); - //test(std::ranges::replace_copy_if, in, out, unary_pred, x); + test(std::ranges::replace_copy, in, out, x, x); + test(std::ranges::replace_copy_if, in, out, unary_pred, x); } test(std::ranges::swap_ranges, in, in2); if constexpr (std::copyable<T>) { diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp index 0f8272896db8..6e0ab4495f7d 100644 --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -123,8 +123,8 @@ static_assert(test(std::ranges::remove_copy, a, a, 42)); static_assert(test(std::ranges::remove_copy_if, a, a, odd)); static_assert(test(std::ranges::remove_if, a, odd)); static_assert(test(std::ranges::replace, a, 42, 43)); -//static_assert(test(std::ranges::replace_copy, a, a, 42, 43)); -//static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43)); +static_assert(test(std::ranges::replace_copy, a, a, 42, 43)); +static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43)); static_assert(test(std::ranges::replace_if, a, odd, 43)); static_assert(test(std::ranges::reverse, a)); static_assert(test(std::ranges::reverse_copy, a, a)); diff --git a/libcxx/test/support/counting_predicates.h b/libcxx/test/support/counting_predicates.h index 3f86bf2a3993..ef3c293109a9 100644 --- a/libcxx/test/support/counting_predicates.h +++ b/libcxx/test/support/counting_predicates.h @@ -63,6 +63,12 @@ public: constexpr counting_predicate(Predicate pred, int& count) : pred_(std::move(pred)), count_(&count) {} template <class... Args> + constexpr decltype(auto) operator()(Args&& ...args) { + ++(*count_); + return pred_(std::forward<Args>(args)...); + } + + template <class... Args> constexpr decltype(auto) operator()(Args&& ...args) const { ++(*count_); return pred_(std::forward<Args>(args)...); |