Iterator for two-dimensional coordinates

code review
1

Per title. In my case, a coordinate is let (x, y): (usize, usize). The start and end coordinate always have either the x or y value in common, so the range is either vertical (start.0 == end.0) or horizontal (start.1 == end.1). The end point should be inclusive.

My current implementation looks like

struct CoordinateRangeIterator {
    stack: Vec<(usize, usize)>,
    idx: usize,
}

impl CoordinateRangeIterator {
    fn new(start: (usize, usize), end: (usize, usize)) -> CoordinateRangeIterator {
        let stack;
        if start.0 == end.0 {
            let y_min;
            let y_max;
            if start.1 < end.1 {
                y_min = start.1;
                y_max = end.1;
            } else {
                y_min = end.1;
                y_max = start.1;
            }
            stack = (y_min..=y_max).map(|y| (start.0, y)).collect();
        } else if start.1 == end.1 {
            let x_min;
            let x_max;
            if start.0 < end.0 {
                x_min = start.0;
                x_max = end.0;
            } else {
                x_min = end.0;
                x_max = start.0;
            }
            stack = (x_min..=x_max).map(|x| (x, start.1)).collect();
        } else {
            unreachable!()
        }
        CoordinateRangeIterator { stack, idx: 0 }
    }
}

impl Iterator for CoordinateRangeIterator {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<Self::Item> {
        if self.idx < self.stack.len() {
            let item = self.stack[self.idx];
            self.idx += 1;
            Some(item)
        } else {
            None
        }
    }
}

This works:

assert_eq!(
    CoordinateRangeIterator::new((4, 6), (7, 6))
        .into_iter()
        .collect::<Vec<_>>(),
    vec![(4, 6), (5, 6), (6, 6), (7, 6)]
);
  
assert_eq!(
    CoordinateRangeIterator::new((2, 5), (2, 3))
        .into_iter()
        .collect::<Vec<_>>(),
    vec![(2, 3), (2, 4), (2, 5)]
);

Playground

My implementation returns the coordinates in "ascending" order, but that is unnecessary in my particular use case. Plus ::new() is pretty verbose for such seemingly simple behavior.

Happy for any pointers how to improve that.

2

Your unreachable! isn't really unreachable; I'd return an Option (or Result) instead. Or maybe an empty iterator.

Collecting everything ahead of time sort of defeats the idea of a lazy iterator. Instead, you can put the "next element" logic into Iterator::next, or perhaps wrap another iterator that does the work for you and call that (and map the resulting Option if needed) in next.

Your struct already is an iterator, so there's no reason to call into_iter in your tests.

Applying all of those, this is what I came up with.

2 Likes
3

Here are a few suggestions that might help.

You can store the RangeInclusive<usize> directly instead of collecting it into a Vec. This will save a lot of memory for large iterators. The other axis can be stored in an enum.

usize has some inherent methods that can simplify the constructor. Particularly min and max.

And some handy pattern patching tricks can make the iterator implementation fairly nice, too.

2 Likes
4

Thanks a ton, this is quite a lot cleaner! This functionally looks very similar to @quinedot's solution, but IMO yours is a little cleaner.

5

Well, it is unreachable within the pipeline I'm building, but you are right in the sense that this can be reached if we only look at the struct on its own. Thus, returning Option<CoordinateRangeIterator> and letting the caller use unwrap() seems cleaner, thanks!

Plus, I learned that there is unimplemented! in @parasyte's solution.

6

Sure, but that's nothing the compiler could reasonably assert (say), so a future human may come along and call it in an untended manner (or make a programming mistake with the same outcome).

Anyway, not necessarily any better or worse than some of the alternatives including the one I used,[1] but it caught my eye in a code-review way; I probably wouldn't have pointed it out if you had used unimplemented!, even.

  1. either one should be documented as an unsupported use ↩ī¸Ž

2 Likes
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.