269 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<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++2017//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++2022 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 35class RandGen {36public: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 45private:46 bool flip = false;47};48 49static_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 that51// a type satisfying the required minimum is still accepted by `ranges::shuffle`.52LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);53 54struct 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};59static_assert(!std::uniform_random_bit_generator<BadGen>);60 61// Test constraints of the (iterator, sentinel) overload.62// ======================================================63 64template <class Iter = int*, class Sent = int*, class Gen = RandGen>65concept 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 70static_assert(HasShuffleIter<int*, int*, RandGen>);71 72// !random_access_iterator<I>73static_assert(!HasShuffleIter<RandomAccessIteratorNotDerivedFrom>);74static_assert(!HasShuffleIter<RandomAccessIteratorBadIndex>);75 76// !sentinel_for<S, I>77static_assert(!HasShuffleIter<int*, SentinelForNotSemiregular>);78static_assert(!HasShuffleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);79 80// !permutable<I>81static_assert(!HasShuffleIter<PermutableNotForwardIterator>);82static_assert(!HasShuffleIter<PermutableNotSwappable>);83 84// !uniform_random_bit_generator<remove_reference_t<Gen>>85static_assert(!HasShuffleIter<int*, int*, BadGen>);86 87// Test constraints of the (range) overload.88// =========================================89 90template <class Range, class Gen = RandGen>91concept HasShuffleRange =92 requires(Range&& range, Gen&& gen) {93 std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen));94 };95 96template <class T>97using R = UncheckedRange<T>;98 99static_assert(HasShuffleRange<R<int*>, RandGen>);100 101// !random_access_range<R>102static_assert(!HasShuffleRange<RandomAccessRangeNotDerivedFrom>);103static_assert(!HasShuffleRange<RandomAccessRangeBadIndex>);104 105// !permutable<iterator_t<R>>106static_assert(!HasShuffleRange<PermutableNotForwardIterator>);107static_assert(!HasShuffleRange<PermutableNotSwappable>);108 109// !uniform_random_bit_generator<remove_reference_t<Gen>>110static_assert(!HasShuffleRange<R<int*>, BadGen>);111 112template <class Iter, class Sent, std::size_t N, class Gen>113void 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 154template <class Iter, class Sent>155void 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 174template <class Iter>175void test_iterators_iter() {176 test_iterators_iter_sent<Iter, Iter>();177 test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();178}179 180void 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 of187// the given generator object.188template <class Gen, bool CheckConst = true>189void 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 given219// generator class has a const or non-const invocation operator (or both).220void 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 241void 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}; //14248 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 swaps256 // might be less than specified in the standard.257 assert(swaps <= expected);258 swaps = 0;259 }260 }261}262 263int main(int, char**) {264 test();265 // Note: `ranges::shuffle` is not `constexpr`.266 267 return 0;268}269