| //===----------------------------------------------------------------------===// |
| // |
| // 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; |
| } |