//===----------------------------------------------------------------------===//
//
// 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 Proj = identity,
// indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
// requires indirectly_copyable<I, O> &&
// (forward_iterator<I> ||
// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
// indirectly_copyable_storable<I, O>)
// constexpr unique_copy_result<I, O>
// unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); // Since C++20
//
// template<input_range R, weakly_incrementable O, class Proj = identity,
// indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
// requires indirectly_copyable<iterator_t<R>, O> &&
// (forward_iterator<iterator_t<R>> ||
// (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
// 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
#include <algorithm>
#include <array>
#include <concepts>
#include <functional>
#include <ranges>
#include "almost_satisfies_types.h"
#include "counting_predicates.h"
#include "counting_projection.h"
#include "MoveOnly.h"
#include "test_iterators.h"
template <
class InIter = int*,
class Sent = int*,
class OutIter = int*,
class Comp = std::ranges::equal_to,
class Proj = std::identity>
concept HasUniqueCopyIter =
requires(InIter&& in, Sent&& sent, OutIter&& out, Comp&& comp, Proj&& proj) {
std::ranges::unique_copy(
std::forward<InIter>(in),
std::forward<Sent>(sent),
std::forward<OutIter>(out),
std::forward<Comp>(comp),
std::forward<Proj>(proj));
};
static_assert(HasUniqueCopyIter<int*, int*, int*>);
// !input_iterator<I>
static_assert(!HasUniqueCopyIter<InputIteratorNotDerivedFrom, sentinel_wrapper<InputIteratorNotDerivedFrom>>);
// !sentinel_for<S, I>
static_assert(!HasUniqueCopyIter<int*, SentinelForNotSemiregular>);
// !weakly_incrementable<O>
static_assert(!HasUniqueCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
// !indirect_equivalence_relation<Comp, projected<I, Proj>>
static_assert(!HasUniqueCopyIter<int*, int*, int*, ComparatorNotCopyable<int>>);
// !indirectly_copyable<I, O>
static_assert(!HasUniqueCopyIter<const int*, const int*, const int*>);
// forward_iterator<I>
// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// !indirectly_copyable_storable<I, O>
struct AssignableFromMoveOnly {
int data;
constexpr AssignableFromMoveOnly& operator=(MoveOnly const& m) {
data = m.get();
return *this;
}
};
static_assert(HasUniqueCopyIter<MoveOnly*, MoveOnly*, AssignableFromMoveOnly*>);
// because:
static_assert(std::forward_iterator<MoveOnly*>);
static_assert(!std::same_as<std::iter_value_t<MoveOnly*>, std::iter_value_t<AssignableFromMoveOnly*>>);
static_assert(!std::indirectly_copyable_storable<MoveOnly*, AssignableFromMoveOnly*>);
// !forward_iterator<I>
// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// !indirectly_copyable_storable<I, O>
struct CopyAssignableNotCopyConstructible {
int data;
constexpr CopyAssignableNotCopyConstructible(int i = 0) : data(i) {}
CopyAssignableNotCopyConstructible(const CopyAssignableNotCopyConstructible&) = delete;
CopyAssignableNotCopyConstructible& operator=(const CopyAssignableNotCopyConstructible&) = default;
friend constexpr bool
operator==(CopyAssignableNotCopyConstructible const&, CopyAssignableNotCopyConstructible const&) = default;
};
using InputAndOutputIterator = cpp17_input_iterator<CopyAssignableNotCopyConstructible*>;
static_assert(std::input_iterator<InputAndOutputIterator>);
static_assert(std::output_iterator<InputAndOutputIterator, CopyAssignableNotCopyConstructible>);
static_assert(
HasUniqueCopyIter<
cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
sentinel_wrapper<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
InputAndOutputIterator>);
// because:
static_assert(!std::forward_iterator< cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>);
static_assert(
std::input_iterator<InputAndOutputIterator> &&
std::same_as<std::iter_value_t<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
std::iter_value_t<InputAndOutputIterator>>);
static_assert(
!std::indirectly_copyable_storable<
cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
InputAndOutputIterator>);
// !forward_iterator<I>
// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// indirectly_copyable_storable<I, O>
static_assert(
HasUniqueCopyIter<
cpp20_input_iterator<int*>,
sentinel_wrapper<cpp20_input_iterator<int*>>,
cpp20_output_iterator<int*>>);
// because:
static_assert(!std::forward_iterator<cpp20_input_iterator<int*>>);
static_assert(!std::input_iterator<cpp20_output_iterator<int*>>);
static_assert(std::indirectly_copyable_storable<cpp20_input_iterator<int*>, cpp20_output_iterator<int*>>);
// !forward_iterator<I>
// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// !indirectly_copyable_storable<I, O>
static_assert(
!HasUniqueCopyIter<
cpp20_input_iterator<MoveOnly*>,
sentinel_wrapper<cpp20_input_iterator<MoveOnly*>>,
cpp20_output_iterator<AssignableFromMoveOnly*>>);
// because:
static_assert(!std::forward_iterator<cpp20_input_iterator<MoveOnly*>>);
static_assert(!std::input_iterator<cpp20_output_iterator<MoveOnly*>>);
static_assert(
!std::
indirectly_copyable_storable<cpp20_input_iterator<MoveOnly*>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
template < class Range, class OutIter = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
concept HasUniqueCopyRange =
requires(Range&& range, OutIter&& out, Comp&& comp, Proj&& proj) {
std::ranges::unique_copy(
std::forward<Range>(range), std::forward<OutIter>(out), std::forward<Comp>(comp), std::forward<Proj>(proj));
};
template <class T>
using R = UncheckedRange<T>;
static_assert(HasUniqueCopyRange<R<int*>, int*>);
// !input_range<R>
static_assert(!HasUniqueCopyRange<R<InputIteratorNotDerivedFrom>>);
// !weakly_incrementable<O>
static_assert(!HasUniqueCopyIter<R<int*>, WeaklyIncrementableNotMovable>);
// !indirect_equivalence_relation<Comp, projected<I, Proj>>
static_assert(!HasUniqueCopyIter<R<int*>, int*, ComparatorNotCopyable<int>>);
// !indirectly_copyable<I, O>
static_assert(!HasUniqueCopyIter<R<const int*>, const int*>);
// !forward_iterator<iterator_t<R>>
// !(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>)
// !indirectly_copyable_storable<iterator_t<R>, O>
static_assert(!HasUniqueCopyIter< R<cpp20_input_iterator<MoveOnly*>>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
constexpr void testUniqueCopyImpl(std::array<int, N1> in, std::array<int, N2> expected) {
using Sent = SentWrapper<InIter>;
// iterator overload
{
std::array<int, N2> out;
std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =
std::ranges::unique_copy(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()});
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<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =
std::ranges::unique_copy(r, OutIter{out.data()});
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() {
// no consecutive elements
{
std::array in{1, 2, 3, 2, 1};
std::array expected{1, 2, 3, 2, 1};
testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
}
// one group of consecutive elements
{
std::array in{2, 3, 3, 3, 4, 3};
std::array expected{2, 3, 4, 3};
testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
}
// multiple groups of consecutive elements
{
std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5};
std::array expected{2, 3, 4, 3, 5};
testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
}
// all the same
{
std::array in{1, 1, 1, 1, 1, 1};
std::array expected{1};
testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
}
// empty range
{
std::array<int, 0> in{};
std::array<int, 0> expected{};
testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
}
}
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 withAllPermutationsOfInIterAndOutIter() {
withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
withAllPermutationsOfInIter<forward_iterator<int*>, SentWrapper>();
withAllPermutationsOfInIter<bidirectional_iterator<int*>, SentWrapper>();
withAllPermutationsOfInIter<random_access_iterator<int*>, SentWrapper>();
withAllPermutationsOfInIter<contiguous_iterator<int*>, SentWrapper>();
withAllPermutationsOfInIter<int*, SentWrapper>();
}
constexpr bool test() {
withAllPermutationsOfInIterAndOutIter<std::type_identity_t>();
withAllPermutationsOfInIterAndOutIter<sentinel_wrapper>();
// Test the overload that re-reads from the input iterator
// forward_iterator<I>
// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// !indirectly_copyable_storable<I, O>
{
MoveOnly in[5] = {1, 3, 3, 3, 1};
// iterator overload
{
AssignableFromMoveOnly out[3] = {};
auto result = std::ranges::unique_copy(in, in + 5, out);
assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));
assert(result.in == in + 5);
assert(result.out == out + 3);
}
// range overload
{
AssignableFromMoveOnly out[3] = {};
auto result = std::ranges::unique_copy(std::ranges::subrange{in, in + 5}, out);
assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));
assert(result.in == in + 5);
assert(result.out == out + 3);
}
}
// Test the overload that re-reads from the output iterator
// !forward_iterator<I>
// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// !indirectly_copyable_storable<I, O>
{
using InIter = cpp20_input_iterator<CopyAssignableNotCopyConstructible*>;
using Sent = sentinel_wrapper<InIter>;
CopyAssignableNotCopyConstructible in[6] = {1, 1, 2, 2, 3, 3};
// iterator overload
{
CopyAssignableNotCopyConstructible out[3];
auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 6}}, InputAndOutputIterator{out});
assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));
assert(base(result.in) == in + 6);
assert(base(result.out) == out + 3);
}
// range overload
{
CopyAssignableNotCopyConstructible out[3];
auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 6}});
auto result = std::ranges::unique_copy(r, InputAndOutputIterator{out});
assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));
assert(base(result.in) == in + 6);
assert(base(result.out) == out + 3);
}
}
// Test the overload that reads from the temporary copy of the value
// !forward_iterator<I>
// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
// indirectly_copyable_storable<I, O>
{
using InIter = cpp20_input_iterator<int*>;
using Sent = sentinel_wrapper<InIter>;
int in[4] = {1, 1, 1, 2};
// iterator overload
{
int out[2];
auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 4}}, cpp20_output_iterator<int*>{out});
assert(std::ranges::equal(out, std::array{1, 2}));
assert(base(result.in) == in + 4);
assert(base(result.out) == out + 2);
}
// range overload
{
int out[2];
auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 4}});
auto result = std::ranges::unique_copy(r, cpp20_output_iterator<int*>{out});
assert(std::ranges::equal(out, std::array{1, 2}));
assert(base(result.in) == in + 4);
assert(base(result.out) == out + 2);
}
}
struct Data {
int data;
};
// Test custom comparator
{
std::array in{Data{4}, Data{8}, Data{8}, Data{8}};
std::array expected{Data{4}, Data{8}};
const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; };
// iterator overload
{
std::array<Data, 2> out;
auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), comp);
assert(std::ranges::equal(out, expected, comp));
assert(base(result.in) == in.begin() + 4);
assert(base(result.out) == out.begin() + 2);
}
// range overload
{
std::array<Data, 2> out;
auto result = std::ranges::unique_copy(in, out.begin(), comp);
assert(std::ranges::equal(out, expected, comp));
assert(base(result.in) == in.begin() + 4);
assert(base(result.out) == out.begin() + 2);
}
}
// Test custom projection
{
std::array in{Data{4}, Data{8}, Data{8}, Data{8}};
std::array expected{Data{4}, Data{8}};
const auto proj = &Data::data;
// iterator overload
{
std::array<Data, 2> out;
auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), {}, proj);
assert(std::ranges::equal(out, expected, {}, proj, proj));
assert(base(result.in) == in.begin() + 4);
assert(base(result.out) == out.begin() + 2);
}
// range overload
{
std::array<Data, 2> out;
auto result = std::ranges::unique_copy(in, out.begin(), {}, proj);
assert(std::ranges::equal(out, expected, {}, proj, proj));
assert(base(result.in) == in.begin() + 4);
assert(base(result.out) == out.begin() + 2);
}
}
// Exactly last - first - 1 applications of the corresponding predicate and no
// more than twice as many applications of any projection.
{
std::array in{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1};
std::array expected{1, 2, 3, 4, 3, 5, 6, 1};
// iterator overload
{
std::array<int, 8> out;
int numberOfComp = 0;
int numberOfProj = 0;
auto result = std::ranges::unique_copy(
in.begin(),
in.end(),
out.begin(),
counting_predicate{std::ranges::equal_to{}, numberOfComp},
counting_projection{numberOfProj});
assert(std::ranges::equal(out, expected));
assert(base(result.in) == in.end());
assert(base(result.out) == out.end());
assert(numberOfComp == static_cast<int>(in.size() - 1));
assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
}
// range overload
{
std::array<int, 8> out;
int numberOfComp = 0;
int numberOfProj = 0;
auto result = std::ranges::unique_copy(
in,
out.begin(),
counting_predicate{std::ranges::equal_to{}, numberOfComp},
counting_projection{numberOfProj});
assert(std::ranges::equal(out, expected));
assert(base(result.in) == in.end());
assert(base(result.out) == out.end());
assert(numberOfComp == static_cast<int>(in.size() - 1));
assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
}
}
return true;
}
int main(int, char**) {
test();
static_assert(test());
return 0;
}
Codebase Browser
llvm