Skip to content

Instantly share code, notes, and snippets.

@AaronM04 AaronM04/bitgrid_iter.rs
Last active Jun 26, 2018

Embed
What would you like to do?
testing BitGrid iterators
// testing bit grid iterators
// $ cargo test
type BitGrid = Vec<Vec<u64>>;
fn new_bitgrid(width_in_words: usize, height: usize) -> BitGrid {
assert!(width_in_words != 0);
assert!(height != 0);
let mut result: BitGrid = Vec::new();
for _ in 0 .. height {
let row: Vec<u64> = vec![0; width_in_words];
result.push(row);
}
result
}
struct Container {
grid: BitGrid
}
impl Container {
fn iter_ones(&self) -> IterOnes {
IterOnes{ c: &self, col: 0, row: 0}
}
}
// iter {{
struct IterOnes<'a> {
c: &'a Container,
// (col, row) is the next bit to check
col: usize,
row: usize
}
impl<'a> Iterator for IterOnes<'a> {
type Item = (usize, usize); // would also contain CellState
fn next(&mut self) -> Option<(usize, usize)> {
let height = self.c.grid.len();
if height == 0 { return None; }
let width_in_words = self.c.grid[0].len();
let mut col = self.col;
for row in self.row .. height {
while (col / 64) < width_in_words {
let mut word;
// find a non-zero word
loop {
word = self.c.grid[row][col / 64];
if word != 0 {
break
}
col &= !(64 - 1); // clear lowest 6 bits
col += 64;
if (col / 64) >= width_in_words {
break;
}
}
if (col / 64) >= width_in_words {
break;
}
let initial_shift = 63 - (col & (64 - 1));
for shift in (0 ..= initial_shift).rev() {
if (word & (1 << shift)) > 0 {
let result = (col, row);
// found a bit! increment col, and row if needed, and return
col += 1;
if (col / 64) >= width_in_words {
col = 0;
self.row = row + 1;
}
self.col = col;
self.row = row;
return Some(result);
}
col += 1;
}
assert_eq!(col & (64 - 1), 0);
}
col = 0;
}
None
}
}
// }}
fn main() {
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn iter_ones_on_empty() {
let c = Container { grid: new_bitgrid(3, 4) };
let coords: Vec<_> = c.iter_ones().collect();
assert_eq!(coords, vec![]);
}
#[test]
fn iter_ones_on_single_bit() {
let c: Container = {
let mut c = Container { grid: new_bitgrid(3, 4) };
c.grid[0][0] = 0x8000000000000000;
c
};
let coords: Vec<_> = c.iter_ones().collect();
assert_eq!(coords, vec![(0, 0)]);
}
#[test]
fn iter_ones_on_several_bits() {
let c: Container = {
let mut c = Container { grid: new_bitgrid(3, 4) };
c.grid[0][0] = 8;
c.grid[1][1] = 0xC00; // bits 10 and 11 set; 63 - 10 = 53; 63 - 11 = 52
c
};
let coords: Vec<_> = c.iter_ones().collect();
assert_eq!(coords, vec![(60, 0), (52+64, 1), (53+64, 1)]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.