My original version used half-open bounds instead of inclusive bounds; perhaps that's the difference.
Still much faster than mine, great,
Along similar lines, here's a version that uses the smallvec
crate for the coordinates. If the dimensionality is small enough (<= 8 as written, but tunable), there won't be heap allocations.
use smallvec::SmallVec; // 1.5.1
type Coord = SmallVec<[u8;8]>;
struct CellIter {
start: Coord,
end: Coord,
pending: Coord,
done: bool,
}
impl Iterator for CellIter {
type Item = Coord;
fn next(&mut self) -> Option<Coord> {
(!self.done).then(|| {
let result = self.pending.clone();
self.done = (0..self.pending.len()).rev().all(|i| {
if self.pending[i] < self.end[i] {
self.pending[i] += 1;
false
} else {
self.pending[i] = self.start[i];
true
}
});
result
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
if self.done {
(0, Some(0))
} else {
let mut x = 1_usize;
let mut r = 1_usize;
for i in (0..self.pending.len()).rev() {
r += (self.end[i] - self.pending[i]) as usize * x;
x *= (self.end[i] - self.start[i]) as usize + 1;
}
(r, Some(r))
}
}
}
impl ExactSizeIterator for CellIter {}
fn calc_cells(start: Coord, end: Coord) -> CellIter {
assert_eq!(start.len(), end.len());
CellIter {
done: start.iter().zip(end.iter()).any(|(s, e)| s > e),
pending: start.clone(),
start,
end,
}
}
fn main() {
let start = SmallVec::from_vec(vec![0, 0, 0]);
let end:Coord = SmallVec::from_vec(vec![127,127,29]);
let all_cells = calc_cells(start.clone(), end.clone()).collect::<Vec<_>>();
let mut l = dbg!(all_cells.len());
let mut iter = calc_cells(start, end);
assert_eq!(iter.size_hint().0, l);
while let Some(_) = iter.next() {
l -= 1;
assert_eq!(iter.size_hint().0, l);
}
assert_eq!(l, 0);
}
4 Likes
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.