libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.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<random_access_iterator I, sentinel_for<I> S, class Gen>
  14 //   requires permutable<I> &&
  15 //            uniform_random_bit_generator<remove_reference_t<Gen>>
  16 //   I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
  17 //
  18 // template<random_access_range R, class Gen>
  19 //   requires permutable<iterator_t<R>> &&
  20 //            uniform_random_bit_generator<remove_reference_t<Gen>>
  21 //   borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20
  22
  23 #include <algorithm>
  24 #include <array>
  25 #include <concepts>
  26 #include <functional>
  27 #include <random>
  28 #include <ranges>
  29 #include <utility>
  30
  31 #include "almost_satisfies_types.h"
  32 #include "test_iterators.h"
  33 #include "test_macros.h"
  34
  35 class RandGen {
  36 public:
  37   constexpr static std::size_t min() { return 0; }
  38   constexpr static std::size_t max() { return 255; }
  39
  40   constexpr std::size_t operator()() {
  41     flip = !flip;
  42     return flip;
  43   }
  44
  45 private:
  46   bool flip = false;
  47 };
  48
  49 static_assert(std::uniform_random_bit_generator<RandGen>);
  50 // `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that
  51 // a type satisfying the required minimum is still accepted by `ranges::shuffle`.
  52 LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
  53
  54 struct BadGen {
  55   constexpr static std::size_t min() { return 255; }
  56   constexpr static std::size_t max() { return 0; }
  57   constexpr std::size_t operator()() const;
  58 };
  59 static_assert(!std::uniform_random_bit_generator<BadGen>);
  60
  61 // Test constraints of the (iterator, sentinel) overload.
  62 // ======================================================
  63
  64 template <class Iter = int*, class Sent = int*, class Gen = RandGen>
  65 concept HasShuffleIter =
  66     requires(Iter&& iter, Sent&& sent, Gen&& gen) {
  67       std::ranges::shuffle(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen));
  68     };
  69
  70 static_assert(HasShuffleIter<int*, int*, RandGen>);
  71
  72 // !random_access_iterator<I>
  73 static_assert(!HasShuffleIter<RandomAccessIteratorNotDerivedFrom>);
  74 static_assert(!HasShuffleIter<RandomAccessIteratorBadIndex>);
  75
  76 // !sentinel_for<S, I>
  77 static_assert(!HasShuffleIter<int*, SentinelForNotSemiregular>);
  78 static_assert(!HasShuffleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
  79
  80 // !permutable<I>
  81 static_assert(!HasShuffleIter<PermutableNotForwardIterator>);
  82 static_assert(!HasShuffleIter<PermutableNotSwappable>);
  83
  84 // !uniform_random_bit_generator<remove_reference_t<Gen>>
  85 static_assert(!HasShuffleIter<int*, int*, BadGen>);
  86
  87 // Test constraints of the (range) overload.
  88 // =========================================
  89
  90 template <class Range, class Gen = RandGen>
  91 concept HasShuffleRange =
  92     requires(Range&& range, Gen&& gen) {
  93       std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen));
  94     };
  95
  96 template <class T>
  97 using R = UncheckedRange<T>;
  98
  99 static_assert(HasShuffleRange<R<int*>, RandGen>);
 100
 101 // !random_access_range<R>
 102 static_assert(!HasShuffleRange<RandomAccessRangeNotDerivedFrom>);
 103 static_assert(!HasShuffleRange<RandomAccessRangeBadIndex>);
 104
 105 // !permutable<iterator_t<R>>
 106 static_assert(!HasShuffleRange<PermutableNotForwardIterator>);
 107 static_assert(!HasShuffleRange<PermutableNotSwappable>);
 108
 109 // !uniform_random_bit_generator<remove_reference_t<Gen>>
 110 static_assert(!HasShuffleRange<R<int*>, BadGen>);
 111
 112 template <class Iter, class Sent, std::size_t N, class Gen>
 113 void test_one(const std::array<int, N> input, Gen gen) {
 114   { // (iterator, sentinel) overload.
 115     auto shuffled = input;
 116     auto begin = Iter(shuffled.data());
 117     auto end = Sent(Iter(shuffled.data() + shuffled.size()));
 118
 119     std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(begin, end, gen);
 120
 121     assert(result == Iter(shuffled.data() + shuffled.size()));
 122     // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
 123     //assert(std::ranges::is_permutation(shuffled, input);
 124     {
 125       auto shuffled_sorted = shuffled;
 126       std::ranges::sort(shuffled_sorted);
 127       auto original_sorted = input;
 128       std::ranges::sort(original_sorted);
 129       assert(shuffled_sorted == original_sorted);
 130     }
 131   }
 132
 133   { // (range) overload.
 134     auto shuffled = input;
 135     auto begin = Iter(shuffled.data());
 136     auto end = Sent(Iter(shuffled.data() + shuffled.size()));
 137     auto range = std::ranges::subrange(begin, end);
 138
 139     std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(range, gen);
 140
 141     assert(result == Iter(shuffled.data() + shuffled.size()));
 142     // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
 143     //assert(std::ranges::is_permutation(shuffled, input);
 144     {
 145       auto shuffled_sorted = shuffled;
 146       std::ranges::sort(shuffled_sorted);
 147       auto original_sorted = input;
 148       std::ranges::sort(original_sorted);
 149       assert(shuffled_sorted == original_sorted);
 150     }
 151   }
 152 }
 153
 154 template <class Iter, class Sent>
 155 void test_iterators_iter_sent() {
 156   RandGen gen;
 157
 158   // Empty sequence.
 159   test_one<Iter, Sent, 0>({}, gen);
 160   // 1-element sequence.
 161   test_one<Iter, Sent, 1>({1}, gen);
 162   // 2-element sequence.
 163   test_one<Iter, Sent, 2>({2, 1}, gen);
 164   // 3-element sequence.
 165   test_one<Iter, Sent, 3>({2, 1, 3}, gen);
 166   // Longer sequence.
 167   test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, gen);
 168   // Longer sequence with duplicates.
 169   test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, gen);
 170   // All elements are the same.
 171   test_one<Iter, Sent, 3>({1, 1, 1}, gen);
 172 }
 173
 174 template <class Iter>
 175 void test_iterators_iter() {
 176   test_iterators_iter_sent<Iter, Iter>();
 177   test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
 178 }
 179
 180 void test_iterators() {
 181   test_iterators_iter<random_access_iterator<int*>>();
 182   test_iterators_iter<contiguous_iterator<int*>>();
 183   test_iterators_iter<int*>();
 184 }
 185
 186 // Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of
 187 // the given generator object.
 188 template <class Gen, bool CheckConst = true>
 189 void test_generator() {
 190   std::array in = {1, 2, 3, 4, 5, 6, 7, 8};
 191   auto begin = in.begin();
 192   auto end = in.end();
 193
 194   { // Lvalue.
 195     Gen g;
 196     std::ranges::shuffle(begin, end, g);
 197     std::ranges::shuffle(in, g);
 198   }
 199
 200   if constexpr (CheckConst) { // Const lvalue.
 201     const Gen g;
 202     std::ranges::shuffle(begin, end, g);
 203     std::ranges::shuffle(in, g);
 204   }
 205
 206   { // Prvalue.
 207     std::ranges::shuffle(begin, end, Gen());
 208     std::ranges::shuffle(in, Gen());
 209   }
 210
 211   { // Xvalue.
 212     Gen g1, g2;
 213     std::ranges::shuffle(begin, end, std::move(g1));
 214     std::ranges::shuffle(in, std::move(g2));
 215   }
 216 }
 217
 218 // Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given
 219 // generator class has a const or non-const invocation operator (or both).
 220 void test_generators() {
 221   struct GenBase {
 222     constexpr static std::size_t min() { return 0; }
 223     constexpr static std::size_t max() { return 255; }
 224   };
 225   struct NonconstGen : GenBase {
 226     std::size_t operator()() { return 1; }
 227   };
 228   struct ConstGen : GenBase {
 229     std::size_t operator()() const { return 1; }
 230   };
 231   struct ConstAndNonconstGen : GenBase {
 232     std::size_t operator()() { return 1; }
 233     std::size_t operator()() const { return 1; }
 234   };
 235
 236   test_generator<ConstGen>();
 237   test_generator<NonconstGen, /*CheckConst=*/false>();
 238   test_generator<ConstAndNonconstGen>();
 239 }
 240
 241 void test() {
 242   test_iterators();
 243   test_generators();
 244
 245   { // Complexity: Exactly `(last - first) - 1` swaps.
 246     {
 247       std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; //14
 248
 249       int swaps = 0;
 250       auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
 251       auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
 252
 253       std::ranges::shuffle(begin, end, RandGen());
 254       int expected = in.size() - 1;
 255       // Note: our implementation doesn't perform a swap when the distribution returns 0, so the actual number of swaps
 256       // might be less than specified in the standard.
 257       assert(swaps <= expected);
 258       swaps = 0;
 259     }
 260   }
 261 }
 262
 263 int main(int, char**) {
 264   test();
 265   // Note: `ranges::shuffle` is not `constexpr`.
 266
 267   return 0;
 268 }