libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique.pass.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 // UNSUPPORTED: c++03, c++11, c++14, c++17
  10
  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++20
  16 //
  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++20
  22
  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
  34 template <class Iter = int*, class Sent = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
  35 concept 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
  41 static_assert(HasUniqueIter<int*, int*>);
  42
  43 // !permutable<I>
  44 static_assert(!HasUniqueIter<PermutableNotForwardIterator>);
  45 static_assert(!HasUniqueIter<PermutableNotSwappable>);
  46
  47 // !sentinel_for<S, I>
  48 static_assert(!HasUniqueIter<int*, SentinelForNotSemiregular>);
  49
  50 // !indirect_equivalence_relation<Comp, projected<I, Proj>>
  51 static_assert(!HasUniqueIter<int*, int*, ComparatorNotCopyable<int>>);
  52
  53 template <class Range, class Comp = std::ranges::equal_to, class Proj = std::identity>
  54 concept 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
  59 template <class T>
  60 using R = UncheckedRange<T>;
  61
  62 static_assert(HasUniqueRange<R<int*>>);
  63
  64 // !forward_range<R>
  65 static_assert(!HasUniqueRange<ForwardRangeNotDerivedFrom>);
  66 static_assert(!HasUniqueRange<ForwardRangeNotIncrementable>);
  67
  68 // permutable<ranges::iterator_t<R>>
  69 static_assert(!HasUniqueRange<R<PermutableNotForwardIterator>>);
  70 static_assert(!HasUniqueRange<R<PermutableNotSwappable>>);
  71
  72 // !indirect_equivalence_relation<Comp, projected<ranges::iterator_t<R>, Proj>>
  73 static_assert(!HasUniqueRange<R<int*>, ComparatorNotCopyable<int>>);
  74
  75 template <class Iter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
  76 constexpr void testUniqueImpl(std::array<int, N1> input, std::array<int, N2> expected) {
  77   using Sent = SentWrapper<Iter>;
  78
  79   // iterator overload
  80   {
  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 overload
  89   {
  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
  98 template <class Iter, template <class> class SentWrapper>
  99 constexpr void testImpl() {
 100   // no consecutive elements
 101   {
 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 elements
 108   {
 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 elements
 115   {
 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 same
 122   {
 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 range
 129   {
 130     std::array<int, 0> in{};
 131     std::array<int, 0> expected{};
 132     testUniqueImpl<Iter, SentWrapper>(in, expected);
 133   }
 134
 135   // single element range
 136     std::array in{1};
 137     std::array expected{1};
 138     testUniqueImpl<Iter, SentWrapper>(in, expected);
 139 }
 140
 141 template <template <class> class SentWrapper>
 142 constexpr 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
 150 constexpr bool test() {
 151   withAllPermutationsOfIter<std::type_identity_t>();
 152   withAllPermutationsOfIter<sentinel_wrapper>();
 153
 154   struct Data {
 155     int data;
 156   };
 157
 158   // Test custom comparator
 159   {
 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 overload
 165     {
 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 overload
 173     {
 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 projection
 182   {
 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 overload
 189     {
 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 overload
 197     {
 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 predicate
 206   // 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 overload
 211     {
 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 overload
 226     {
 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
 242 int main(int, char**) {
 243   test();
 244   static_assert(test());
 245
 246   return 0;
 247 }