shuffled_iter/
lib.rs

1//! This crate provides methods to iterate over a group of values in random
2//! order, without allocation and shuffling them all.
3//!
4//! Such an iterator may be obtained via the `ShuffledIterGen` trait.
5
6#[cfg(test)] extern crate bit_vec;
7extern crate rand;
8
9pub use iter::ShuffledIterGen;
10
11use std::num::Wrapping;
12use rand::Rng;
13
14mod iter;
15
16#[allow(non_camel_case_types)]
17type w32 = Wrapping<u32>;
18
19#[inline(always)]
20fn w32(u: u32) -> w32 {
21    Wrapping(u)
22}
23
24#[inline(always)]
25fn shl_ignore(slf: u32, rhs: u32) -> u32 {
26    if rhs >= 32 { 0 } else { slf << rhs }
27}
28
29// This needs to be an odd number so that the multiplicative inverse of the
30// result modulo 2^n exists
31// ie.: gcd(2^n, res) == 1
32#[inline(always)]
33fn gen_factor<R: Rng>(rng: &mut R) -> w32 {
34    w32((rng.next_u32() << 1) | 1)
35}
36
37// No restricitions here
38#[inline(always)]
39fn gen_xor_op<R: Rng>(rng: &mut R) -> w32 {
40    w32(rng.next_u32())
41}
42
43/// The actual iterator which iterates over, in random order, all `u32`s
44/// smaller than or equal to a given maximum value.
45///
46/// An instance of this struct may be obtained via the `ShuffletIterGen` trait.
47///
48/// No gurantees are made about the quality of the randomiziation, nor is the
49/// algorithem guranteed to remain unchanged between version.
50#[derive(Copy, Clone, Debug)]
51pub struct ShuffledIter {
52    max: w32,
53    mask: w32,
54
55    index: w32,
56    count: w32,
57
58    f1: w32,
59    f2: w32,
60    x1: w32,
61    x2: w32,
62
63    done: bool,
64}
65
66impl ShuffledIter {
67    fn new<R: Rng>(max: u32, rng: &mut R) -> ShuffledIter {
68        let bits = 32 - max.leading_zeros();
69
70        let max = w32(max);
71
72        let mask = w32(shl_ignore(1, bits)) - w32(1);
73
74        ShuffledIter {
75            max: max,
76            mask: mask,
77
78            index: w32(rng.next_u32()),
79            count: w32(0),
80
81            f1: gen_factor(rng),
82            f2: gen_factor(rng),
83            x1: gen_xor_op(rng),
84            x2: gen_xor_op(rng),
85
86            done: false,
87        }
88    }
89
90    #[inline(always)]
91    fn next_value(&mut self) -> u32 {
92        self.index = self.index + w32(1);
93        self.count = self.count + w32(1);
94
95        let mut val = self.calc(self.index);
96
97        while val > self.max {
98            self.index = self.index + w32(1);
99            val = self.calc(self.index);
100        }
101
102        val.0
103    }
104
105    #[inline(always)]
106    fn calc(&self, val: w32) -> w32 {
107        ((((val * self.f1) ^ self.x1) * self.f2) ^ self.x2) & self.mask
108    }
109}
110
111impl Iterator for ShuffledIter {
112    type Item = u32;
113
114    #[inline]
115    fn next(&mut self) -> Option<u32> {
116        if self.count < self.max {
117            Some(self.next_value())
118        } else if self.done {
119            None
120        } else {
121            self.done = true;
122            self.count = self.count - w32(1);
123            // if max == u32::max, next_value would wrap to 0, triggering the first block again
124            Some(self.next_value())
125        }
126    }
127}
128
129#[test]
130fn gen_1_1024() {
131    use bit_vec::BitVec;
132    use rand::XorShiftRng;
133
134    let mut rng = XorShiftRng::new_unseeded();
135
136    for i in 0u32 .. 1025 {
137        let mut bv = BitVec::from_elem(i as usize + 1, false);
138
139        let it = ShuffledIter::new(i, &mut rng);
140
141        for j in it {
142            assert!(bv.get(j as usize) == Some(false));
143            bv.set(j as usize, true);
144        }
145
146        assert!(bv.all());
147    }
148}
149
150#[test]
151fn max_u32_max() {
152    use std::u32;
153    use rand::XorShiftRng;
154
155    let mut rng = XorShiftRng::new_unseeded();
156
157    let mut it = ShuffledIter::new(u32::MAX, &mut rng);
158
159    for _ in 0 .. 10 {
160        assert!(it.next().is_some());
161    }
162
163    it.count = w32(u32::MAX - 9);
164    // We now should have 10 values left (u32::MAX plus 9 others)
165
166    for _ in 0 .. 10 {
167        assert!(it.next().is_some());
168    }
169
170    println!("{}", it.count.0);
171
172    assert!(it.next().is_none());
173}
shuffled_iter/lib.rs

shuffled_iter/
lib.rs
