primesieve/
iterator.rs

1//! Iteration over the numbers encoded in a sieve.
2
3const MODULUS: u64 = 240;
4const OFFSETS: &'static [u64; 64] =
5    &[1, 7, 11, 13, 17, 19, 23, 29,
6      31, 37, 41, 43, 47, 49, 53, 59,
7      61, 67, 71, 73, 77, 79, 83, 89,
8      91, 97, 101, 103, 107, 109, 113, 119,
9      121, 127, 131, 133, 137, 139, 143, 149,
10      151, 157, 161, 163, 167, 169, 173, 179,
11      181, 187, 191, 193, 197, 199, 203, 209,
12      211, 217, 221, 223, 227, 229, 233, 239];
13
14/// A structure which iterates over the numbers represented by a given sequence of integers using
15/// the encoding described in the module `segment`.
16pub struct SieveIterator<'a> {
17    /// The current `u64` we are extracting numbers from.
18    current: u64,
19    /// The offset to add to the numbers we extract from the current `u64`.
20    base: u64,
21    /// The index in the sieve of the current `u64`.
22    curr_idx: usize,
23    /// The sieve encoding the numbers to iterate over.
24    sieve: &'a [u64],
25}
26
27impl<'a> SieveIterator<'a> {
28    /// Create a new `SieveIterator` which is ready to iterate over the numbers encoded in the
29    /// given sieve of `u64`s.
30    pub fn new(sieve: &'a [u64]) -> SieveIterator {
31        if sieve.len() == 0 {
32            SieveIterator {
33                current: 0,
34                base: 0,
35                curr_idx: 0,
36                sieve: sieve,
37            }
38        } else {
39            SieveIterator {
40                current: sieve[0],
41                base: 0,
42                curr_idx: 0,
43                sieve: sieve,
44            }
45        }
46    }
47}
48
49impl<'a> Iterator for SieveIterator<'a> {
50    type Item = u64;
51
52    fn next(&mut self) -> Option<u64> {
53        // If all the numbers from the current `u64` have been considered, look for the next `u64`
54        // which encodes a number.
55        if self.current == 0 {
56            for idx in self.curr_idx + 1..self.sieve.len() {
57                self.base += MODULUS;
58                if self.sieve[idx] != 0 {
59                    self.current = self.sieve[idx];
60                    self.curr_idx = idx;
61                    break;
62                }
63            }
64        }
65
66        // If we've exhausted all the numbers, indicate so.
67        if self.current == 0 {
68            return None;
69        }
70
71        // Get the next number from the current `u64`.
72        let bit = self.current.trailing_zeros();
73        self.current &= self.current - 1;
74        Some(self.base + OFFSETS[bit as usize])
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_empty() {
84        assert_eq!(SieveIterator::new(&[]).collect::<Vec<u64>>(), vec![]);
85    }
86
87    #[test]
88    fn test_small() {
89        let sieve = [0b1001001100101100000001011010010];
90        let iter = SieveIterator::new(&sieve);
91        assert_eq!(iter.collect::<Vec<u64>>(),
92                   vec![7, 17, 23, 29, 37, 67, 71, 77, 89, 91, 103, 113]);
93    }
94
95    #[test]
96    fn test_medium() {
97        let sieve = [0b1001001100101100000001011010010, 0b0, 0b1100101100000001011010010];
98        let iter = SieveIterator::new(&sieve);
99        assert_eq!(iter.collect::<Vec<u64>>(),
100                   vec![7, 17, 23, 29, 37, 67, 71, 77, 89, 91, 103, 113,
101                        487, 497, 503, 509, 517, 547, 551, 557, 569, 571]);
102    }
103}
primesieve/iterator.rs

primesieve/
iterator.rs
