From 1b6a04ca5504955c571d1c97504fb45ea0befee4 Mon Sep 17 00:00:00 2001
From: Valentin Popov <valentin@popov.link>
Date: Mon, 8 Jan 2024 01:21:28 +0400
Subject: Initial vendor packages
Signed-off-by: Valentin Popov <valentin@popov.link>
---
vendor/rand/src/seq.rs | 337 +++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 337 insertions(+)
create mode 100644 vendor/rand/src/seq.rs
(limited to 'vendor/rand/src/seq.rs')
diff --git a/vendor/rand/src/seq.rs b/vendor/rand/src/seq.rs
new file mode 100644
index 0000000..a7889fe
--- /dev/null
+++ b/vendor/rand/src/seq.rs
@@ -0,0 +1,337 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Functions for randomly accessing and sampling sequences.
+
+use super::Rng;
+
+// This crate is only enabled when either std or alloc is available.
+// BTreeMap is not as fast in tests, but better than nothing.
+#[cfg(feature="std")] use std::collections::HashMap;
+#[cfg(not(feature="std"))] use alloc::btree_map::BTreeMap;
+
+#[cfg(not(feature="std"))] use alloc::Vec;
+
+/// Randomly sample `amount` elements from a finite iterator.
+///
+/// The following can be returned:
+/// - `Ok`: `Vec` of `amount` non-repeating randomly sampled elements. The order is not random.
+/// - `Err`: `Vec` of all the elements from `iterable` in sequential order. This happens when the
+/// length of `iterable` was less than `amount`. This is considered an error since exactly
+/// `amount` elements is typically expected.
+///
+/// This implementation uses `O(len(iterable))` time and `O(amount)` memory.
+///
+/// # Example
+///
+/// ```rust
+/// use rand::{thread_rng, seq};
+///
+/// let mut rng = thread_rng();
+/// let sample = seq::sample_iter(&mut rng, 1..100, 5).unwrap();
+/// println!("{:?}", sample);
+/// ```
+pub fn sample_iter<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Result<Vec<T>, Vec<T>>
+ where I: IntoIterator<Item=T>,
+ R: Rng,
+{
+ let mut iter = iterable.into_iter();
+ let mut reservoir = Vec::with_capacity(amount);
+ reservoir.extend(iter.by_ref().take(amount));
+
+ // Continue unless the iterator was exhausted
+ //
+ // note: this prevents iterators that "restart" from causing problems.
+ // If the iterator stops once, then so do we.
+ if reservoir.len() == amount {
+ for (i, elem) in iter.enumerate() {
+ let k = rng.gen_range(0, i + 1 + amount);
+ if let Some(spot) = reservoir.get_mut(k) {
+ *spot = elem;
+ }
+ }
+ Ok(reservoir)
+ } else {
+ // Don't hang onto extra memory. There is a corner case where
+ // `amount` was much less than `len(iterable)`.
+ reservoir.shrink_to_fit();
+ Err(reservoir)
+ }
+}
+
+/// Randomly sample exactly `amount` values from `slice`.
+///
+/// The values are non-repeating and in random order.
+///
+/// This implementation uses `O(amount)` time and memory.
+///
+/// Panics if `amount > slice.len()`
+///
+/// # Example
+///
+/// ```rust
+/// use rand::{thread_rng, seq};
+///
+/// let mut rng = thread_rng();
+/// let values = vec![5, 6, 1, 3, 4, 6, 7];
+/// println!("{:?}", seq::sample_slice(&mut rng, &values, 3));
+/// ```
+pub fn sample_slice<R, T>(rng: &mut R, slice: &[T], amount: usize) -> Vec<T>
+ where R: Rng,
+ T: Clone
+{
+ let indices = sample_indices(rng, slice.len(), amount);
+
+ let mut out = Vec::with_capacity(amount);
+ out.extend(indices.iter().map(|i| slice[*i].clone()));
+ out
+}
+
+/// Randomly sample exactly `amount` references from `slice`.
+///
+/// The references are non-repeating and in random order.
+///
+/// This implementation uses `O(amount)` time and memory.
+///
+/// Panics if `amount > slice.len()`
+///
+/// # Example
+///
+/// ```rust
+/// use rand::{thread_rng, seq};
+///
+/// let mut rng = thread_rng();
+/// let values = vec![5, 6, 1, 3, 4, 6, 7];
+/// println!("{:?}", seq::sample_slice_ref(&mut rng, &values, 3));
+/// ```
+pub fn sample_slice_ref<'a, R, T>(rng: &mut R, slice: &'a [T], amount: usize) -> Vec<&'a T>
+ where R: Rng
+{
+ let indices = sample_indices(rng, slice.len(), amount);
+
+ let mut out = Vec::with_capacity(amount);
+ out.extend(indices.iter().map(|i| &slice[*i]));
+ out
+}
+
+/// Randomly sample exactly `amount` indices from `0..length`.
+///
+/// The values are non-repeating and in random order.
+///
+/// This implementation uses `O(amount)` time and memory.
+///
+/// This method is used internally by the slice sampling methods, but it can sometimes be useful to
+/// have the indices themselves so this is provided as an alternative.
+///
+/// Panics if `amount > length`
+pub fn sample_indices<R>(rng: &mut R, length: usize, amount: usize) -> Vec<usize>
+ where R: Rng,
+{
+ if amount > length {
+ panic!("`amount` must be less than or equal to `slice.len()`");
+ }
+
+ // We are going to have to allocate at least `amount` for the output no matter what. However,
+ // if we use the `cached` version we will have to allocate `amount` as a HashMap as well since
+ // it inserts an element for every loop.
+ //
+ // Therefore, if `amount >= length / 2` then inplace will be both faster and use less memory.
+ // In fact, benchmarks show the inplace version is faster for length up to about 20 times
+ // faster than amount.
+ //
+ // TODO: there is probably even more fine-tuning that can be done here since
+ // `HashMap::with_capacity(amount)` probably allocates more than `amount` in practice,
+ // and a trade off could probably be made between memory/cpu, since hashmap operations
+ // are slower than array index swapping.
+ if amount >= length / 20 {
+ sample_indices_inplace(rng, length, amount)
+ } else {
+ sample_indices_cache(rng, length, amount)
+ }
+}
+
+/// Sample an amount of indices using an inplace partial fisher yates method.
+///
+/// This allocates the entire `length` of indices and randomizes only the first `amount`.
+/// It then truncates to `amount` and returns.
+///
+/// This is better than using a HashMap "cache" when `amount >= length / 2` since it does not
+/// require allocating an extra cache and is much faster.
+fn sample_indices_inplace<R>(rng: &mut R, length: usize, amount: usize) -> Vec<usize>
+ where R: Rng,
+{
+ debug_assert!(amount <= length);
+ let mut indices: Vec<usize> = Vec::with_capacity(length);
+ indices.extend(0..length);
+ for i in 0..amount {
+ let j: usize = rng.gen_range(i, length);
+ let tmp = indices[i];
+ indices[i] = indices[j];
+ indices[j] = tmp;
+ }
+ indices.truncate(amount);
+ debug_assert_eq!(indices.len(), amount);
+ indices
+}
+
+
+/// This method performs a partial fisher-yates on a range of indices using a HashMap
+/// as a cache to record potential collisions.
+///
+/// The cache avoids allocating the entire `length` of values. This is especially useful when
+/// `amount <<< length`, i.e. select 3 non-repeating from 1_000_000
+fn sample_indices_cache<R>(
+ rng: &mut R,
+ length: usize,
+ amount: usize,
+) -> Vec<usize>
+ where R: Rng,
+{
+ debug_assert!(amount <= length);
+ #[cfg(feature="std")] let mut cache = HashMap::with_capacity(amount);
+ #[cfg(not(feature="std"))] let mut cache = BTreeMap::new();
+ let mut out = Vec::with_capacity(amount);
+ for i in 0..amount {
+ let j: usize = rng.gen_range(i, length);
+
+ // equiv: let tmp = slice[i];
+ let tmp = match cache.get(&i) {
+ Some(e) => *e,
+ None => i,
+ };
+
+ // equiv: slice[i] = slice[j];
+ let x = match cache.get(&j) {
+ Some(x) => *x,
+ None => j,
+ };
+
+ // equiv: slice[j] = tmp;
+ cache.insert(j, tmp);
+
+ // note that in the inplace version, slice[i] is automatically "returned" value
+ out.push(x);
+ }
+ debug_assert_eq!(out.len(), amount);
+ out
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+ use {thread_rng, XorShiftRng, SeedableRng};
+
+ #[test]
+ fn test_sample_iter() {
+ let min_val = 1;
+ let max_val = 100;
+
+ let mut r = thread_rng();
+ let vals = (min_val..max_val).collect::<Vec<i32>>();
+ let small_sample = sample_iter(&mut r, vals.iter(), 5).unwrap();
+ let large_sample = sample_iter(&mut r, vals.iter(), vals.len() + 5).unwrap_err();
+
+ assert_eq!(small_sample.len(), 5);
+ assert_eq!(large_sample.len(), vals.len());
+ // no randomization happens when amount >= len
+ assert_eq!(large_sample, vals.iter().collect::<Vec<_>>());
+
+ assert!(small_sample.iter().all(|e| {
+ **e >= min_val && **e <= max_val
+ }));
+ }
+ #[test]
+ fn test_sample_slice_boundaries() {
+ let empty: &[u8] = &[];
+
+ let mut r = thread_rng();
+
+ // sample 0 items
+ assert_eq!(sample_slice(&mut r, empty, 0), vec![]);
+ assert_eq!(sample_slice(&mut r, &[42, 2, 42], 0), vec![]);
+
+ // sample 1 item
+ assert_eq!(sample_slice(&mut r, &[42], 1), vec![42]);
+ let v = sample_slice(&mut r, &[1, 42], 1)[0];
+ assert!(v == 1 || v == 42);
+
+ // sample "all" the items
+ let v = sample_slice(&mut r, &[42, 133], 2);
+ assert!(v == vec![42, 133] || v == vec![133, 42]);
+
+ assert_eq!(sample_indices_inplace(&mut r, 0, 0), vec![]);
+ assert_eq!(sample_indices_inplace(&mut r, 1, 0), vec![]);
+ assert_eq!(sample_indices_inplace(&mut r, 1, 1), vec![0]);
+
+ assert_eq!(sample_indices_cache(&mut r, 0, 0), vec![]);
+ assert_eq!(sample_indices_cache(&mut r, 1, 0), vec![]);
+ assert_eq!(sample_indices_cache(&mut r, 1, 1), vec![0]);
+
+ // Make sure lucky 777's aren't lucky
+ let slice = &[42, 777];
+ let mut num_42 = 0;
+ let total = 1000;
+ for _ in 0..total {
+ let v = sample_slice(&mut r, slice, 1);
+ assert_eq!(v.len(), 1);
+ let v = v[0];
+ assert!(v == 42 || v == 777);
+ if v == 42 {
+ num_42 += 1;
+ }
+ }
+ let ratio_42 = num_42 as f64 / 1000 as f64;
+ assert!(0.4 <= ratio_42 || ratio_42 <= 0.6, "{}", ratio_42);
+ }
+
+ #[test]
+ fn test_sample_slice() {
+ let xor_rng = XorShiftRng::from_seed;
+
+ let max_range = 100;
+ let mut r = thread_rng();
+
+ for length in 1usize..max_range {
+ let amount = r.gen_range(0, length);
+ let seed: [u32; 4] = [
+ r.next_u32(), r.next_u32(), r.next_u32(), r.next_u32()
+ ];
+
+ println!("Selecting indices: len={}, amount={}, seed={:?}", length, amount, seed);
+
+ // assert that the two index methods give exactly the same result
+ let inplace = sample_indices_inplace(
+ &mut xor_rng(seed), length, amount);
+ let cache = sample_indices_cache(
+ &mut xor_rng(seed), length, amount);
+ assert_eq!(inplace, cache);
+
+ // assert the basics work
+ let regular = sample_indices(
+ &mut xor_rng(seed), length, amount);
+ assert_eq!(regular.len(), amount);
+ assert!(regular.iter().all(|e| *e < length));
+ assert_eq!(regular, inplace);
+
+ // also test that sampling the slice works
+ let vec: Vec<usize> = (0..length).collect();
+ {
+ let result = sample_slice(&mut xor_rng(seed), &vec, amount);
+ assert_eq!(result, regular);
+ }
+
+ {
+ let result = sample_slice_ref(&mut xor_rng(seed), &vec, amount);
+ let expected = regular.iter().map(|v| v).collect::<Vec<_>>();
+ assert_eq!(result, expected);
+ }
+ }
+ }
+}
--
cgit v1.2.3