diff options
author | Nikolas Klauser <nikolasklauser@berlin.de> | 2022-08-02 22:13:59 -0700 |
---|---|---|
committer | Tom Stellard <tstellar@redhat.com> | 2022-08-05 01:04:08 -0700 |
commit | 33a5980f2f332e748c86c2a03757e078e967407b (patch) | |
tree | c03f4033b85128174b4be65501f3fada275cc2e1 | |
parent | b0eab153405eaa29653f86ff13fa1832e0fbf991 (diff) |
[libc++][ranges] Implement `ranges::remove_copy{, _if}`.
Co-authored-by: Hui Xie <hui.xie1990@gmail.com>
Differential Revision: https://reviews.llvm.org/D130599
(cherry picked from commit 760d2b462c04537d119d76d3cc37d2cb53774a05)
15 files changed, 578 insertions, 84 deletions
diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 4251b12463ac..4299410089df 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -47,8 +47,8 @@ Write,fill_n,Nikolas Klauser,`D123462 <https://llvm.org/D123462>`_,✅ Write,transform,Nikolas Klauser,`D122173 <https://llvm.org/D122173>`_,✅ Write,generate,Konstantin Varlamov,`D130552 <https://llvm.org/D130552>`_,✅ Write,generate_n,Konstantin Varlamov,`D130552 <https://llvm.org/D130552>`_,✅ -Write,remove_copy,Nikolas Klauser,n/a,Not started -Write,remove_copy_if,Nikolas Klauser,n/a,Not started +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 diff --git a/libcxx/include/__algorithm/ranges_remove_copy.h b/libcxx/include/__algorithm/ranges_remove_copy.h index 16e9009e7ef0..a8144ce0ecbf 100644 --- a/libcxx/include/__algorithm/ranges_remove_copy.h +++ b/libcxx/include/__algorithm/ranges_remove_copy.h @@ -10,19 +10,16 @@ #define _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_H #include <__algorithm/in_out_result.h> -#include <__algorithm/make_projected.h> -#include <__algorithm/remove_copy.h> +#include <__algorithm/ranges_remove_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,32 +37,30 @@ using remove_copy_result = in_out_result<_InIter, _OutIter>; namespace __remove_copy { -struct __fn { - - template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, class _Type, - class _Proj = identity> - requires indirectly_copyable<_InIter, _OutIter> && - indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type*> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_result<_InIter, _OutIter> - operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__value; (void)__proj; - return {}; - } - - template <input_range _Range, weakly_incrementable _OutIter, class _Type, class _Proj = identity> - requires indirectly_copyable<iterator_t<_Range>, _OutIter> && - indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_result<borrowed_iterator_t<_Range>, _OutIter> - operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__value; (void)__proj; - return {}; - } - -}; + struct __fn { + template <input_iterator _InIter, + sentinel_for<_InIter> _Sent, + weakly_incrementable _OutIter, + class _Type, + class _Proj = identity> + requires indirectly_copyable<_InIter, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __val) { return __value == __val; }; + return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj); + } + + template <input_range _Range, weakly_incrementable _OutIter, class _Type, class _Proj = identity> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __val) { return __value == __val; }; + return ranges::__remove_copy_if_impl( + ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj); + } + }; } // namespace __remove_copy diff --git a/libcxx/include/__algorithm/ranges_remove_copy_if.h b/libcxx/include/__algorithm/ranges_remove_copy_if.h index 4eafe425b8e3..3f56693fa1f2 100644 --- a/libcxx/include/__algorithm/ranges_remove_copy_if.h +++ b/libcxx/include/__algorithm/ranges_remove_copy_if.h @@ -38,33 +38,43 @@ namespace ranges { template <class _InIter, class _OutIter> using remove_copy_if_result = in_out_result<_InIter, _OutIter>; -namespace __remove_copy_if { - -struct __fn { - - template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, - class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> - requires indirectly_copyable<_InIter, _OutIter> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_if_result<_InIter, _OutIter> - operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__pred; (void)__proj; - return {}; +template <class _InIter, class _Sent, class _OutIter, class _Proj, class _Pred> +_LIBCPP_HIDE_FROM_ABI constexpr in_out_result<_InIter, _OutIter> +__remove_copy_if_impl(_InIter __first, _Sent __last, _OutIter __result, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (!std::invoke(__pred, std::invoke(__proj, *__first))) { + *__result = *__first; + ++__result; + } } + return {std::move(__first), std::move(__result)}; +} - template <input_range _Range, weakly_incrementable _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 - remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter> - operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__pred; (void)__proj; - return {}; - } +namespace __remove_copy_if { -}; + struct __fn { + template <input_iterator _InIter, + sentinel_for<_InIter> _Sent, + weakly_incrementable _OutIter, + class _Proj = identity, + indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_if_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj); + } + + template <input_range _Range, + weakly_incrementable _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 remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_copy_if_impl( + ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj); + } + }; } // namespace __remove_copy_if diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 92e9327442ff..b4e1b82350f2 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -912,6 +912,38 @@ namespace ranges { indirectly_copyable_storable<iterator_t<R>, O>) constexpr unique_copy_result<borrowed_iterator_t<R>, O> unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++20 + + template<class I, class O> + using remove_copy_result = in_out_result<I, O>; // Since C++20 + + template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T, + class Proj = identity> + indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> + constexpr remove_copy_result<I, O> + remove_copy(I first, S last, O result, const T& value, Proj proj = {}); // Since C++20 + + template<input_range R, weakly_incrementable O, class T, class Proj = identity> + requires indirectly_copyable<iterator_t<R>, O> && + indirect_binary_predicate<ranges::equal_to, + projected<iterator_t<R>, Proj>, const T*> + constexpr remove_copy_result<borrowed_iterator_t<R>, O> + remove_copy(R&& r, O result, const T& value, Proj proj = {}); // Since C++20 + + template<class I, class O> + using remove_copy_if_result = in_out_result<I, O>; // Since C++20 + + template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, + class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> + requires indirectly_copyable<I, O> + constexpr remove_copy_if_result<I, O> + remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {}); // Since C++20 + + template<input_range R, weakly_incrementable O, class Proj = identity, + indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> + requires indirectly_copyable<iterator_t<R>, O> + constexpr remove_copy_if_result<borrowed_iterator_t<R>, O> + remove_copy_if(R&& r, O result, Pred pred, Proj proj = {}); // Since C++20 + } constexpr bool // constexpr in C++20 @@ -1694,6 +1726,8 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/ranges_pop_heap.h> #include <__algorithm/ranges_push_heap.h> #include <__algorithm/ranges_remove.h> +#include <__algorithm/ranges_remove_copy.h> +#include <__algorithm/ranges_remove_copy_if.h> #include <__algorithm/ranges_remove_if.h> #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.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 6e64454358b1..b809db91e42e 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 @@ -187,8 +187,8 @@ constexpr bool all_the_algorithms() //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0); (void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0); - //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0); + (void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0); + (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); 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 7f0015456d75..687d4fa18d66 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 @@ -170,10 +170,10 @@ constexpr bool all_the_algorithms() //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0); - //(void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0); - //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0); + (void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0); + (void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::remove_copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::remove(first, last, value, Proj(&copies)); assert(copies == 0); (void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0); (void)std::ranges::remove_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp index fb8a615f682d..f31734417bfa 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp @@ -30,16 +30,223 @@ #include <concepts> #include <functional> #include <ranges> +#include <utility> #include "almost_satisfies_types.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct ToPtr { + int* operator()(int) const; +}; + +template <class Iter = int*, class Sent = int*, class OutIter = int*, class Proj = std::identity> +concept HasRemoveCopyIter = + requires(Iter&& iter, Sent&& sent, OutIter&& out, Proj&& proj) { + std::ranges::remove_copy( + std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<OutIter>(out), 0, std::forward<Proj>(proj)); +}; + +static_assert(HasRemoveCopyIter<int*>); + +// !input_iterator<I> +static_assert(!HasRemoveCopyIter<InputIteratorNotDerivedFrom>); +static_assert(!HasRemoveCopyIter<cpp20_output_iterator<int*>>); + +// !sentinel_for<S, I> +static_assert(!HasRemoveCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>); +static_assert(!HasRemoveCopyIter<int*, SentinelForNotSemiregular>); + +// !weakly_incrementable<O> +static_assert(!HasRemoveCopyIter<int*, int*, WeaklyIncrementableNotMovable>); + +// !indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> +static_assert(!HasRemoveCopyIter<int*, int*, int*, ToPtr>); + +// !indirectly_copyable<I, O> +static_assert(!HasRemoveCopyIter<int*, int*, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasRemoveCopyIter<const int*, const int*, const int*>); + +template <class Range, class OutIter = int*, class Proj = std::identity> +concept HasRemoveCopyRange = + requires(Range&& range, OutIter&& out, Proj&& proj) { + std::ranges::remove_copy( + std::forward<Range>(range), std::forward<OutIter>(out), 0, std::forward<Proj>(proj)); +}; + +template <class T> +using R = UncheckedRange<T>; + +static_assert(HasRemoveCopyRange<R<int*>>); + +// !input_range<R> +static_assert(!HasRemoveCopyRange<InputRangeNotDerivedFrom>); +static_assert(!HasRemoveCopyRange<InputRangeNotIndirectlyReadable>); +static_assert(!HasRemoveCopyRange<InputRangeNotInputOrOutputIterator>); +static_assert(!HasRemoveCopyRange<InputRangeNotSentinelSemiregular>); +static_assert(!HasRemoveCopyRange<InputRangeNotSentinelEqualityComparableWith>); + +// !weakly_incrementable<O> +static_assert(!HasRemoveCopyRange<R<int*>, WeaklyIncrementableNotMovable>); + +// !indirect_binary_predicate<ranges::equal_to, projected<iterator_t<I>, Proj>, const T*> +static_assert(!HasRemoveCopyRange<R<int*>, int*, ToPtr>); + +// !indirectly_copyable<I, O> +static_assert(!HasRemoveCopyRange<R<int*>, int*, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasRemoveCopyRange<const int*, const int*, const int*>); + +template <int N, int M> +struct Data { + std::array<int, N> input; + std::array<int, M> expected; + int val; +}; + +template <class InIter, class Sent, class OutIter, int N, int M> +constexpr void test(Data<N, M> d) { + using Result = std::ranges::remove_copy_result<InIter, OutIter>; + + { // iterator overload + std::array<int, M> output; + + std::same_as<Result> decltype(auto) ret = std::ranges::remove_copy( + InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())), OutIter(output.data()), d.val); + + assert(base(ret.in) == d.input.data() + N); + assert(base(ret.out) == output.data() + M); + assert(d.expected == output); + } + + { // range overload + std::array<int, M> output; + auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size()))); + + std::same_as<Result> decltype(auto) ret = + std::ranges::remove_copy(range, OutIter(output.data()), d.val); + + assert(base(ret.in) == d.input.data() + N); + assert(base(ret.out) == output.data() + M); + assert(d.expected == output); + } +} + +template <class Iter, class Sent, class OutIter> +constexpr void tests() { + // simple test + test<Iter, Sent, OutIter, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5}); + // empty range + test<Iter, Sent, OutIter, 0, 0>({}); + // single element range - match + test<Iter, Sent, OutIter, 1, 0>({.input = {1}, .expected = {}, .val = 1}); + // single element range - no match + test<Iter, Sent, OutIter, 1, 1>({.input = {1}, .expected = {1}, .val = 2}); + // two element range - same order + test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2}); + // two element range - reversed order + test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1}); + // all elements match + test<Iter, Sent, OutIter, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1}); + // the relative order of elements isn't changed + test<Iter, Sent, OutIter, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 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 Iter> +constexpr void test_sentinels() { + test_output_iterators<Iter, Iter>(); + test_output_iterators<Iter, sentinel_wrapper<Iter>>(); + test_output_iterators<Iter, sized_sentinel<Iter>>(); +} 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<cpp17_input_iterator<int*>, sized_sentinel<cpp17_input_iterator<int*>>>(); + test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); + test_output_iterators<cpp20_input_iterator<int*>, sized_sentinel<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*>(); + + { // check that passing a different type works + struct S { + constexpr operator int() const { return 3; } + }; + + { // iterator overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{}); + } + + { // range overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(a, std::begin(b), S{}); + } + } + + { // check that a custom projection works + struct S { + constexpr operator int() const { return 3; } + }; + + { // iterator overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{}); + + } + { // range overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(a, std::begin(b), S{}); + } + } + + // Complexity: Exactly last - first applications of the corresponding predicate and any projection. + + { + std::array in{4, 4, 5, 6}; + std::array expected{5, 6}; + + // iterator overload + { + int numberOfProj = 0; + std::array<int, 2> out; + std::ranges::remove_copy( + in.begin(), + in.end(), + out.begin(), + 4, + counting_projection(numberOfProj)); + + assert(numberOfProj == static_cast<int>(in.size())); + + assert(std::ranges::equal(out, expected)); + } + + // range overload + { + int numberOfProj = 0; + std::array<int, 2> out; + std::ranges::remove_copy( + in, out.begin(), 4, counting_projection(numberOfProj)); + assert(numberOfProj == static_cast<int>(in.size())); + assert(std::ranges::equal(out, expected)); + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy_if.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy_if.pass.cpp index 8e3e46e12192..3a0d1ea424fd 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy_if.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy_if.pass.cpp @@ -28,16 +28,264 @@ #include <concepts> #include <functional> #include <ranges> +#include <type_traits> +#include <utility> #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct AlwaysTrue { + constexpr bool operator()(auto&&...) const { return true; } +}; + +template < + class I, + class S = sentinel_wrapper<std::decay_t<I>>, + class O = int*, + class Pred = AlwaysTrue> +concept HasRemoveCopyIfIter = + requires(I&& iter, S&& sent, O&& out, Pred&& pred) { + std::ranges::remove_copy_if(std::forward<I>(iter), std::forward<S>(sent), + std::forward<O>(out), std::forward<Pred>(pred)); +}; + +static_assert(HasRemoveCopyIfIter<int*, int*, int*>); + +// !input_iterator<I> +static_assert(!HasRemoveCopyIfIter<InputIteratorNotDerivedFrom>); +static_assert(!HasRemoveCopyIfIter<cpp20_output_iterator<int*>>); + +// !sentinel_for<S, I> +static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>); +static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotSemiregular>); + +// !weakly_incrementable<O> +static_assert(!HasRemoveCopyIfIter<int*, int*, WeaklyIncrementableNotMovable>); + +// !indirect_unary_predicate<Pred, projected<I, Proj>> +static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotPredicate>); +static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>); + +// !indirectly_copyable<I, O> +static_assert(!HasRemoveCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasRemoveCopyIfIter<const int*, const int*, const int*>); + +template < class R, class O = int*, class Pred = AlwaysTrue, class Proj = std::identity> +concept HasRemoveCopyIfRange = + requires(R&& r, O&& out, Pred&& pred, Proj&& proj) { + std::ranges::remove_copy_if( + std::forward<R>(r), std::forward<O>(out), std::forward<Pred>(pred), std::forward<Proj>(proj)); + }; + +template <class T> +using R = UncheckedRange<T>; + +static_assert(HasRemoveCopyIfRange<R<int*>>); + +// !input_range<R> +static_assert(!HasRemoveCopyIfRange<R<InputIteratorNotDerivedFrom>>); +static_assert(!HasRemoveCopyIfRange<R<cpp20_output_iterator<int*>>>); + +// !weakly_incrementable<O> +static_assert(!HasRemoveCopyIfRange<R<int*>, WeaklyIncrementableNotMovable>); + +// !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>> +static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotPredicate>); +static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotCopyConstructible>); + +// !indirectly_copyable<iterator_t<R>, O> +static_assert(!HasRemoveCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasRemoveCopyIfRange<R<const int*>, const int*>); + +template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2, class Pred> +constexpr void testRemoveCopyIfImpl(std::array<int, N1> in, std::array<int, N2> expected, Pred pred) { + using Sent = SentWrapper<InIter>; + using Result = std::ranges::remove_copy_if_result<InIter, OutIter>; + + // iterator overload + { + std::array<int, N2> out; + std::same_as<Result> decltype(auto) result = + std::ranges::remove_copy_if(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()}, pred); + assert(std::ranges::equal(out, expected)); + assert(base(result.in) == in.data() + in.size()); + assert(base(result.out) == out.data() + out.size()); + } + + // range overload + { + std::array<int, N2> out; + std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}}; + std::same_as<Result> decltype(auto) result = + std::ranges::remove_copy_if(r, OutIter{out.data()}, pred); + assert(std::ranges::equal(out, expected)); + assert(base(result.in) == in.data() + in.size()); + assert(base(result.out) == out.data() + out.size()); + } +} + +template <class InIter, class OutIter, template <class> class SentWrapper> +constexpr void testImpl() { + // remove multiple elements + { + std::array in{1, 2, 3, 2, 1}; + std::array expected{1, 3, 1}; + auto pred = [](int i) { return i == 2; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // remove single elements + { + std::array in{1, 2, 3, 2, 1}; + std::array expected{1, 2, 2, 1}; + auto pred = [](int i) { return i == 3; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // nothing removed + { + std::array in{1, 2, 3, 2, 1}; + std::array expected{1, 2, 3, 2, 1}; + auto pred = [](int) { return false; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // all removed + { + std::array in{1, 2, 3, 2, 1}; + std::array<int, 0> expected{}; + auto pred = [](int) { return true; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // remove first + { + std::array in{1, 2, 3, 2}; + std::array expected{2, 3, 2}; + auto pred = [](int i) { return i < 2; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // remove last + { + std::array in{1, 2, 3, 2, 5}; + std::array expected{1, 2, 3, 2}; + auto pred = [](int i) { return i > 3; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // stable + { + std::array in{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + std::array expected{6, 7, 8, 9, 10}; + auto pred = [](int i) { return i < 6; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // empty range + { + std::array<int, 0> in{}; + std::array<int, 0> expected{}; + auto pred = [](int) { return false; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } + + // one element range + { + std::array in{1}; + std::array<int, 0> expected{}; + auto pred = [](int i) { return i == 1; }; + testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred); + } +} + +template <class OutIter, template <class> class SentWrapper> +constexpr void withAllPermutationsOfInIter() { + testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>(); + testImpl<forward_iterator<int*>, OutIter, SentWrapper>(); + testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>(); + testImpl<random_access_iterator<int*>, OutIter, SentWrapper>(); + testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>(); + testImpl<int*, OutIter, SentWrapper>(); +} + +template <template <class> class SentWrapper> +constexpr void withAllPermutationsOfInIterOutIter() { + withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>(); + withAllPermutationsOfInIter<int*, SentWrapper>(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + withAllPermutationsOfInIterOutIter<std::type_identity_t>(); + withAllPermutationsOfInIterOutIter<sentinel_wrapper>(); + + // Test custom projection + { + struct Data { + int data; + }; + + std::array in{Data{4}, Data{8}, Data{12}, Data{12}}; + std::array expected{Data{4}, Data{12}, Data{12}}; + + const auto proj = &Data::data; + const auto pred = [](int i) { return i == 8; }; + + const auto equals = [](const Data& x, const Data& y) { return x.data == y.data; }; + // iterator overload + { + std::array<Data, 3> out; + auto result = std::ranges::remove_copy_if(in.begin(), in.end(), out.begin(), pred, proj); + assert(std::ranges::equal(out, expected, equals)); + assert(result.in == in.end()); + assert(result.out == out.end()); + } + + // range overload + { + std::array<Data, 3> out; + auto result = std::ranges::remove_copy_if(in, out.begin(), pred, proj); + assert(std::ranges::equal(out, expected, equals)); + assert(result.in == in.end()); + assert(result.out == out.end()); + } + } + + // Complexity: Exactly last - first applications of the corresponding predicate and any projection. + { + std::array in{4, 4, 5, 6}; + std::array expected{5, 6}; + + const auto pred = [](int i) { return i == 4; }; + + // iterator overload + { + int numberOfPred = 0; + int numberOfProj = 0; + std::array<int, 2> out; + std::ranges::remove_copy_if( + in.begin(), in.end(), out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj)); + + assert(numberOfPred == static_cast<int>(in.size())); + assert(numberOfProj == static_cast<int>(in.size())); + + assert(std::ranges::equal(out, expected)); + } + + // range overload + { + int numberOfPred = 0; + int numberOfProj = 0; + std::array<int, 2> out; + std::ranges::remove_copy_if( + in, out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj)); + assert(numberOfPred == static_cast<int>(in.size())); + assert(numberOfProj == static_cast<int>(in.size())); + assert(std::ranges::equal(out, expected)); + } + } 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 7198a3408e28..6a0fa1ac0b03 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 @@ -32,8 +32,8 @@ static_assert(std::is_same_v<in_out_result<int, long>, copy_backward_result<int, static_assert(std::is_same_v<in_out_result<int, long>, move_result<int, long>>); static_assert(std::is_same_v<in_out_result<int, long>, move_backward_result<int, long>>); 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>, 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>, reverse_copy_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 c0468de8365c..b280dca05ad9 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -78,8 +78,8 @@ constexpr bool test_all() { //using std::ranges::move_backward_result; using std::ranges::partial_sort_copy_result; using std::ranges::partition_copy_result; - //using std::ranges::remove_copy_result; - //using std::ranges::remove_copy_if_result; + using std::ranges::remove_copy_result; + using std::ranges::remove_copy_if_result; using std::ranges::reverse_copy_result; using std::ranges::rotate_copy_result; using std::ranges::set_difference_result; @@ -146,8 +146,8 @@ constexpr bool test_all() { std::ranges::transform, in, in2, out_transform.begin(), binary_pred); } dangling_1st(std::ranges::generate, in, gen); - //dangling_1st<remove_copy_result<dangling, int*>>(std::ranges::remove_copy, in, out, x); - //dangling_1st<remove_copy_if_result<dangling, int*>>(std::ranges::remove_copy_if, in, out, unary_pred); + dangling_1st<remove_copy_result<dangling, int*>>(std::ranges::remove_copy, in, out, x); + 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); 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 a38891792a82..37d454ca4979 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 @@ -112,7 +112,7 @@ constexpr bool test_all() { //std::ranges::clamp(2, 1, 3, binary_pred); //test(std::ranges::is_permutation, in, in2, binary_pred); test(std::ranges::copy_if, in, out, unary_pred); - //test(std::ranges::remove_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::unique_copy, in, out, 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 0c39e901f275..120c0bc7e225 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 @@ -129,8 +129,8 @@ constexpr bool test_all() { test(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val); } // Whether `ranges::generate{,_n}` invokes `gen` via `std::invoke` is not observable. - //test(std::ranges::remove_copy, in, out, x, &Bar::val); - //test(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val); + test(std::ranges::remove_copy, in, out, x, &Bar::val); + test(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val); // `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); 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 e77153ae828c..9193333457a9 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 @@ -125,8 +125,8 @@ constexpr void run_tests() { test(std::ranges::generate, in, gen); std::ranges::generate_n(in.begin(), count, gen); if constexpr (std::copyable<T>) { - //test(std::ranges::remove_copy, in, out, x); - //test(std::ranges::remove_copy_if, in, out, unary_pred); + test(std::ranges::remove_copy, in, out, x); + 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); 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 5e9d9f27ff2e..0f8272896db8 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 @@ -119,8 +119,8 @@ static_assert(test(std::ranges::pop_heap, a)); //static_assert(test(std::ranges::prev_permutation, a)); static_assert(test(std::ranges::push_heap, a)); static_assert(test(std::ranges::remove, a, 42)); -//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_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)); diff --git a/libcxx/test/support/counting_projection.h b/libcxx/test/support/counting_projection.h index 714058c1c045..1af2c80f244d 100644 --- a/libcxx/test/support/counting_projection.h +++ b/libcxx/test/support/counting_projection.h @@ -28,7 +28,7 @@ public: template <class T> constexpr decltype(auto) operator()(T&& value) const { ++(*count_); - return proj_(std::forward<T>(value)); + return std::invoke(proj_, std::forward<T>(value)); } }; |