hashed_permutation/
iterator.rs

1use crate::HashedPermutation;
2use std::num::NonZeroU32;
3
4/// An iterator that allows you to iterate over a sequence of permuted numbers with O(1) space.
5pub struct HashedIter {
6    /// The "engine" driving the permutations
7    permutation_engine: HashedPermutation,
8
9    /// The current index that's being iterated on
10    current_idx: u32,
11}
12
13/// The iterator version of the hashed permutation algorithm
14///
15/// This allows you to use an iterator as you would normally.
16///
17/// ```
18/// # use hashed_permutation::HashedIter;
19/// use std::num::NonZeroU32;
20///
21/// let mut iterator = HashedIter::new_with_seed(NonZeroU32::new(5).unwrap(), 100);
22///
23/// for i in iterator {
24///     println!("{}", i);
25/// }
26/// ```
27impl HashedIter {
28    /// Create a new hashed iterator with a given length
29    ///
30    /// This will create an iterator with an underlying `HashedPermutation` engine with a random
31    /// seed. The seed is generated using the standard library's `thread_rng` class.
32    #[cfg(feature = "use-rand")]
33    pub fn new(length: NonZeroU32) -> Self {
34        let permutation_engine = HashedPermutation::new(length);
35
36        Self {
37            permutation_engine,
38            current_idx: 0,
39        }
40    }
41
42    /// Create a new hashed iterator with a given length and a seed value
43    pub fn new_with_seed(length: NonZeroU32, seed: u32) -> Self {
44        let permutation_engine = HashedPermutation::new_with_seed(length, seed);
45
46        Self {
47            permutation_engine,
48            current_idx: 0,
49        }
50    }
51}
52
53impl Iterator for HashedIter {
54    type Item = u32;
55
56    fn next(&mut self) -> Option<Self::Item> {
57        match self.permutation_engine.shuffle(self.current_idx) {
58            Ok(elem) => {
59                self.current_idx += 1;
60                Some(elem)
61            }
62            Err(_) => None,
63        }
64    }
65}
66
67#[cfg(test)]
68mod test {
69    use super::*;
70    use std::collections::HashSet;
71
72    /// A convenient helper method that returns a pair of lengths and seeds (in that order).
73    ///
74    /// This method defines the lengths and the seeds for the test cases, since these are reused
75    /// in the tests, and it's best practice to consolidate them in one place so code is not
76    /// repeated.
77    fn lengths_and_seeds() -> (Vec<NonZeroU32>, Vec<u32>) {
78        let lengths: Vec<NonZeroU32> = vec![100, 5, 13, 128, 249]
79            .iter()
80            .map(|&x| NonZeroU32::new(x).unwrap())
81            .collect();
82        let seeds = vec![100, 5, 13, 128, 249];
83        assert_eq!(lengths.len(), seeds.len());
84        (lengths, seeds)
85    }
86
87    #[test]
88    // This method checks to see that a permutation does not have any collisions and that every
89    // number maps to another unique number. In other words, we are testing to see whether we have
90    // a bijective function.
91    fn test_bijection() {
92        let (lengths, seeds) = lengths_and_seeds();
93
94        for (&length, seed) in lengths.iter().zip(seeds) {
95            let it = HashedIter::new_with_seed(length, seed);
96
97            // Check that each entry doesn't exist
98            // Check that every number is "hit" (as they'd have to be) for a perfect bijection
99            // Check that the number is within range
100            let mut set = HashSet::new();
101
102            for elem in it {
103                let set_result = set.get(&elem);
104
105                // Make sure there are no duplicates
106                assert!(set_result.is_none());
107                set.insert(elem);
108            }
109            // Need to dereference the types into regular integers
110            let mut result: Vec<u32> = set.into_iter().collect();
111            result.sort();
112            let expected: Vec<u32> = (0..length.get()).collect();
113            assert_eq!(expected, result);
114        }
115    }
116}
hashed_permutation/iterator.rs

hashed_permutation/
iterator.rs
