1
\$\begingroup\$

I am developing (WIP) a mine sweeping game to get more familiar with Rust. I decided to represent the mine field as a 2D grid. While developing I realized that this grid can be outsourced as a general purpose grid into an own module. Here it goes:

#[derive(Debug)]
pub struct Grid<T> {
    width: usize,
    height: usize,
    items: Vec<Vec<T>>,
}

impl<T> Grid<T> {
    pub fn new(width: usize, height: usize, initializer: impl Fn() -> T) -> Self {
        Self {
            width,
            height,
            items: (0..height)
                .map(move |_| (0..width).map(|_| initializer()).collect())
                .collect(),
        }
    }

    pub fn width(&self) -> usize {
        self.width
    }

    pub fn height(&self) -> usize {
        self.height
    }

    pub fn get(&self, x: usize, y: usize) -> Option<&T> {
        if x < self.width() && y < self.height() {
            Some(&self.items[y][x])
        } else {
            None
        }
    }

    pub fn get_mut(&mut self, x: usize, y: usize) -> Option<&mut T> {
        if x < self.width() && y < self.height() {
            Some(&mut self.items[y][x])
        } else {
            None
        }
    }

    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.items.iter().flat_map(|line| line)
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.items.iter_mut().flat_map(|line| line)
    }

    pub fn enumerate(&self) -> impl Iterator<Item = (usize, usize, &T)> {
        self.items
            .iter()
            .enumerate()
            .flat_map(|(y, line)| line.iter().enumerate().map(move |(x, item)| (x, y, item)))
    }

    pub fn enumerate_mut(&mut self) -> impl Iterator<Item = (usize, usize, &mut T)> {
        self.items.iter_mut().enumerate().flat_map(|(y, line)| {
            line.iter_mut()
                .enumerate()
                .map(move |(x, item)| (x, y, item))
        })
    }

    pub fn neighbors(&self, x: usize, y: usize) -> impl Iterator<Item = (usize, usize, &T)> {
        self.enumerate().filter(move |(other_x, other_y, _)| {
            is_neighbor(other_x.abs_diff(x), other_y.abs_diff(y))
        })
    }

    pub fn neighbors_mut(
        &mut self,
        x: usize,
        y: usize,
    ) -> impl Iterator<Item = (usize, usize, &mut T)> {
        self.enumerate_mut().filter(move |(other_x, other_y, _)| {
            is_neighbor(other_x.abs_diff(x), other_y.abs_diff(y))
        })
    }
}

fn is_neighbor(dx: usize, dy: usize) -> bool {
    is_adjunct(dx) && is_adjunct(dy) && !same_field(dx, dy)
}

fn is_adjunct(offset: usize) -> bool {
    offset == 0 || offset == 1
}

fn same_field(dx: usize, dy: usize) -> bool {
    dx == 0 && dy == 0
}

As I am still a beginner regarding Rust, I'd like to have feedback on the proper and idiomatic use of the language.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

That code is already of utterly high quality for a "beginner" in Rust. I think you should be proud of yourself here!

Highlights:

  • you use an initializer function in the constructor!
  • your code is generic over all types, and you use impl types where possible
  • your code is free of panics
  • you have tests for the important items

Here's what I would improve.


Linting

Use clippy to lint your code. It's the default for Rust.

The first "warning" is clippy::len_without_is_empty, which normally applies to vectors, and warns if a struct has a len(&self) -> usize method without an is_empty(&self) -> bool method. Since the length of your array is not variable, but constant after initialization, I would rename the method to something else to avoid associating your len with variable-length objects.

pub fn size(&self) -> usize {
    self.width * self.height
}

Then you have a clippy::flat_map_identity lint. Your iter and iter_mut methods make use of flat_map, which combines flatten() and map() in one function. You do not need the map part, since you do not apply any function to row. So you can shorten that to flatten().

pub fn iter(&self) -> impl Iterator<Item = &T> {
    self.items.iter().flatten()
}

pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
    self.items.iter_mut().flatten()
}

Finding neighbors

Your fn neighbors(...) -> impl Iterator is very inefficient, since you traverse the whole Grid to find the neighbors, whose coordinates you could calculate very easily instead. Calculating the coordinates directly is a constant-time operation, while your current implementation is O(n * m) where n and m are the height and width of your grid.

I would write this with slightly more code, but in a more efficient manner. Unfortunately, we need to convert between usize and isize a couple of times then.


