testing BitGrid iterators

bitgrid_iter.rs

// 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)]);
    }
}