//===----------------------------------------------------------------------===//
//
// 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<permutable I, sentinel_for<I> S, class Proj = identity,
// indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
// constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {}); // Since C++20
//
// template<forward_range R, class Proj = identity,
// indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
// requires permutable<iterator_t<R>>
// constexpr borrowed_subrange_t<R>
// unique(R&& r, 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 "test_iterators.h"
template <class Iter = int*, class Sent = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
concept HasUniqueIter =
requires(Iter&& iter, Sent&& sent, Comp&& comp, Proj&& proj) {
std::ranges::unique(
std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp), std::forward<Proj>(proj));
};
static_assert(HasUniqueIter<int*, int*>);
// !permutable<I>
static_assert(!HasUniqueIter<PermutableNotForwardIterator>);
static_assert(!HasUniqueIter<PermutableNotSwappable>);
// !sentinel_for<S, I>
static_assert(!HasUniqueIter<int*, SentinelForNotSemiregular>);
// !indirect_equivalence_relation<Comp, projected<I, Proj>>
static_assert(!HasUniqueIter<int*, int*, ComparatorNotCopyable<int>>);
template <class Range, class Comp = std::ranges::equal_to, class Proj = std::identity>
concept HasUniqueRange =
requires(Range&& range, Comp&& comp, Proj&& proj) {
std::ranges::unique(std::forward<Range>(range), std::forward<Comp>(comp), std::forward<Proj>(proj));
};
template <class T>
using R = UncheckedRange<T>;
static_assert(HasUniqueRange<R<int*>>);
// !forward_range<R>
static_assert(!HasUniqueRange<ForwardRangeNotDerivedFrom>);
static_assert(!HasUniqueRange<ForwardRangeNotIncrementable>);
// permutable<ranges::iterator_t<R>>
static_assert(!HasUniqueRange<R<PermutableNotForwardIterator>>);
static_assert(!HasUniqueRange<R<PermutableNotSwappable>>);
// !indirect_equivalence_relation<Comp, projected<ranges::iterator_t<R>, Proj>>
static_assert(!HasUniqueRange<R<int*>, ComparatorNotCopyable<int>>);
template <class Iter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
constexpr void testUniqueImpl(std::array<int, N1> input, std::array<int, N2> expected) {
using Sent = SentWrapper<Iter>;
// iterator overload
{
auto in = input;
std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
std::ranges::unique(Iter{in.data()}, Sent{Iter{in.data() + in.size()}});
assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected));
assert(base(result.end()) == in.data() + in.size());
}
// range overload
{
auto in = input;
std::ranges::subrange r{Iter{in.data()}, Sent{Iter{in.data() + in.size()}}};
std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::unique(r);
assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected));
assert(base(result.end()) == in.data() + in.size());
}
}
template <class Iter, 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};
testUniqueImpl<Iter, SentWrapper>(in, expected);
}
// one group of consecutive elements
{
std::array in{2, 3, 3, 3, 4, 3};
std::array expected{2, 3, 4, 3};
testUniqueImpl<Iter, 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};
testUniqueImpl<Iter, SentWrapper>(in, expected);
}
// all the same
{
std::array in{1, 1, 1, 1, 1, 1};
std::array expected{1};
testUniqueImpl<Iter, SentWrapper>(in, expected);
}
// empty range
{
std::array<int, 0> in{};
std::array<int, 0> expected{};
testUniqueImpl<Iter, SentWrapper>(in, expected);
}
// single element range
std::array in{1};
std::array expected{1};
testUniqueImpl<Iter, SentWrapper>(in, expected);
}
template <template <class> class SentWrapper>
constexpr void withAllPermutationsOfIter() {
testImpl<forward_iterator<int*>, SentWrapper>();
testImpl<bidirectional_iterator<int*>, SentWrapper>();
testImpl<random_access_iterator<int*>, SentWrapper>();
testImpl<contiguous_iterator<int*>, SentWrapper>();
testImpl<int*, SentWrapper>();
}
constexpr bool test() {
withAllPermutationsOfIter<std::type_identity_t>();
withAllPermutationsOfIter<sentinel_wrapper>();
struct Data {
int data;
};
// Test custom comparator
{
std::array input{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
{
auto in = input;
auto result = std::ranges::unique(in.begin(), in.end(), comp);
assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp));
assert(base(result.end()) == in.end());
}
// range overload
{
auto in = input;
auto result = std::ranges::unique(in, comp);
assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp));
assert(base(result.end()) == in.end());
}
}
// Test custom projection
{
std::array input{Data{4}, Data{8}, Data{8}, Data{8}};
std::array expected{Data{4}, Data{8}};
const auto proj = &Data::data;
// iterator overload
{
auto in = input;
auto result = std::ranges::unique(in.begin(), in.end(), {}, proj);
assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj));
assert(base(result.end()) == in.end());
}
// range overload
{
auto in = input;
auto result = std::ranges::unique(in, {}, proj);
assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj));
assert(base(result.end()) == in.end());
}
}
// Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate
// and no more than twice as many applications of any projection.
{
std::array input{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
{
auto in = input;
int numberOfComp = 0;
int numberOfProj = 0;
auto result = std::ranges::unique(
in.begin(),
in.end(),
counting_predicate{std::ranges::equal_to{}, numberOfComp},
counting_projection{numberOfProj});
assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end()));
assert(base(result.end()) == in.end());
assert(numberOfComp == in.size() - 1);
assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
}
// range overload
{
auto in = input;
int numberOfComp = 0;
int numberOfProj = 0;
auto result = std::ranges::unique(
in, counting_predicate{std::ranges::equal_to{}, numberOfComp}, counting_projection{numberOfProj});
assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end()));
assert(base(result.end()) == in.end());
assert(numberOfComp == 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