// Copyright 2021 Developers of the Rand project.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
//
https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or
https://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
use crate::distributions::{Distribution, Uniform};
/// A distribution to sample items uniformly from a slice.
///
/// [`Slice::new`] constructs a distribution referencing a slice and uniformly
/// samples references from the items in the slice. It may do extra work up
/// front to make sampling of multiple values faster; if only one sample from
/// the slice is required, [`SliceRandom::choose`] can be more efficient.
///
/// Steps are taken to avoid bias which might be present in naive
/// implementations; for example `slice[rng.gen() % slice.len()]` samples from
/// the slice, but may be more likely to select numbers in the low range than
/// other values.
///
/// This distribution samples with replacement; each sample is independent.
/// Sampling without replacement requires state to be retained, and therefore
/// cannot be handled by a distribution; you should instead consider methods
/// on [`SliceRandom`], such as [`SliceRandom::choose_multiple`].
///
/// # Example
///
/// ```
/// use rand::Rng;
/// use rand::distributions::Slice;
///
/// let vowels = ['a', 'e', 'i', 'o', 'u'];
/// let vowels_dist = Slice::new(&vowels).unwrap();
/// let rng = rand::thread_rng();
///
/// // build a string of 10 vowels
/// let vowel_string: String = rng
/// .sample_iter(&vowels_dist)
/// .take(10)
/// .collect();
///
/// println!("{}", vowel_string);
/// assert_eq!(vowel_string.len(), 10);
/// assert!(vowel_string.chars().all(|c| vowels.contains(&c)));
/// ```
///
/// For a single sample, [`SliceRandom::choose`][crate::seq::SliceRandom::choose]
/// may be preferred:
///
/// ```
/// use rand::seq::SliceRandom;
///
/// let vowels = ['a', 'e', 'i', 'o', 'u'];
/// let mut rng = rand::thread_rng();
///
/// println!("{}", vowels.choose(&mut rng).unwrap())
/// ```
///
/// [`SliceRandom`]: crate::seq::SliceRandom
/// [`SliceRandom::choose`]: crate::seq::SliceRandom::choose
/// [`SliceRandom::choose_multiple`]: crate::seq::SliceRandom::choose_multiple
#[derive(Debug, Clone, Copy)]
pub struct Slice<'a, T> {
slice: &'a [T],
range: Uniform<usize>,
}
impl<'a, T> Slice<'a, T> {
/// Create a new `Slice` instance which samples uniformly from the slice.
/// Returns `Err` if the slice is empty.
pub fn new(slice: &'a [T]) -> Result<Self, EmptySlice> {
match slice.len() {
0 => Err(EmptySlice),
len => Ok(Self {
slice,
range: Uniform::new(0, len),
}),
}
}
}
impl<'a, T> Distribution<&'a T> for Slice<'a, T> {
fn sample<R: crate::Rng + ?Sized>(&self, rng: &mut R) -> &'a T {
let idx = self.range.sample(rng);
debug_assert!(
idx < self.slice.len(),
"Uniform::new(0, {}) somehow returned {}",
self.slice.len(),
idx
);
// Safety: at construction time, it was ensured that the slice was
// non-empty, and that the `Uniform` range produces values in range
// for the slice
unsafe { self.slice.get_unchecked(idx) }
}
}
/// Error type indicating that a [`Slice`] distribution was improperly
/// constructed with an empty slice.
#[derive(Debug, Clone, Copy)]
pub struct EmptySlice;
impl core::fmt::Display for EmptySlice {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(
f,
"Tried to create a `distributions::Slice` with an empty slice"
)
}
}
#[cfg(feature = "std")]
impl std::error::Error for EmptySlice {}
