libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.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 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++20
  18 //
  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++20
  24
  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
  37 class RandGen {
  38 public:
  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
  47 private:
  48   bool flip = false;
  49 };
  50
  51 static_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 that
  53 // a type satisfying the required minimum is still accepted by `ranges::shuffle`.
  54 LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
  55
  56 struct 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 };
  61 static_assert(!std::uniform_random_bit_generator<BadGen>);
  62
  63 // Test constraints of the (iterator, sentinel) overload.
  64 // ======================================================
  65
  66 template <class Iter = int*, class Sent = int*, class Out = int*, class Gen = RandGen>
  67 concept 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
  73 static_assert(HasSampleIter<int*, int*, int*, RandGen>);
  74
  75 // !input_iterator<I>
  76 static_assert(!HasSampleIter<InputIteratorNotDerivedFrom>);
  77 static_assert(!HasSampleIter<InputIteratorNotIndirectlyReadable>);
  78 static_assert(!HasSampleIter<InputIteratorNotInputOrOutputIterator>);
  79
  80 // !sentinel_for<S, I>
  81 static_assert(!HasSampleIter<int*, SentinelForNotSemiregular>);
  82 static_assert(!HasSampleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
  83
  84 // !weakly_incrementable<O>
  85 static_assert(!HasSampleIter<int*, int*, WeaklyIncrementableNotMovable>);
  86
  87 // (forward_iterator<I> || random_access_iterator<O>)
  88 static_assert(HasSampleIter<
  89     forward_iterator<int*>, forward_iterator<int*>,
  90     cpp20_output_iterator<int*>
  91 >);
  92 static_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>)
  97 static_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>
 103 static_assert(!HasSampleIter<int*, int*, int**>);
 104
 105 // !uniform_random_bit_generator<remove_reference_t<Gen>>
 106 static_assert(!HasSampleIter<int*, int*, int*, BadGen>);
 107
 108 // Test constraints of the (range) overload.
 109 // =========================================
 110
 111 template <class Range, class Out = int*, class Gen = RandGen>
 112 concept 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
 117 template <class T>
 118 using R = UncheckedRange<T>;
 119
 120 static_assert(HasSampleRange<R<int*>, int*, RandGen>);
 121
 122 // !input_range<R>
 123 static_assert(!HasSampleRange<InputRangeNotDerivedFrom>);
 124 static_assert(!HasSampleRange<InputRangeNotIndirectlyReadable>);
 125 static_assert(!HasSampleRange<InputRangeNotInputOrOutputIterator>);
 126
 127 // !weakly_incrementable<O>
 128 static_assert(!HasSampleRange<R<int*>, WeaklyIncrementableNotMovable>);
 129
 130 // (forward_range<R> || random_access_iterator<O>)
 131 static_assert(HasSampleRange<
 132     R<forward_iterator<int*>>,
 133     cpp20_output_iterator<int*>
 134 >);
 135 static_assert(HasSampleRange<
 136     R<cpp20_input_iterator<int*>>,
 137     random_access_iterator<int*>
 138 >);
 139 // !(forward_range<R> || random_access_iterator<O>)
 140 static_assert(!HasSampleRange<
 141     R<cpp20_input_iterator<int*>>,
 142     cpp20_output_iterator<int*>
 143 >);
 144
 145 // !indirectly_copyable<I, O>
 146 static_assert(!HasSampleRange<R<int*>, int**>);
 147
 148 // !uniform_random_bit_generator<remove_reference_t<Gen>>
 149 static_assert(!HasSampleRange<R<int*>, int*, BadGen>);
 150
 151 template <class Iter, class Sent, class Out, std::size_t N, class Gen>
 152 void 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.begin());
 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.begin());
 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
 190 template <class Iter, class Sent, class Out>
 191 void 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
 213 template <class Iter, class Sent>
 214 void 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
 224 template <class Iter>
 225 void 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
 232 void 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 of
 241 // the given generator object.
 242 template <class Gen, bool CheckConst = true>
 243 void 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 given
 276 // generator class has a const or non-const invocation operator (or both).
 277 void 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
 298 void 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
 328 int main(int, char**) {
 329   test();
 330   // Note: `ranges::sample` is not `constexpr`.
 331
 332   return 0;
 333 }