const NEIGHBOR_INDICES: [isize; 3] = [-1, 0, 1];

..... // impl Grid

pub fn neighbors(&self, x: usize, y: usize) -> impl Iterator<Item = (usize, usize, &T)> {
    self.calc_neighbor_indices(x, y)
        .map(|(x, y)| (x, y, self.get(x, y).unwrap()))
}

fn generate_neighbor_offsets() -> impl Iterator<Item = (isize, isize)> {
    NEIGHBOR_INDICES
        .into_iter()
        .flat_map(|i| [i].into_iter().cycle().zip(NEIGHBOR_INDICES))
        .filter(|(x, y)| !(*x == 0 && *y == 0))
}

fn calc_neighbor_indices(&self, x: usize, y: usize) -> impl Iterator<Item = (usize, usize)> + '_ {
    Self::generate_neighbor_offsets()
        .map(move |(nx, ny)| (x as isize + nx, y as isize + ny))
        .filter(|(nx, ny)| {
            // remove elements outside of grid
            0 <= *nx && *nx < self.width as isize && 0 <= *ny && *ny < self.height as isize
        })
        .map(|(nx, ny)| (nx as usize, ny as usize))
}

I was surprised to find out that neighbors_mut() cannot be written in the same manner, but I cannot figure out right now how to fix it. So this does not work.

pub fn neighbors_mut(
    &mut self,
    x: usize,
    y: usize,
) -> impl Iterator<Item = (usize, usize, &mut T)> {
    self.calc_neighbor_indices(x, y)
        .map(|(x, y)| (x, y, self.get_mut(x, y).unwrap()))
}

If you could figure out how to write that correctly, you could get rid of the is_adjunct() and is_neighbor() functions.


data structure

You have decided to represent the 2D grid as a Vec<Vec<T>>, which is the trivial solution, but by far not the most efficient.

AFAICR allocating a new Vec reserves space for one element. If that space is used, and you want to push another element to the vector, the current size is doubled. So the vector grows exponentially, which is good for the runtime performance, but slow for allocation. Generally, think that each row requires ld(width) allocations, where ld is the binary logarithm. Furthermore, the same considerations apply to your outer vector. So you are looking at a total of ld(height) * ld(width) allocations (assuming no optimizations). BUT, since you used collect(), which uses FromIterator, the vector automatically is allocated with the right capacity from the size hint of the iterator, so you wouldn't need to worry about that here.

Now you have an outer vector which stores the starting address of each row vector, so you have height + 1 vectors. Since they are allocated individually, they are very likely located at different positions on the heap. That is bad for performance, since when you need the data, the CPU needs to "jump" to different addresses often. This is not critical for your envisioned minesweeper, but nevertheless good to keep in mind.

What I would do here is storing the data as 1D-vector internally, and then calculating the offsets in the vector from a provided x and y. This is often done in numerical applications, where performance is of highest importance.

#[derive(Debug)]
pub struct Grid<T> {
    width: usize,
    height: usize,
    items: Vec<T>,
}

impl<T> Grid<T> {
    pub fn new(width: usize, height: usize, initializer: impl Fn() -> T) -> Self {
        Self {
            width,
            height,
            items: (0..height)
                .flat_map(|_| (0..width).map(|_| initializer()))
                .collect(),
        }
    }


    pub fn get(&self, x: usize, y: usize) -> Option<&T> {
        if x < self.width() && y < self.height() {
            Some(&self.items[self.coordinate_to_idx(x, y)])
        } else {
            None
        }
    }

    pub fn get_mut(&mut self, x: usize, y: usize) -> Option<&mut T> {
        if x < self.width() && y < self.height() {
            let idx = self.coordinate_to_idx(x, y);
            Some(&mut self.items[idx])
        } else {
            None
        }
    }

    fn idx_to_coordinate(&self, idx: usize) -> (usize, usize) {
        let x = idx % self.width;
        let y = (idx - x) / self.width;
        (x, y)
    }


    fn coordinate_to_idx(&self, x: usize, y: usize) -> usize {
        y * self.width + x
    }

Then you can also remove the flatten() call in iter. Unfortunately, the iter_mut method has the same issue as neighbors_mut. Maybe someone else can figure that out. I have commented it out for now, to make the code compile.

Here is my final code. Please apologize that I could not get it to work entirely.

const NEIGHBOR_INDICES: [isize; 3] = [-1, 0, 1];

#[derive(Debug)]
pub struct Grid<T> {
    width: usize,
    height: usize,
    items: Vec<T>,
}

impl<T> Grid<T> {
    pub fn new(width: usize, height: usize, initializer: impl Fn() -> T) -> Self {
        Self {
            width,
            height,
            items: (0..height)
                .flat_map(|_| (0..width).map(|_| initializer()))
                .collect(),
        }
    }

