urng 1.0.0

Universal Random Number Generator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

/// Error returned when attempting to shuffle an empty slice.
#[derive(Debug)]
pub struct SliceShuffleError(pub(crate) ());
impl std::fmt::Display for SliceShuffleError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Cannot shuffle an empty slice.")
    }
}
impl std::error::Error for SliceShuffleError {}

/// Result type for shuffle operations, failing on an empty slice.
pub type ShuffleResult<T> = std::result::Result<T, self::SliceShuffleError>;

/// An iterator that yields references to the elements of a slice in a shuffled order.
///
/// Returned by [`Shuffle::shuffled`].
pub struct ShuffledIterator<'a, T> {
    pub(crate) slice: &'a [T],
    pub(crate) indices: Vec<usize>,
    pub(crate) pos: usize,
}

impl<'a, T> Iterator for ShuffledIterator<'a, T> {
    type Item = &'a T;

    #[inline(always)]
    fn next(&mut self) -> Option<&'a T> {
        let index = *self.indices.get(self.pos)?;
        self.pos += 1;
        Some(&self.slice[index])
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.indices.len() - self.pos;
        (remaining, Some(remaining))
    }
}

use crate::rng::{Rng, Word};

/// Shuffles a slice in-place or returns a shuffled iterator, for any [`Rng`].
pub trait Shuffle: Rng {
    /// Shuffles `src` in place.
    #[inline(always)]
    fn shuffle<T>(&mut self, src: &mut [T]) -> crate::ShuffleResult<()> {
        if src.is_empty() {
            Err(crate::SliceShuffleError(()))
        } else {
            let len = src.len();
            (0..len - 1).for_each(|i| {
                let j = self.nextu().to_index(len);
                src.swap(i, j);
            });
            Ok(())
        }
    }

    /// Returns an iterator over `src` in a shuffled order.
    #[inline(always)]
    fn shuffled<'a, T>(
        &mut self,
        src: &'a [T],
    ) -> crate::ShuffleResult<crate::ShuffledIterator<'a, T>> {
        if src.is_empty() {
            return Err(crate::SliceShuffleError(()));
        }
        let len = src.len();
        let mut indices: Vec<usize> = (0..len).collect();
        (0..len - 1).for_each(|i| {
            let j = self.nextu().to_index(len);
            indices.swap(i, j);
        });
        Ok(crate::ShuffledIterator {
            slice: src,
            indices,
            pos: 0,
        })
    }
}

impl<R: Rng + ?Sized> Shuffle for R {}