libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique_copy.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<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
  14 //          indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
  15 //   requires indirectly_copyable<I, O> &&
  16 //            (forward_iterator<I> ||
  17 //             (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
  18 //             indirectly_copyable_storable<I, O>)
  19 //   constexpr unique_copy_result<I, O>
  20 //     unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});                         // Since C++20
  21 //
  22 // template<input_range R, weakly_incrementable O, class Proj = identity,
  23 //          indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
  24 //   requires indirectly_copyable<iterator_t<R>, O> &&
  25 //            (forward_iterator<iterator_t<R>> ||
  26 //             (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
  27 //             indirectly_copyable_storable<iterator_t<R>, O>)
  28 //   constexpr unique_copy_result<borrowed_iterator_t<R>, O>
  29 //     unique_copy(R&& r, O result, C comp = {}, Proj proj = {});                                   // Since C++20
  30
  31 #include <algorithm>
  32 #include <array>
  33 #include <concepts>
  34 #include <functional>
  35 #include <ranges>
  36
  37 #include "almost_satisfies_types.h"
  38 #include "counting_predicates.h"
  39 #include "counting_projection.h"
  40 #include "MoveOnly.h"
  41 #include "test_iterators.h"
  42
  43 template <
  44     class InIter  = int*,
  45     class Sent    = int*,
  46     class OutIter = int*,
  47     class Comp    = std::ranges::equal_to,
  48     class Proj    = std::identity>
  49 concept HasUniqueCopyIter =
  50     requires(InIter&& in, Sent&& sent, OutIter&& out, Comp&& comp, Proj&& proj) {
  51       std::ranges::unique_copy(
  52           std::forward<InIter>(in),
  53           std::forward<Sent>(sent),
  54           std::forward<OutIter>(out),
  55           std::forward<Comp>(comp),
  56           std::forward<Proj>(proj));
  57     };
  58
  59 static_assert(HasUniqueCopyIter<int*, int*, int*>);
  60
  61 // !input_iterator<I>
  62 static_assert(!HasUniqueCopyIter<InputIteratorNotDerivedFrom, sentinel_wrapper<InputIteratorNotDerivedFrom>>);
  63
  64 // !sentinel_for<S, I>
  65 static_assert(!HasUniqueCopyIter<int*, SentinelForNotSemiregular>);
  66
  67 // !weakly_incrementable<O>
  68 static_assert(!HasUniqueCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
  69
  70 // !indirect_equivalence_relation<Comp, projected<I, Proj>>
  71 static_assert(!HasUniqueCopyIter<int*, int*, int*, ComparatorNotCopyable<int>>);
  72
  73 // !indirectly_copyable<I, O>
  74 static_assert(!HasUniqueCopyIter<const int*, const int*, const int*>);
  75
  76 // forward_iterator<I>
  77 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
  78 // !indirectly_copyable_storable<I, O>
  79 struct AssignableFromMoveOnly {
  80   int data;
  81   constexpr AssignableFromMoveOnly& operator=(MoveOnly const& m) {
  82     data = m.get();
  83     return *this;
  84   }
  85 };
  86 static_assert(HasUniqueCopyIter<MoveOnly*, MoveOnly*, AssignableFromMoveOnly*>);
  87 // because:
  88 static_assert(std::forward_iterator<MoveOnly*>);
  89 static_assert(!std::same_as<std::iter_value_t<MoveOnly*>, std::iter_value_t<AssignableFromMoveOnly*>>);
  90 static_assert(!std::indirectly_copyable_storable<MoveOnly*, AssignableFromMoveOnly*>);
  91
  92 // !forward_iterator<I>
  93 // (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
  94 // !indirectly_copyable_storable<I, O>
  95 struct CopyAssignableNotCopyConstructible {
  96   int data;
  97   constexpr CopyAssignableNotCopyConstructible(int i = 0) : data(i) {}
  98   CopyAssignableNotCopyConstructible(const CopyAssignableNotCopyConstructible&)            = delete;
  99   CopyAssignableNotCopyConstructible& operator=(const CopyAssignableNotCopyConstructible&) = default;
 100   friend constexpr bool
 101   operator==(CopyAssignableNotCopyConstructible const&, CopyAssignableNotCopyConstructible const&) = default;
 102 };
 103
 104 using InputAndOutputIterator = cpp17_input_iterator<CopyAssignableNotCopyConstructible*>;
 105 static_assert(std::input_iterator<InputAndOutputIterator>);
 106 static_assert(std::output_iterator<InputAndOutputIterator, CopyAssignableNotCopyConstructible>);
 107
 108 static_assert(
 109     HasUniqueCopyIter<
 110         cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
 111         sentinel_wrapper<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
 112         InputAndOutputIterator>);
 113 // because:
 114 static_assert(!std::forward_iterator< cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>);
 115 static_assert(
 116     std::input_iterator<InputAndOutputIterator> &&
 117     std::same_as<std::iter_value_t<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
 118                  std::iter_value_t<InputAndOutputIterator>>);
 119 static_assert(
 120     !std::indirectly_copyable_storable<
 121         cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
 122         InputAndOutputIterator>);
 123
 124 // !forward_iterator<I>
 125 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
 126 // indirectly_copyable_storable<I, O>
 127 static_assert(
 128     HasUniqueCopyIter<
 129         cpp20_input_iterator<int*>,
 130         sentinel_wrapper<cpp20_input_iterator<int*>>,
 131         cpp20_output_iterator<int*>>);
 132 // because:
 133 static_assert(!std::forward_iterator<cpp20_input_iterator<int*>>);
 134 static_assert(!std::input_iterator<cpp20_output_iterator<int*>>);
 135 static_assert(std::indirectly_copyable_storable<cpp20_input_iterator<int*>, cpp20_output_iterator<int*>>);
 136
 137 // !forward_iterator<I>
 138 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
 139 // !indirectly_copyable_storable<I, O>
 140 static_assert(
 141     !HasUniqueCopyIter<
 142         cpp20_input_iterator<MoveOnly*>,
 143         sentinel_wrapper<cpp20_input_iterator<MoveOnly*>>,
 144         cpp20_output_iterator<AssignableFromMoveOnly*>>);
 145 // because:
 146 static_assert(!std::forward_iterator<cpp20_input_iterator<MoveOnly*>>);
 147 static_assert(!std::input_iterator<cpp20_output_iterator<MoveOnly*>>);
 148 static_assert(
 149     !std::
 150         indirectly_copyable_storable<cpp20_input_iterator<MoveOnly*>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
 151
 152 template < class Range, class OutIter = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
 153 concept HasUniqueCopyRange =
 154     requires(Range&& range, OutIter&& out, Comp&& comp, Proj&& proj) {
 155       std::ranges::unique_copy(
 156           std::forward<Range>(range), std::forward<OutIter>(out), std::forward<Comp>(comp), std::forward<Proj>(proj));
 157     };
 158
 159 template <class T>
 160 using R = UncheckedRange<T>;
 161
 162 static_assert(HasUniqueCopyRange<R<int*>, int*>);
 163
 164 // !input_range<R>
 165 static_assert(!HasUniqueCopyRange<R<InputIteratorNotDerivedFrom>>);
 166
 167 // !weakly_incrementable<O>
 168 static_assert(!HasUniqueCopyIter<R<int*>, WeaklyIncrementableNotMovable>);
 169
 170 // !indirect_equivalence_relation<Comp, projected<I, Proj>>
 171 static_assert(!HasUniqueCopyIter<R<int*>, int*, ComparatorNotCopyable<int>>);
 172
 173 // !indirectly_copyable<I, O>
 174 static_assert(!HasUniqueCopyIter<R<const int*>, const int*>);
 175
 176 // !forward_iterator<iterator_t<R>>
 177 // !(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>)
 178 // !indirectly_copyable_storable<iterator_t<R>, O>
 179 static_assert(!HasUniqueCopyIter< R<cpp20_input_iterator<MoveOnly*>>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
 180
 181 template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
 182 constexpr void testUniqueCopyImpl(std::array<int, N1> in, std::array<int, N2> expected) {
 183   using Sent = SentWrapper<InIter>;
 184
 185   // iterator overload
 186   {
 187     std::array<int, N2> out;
 188     std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =
 189         std::ranges::unique_copy(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.begin()});
 190     assert(std::ranges::equal(out, expected));
 191     assert(base(result.in) == in.data() + in.size());
 192     assert(base(result.out) == out.data() + out.size());
 193   }
 194
 195   // range overload
 196   {
 197     std::array<int, N2> out;
 198     std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};
 199     std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =
 200         std::ranges::unique_copy(r, OutIter{out.begin()});
 201     assert(std::ranges::equal(out, expected));
 202     assert(base(result.in) == in.data() + in.size());
 203     assert(base(result.out) == out.data() + out.size());
 204   }
 205 }
 206
 207 template <class InIter, class OutIter, template <class> class SentWrapper>
 208 constexpr void testImpl() {
 209   // no consecutive elements
 210   {
 211     std::array in{1, 2, 3, 2, 1};
 212     std::array expected{1, 2, 3, 2, 1};
 213     testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
 214   }
 215
 216   // one group of consecutive elements
 217   {
 218     std::array in{2, 3, 3, 3, 4, 3};
 219     std::array expected{2, 3, 4, 3};
 220     testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
 221   }
 222
 223   // multiple groups of consecutive elements
 224   {
 225     std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5};
 226     std::array expected{2, 3, 4, 3, 5};
 227     testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
 228   }
 229
 230   // all the same
 231   {
 232     std::array in{1, 1, 1, 1, 1, 1};
 233     std::array expected{1};
 234     testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
 235   }
 236
 237   // empty range
 238   {
 239     std::array<int, 0> in{};
 240     std::array<int, 0> expected{};
 241     testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
 242   }
 243 }
 244
 245 template <class OutIter, template <class> class SentWrapper>
 246 constexpr void withAllPermutationsOfInIter() {
 247   testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>();
 248   testImpl<forward_iterator<int*>, OutIter, SentWrapper>();
 249   testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>();
 250   testImpl<random_access_iterator<int*>, OutIter, SentWrapper>();
 251   testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>();
 252   testImpl<int*, OutIter, SentWrapper>();
 253 }
 254
 255 template <template <class> class SentWrapper>
 256 constexpr void withAllPermutationsOfInIterAndOutIter() {
 257   withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
 258   withAllPermutationsOfInIter<forward_iterator<int*>, SentWrapper>();
 259   withAllPermutationsOfInIter<bidirectional_iterator<int*>, SentWrapper>();
 260   withAllPermutationsOfInIter<random_access_iterator<int*>, SentWrapper>();
 261   withAllPermutationsOfInIter<contiguous_iterator<int*>, SentWrapper>();
 262   withAllPermutationsOfInIter<int*, SentWrapper>();
 263 }
 264
 265 constexpr bool test() {
 266   withAllPermutationsOfInIterAndOutIter<std::type_identity_t>();
 267   withAllPermutationsOfInIterAndOutIter<sentinel_wrapper>();
 268
 269   // Test the overload that re-reads from the input iterator
 270   // forward_iterator<I>
 271   // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
 272   // !indirectly_copyable_storable<I, O>
 273   {
 274     MoveOnly in[5] = {1, 3, 3, 3, 1};
 275     // iterator overload
 276     {
 277       AssignableFromMoveOnly out[3] = {};
 278       auto result                   = std::ranges::unique_copy(in, in + 5, out);
 279       assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));
 280       assert(result.in == in + 5);
 281       assert(result.out == out + 3);
 282     }
 283     // range overload
 284     {
 285       AssignableFromMoveOnly out[3] = {};
 286       auto result                   = std::ranges::unique_copy(std::ranges::subrange{in, in + 5}, out);
 287       assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));
 288       assert(result.in == in + 5);
 289       assert(result.out == out + 3);
 290     }
 291   }
 292
 293   // Test the overload that re-reads from the output iterator
 294   // !forward_iterator<I>
 295   // (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
 296   // !indirectly_copyable_storable<I, O>
 297   {
 298     using InIter                             = cpp20_input_iterator<CopyAssignableNotCopyConstructible*>;
 299     using Sent                               = sentinel_wrapper<InIter>;
 300     CopyAssignableNotCopyConstructible in[6] = {1, 1, 2, 2, 3, 3};
 301     // iterator overload
 302     {
 303       CopyAssignableNotCopyConstructible out[3];
 304       auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 6}}, InputAndOutputIterator{out});
 305       assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));
 306       assert(base(result.in) == in + 6);
 307       assert(base(result.out) == out + 3);
 308     }
 309     // range overload
 310     {
 311       CopyAssignableNotCopyConstructible out[3];
 312       auto r      = std::ranges::subrange(InIter{in}, Sent{InIter{in + 6}});
 313       auto result = std::ranges::unique_copy(r, InputAndOutputIterator{out});
 314       assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));
 315       assert(base(result.in) == in + 6);
 316       assert(base(result.out) == out + 3);
 317     }
 318   }
 319
 320   // Test the overload that reads from the temporary copy of the value
 321   // !forward_iterator<I>
 322   // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
 323   // indirectly_copyable_storable<I, O>
 324   {
 325     using InIter = cpp20_input_iterator<int*>;
 326     using Sent   = sentinel_wrapper<InIter>;
 327     int in[4]    = {1, 1, 1, 2};
 328     // iterator overload
 329     {
 330       int out[2];
 331       auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 4}}, cpp20_output_iterator<int*>{out});
 332       assert(std::ranges::equal(out, std::array{1, 2}));
 333       assert(base(result.in) == in + 4);
 334       assert(base(result.out) == out + 2);
 335     }
 336     // range overload
 337     {
 338       int out[2];
 339       auto r      = std::ranges::subrange(InIter{in}, Sent{InIter{in + 4}});
 340       auto result = std::ranges::unique_copy(r, cpp20_output_iterator<int*>{out});
 341       assert(std::ranges::equal(out, std::array{1, 2}));
 342       assert(base(result.in) == in + 4);
 343       assert(base(result.out) == out + 2);
 344     }
 345   }
 346
 347   struct Data {
 348     int data;
 349   };
 350
 351   // Test custom comparator
 352   {
 353     std::array in{Data{4}, Data{8}, Data{8}, Data{8}};
 354     std::array expected{Data{4}, Data{8}};
 355     const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; };
 356
 357     // iterator overload
 358     {
 359       std::array<Data, 2> out;
 360       auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), comp);
 361       assert(std::ranges::equal(out, expected, comp));
 362       assert(base(result.in) == in.begin() + 4);
 363       assert(base(result.out) == out.begin() + 2);
 364     }
 365
 366     // range overload
 367     {
 368       std::array<Data, 2> out;
 369       auto result = std::ranges::unique_copy(in, out.begin(), comp);
 370       assert(std::ranges::equal(out, expected, comp));
 371       assert(base(result.in) == in.begin() + 4);
 372       assert(base(result.out) == out.begin() + 2);
 373     }
 374   }
 375
 376   // Test custom projection
 377   {
 378     std::array in{Data{4}, Data{8}, Data{8}, Data{8}};
 379     std::array expected{Data{4}, Data{8}};
 380
 381     const auto proj = &Data::data;
 382
 383     // iterator overload
 384     {
 385       std::array<Data, 2> out;
 386       auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), {}, proj);
 387       assert(std::ranges::equal(out, expected, {}, proj, proj));
 388       assert(base(result.in) == in.begin() + 4);
 389       assert(base(result.out) == out.begin() + 2);
 390     }
 391
 392     // range overload
 393     {
 394       std::array<Data, 2> out;
 395       auto result = std::ranges::unique_copy(in, out.begin(), {}, proj);
 396       assert(std::ranges::equal(out, expected, {}, proj, proj));
 397       assert(base(result.in) == in.begin() + 4);
 398       assert(base(result.out) == out.begin() + 2);
 399     }
 400   }
 401
 402   // Exactly last - first - 1 applications of the corresponding predicate and no
 403   // more than twice as many applications of any projection.
 404   {
 405     std::array in{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1};
 406     std::array expected{1, 2, 3, 4, 3, 5, 6, 1};
 407     // iterator overload
 408     {
 409       std::array<int, 8> out;
 410       int numberOfComp = 0;
 411       int numberOfProj = 0;
 412       auto result      = std::ranges::unique_copy(
 413           in.begin(),
 414           in.end(),
 415           out.begin(),
 416           counting_predicate{std::ranges::equal_to{}, numberOfComp},
 417           counting_projection{numberOfProj});
 418       assert(std::ranges::equal(out, expected));
 419       assert(base(result.in) == in.end());
 420       assert(base(result.out) == out.end());
 421       assert(numberOfComp == in.size() - 1);
 422       assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
 423     }
 424     // range overload
 425     {
 426       std::array<int, 8> out;
 427       int numberOfComp = 0;
 428       int numberOfProj = 0;
 429       auto result      = std::ranges::unique_copy(
 430           in,
 431           out.begin(),
 432           counting_predicate{std::ranges::equal_to{}, numberOfComp},
 433           counting_projection{numberOfProj});
 434       assert(std::ranges::equal(out, expected));
 435       assert(base(result.in) == in.end());
 436       assert(base(result.out) == out.end());
 437       assert(numberOfComp == in.size() - 1);
 438       assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
 439     }
 440   }
 441   return true;
 442 }
 443
 444 int main(int, char**) {
 445   test();
 446   static_assert(test());
 447
 448   return 0;
 449 }