    pub fn width(&self) -> usize {
        self.width
    }

    pub fn height(&self) -> usize {
        self.height
    }

    pub fn size(&self) -> usize {
        self.width * self.height
    }

    pub fn get(&self, x: usize, y: usize) -> Option<&T> {
        if x < self.width() && y < self.height() {
            Some(&self.items[self.coordinate_to_idx(x, y)])
        } else {
            None
        }
    }

    fn coordinate_to_idx(&self, x: usize, y: usize) -> usize {
        y * self.width + x
    }

    pub fn get_mut(&mut self, x: usize, y: usize) -> Option<&mut T> {
        if x < self.width() && y < self.height() {
            let idx = self.coordinate_to_idx(x, y);
            Some(&mut self.items[idx])
        } else {
            None
        }
    }

    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.items.iter()
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.items.iter_mut()
    }

    pub fn enumerate(&self) -> impl Iterator<Item = (usize, usize, &T)> {
        self.items.iter().enumerate().map(|(idx, item)| {
            let (x, y) = self.idx_to_coordinate(idx);
            (x, y, item)
        })
    }

    // pub fn enumerate_mut(&mut self) -> impl Iterator<Item = (usize, usize, &mut T)> {
    //     self.items.iter_mut().enumerate().map(|(idx, item)| {
    //         let (x, y) = self.idx_to_coordinate(idx);
    //         (x, y, item)
    //     })
    // }

    fn idx_to_coordinate(&self, idx: usize) -> (usize, usize) {
        let x = idx % self.width;
        let y = (idx - x) / self.width;
        (x, y)
    }

    pub fn neighbors(&self, x: usize, y: usize) -> impl Iterator<Item = (usize, usize, &T)> {
        self.calc_neighbor_indices(x, y)
            .map(|(x, y)| (x, y, self.get(x, y).unwrap()))
    }

    fn generate_neighbor_offsets() -> impl Iterator<Item = (isize, isize)> {
        NEIGHBOR_INDICES
            .into_iter()
            .flat_map(|i| [i].into_iter().cycle().zip(NEIGHBOR_INDICES))
            .filter(|(x, y)| !(*x == 0 && *y == 0))
    }

    fn calc_neighbor_indices(
        &self,
        x: usize,
        y: usize,
    ) -> impl Iterator<Item = (usize, usize)> + '_ {
        Self::generate_neighbor_offsets()
            .map(move |(nx, ny)| (x as isize + nx, y as isize + ny))
            .filter(|(nx, ny)| {
                // remove elements outside of grid
                0 <= *nx && *nx < self.width as isize && 0 <= *ny && *ny < self.height as isize
            })
            .map(|(nx, ny)| (nx as usize, ny as usize))
    }

    // pub fn neighbors_mut(
    //     &mut self,
    //     x: usize,
    //     y: usize,
    // ) -> impl Iterator<Item = (usize, usize, &mut T)> {
    //     self.enumerate_mut().filter(move |(other_x, other_y, _)| {
    //         is_neighbor(other_x.abs_diff(x), other_y.abs_diff(y))
    //     })
    // }
}

fn is_neighbor(dx: usize, dy: usize) -> bool {
    is_adjunct(dx) && is_adjunct(dy) && !same_field(dx, dy)
}

fn is_adjunct(offset: usize) -> bool {
    offset == 0 || offset == 1
}

fn same_field(dx: usize, dy: usize) -> bool {
    dx == 0 && dy == 0
}

\$\endgroup\$
2
  • \$\begingroup\$ Thanks. I think regarding neighbors_mut, you borrow self first immutable and then mutable, which is not allowed. You probably can first put self.calc_neighbor_indices() into a temporary variable and then operate on it. I will test this tomorrow. \$\endgroup\$ Commented Sep 24, 2022 at 8:57
  • \$\begingroup\$ Regarding the implementation with one single linear Vec, I will probably use this one, since it'll make the code easier and since the external interface is not affected by this implementation detail. \$\endgroup\$ Commented Sep 24, 2022 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.