| //===----------------------------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // UNSUPPORTED: c++03, c++11, c++14, c++17 |
| |
| // <algorithm> |
| |
| // template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T, |
| // class Proj = identity> |
| // requires indirectly_copyable<I, O> && |
| // 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 |
| |
| #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" |
| |
| 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() { |
| 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; |
| } |
| |
| int main(int, char**) { |
| test(); |
| static_assert(test()); |
| |
| return 0; |
| } |