334 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<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>14// requires (forward_iterator<I> || random_access_iterator<O>) &&15// indirectly_copyable<I, O> &&16// uniform_random_bit_generator<remove_reference_t<Gen>>17// O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g); // Since C++2018//19// template<input_range R, weakly_incrementable O, class Gen>20// requires (forward_range<R> || random_access_iterator<O>) &&21// indirectly_copyable<iterator_t<R>, O> &&22// uniform_random_bit_generator<remove_reference_t<Gen>>23// O sample(R&& r, O out, range_difference_t<R> n, Gen&& g); // Since C++2024 25#include <algorithm>26#include <array>27#include <concepts>28#include <functional>29#include <random>30#include <ranges>31#include <utility>32 33#include "almost_satisfies_types.h"34#include "test_iterators.h"35#include "test_macros.h"36 37class RandGen {38public:39 constexpr static std::size_t min() { return 0; }40 constexpr static std::size_t max() { return 255; }41 42 constexpr std::size_t operator()() {43 flip = !flip;44 return flip;45 }46 47private:48 bool flip = false;49};50 51static_assert(std::uniform_random_bit_generator<RandGen>);52// `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that53// a type satisfying the required minimum is still accepted by `ranges::shuffle`.54LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);55 56struct BadGen {57 constexpr static std::size_t min() { return 255; }58 constexpr static std::size_t max() { return 0; }59 constexpr std::size_t operator()() const;60};61static_assert(!std::uniform_random_bit_generator<BadGen>);62 63// Test constraints of the (iterator, sentinel) overload.64// ======================================================65 66template <class Iter = int*, class Sent = int*, class Out = int*, class Gen = RandGen>67concept HasSampleIter =68 requires(Iter&& iter, Sent&& sent, Out&& out, std::iter_difference_t<Iter> n, Gen&& gen) {69 std::ranges::sample(std::forward<Iter>(iter), std::forward<Sent>(sent),70 std::forward<Out>(out), n, std::forward<Gen>(gen));71 };72 73static_assert(HasSampleIter<int*, int*, int*, RandGen>);74 75// !input_iterator<I>76static_assert(!HasSampleIter<InputIteratorNotDerivedFrom>);77static_assert(!HasSampleIter<InputIteratorNotIndirectlyReadable>);78static_assert(!HasSampleIter<InputIteratorNotInputOrOutputIterator>);79 80// !sentinel_for<S, I>81static_assert(!HasSampleIter<int*, SentinelForNotSemiregular>);82static_assert(!HasSampleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);83 84// !weakly_incrementable<O>85static_assert(!HasSampleIter<int*, int*, WeaklyIncrementableNotMovable>);86 87// (forward_iterator<I> || random_access_iterator<O>)88static_assert(HasSampleIter<89 forward_iterator<int*>, forward_iterator<int*>,90 cpp20_output_iterator<int*>91>);92static_assert(HasSampleIter<93 cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>,94 random_access_iterator<int*>95>);96// !(forward_iterator<I> || random_access_iterator<O>)97static_assert(!HasSampleIter<98 cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>,99 cpp20_output_iterator<int*>100>);101 102// !indirectly_copyable<I, O>103static_assert(!HasSampleIter<int*, int*, int**>);104 105// !uniform_random_bit_generator<remove_reference_t<Gen>>106static_assert(!HasSampleIter<int*, int*, int*, BadGen>);107 108// Test constraints of the (range) overload.109// =========================================110 111template <class Range, class Out = int*, class Gen = RandGen>112concept HasSampleRange =113 requires(Range&& range, Out&& out, std::ranges::range_difference_t<Range> n, Gen&& gen) {114 std::ranges::sample(std::forward<Range>(range), std::forward<Out>(out), n, std::forward<Gen>(gen));115 };116 117template <class T>118using R = UncheckedRange<T>;119 120static_assert(HasSampleRange<R<int*>, int*, RandGen>);121 122// !input_range<R>123static_assert(!HasSampleRange<InputRangeNotDerivedFrom>);124static_assert(!HasSampleRange<InputRangeNotIndirectlyReadable>);125static_assert(!HasSampleRange<InputRangeNotInputOrOutputIterator>);126 127// !weakly_incrementable<O>128static_assert(!HasSampleRange<R<int*>, WeaklyIncrementableNotMovable>);129 130// (forward_range<R> || random_access_iterator<O>)131static_assert(HasSampleRange<132 R<forward_iterator<int*>>,133 cpp20_output_iterator<int*>134>);135static_assert(HasSampleRange<136 R<cpp20_input_iterator<int*>>,137 random_access_iterator<int*>138>);139// !(forward_range<R> || random_access_iterator<O>)140static_assert(!HasSampleRange<141 R<cpp20_input_iterator<int*>>,142 cpp20_output_iterator<int*>143>);144 145// !indirectly_copyable<I, O>146static_assert(!HasSampleRange<R<int*>, int**>);147 148// !uniform_random_bit_generator<remove_reference_t<Gen>>149static_assert(!HasSampleRange<R<int*>, int*, BadGen>);150 151template <class Iter, class Sent, class Out, std::size_t N, class Gen>152void test_one(std::array<int, N> in, std::size_t n, Gen gen) {153 assert(n <= static_cast<std::size_t>(N));154 155 auto verify_is_subsequence = [&] (auto output) {156 auto sorted_input = in;157 std::ranges::sort(sorted_input);158 auto sorted_output = std::ranges::subrange(output.begin(), output.begin() + n);159 std::ranges::sort(sorted_output);160 assert(std::ranges::includes(sorted_input, sorted_output));161 };162 163 { // (iterator, sentinel) overload.164 auto begin = Iter(in.data());165 auto end = Sent(Iter(in.data() + in.size()));166 std::array<int, N> output;167 auto out = Out(output.data());168 169 std::same_as<Out> decltype(auto) result = std::ranges::sample(170 std::move(begin), std::move(end), std::move(out), n, gen);171 assert(base(result) == output.data() + n);172 verify_is_subsequence(output);173 // The output of `sample` is implementation-specific.174 }175 176 { // (range) overload.177 auto begin = Iter(in.data());178 auto end = Sent(Iter(in.data() + in.size()));179 std::array<int, N> output;180 auto out = Out(output.data());181 182 std::same_as<Out> decltype(auto) result = std::ranges::sample(std::ranges::subrange(183 std::move(begin), std::move(end)), std::move(out), n, gen);184 assert(base(result) == output.data() + n);185 verify_is_subsequence(output);186 // The output of `sample` is implementation-specific.187 }188}189 190template <class Iter, class Sent, class Out>191void test_iterators_iter_sent_out() {192 RandGen gen;193 194 // Empty sequence.195 test_one<Iter, Sent, Out, 0>({}, 0, gen);196 // 1-element sequence.197 test_one<Iter, Sent, Out, 1>({1}, 1, gen);198 // 2-element sequence.199 test_one<Iter, Sent, Out, 2>({1, 2}, 1, gen);200 test_one<Iter, Sent, Out, 2>({1, 2}, 2, gen);201 // n == 0.202 test_one<Iter, Sent, Out, 3>({1, 2, 3}, 0, gen);203 204 // Longer sequence.205 {206 std::array input = {1, 8, 2, 3, 4, 6, 5, 7};207 for (int i = 0; i <= static_cast<int>(input.size()); ++i){208 test_one<Iter, Sent, Out, input.size()>(input, i, gen);209 }210 }211}212 213template <class Iter, class Sent>214void test_iterators_iter_sent() {215 if constexpr (std::forward_iterator<Iter>) {216 test_iterators_iter_sent_out<Iter, Sent, cpp20_output_iterator<int*>>();217 test_iterators_iter_sent_out<Iter, Sent, forward_iterator<int*>>();218 }219 test_iterators_iter_sent_out<Iter, Sent, random_access_iterator<int*>>();220 test_iterators_iter_sent_out<Iter, Sent, contiguous_iterator<int*>>();221 test_iterators_iter_sent_out<Iter, Sent, int*>();222}223 224template <class Iter>225void test_iterators_iter() {226 if constexpr (std::sentinel_for<Iter, Iter>) {227 test_iterators_iter_sent<Iter, Iter>();228 }229 test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();230}231 232void test_iterators() {233 test_iterators_iter<cpp20_input_iterator<int*>>();234 test_iterators_iter<random_access_iterator<int*>>();235 test_iterators_iter<contiguous_iterator<int*>>();236 test_iterators_iter<int*>();237 test_iterators_iter<const int*>();238}239 240// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of241// the given generator object.242template <class Gen, bool CheckConst = true>243void test_generator() {244 std::array in = {1, 2, 3, 4, 5, 6, 7, 8};245 constexpr int N = 5;246 std::array<int, N> output;247 auto begin = in.begin();248 auto end = in.end();249 auto out = output.begin();250 251 { // Lvalue.252 Gen g;253 std::ranges::sample(begin, end, out, N, g);254 std::ranges::sample(in, out, N, g);255 }256 257 if constexpr (CheckConst) { // Const lvalue.258 const Gen g;259 std::ranges::sample(begin, end, out, N, g);260 std::ranges::sample(in, out, N, g);261 }262 263 { // Prvalue.264 std::ranges::sample(begin, end, out, N, Gen());265 std::ranges::sample(in, out, N, Gen());266 }267 268 { // Xvalue.269 Gen g1, g2;270 std::ranges::sample(begin, end, out, N, std::move(g1));271 std::ranges::sample(in, out, N, std::move(g2));272 }273}274 275// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given276// generator class has a const or non-const invocation operator (or both).277void test_generators() {278 struct GenBase {279 constexpr static std::size_t min() { return 0; }280 constexpr static std::size_t max() { return 255; }281 };282 struct NonconstGen : GenBase {283 std::size_t operator()() { return 1; }284 };285 struct ConstGen : GenBase {286 std::size_t operator()() const { return 1; }287 };288 struct ConstAndNonconstGen : GenBase {289 std::size_t operator()() { return 1; }290 std::size_t operator()() const { return 1; }291 };292 293 test_generator<ConstGen>();294 test_generator<NonconstGen, /*CheckConst=*/false>();295 test_generator<ConstAndNonconstGen>();296}297 298void test() {299 test_iterators();300 test_generators();301 302 { // Stable (if `I` models `forward_iterator`).303 struct OrderedValue {304 int value;305 int original_order;306 bool operator==(const OrderedValue&) const = default;307 auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; }308 };309 310 const std::array<OrderedValue, 8> in = {{311 {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}312 }};313 314 { // (iterator, sentinel) overload.315 std::array<OrderedValue, in.size()> out;316 std::ranges::sample(in.begin(), in.end(), out.begin(), in.size(), RandGen());317 assert(out == in);318 }319 320 { // (range) overload.321 std::array<OrderedValue, in.size()> out;322 std::ranges::sample(in, out.begin(), in.size(), RandGen());323 assert(out == in);324 }325 }326}327 328int main(int, char**) {329 test();330 // Note: `ranges::sample` is not `constexpr`.331 332 return 0;333}334