#[cfg(feature="alloc")] pub mod index;
#[cfg(feature="alloc")] use core::ops::Index;
#[cfg(all(feature="alloc", not(feature="std")))] use alloc::vec::Vec;
use Rng;
#[cfg(feature="alloc")] use distributions::WeightedError;
#[cfg(feature="alloc")] use distributions::uniform::{SampleUniform, SampleBorrow};
pub trait SliceRandom {
type Item;
fn choose<R>(&self, rng: &mut R) -> Option<&Self::Item>
where R: Rng + ?Sized;
fn choose_mut<R>(&mut self, rng: &mut R) -> Option<&mut Self::Item>
where R: Rng + ?Sized;
#[cfg(feature = "alloc")]
fn choose_multiple<R>(&self, rng: &mut R, amount: usize) -> SliceChooseIter<Self, Self::Item>
where R: Rng + ?Sized;
#[cfg(feature = "alloc")]
fn choose_weighted<R, F, B, X>(&self, rng: &mut R, weight: F) -> Result<&Self::Item, WeightedError>
where R: Rng + ?Sized,
F: Fn(&Self::Item) -> B,
B: SampleBorrow<X>,
X: SampleUniform +
for<'a> ::core::ops::AddAssign<&'a X> +
::core::cmp::PartialOrd<X> +
Clone +
Default;
#[cfg(feature = "alloc")]
fn choose_weighted_mut<R, F, B, X>(&mut self, rng: &mut R, weight: F) -> Result<&mut Self::Item, WeightedError>
where R: Rng + ?Sized,
F: Fn(&Self::Item) -> B,
B: SampleBorrow<X>,
X: SampleUniform +
for<'a> ::core::ops::AddAssign<&'a X> +
::core::cmp::PartialOrd<X> +
Clone +
Default;
fn shuffle<R>(&mut self, rng: &mut R) where R: Rng + ?Sized;
fn partial_shuffle<R>(&mut self, rng: &mut R, amount: usize)
-> (&mut [Self::Item], &mut [Self::Item]) where R: Rng + ?Sized;
}
pub trait IteratorRandom: Iterator + Sized {
fn choose<R>(mut self, rng: &mut R) -> Option<Self::Item>
where R: Rng + ?Sized
{
let (mut lower, mut upper) = self.size_hint();
let mut consumed = 0;
let mut result = None;
if upper == Some(lower) {
return if lower == 0 { None } else { self.nth(rng.gen_range(0, lower)) };
}
loop {
if lower > 1 {
let ix = rng.gen_range(0, lower + consumed);
let skip;
if ix < lower {
result = self.nth(ix);
skip = lower - (ix + 1);
} else {
skip = lower;
}
if upper == Some(lower) {
return result;
}
consumed += lower;
if skip > 0 {
self.nth(skip - 1);
}
} else {
let elem = self.next();
if elem.is_none() {
return result;
}
consumed += 1;
let denom = consumed as f64;
if rng.gen_bool(1.0 / denom) {
result = elem;
}
}
let hint = self.size_hint();
lower = hint.0;
upper = hint.1;
}
}
fn choose_multiple_fill<R>(mut self, rng: &mut R, buf: &mut [Self::Item])
-> usize where R: Rng + ?Sized
{
let amount = buf.len();
let mut len = 0;
while len < amount {
if let Some(elem) = self.next() {
buf[len] = elem;
len += 1;
} else {
return len;
}
}
for (i, elem) in self.enumerate() {
let k = rng.gen_range(0, i + 1 + amount);
if let Some(slot) = buf.get_mut(k) {
*slot = elem;
}
}
len
}
#[cfg(feature = "alloc")]
fn choose_multiple<R>(mut self, rng: &mut R, amount: usize) -> Vec<Self::Item>
where R: Rng + ?Sized
{
let mut reservoir = Vec::with_capacity(amount);
reservoir.extend(self.by_ref().take(amount));
if reservoir.len() == amount {
for (i, elem) in self.enumerate() {
let k = rng.gen_range(0, i + 1 + amount);
if let Some(slot) = reservoir.get_mut(k) {
*slot = elem;
}
}
} else {
reservoir.shrink_to_fit();
}
reservoir
}
}
impl<T> SliceRandom for [T] {
type Item = T;
fn choose<R>(&self, rng: &mut R) -> Option<&Self::Item>
where R: Rng + ?Sized
{
if self.is_empty() {
None
} else {
Some(&self[rng.gen_range(0, self.len())])
}
}
fn choose_mut<R>(&mut self, rng: &mut R) -> Option<&mut Self::Item>
where R: Rng + ?Sized
{
if self.is_empty() {
None
} else {
let len = self.len();
Some(&mut self[rng.gen_range(0, len)])
}
}
#[cfg(feature = "alloc")]
fn choose_multiple<R>(&self, rng: &mut R, amount: usize)
-> SliceChooseIter<Self, Self::Item>
where R: Rng + ?Sized
{
let amount = ::core::cmp::min(amount, self.len());
SliceChooseIter {
slice: self,
_phantom: Default::default(),
indices: index::sample(rng, self.len(), amount).into_iter(),
}
}
#[cfg(feature = "alloc")]
fn choose_weighted<R, F, B, X>(&self, rng: &mut R, weight: F) -> Result<&Self::Item, WeightedError>
where R: Rng + ?Sized,
F: Fn(&Self::Item) -> B,
B: SampleBorrow<X>,
X: SampleUniform +
for<'a> ::core::ops::AddAssign<&'a X> +
::core::cmp::PartialOrd<X> +
Clone +
Default {
use distributions::{Distribution, WeightedIndex};
let distr = WeightedIndex::new(self.iter().map(weight))?;
Ok(&self[distr.sample(rng)])
}
#[cfg(feature = "alloc")]
fn choose_weighted_mut<R, F, B, X>(&mut self, rng: &mut R, weight: F) -> Result<&mut Self::Item, WeightedError>
where R: Rng + ?Sized,
F: Fn(&Self::Item) -> B,
B: SampleBorrow<X>,
X: SampleUniform +
for<'a> ::core::ops::AddAssign<&'a X> +
::core::cmp::PartialOrd<X> +
Clone +
Default {
use distributions::{Distribution, WeightedIndex};
let distr = WeightedIndex::new(self.iter().map(weight))?;
Ok(&mut self[distr.sample(rng)])
}
fn shuffle<R>(&mut self, rng: &mut R) where R: Rng + ?Sized
{
for i in (1..self.len()).rev() {
self.swap(i, rng.gen_range(0, i + 1));
}
}
fn partial_shuffle<R>(&mut self, rng: &mut R, amount: usize)
-> (&mut [Self::Item], &mut [Self::Item]) where R: Rng + ?Sized
{
let len = self.len();
let end = if amount >= len { 0 } else { len - amount };
for i in (end..len).rev() {
self.swap(i, rng.gen_range(0, i + 1));
}
let r = self.split_at_mut(end);
(r.1, r.0)
}
}
impl<I> IteratorRandom for I where I: Iterator + Sized {}
#[cfg(feature = "alloc")]
#[derive(Debug)]
pub struct SliceChooseIter<'a, S: ?Sized + 'a, T: 'a> {
slice: &'a S,
_phantom: ::core::marker::PhantomData<T>,
indices: index::IndexVecIntoIter,
}
#[cfg(feature = "alloc")]
impl<'a, S: Index<usize, Output = T> + ?Sized + 'a, T: 'a> Iterator for SliceChooseIter<'a, S, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.indices.next().map(|i| &self.slice[i as usize])
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.indices.len(), Some(self.indices.len()))
}
}
#[cfg(feature = "alloc")]
impl<'a, S: Index<usize, Output = T> + ?Sized + 'a, T: 'a> ExactSizeIterator
for SliceChooseIter<'a, S, T>
{
fn len(&self) -> usize {
self.indices.len()
}
}
#[cfg(feature = "alloc")]
#[deprecated(since="0.6.0", note="use IteratorRandom::choose_multiple instead")]
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 + ?Sized,
{
use seq::IteratorRandom;
let iter = iterable.into_iter();
let result = iter.choose_multiple(rng, amount);
if result.len() == amount {
Ok(result)
} else {
Err(result)
}
}
#[cfg(feature = "alloc")]
#[deprecated(since="0.6.0", note="use SliceRandom::choose_multiple instead")]
pub fn sample_slice<R, T>(rng: &mut R, slice: &[T], amount: usize) -> Vec<T>
where R: Rng + ?Sized,
T: Clone
{
let indices = index::sample(rng, slice.len(), amount).into_iter();
let mut out = Vec::with_capacity(amount);
out.extend(indices.map(|i| slice[i].clone()));
out
}
#[cfg(feature = "alloc")]
#[deprecated(since="0.6.0", note="use SliceRandom::choose_multiple instead")]
pub fn sample_slice_ref<'a, R, T>(rng: &mut R, slice: &'a [T], amount: usize) -> Vec<&'a T>
where R: Rng + ?Sized
{
let indices = index::sample(rng, slice.len(), amount).into_iter();
let mut out = Vec::with_capacity(amount);
out.extend(indices.map(|i| &slice[i]));
out
}
#[cfg(test)]
mod test {
use super::*;
#[cfg(feature = "alloc")] use {Rng, SeedableRng};
#[cfg(feature = "alloc")] use rngs::SmallRng;
#[cfg(all(feature="alloc", not(feature="std")))]
use alloc::vec::Vec;
#[test]
fn test_slice_choose() {
let mut r = ::test::rng(107);
let chars = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n'];
let mut chosen = [0i32; 14];
for _ in 0..1000 {
let picked = *chars.choose(&mut r).unwrap();
chosen[(picked as usize) - ('a' as usize)] += 1;
}
for count in chosen.iter() {
let err = *count - (1000 / (chars.len() as i32));
assert!(-20 <= err && err <= 20);
}
chosen.iter_mut().for_each(|x| *x = 0);
for _ in 0..1000 {
*chosen.choose_mut(&mut r).unwrap() += 1;
}
for count in chosen.iter() {
let err = *count - (1000 / (chosen.len() as i32));
assert!(-20 <= err && err <= 20);
}
let mut v: [isize; 0] = [];
assert_eq!(v.choose(&mut r), None);
assert_eq!(v.choose_mut(&mut r), None);
}
#[derive(Clone)]
struct UnhintedIterator<I: Iterator + Clone> {
iter: I,
}
impl<I: Iterator + Clone> Iterator for UnhintedIterator<I> {
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
#[derive(Clone)]
struct ChunkHintedIterator<I: ExactSizeIterator + Iterator + Clone> {
iter: I,
chunk_remaining: usize,
chunk_size: usize,
hint_total_size: bool,
}
impl<I: ExactSizeIterator + Iterator + Clone> Iterator for ChunkHintedIterator<I> {
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
if self.chunk_remaining == 0 {
self.chunk_remaining = ::core::cmp::min(self.chunk_size,
self.iter.len());
}
self.chunk_remaining = self.chunk_remaining.saturating_sub(1);
self.iter.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.chunk_remaining,
if self.hint_total_size { Some(self.iter.len()) } else { None })
}
}
#[derive(Clone)]
struct WindowHintedIterator<I: ExactSizeIterator + Iterator + Clone> {
iter: I,
window_size: usize,
hint_total_size: bool,
}
impl<I: ExactSizeIterator + Iterator + Clone> Iterator for WindowHintedIterator<I> {
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(::core::cmp::min(self.iter.len(), self.window_size),
if self.hint_total_size { Some(self.iter.len()) } else { None })
}
}
#[test]
fn test_iterator_choose() {
let r = &mut ::test::rng(109);
fn test_iter<R: Rng + ?Sized, Iter: Iterator<Item=usize> + Clone>(r: &mut R, iter: Iter) {
let mut chosen = [0i32; 9];
for _ in 0..1000 {
let picked = iter.clone().choose(r).unwrap();
chosen[picked] += 1;
}
for count in chosen.iter() {
assert!(72 < *count && *count < 154, "count not close to 1000/9: {}", count);
}
}
test_iter(r, 0..9);
test_iter(r, [0, 1, 2, 3, 4, 5, 6, 7, 8].iter().cloned());
#[cfg(feature = "alloc")]
test_iter(r, (0..9).collect::<Vec<_>>().into_iter());
test_iter(r, UnhintedIterator { iter: 0..9 });
test_iter(r, ChunkHintedIterator { iter: 0..9, chunk_size: 4, chunk_remaining: 4, hint_total_size: false });
test_iter(r, ChunkHintedIterator { iter: 0..9, chunk_size: 4, chunk_remaining: 4, hint_total_size: true });
test_iter(r, WindowHintedIterator { iter: 0..9, window_size: 2, hint_total_size: false });
test_iter(r, WindowHintedIterator { iter: 0..9, window_size: 2, hint_total_size: true });
assert_eq!((0..0).choose(r), None);
assert_eq!(UnhintedIterator{ iter: 0..0 }.choose(r), None);
}
#[test]
fn test_shuffle() {
let mut r = ::test::rng(108);
let empty: &mut [isize] = &mut [];
empty.shuffle(&mut r);
let mut one = [1];
one.shuffle(&mut r);
let b: &[_] = &[1];
assert_eq!(one, b);
let mut two = [1, 2];
two.shuffle(&mut r);
assert!(two == [1, 2] || two == [2, 1]);
fn move_last(slice: &mut [usize], pos: usize) {
let last_val = slice[pos];
for i in pos..slice.len() - 1 {
slice[i] = slice[i + 1];
}
*slice.last_mut().unwrap() = last_val;
}
let mut counts = [0i32; 24];
for _ in 0..10000 {
let mut arr: [usize; 4] = [0, 1, 2, 3];
arr.shuffle(&mut r);
let mut permutation = 0usize;
let mut pos_value = counts.len();
for i in 0..4 {
pos_value /= 4 - i;
let pos = arr.iter().position(|&x| x == i).unwrap();
assert!(pos < (4 - i));
permutation += pos * pos_value;
move_last(&mut arr, pos);
assert_eq!(arr[3], i);
}
for i in 0..4 {
assert_eq!(arr[i], i);
}
counts[permutation] += 1;
}
for count in counts.iter() {
let err = *count - 10000i32 / 24;
assert!(-50 <= err && err <= 50);
}
}
#[test]
fn test_partial_shuffle() {
let mut r = ::test::rng(118);
let mut empty: [u32; 0] = [];
let res = empty.partial_shuffle(&mut r, 10);
assert_eq!((res.0.len(), res.1.len()), (0, 0));
let mut v = [1, 2, 3, 4, 5];
let res = v.partial_shuffle(&mut r, 2);
assert_eq!((res.0.len(), res.1.len()), (2, 3));
assert!(res.0[0] != res.0[1]);
assert!(res.1[0] == 1 || res.1[1] == 2 || res.1[2] == 3);
}
#[test]
#[cfg(feature = "alloc")]
fn test_sample_iter() {
let min_val = 1;
let max_val = 100;
let mut r = ::test::rng(401);
let vals = (min_val..max_val).collect::<Vec<i32>>();
let small_sample = vals.iter().choose_multiple(&mut r, 5);
let large_sample = vals.iter().choose_multiple(&mut r, vals.len() + 5);
assert_eq!(small_sample.len(), 5);
assert_eq!(large_sample.len(), vals.len());
assert_eq!(large_sample, vals.iter().collect::<Vec<_>>());
assert!(small_sample.iter().all(|e| {
**e >= min_val && **e <= max_val
}));
}
#[test]
#[cfg(feature = "alloc")]
#[allow(deprecated)]
fn test_sample_slice_boundaries() {
let empty: &[u8] = &[];
let mut r = ::test::rng(402);
assert_eq!(&sample_slice(&mut r, empty, 0)[..], [0u8; 0]);
assert_eq!(&sample_slice(&mut r, &[42, 2, 42], 0)[..], [0u8; 0]);
assert_eq!(&sample_slice(&mut r, &[42], 1)[..], [42]);
let v = sample_slice(&mut r, &[1, 42], 1)[0];
assert!(v == 1 || v == 42);
let v = sample_slice(&mut r, &[42, 133], 2);
assert!(&v[..] == [42, 133] || v[..] == [133, 42]);
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]
#[cfg(feature = "alloc")]
#[allow(deprecated)]
fn test_sample_slice() {
let seeded_rng = SmallRng::from_seed;
let mut r = ::test::rng(403);
for n in 1..20 {
let length = 5*n - 4;
let amount = r.gen_range(0, length);
let mut seed = [0u8; 16];
r.fill(&mut seed);
let regular = index::sample(&mut seeded_rng(seed), length, amount);
assert_eq!(regular.len(), amount);
assert!(regular.iter().all(|e| e < length));
let vec: Vec<u32> = (0..(length as u32)).collect();
let result = sample_slice(&mut seeded_rng(seed), &vec, amount);
assert_eq!(result, regular.iter().map(|i| i as u32).collect::<Vec<_>>());
let result = sample_slice_ref(&mut seeded_rng(seed), &vec, amount);
assert!(result.iter().zip(regular.iter()).all(|(i,j)| **i == j as u32));
}
}
#[test]
#[cfg(feature = "alloc")]
fn test_weighted() {
let mut r = ::test::rng(406);
const N_REPS: u32 = 3000;
let weights = [1u32, 2, 3, 0, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7];
let total_weight = weights.iter().sum::<u32>() as f32;
let verify = |result: [i32; 14]| {
for (i, count) in result.iter().enumerate() {
let exp = (weights[i] * N_REPS) as f32 / total_weight;
let mut err = (*count as f32 - exp).abs();
if err != 0.0 {
err /= exp;
}
assert!(err <= 0.25);
}
};
fn get_weight<T>(item: &(u32, T)) -> u32 {
item.0
}
let mut chosen = [0i32; 14];
let mut items = [(0u32, 0usize); 14];
for (i, item) in items.iter_mut().enumerate() {
*item = (weights[i], i);
}
for _ in 0..N_REPS {
let item = items.choose_weighted(&mut r, get_weight).unwrap();
chosen[item.1] += 1;
}
verify(chosen);
let mut items = [(0u32, 0i32); 14];
for (i, item) in items.iter_mut().enumerate() {
*item = (weights[i], 0);
}
for _ in 0..N_REPS {
items.choose_weighted_mut(&mut r, get_weight).unwrap().1 += 1;
}
for (ch, item) in chosen.iter_mut().zip(items.iter()) {
*ch = item.1;
}
verify(chosen);
let empty_slice = &mut [10][0..0];
assert_eq!(empty_slice.choose_weighted(&mut r, |_| 1), Err(WeightedError::NoItem));
assert_eq!(empty_slice.choose_weighted_mut(&mut r, |_| 1), Err(WeightedError::NoItem));
assert_eq!(['x'].choose_weighted_mut(&mut r, |_| 0), Err(WeightedError::AllWeightsZero));
assert_eq!([0, -1].choose_weighted_mut(&mut r, |x| *x), Err(WeightedError::NegativeWeight));
assert_eq!([-1, 0].choose_weighted_mut(&mut r, |x| *x), Err(WeightedError::NegativeWeight));
}
}