1// Copyright 2021 Developers of the Rand project.
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9use crate::distributions::{Distribution, Uniform};
10
11/// A distribution to sample items uniformly from a slice.
12///
13/// [`Slice::new`] constructs a distribution referencing a slice and uniformly
14/// samples references from the items in the slice. It may do extra work up
15/// front to make sampling of multiple values faster; if only one sample from
16/// the slice is required, [`SliceRandom::choose`] can be more efficient.
17///
18/// Steps are taken to avoid bias which might be present in naive
19/// implementations; for example `slice[rng.gen() % slice.len()]` samples from
20/// the slice, but may be more likely to select numbers in the low range than
21/// other values.
22///
23/// This distribution samples with replacement; each sample is independent.
24/// Sampling without replacement requires state to be retained, and therefore
25/// cannot be handled by a distribution; you should instead consider methods
26/// on [`SliceRandom`], such as [`SliceRandom::choose_multiple`].
27///
28/// # Example
29///
30/// ```
31/// use rand::Rng;
32/// use rand::distributions::Slice;
33///
34/// let vowels = ['a', 'e', 'i', 'o', 'u'];
35/// let vowels_dist = Slice::new(&vowels).unwrap();
36/// let rng = rand::thread_rng();
37///
38/// // build a string of 10 vowels
39/// let vowel_string: String = rng
40/// .sample_iter(&vowels_dist)
41/// .take(10)
42/// .collect();
43///
44/// println!("{}", vowel_string);
45/// assert_eq!(vowel_string.len(), 10);
46/// assert!(vowel_string.chars().all(|c| vowels.contains(&c)));
47/// ```
48///
49/// For a single sample, [`SliceRandom::choose`][crate::seq::SliceRandom::choose]
50/// may be preferred:
51///
52/// ```
53/// use rand::seq::SliceRandom;
54///
55/// let vowels = ['a', 'e', 'i', 'o', 'u'];
56/// let mut rng = rand::thread_rng();
57///
58/// println!("{}", vowels.choose(&mut rng).unwrap())
59/// ```
60///
61/// [`SliceRandom`]: crate::seq::SliceRandom
62/// [`SliceRandom::choose`]: crate::seq::SliceRandom::choose
63/// [`SliceRandom::choose_multiple`]: crate::seq::SliceRandom::choose_multiple
64#[derive(Debug, Clone, Copy)]
65pub struct Slice<'a, T> {
66 slice: &'a [T],
67 range: Uniform<usize>,
68}
69
70impl<'a, T> Slice<'a, T> {
71 /// Create a new `Slice` instance which samples uniformly from the slice.
72 /// Returns `Err` if the slice is empty.
73 pub fn new(slice: &'a [T]) -> Result<Self, EmptySlice> {
74 match slice.len() {
75 0 => Err(EmptySlice),
76 len: usize => Ok(Self {
77 slice,
78 range: Uniform::new(low:0, high:len),
79 }),
80 }
81 }
82}
83
84impl<'a, T> Distribution<&'a T> for Slice<'a, T> {
85 fn sample<R: crate::Rng + ?Sized>(&self, rng: &mut R) -> &'a T {
86 let idx: usize = self.range.sample(rng);
87
88 debug_assert!(
89 idx < self.slice.len(),
90 "Uniform::new(0, {}) somehow returned {}",
91 self.slice.len(),
92 idx
93 );
94
95 // Safety: at construction time, it was ensured that the slice was
96 // non-empty, and that the `Uniform` range produces values in range
97 // for the slice
98 unsafe { self.slice.get_unchecked(index:idx) }
99 }
100}
101
102/// Error type indicating that a [`Slice`] distribution was improperly
103/// constructed with an empty slice.
104#[derive(Debug, Clone, Copy)]
105pub struct EmptySlice;
106
107impl core::fmt::Display for EmptySlice {
108 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
109 write!(
110 f,
111 "Tried to create a `distributions::Slice` with an empty slice"
112 )
113 }
114}
115
116#[cfg(feature = "std")]
117impl std::error::Error for EmptySlice {}
118