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 
9 use 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)]
65 pub struct Slice<'a, T> {
66     slice: &'a [T],
67     range: Uniform<usize>,
68 }
69 
70 impl<'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.
new(slice: &'a [T]) -> Result<Self, EmptySlice>73     pub fn new(slice: &'a [T]) -> Result<Self, EmptySlice> {
74         match slice.len() {
75             0 => Err(EmptySlice),
76             len => Ok(Self {
77                 slice,
78                 range: Uniform::new(0, len),
79             }),
80         }
81     }
82 }
83 
84 impl<'a, T> Distribution<&'a T> for Slice<'a, T> {
sample<R: crate::Rng + ?Sized>(&self, rng: &mut R) -> &'a T85     fn sample<R: crate::Rng + ?Sized>(&self, rng: &mut R) -> &'a T {
86         let idx = 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(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)]
105 pub struct EmptySlice;
106 
107 impl core::fmt::Display for EmptySlice {
fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result108     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")]
117 impl std::error::Error for EmptySlice {}
118