CODEWITHSUNDEEP
rustiterator
Julian
Julian

Reputation: 71

How to return borrowed iterators for arbitrary subsets of arrays in Rust

I learn Rust and want to implement some toy project: A DFS/BFS Sudoku solver

To do so I've chosen the underlying data structure to be a sugar coated [Option<u8>; 81]. I experienced some problems defining methods to return rows and columns from the board. What I also tried to achieve is to have some kind of efficient implementation. For example to check if all rows/columns are valid (with early abort) or just display all values in a grid. Therefore I wanted to check if it is possible to not copy any data, but rather have iterators that just point to the right data cells.

Here is what I came up with:

struct Board {
    fields: [Option<u8>; 81],
}

impl Board {
    pub fn rows(&self) -> impl Iterator<Item = &[Option<u8>]> {
        (0..81)
            .step_by(9)
            .map(|index| &self.fields[index..(index + 9)])
    }

    pub fn columns(&self) -> impl Iterator<Item = Vec<&Option<u8>>> {
        (0..9).map(|offset| {
            let map = (0..9).map(|index| &self.fields[9 * index + offset]);
            let row: Vec<&Option<u8>> = map.collect();
            row
        })
    }
}

fn main() {
    let board = Board {
        fields: std::iter::repeat(Some(1))
            .take(81)
            .collect::<Vec<_>>()
            .try_into()
            .unwrap(),
    };
    println!("{}", board);
}

impl std::fmt::Display for Board {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        for row in self.rows() {
            for field in row.iter() {
                match field {
                    Some(number) => write!(f, "{}", number)?,
                    None => write!(f, " ")?,
                }
            }
            write!(f, "\n")?
        }
        Ok(())
    }
}

Despite the similar idea of row and column the return types are quite different. Iterator over reference of Arrays containing options (seems right to me) and iterator over vectors of references of options. Especially the columns method looks wrong to me as it materializes a Vec and has references of the options inside. How do I align those return types? Bonus: How would the 3x3 sub-matrices look like?

Upvotes: 0

Views: 155

Answers (1)

Chayim Friedman
Chayim Friedman

Reputation: 71450

You wanted to optimize and went with allocating Vecs? Certainly an example of mis-optimization.

I would recommend you to not try optimizing it unless profling shows a bottleneck. Copying 162 bytes (81 * mem::size_of::<Option<u8>>()) is unlikely to be a bottleneck, and you can optimize the memory layout even more (one of the simplest options come to mind is to use Option<std::num::NonZeroU8> for cells, since it occupies only one byte (instead of two) and cells cannot contain zeroes).

Anyway, answering your question: &[Option<u8>] (a reference to slice of Option<u8>) is not owned, while Vec<&Option<u8>> is. The first is a view into the collection - and as such, you can only get references out of it. That is, you cannot move out of it. Because of that, it makes no sense to use &[&Option<u8>]. Looking on it from a different angle, <&[Option<u8>]>::into_iter() (actually same as <&[Option<u8>]>::iter()) will provide you an iterator over &Option<u8>. On the other hand, Vec<T> is owned - and thus you had to be explicit with the references, because <Vec<Option<u8>>>::into_iter() provides an iterator over owned Option<T>s.

If you insist on using iterators, you can return iterator-of-iterators instead of a container. E.g.:


    pub fn rows(&self) -> impl Iterator<Item = impl Iterator<Item = &Option<u8>>> {
        (0..81)
            .step_by(9)
            .map(move |index| self.fields[index..(index + 9)].iter())
    }

    pub fn columns(&self) -> impl Iterator<Item = impl Iterator<Item = &Option<u8>>> {
        (0..9).map(move |offset| (0..9).map(move |index| &self.fields[9 * index + offset]))
    }

Although I would probably use an easier-to-maintain custom Iterator type:

struct Row<'a> {
    left: std::slice::Iter<'a, Option<u8>>,
}
impl Iterator for Row<'_> {
    type Item = Option<u8>;
    fn next(&mut self) -> Option<Self::Item> {
        self.left.next().copied()
    }
    // May implement `size_hint()` and `ExactSizeIterator` for better performance
}

struct Column<'a> {
    board: &'a Board,
    index: usize,
}
impl Iterator for Column<'_> {
    type Item = Option<u8>;
    fn next(&mut self) -> Option<Self::Item> {
        let result = self.board.fields.get(self.index)?;
        self.index += 9;
        Some(*result)
    }
}

impl Board {
    pub fn rows(&self) -> impl Iterator<Item = Row<'_>> {
        self.fields
            .chunks_exact(9)
            .map(|row| Row { left: row.iter() })
    }

    pub fn columns(&self) -> impl Iterator<Item = Column<'_>> {
        (0..9).map(move |index| Column { board: self, index })
    }
}

Upvotes: 1

Related Questions