More efficient iteration through cells in a grid

6

Are you familiar with integer division and modulus? There is a very simple trick for converting between flat indices into your Vec and (row, col) pairs.

Assuming data is ordered so that values of equal row are contiguous:

  • index = width * row + col
  • col = index % width
  • row = index / width

With this, you do not need a Cell type, because you can easily recover row and col from an index. Here is a wrapper type which makes use of these relationships. Try working with a Grid<Enum>:

struct Grid<T> {
    dim: (usize, usize),
    data: Vec<T>,
}

type Pos = (usize, usize); // written as (row, column)

impl<T> Grid<T> {
    pub fn new(dim: (usize, usize), data: Vec<T>) -> Self {
        assert_eq!(dim.0 * dim.1, data.len());
        Grid { dim, data }
    }
    fn flat_index(&self, pos: Pos) -> usize {
        assert!(pos.0 < self.dim.0);
        assert!(pos.1 < self.dim.1);

        let strides = (self.dim.1, 1);

        pos.0 * strides.0 + pos.1 * strides.1
    }

    // inverse of flat_index
    fn pos(&self, index: usize) -> Pos {
        (index / self.dim.1, index % self.dim.1)
    }

    pub fn at_pos(&self, pos: Pos) -> &T {
        &self.data[self.flat_index(pos)]
    }
}

Such a helper type could expose methods for viewing neighbors as follows:

impl<T> Grid<T> {
    pub fn neighbors(&self, pos: Pos) -> Vec<&T> {
        let mut out = Vec::with_capacity(4);
        self.each_neighbor_pos(pos, |neighbor| {
            out.push(self.at_pos(neighbor));
        });
        out
    }

    // helper, written in the form of an "internal iterator" to make it
    // easier to add other things (like e.g. a `neighbors_mut` function)
    fn each_neighbor_pos(&self, pos: Pos, mut func: impl FnMut(Pos)) {
        if pos.0 != 0 {
            func((pos.0 - 1, pos.1));
        }
        if pos.1 != 0 {
            func((pos.0, pos.1 - 1));
        }

        if pos.0 + 1 != self.dim.0 {
            func((pos.0 + 1, pos.1));
        }
        if pos.1 + 1 != self.dim.1 {
            func((pos.0, pos.1 + 1));
        }
    }
}

Note that several popular third-party implementations of my Grid type already exist if you are interested. See:

  • ndarray, a generalization to n dimensions which also works with discontiguous data. (this is on the "complicated but powerful" end!)
  • imgref, which despite the name is not just for images! I've never used it but I know it provides a 2D type much like my Grid (as well as "grid views" for viewing a region of the grid), and is probably easier to learn than ndarray.