algorithmmatrixrust

How do I get all the neighbour-indices in a matrix without including negative values?


I'm struggling to find all direct neighbours for a given position (which is a (usize, usize)) in an N x M matrix.

The matrix provides a method get(p: Position) -> Option<T> where it does bounds checking and returns None if the position is out of range. This means an upper bound does not need to be checked, but a lower bound still needs to. That is, it does not underflow 0 in any direction.

My first attempt was to iterate over the slice &[-1, 0, 1] and use checked_add, but this does not work because -1 is not a usize.

My next attempt was to subtract 1 from my position (both x and y) and then iterate over the slice &[0, 1, 2], but that does not work the position (0, _) or (_, 0).

I prepared a playground, where one just can implement the one function. (I hope my tests are correct)

type Position = (usize, usize); //x, y

fn get_neighbours(p: Position) -> impl Iterator<Item = Position> {
    unimplemented!()
}

(impl Iterator can be replaced by Vec if necessary).


Solution

  • You just need to use if expressions to handle the special case that the coordinates are zero, e.g.

    fn get_neighbours(p: Position) -> impl Iterator<Item = Position> {
        let m_range = if p.0 > 0 { p.0 - 1..p.0 + 2 } else { 0..2 };
        let n_range = if p.1 > 0 { p.1 - 1..p.1 + 2 } else { 0..2 };
        m_range
            .flat_map(move |m| n_range.clone().map(move |n| (m, n)))
            .filter(move |&q| p != q)
    }