rlp_iter/
lib.rs

1//! # rlp-iter
2//!
3//! ![demo.gif](https://raw.githubusercontent.com/Nessex/rlp-iter/master/demo.gif)
4//!
5//! rlp-iter (Resolving Lattice Point Iterator) is an iterator that returns a space-filling permutation of integers in a given range. Specifically, it emits integers roughly in order of the most distant integer from any other previously emitted integer.
6//!
7//!  - Iterates over all values in a range (e.g. `0..=100`)
8//!  - Follows a space filling pattern
9//!  - No duplicate values
10//!
11//! #### Example
12//!
13//! Say you need an iterator over the range `0..=100`. This will emit integers in roughly the following order:
14//!
15//! ```text
16//! [ 0, 100, 50, 25, 75, 13, 38, 63, 88, ... ]
17//! ```
18//!
19//! ## Usage
20//!
21//! This iterator works on inclusive and exclusive ranges of `usize`. You can access it via:
22//!
23//! ```rust
24//! use rlp_iter::RlpIterator;
25//!
26//! for i in (0..=100).rlp_iter() {
27//!     println!("{}", i);
28//! }
29//! ```
30//!
31//! ## Overhead
32//!
33//! This requires a small constant amount of memory, plus one bit of memory per value in the sampled space (required to ensure there are no duplicate values emitted).
34//!
35//! ## License
36//!
37//! Licensed under either of
38//!
39//! * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or <http://www.apache.org/licenses/LICENSE-2.0>)
40//! * MIT license ([LICENSE-MIT](LICENSE-MIT) or <http://opensource.org/licenses/MIT>)
41//!
42//! at your option.
43//!
44//! ### Contribution
45//!
46//! Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
47//!
48
49use bit_vec::BitVec;
50use std::ops::{Range, RangeInclusive};
51
52enum State {
53    Start,
54    End,
55    Lattice,
56    Finished,
57}
58
59pub struct RlpIter {
60    tested: BitVec,
61    shift: usize,
62    range: usize,
63    numerator: usize,
64    pow: usize,
65    final_pow: usize,
66    state: State,
67}
68
69// NOTE(nathan): This should be replaced with the builtin log2
70// once it is stabilized.
71//
72// https://github.com/rust-lang/rust/issues/70887
73fn ilog2(i: usize) -> usize {
74    (i as f64).log2().round() as usize
75}
76
77impl Iterator for RlpIter {
78    type Item = usize;
79
80    fn next(&mut self) -> Option<Self::Item> {
81        let unshifted = match self.state {
82            State::Start => {
83                self.state = State::End;
84                self.tested.set(0, true);
85                Some(0)
86            }
87            State::End => {
88                if self.range == 0 {
89                    self.state = State::Finished;
90                    None
91                } else {
92                    self.state = State::Lattice;
93                    self.tested.set(self.range, true);
94                    Some(self.range)
95                }
96            }
97            State::Lattice => {
98                let mut out = None;
99
100                while self.pow <= self.final_pow {
101                    // Calculate next value
102                    let denominator = (1_u64 << self.pow) as usize;
103                    let val = (self.range as f64 * (self.numerator as f64 / denominator as f64))
104                        .round() as usize;
105
106                    if !self.tested.get(val).unwrap() {
107                        out = Some(val);
108                        self.tested.set(val, true);
109                    }
110
111                    // Increment numerator / denominator
112                    if self.numerator == denominator - 1 {
113                        self.numerator = 1;
114                        self.pow += 1;
115                    } else {
116                        self.numerator += 1;
117                    }
118
119                    if out.is_some() {
120                        break;
121                    }
122                }
123
124                if out.is_some() {
125                    out
126                } else {
127                    // Fill gaps with simple iteration
128                    // This is equivalent to doing the next pow, but with less redundant checks
129                    while self.numerator <= self.range {
130                        if !self.tested.get(self.numerator).unwrap() {
131                            out = Some(self.numerator);
132                            self.tested.set(self.numerator, true);
133                            self.numerator += 1;
134                            break;
135                        } else {
136                            self.numerator += 1;
137                        }
138                    }
139
140                    // Progress to finished
141                    if self.numerator > self.range {
142                        self.state = State::Finished;
143                    }
144
145                    out
146                }
147            }
148            State::Finished => None,
149        };
150
151        unshifted.map(|v| v + self.shift)
152    }
153}
154
155pub trait RlpIterator {
156    fn rlp_iter(&self) -> RlpIter;
157}
158
159impl RlpIterator for Range<usize> {
160    fn rlp_iter(&self) -> RlpIter {
161        let range = self.end - self.start - 1;
162        RlpIter {
163            tested: BitVec::from_elem(range + 1, false),
164            shift: self.start,
165            range,
166            numerator: 1,
167            pow: 1,
168            final_pow: ilog2(range),
169            state: State::Start,
170        }
171    }
172}
173
174impl RlpIterator for RangeInclusive<usize> {
175    fn rlp_iter(&self) -> RlpIter {
176        let range = self.end() - self.start();
177        RlpIter {
178            tested: BitVec::from_elem(range + 1, false),
179            shift: *self.start(),
180            range,
181            numerator: 1,
182            pow: 1,
183            final_pow: ilog2(range),
184            state: State::Start,
185        }
186    }
187}
188
189#[cfg(test)]
190mod tests {
191    use crate::RlpIterator;
192
193    #[test]
194    fn inclusive_range_works() {
195        let out: Vec<usize> = (0..=8).rlp_iter().collect();
196        assert_eq!(out[..], [0, 8, 4, 2, 6, 1, 3, 5, 7]);
197    }
198
199    #[test]
200    fn exclusive_range_works() {
201        let out: Vec<usize> = (0..9).rlp_iter().collect();
202        assert_eq!(out[..], [0, 8, 4, 2, 6, 1, 3, 5, 7]);
203    }
204
205    #[test]
206    fn offset_works() {
207        let out: Vec<usize> = (1..=9).rlp_iter().collect();
208        assert_eq!(out[..], [1, 9, 5, 3, 7, 2, 4, 6, 8]);
209    }
210
211    #[test]
212    fn extreme_offset_inclusive_works() {
213        let out: Vec<usize> = (1_000..=1_008).rlp_iter().collect();
214        assert_eq!(
215            out[..],
216            [1_000, 1_008, 1_004, 1_002, 1_006, 1_001, 1_003, 1_005, 1_007]
217        );
218    }
219
220    #[test]
221    fn extreme_offset_exclusive_works() {
222        let out: Vec<usize> = (1_000..1_009).rlp_iter().collect();
223        assert_eq!(
224            out[..],
225            [1_000, 1_008, 1_004, 1_002, 1_006, 1_001, 1_003, 1_005, 1_007]
226        );
227    }
228
229    #[test]
230    fn output_inclusive_is_complete() {
231        let mut out: Vec<usize> = (7..=7919).rlp_iter().collect();
232        let expected: Vec<usize> = (7..=7919).into_iter().collect();
233
234        out.sort();
235        assert_eq!(expected, out);
236    }
237
238    #[test]
239    fn output_exclusive_is_complete() {
240        let mut out: Vec<usize> = (7..7919).rlp_iter().collect();
241        let expected: Vec<usize> = (7..7919).into_iter().collect();
242
243        out.sort();
244        assert_eq!(expected, out);
245    }
246
247    #[test]
248    fn test_readme_example() {
249        let out: Vec<usize> = (0..=100).rlp_iter().collect();
250
251        assert_eq!(out[0..9], [0, 100, 50, 25, 75, 13, 38, 63, 88]);
252    }
253}
rlp_iter/lib.rs

rlp_iter/
lib.rs
