248 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 11// <algorithm>12 13// template<permutable I, sentinel_for<I> S, class Proj = identity,14// indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>15// constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {}); // Since C++2016//17// template<forward_range R, class Proj = identity,18// indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>19// requires permutable<iterator_t<R>>20// constexpr borrowed_subrange_t<R>21// unique(R&& r, C comp = {}, Proj proj = {}); // Since C++2022 23#include <algorithm>24#include <array>25#include <concepts>26#include <functional>27#include <ranges>28 29#include "almost_satisfies_types.h"30#include "counting_predicates.h"31#include "counting_projection.h"32#include "test_iterators.h"33 34template <class Iter = int*, class Sent = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>35concept HasUniqueIter =36 requires(Iter&& iter, Sent&& sent, Comp&& comp, Proj&& proj) {37 std::ranges::unique(38 std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp), std::forward<Proj>(proj));39 };40 41static_assert(HasUniqueIter<int*, int*>);42 43// !permutable<I>44static_assert(!HasUniqueIter<PermutableNotForwardIterator>);45static_assert(!HasUniqueIter<PermutableNotSwappable>);46 47// !sentinel_for<S, I>48static_assert(!HasUniqueIter<int*, SentinelForNotSemiregular>);49 50// !indirect_equivalence_relation<Comp, projected<I, Proj>>51static_assert(!HasUniqueIter<int*, int*, ComparatorNotCopyable<int>>);52 53template <class Range, class Comp = std::ranges::equal_to, class Proj = std::identity>54concept HasUniqueRange =55 requires(Range&& range, Comp&& comp, Proj&& proj) {56 std::ranges::unique(std::forward<Range>(range), std::forward<Comp>(comp), std::forward<Proj>(proj));57 };58 59template <class T>60using R = UncheckedRange<T>;61 62static_assert(HasUniqueRange<R<int*>>);63 64// !forward_range<R>65static_assert(!HasUniqueRange<ForwardRangeNotDerivedFrom>);66static_assert(!HasUniqueRange<ForwardRangeNotIncrementable>);67 68// permutable<ranges::iterator_t<R>>69static_assert(!HasUniqueRange<R<PermutableNotForwardIterator>>);70static_assert(!HasUniqueRange<R<PermutableNotSwappable>>);71 72// !indirect_equivalence_relation<Comp, projected<ranges::iterator_t<R>, Proj>>73static_assert(!HasUniqueRange<R<int*>, ComparatorNotCopyable<int>>);74 75template <class Iter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>76constexpr void testUniqueImpl(std::array<int, N1> input, std::array<int, N2> expected) {77 using Sent = SentWrapper<Iter>;78 79 // iterator overload80 {81 auto in = input;82 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =83 std::ranges::unique(Iter{in.data()}, Sent{Iter{in.data() + in.size()}});84 assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected));85 assert(base(result.end()) == in.data() + in.size());86 }87 88 // range overload89 {90 auto in = input;91 std::ranges::subrange r{Iter{in.data()}, Sent{Iter{in.data() + in.size()}}};92 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::unique(r);93 assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected));94 assert(base(result.end()) == in.data() + in.size());95 }96}97 98template <class Iter, template <class> class SentWrapper>99constexpr void testImpl() {100 // no consecutive elements101 {102 std::array in{1, 2, 3, 2, 1};103 std::array expected{1, 2, 3, 2, 1};104 testUniqueImpl<Iter, SentWrapper>(in, expected);105 }106 107 // one group of consecutive elements108 {109 std::array in{2, 3, 3, 3, 4, 3};110 std::array expected{2, 3, 4, 3};111 testUniqueImpl<Iter, SentWrapper>(in, expected);112 }113 114 // multiple groups of consecutive elements115 {116 std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5};117 std::array expected{2, 3, 4, 3, 5};118 testUniqueImpl<Iter, SentWrapper>(in, expected);119 }120 121 // all the same122 {123 std::array in{1, 1, 1, 1, 1, 1};124 std::array expected{1};125 testUniqueImpl<Iter, SentWrapper>(in, expected);126 }127 128 // empty range129 {130 std::array<int, 0> in{};131 std::array<int, 0> expected{};132 testUniqueImpl<Iter, SentWrapper>(in, expected);133 }134 135 // single element range136 std::array in{1};137 std::array expected{1};138 testUniqueImpl<Iter, SentWrapper>(in, expected);139}140 141template <template <class> class SentWrapper>142constexpr void withAllPermutationsOfIter() {143 testImpl<forward_iterator<int*>, SentWrapper>();144 testImpl<bidirectional_iterator<int*>, SentWrapper>();145 testImpl<random_access_iterator<int*>, SentWrapper>();146 testImpl<contiguous_iterator<int*>, SentWrapper>();147 testImpl<int*, SentWrapper>();148}149 150constexpr bool test() {151 withAllPermutationsOfIter<std::type_identity_t>();152 withAllPermutationsOfIter<sentinel_wrapper>();153 154 struct Data {155 int data;156 };157 158 // Test custom comparator159 {160 std::array input{Data{4}, Data{8}, Data{8}, Data{8}};161 std::array expected{Data{4}, Data{8}};162 const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; };163 164 // iterator overload165 {166 auto in = input;167 auto result = std::ranges::unique(in.begin(), in.end(), comp);168 assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp));169 assert(base(result.end()) == in.end());170 }171 172 // range overload173 {174 auto in = input;175 auto result = std::ranges::unique(in, comp);176 assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp));177 assert(base(result.end()) == in.end());178 }179 }180 181 // Test custom projection182 {183 std::array input{Data{4}, Data{8}, Data{8}, Data{8}};184 std::array expected{Data{4}, Data{8}};185 186 const auto proj = &Data::data;187 188 // iterator overload189 {190 auto in = input;191 auto result = std::ranges::unique(in.begin(), in.end(), {}, proj);192 assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj));193 assert(base(result.end()) == in.end());194 }195 196 // range overload197 {198 auto in = input;199 auto result = std::ranges::unique(in, {}, proj);200 assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj));201 assert(base(result.end()) == in.end());202 }203 }204 205 // Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate206 // and no more than twice as many applications of any projection.207 {208 std::array input{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1};209 std::array expected{1, 2, 3, 4, 3, 5, 6, 1};210 // iterator overload211 {212 auto in = input;213 int numberOfComp = 0;214 int numberOfProj = 0;215 auto result = std::ranges::unique(216 in.begin(),217 in.end(),218 counting_predicate{std::ranges::equal_to{}, numberOfComp},219 counting_projection{numberOfProj});220 assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end()));221 assert(base(result.end()) == in.end());222 assert(numberOfComp == in.size() - 1);223 assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));224 }225 // range overload226 {227 auto in = input;228 int numberOfComp = 0;229 int numberOfProj = 0;230 auto result = std::ranges::unique(231 in, counting_predicate{std::ranges::equal_to{}, numberOfComp}, counting_projection{numberOfProj});232 assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end()));233 assert(base(result.end()) == in.end());234 assert(numberOfComp == in.size() - 1);235 assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));236 }237 }238 239 return true;240}241 242int main(int, char**) {243 test();244 static_assert(test());245 246 return 0;247}248