#[derive(Clone, Debug)]
pub struct Grid<T> {
    width: usize,
    height: usize,
    // data.len() == width * height
    data: Box<[T]>,
}

/// An `Iterator<Item = (Coord, &mut T)>` over a sub-section of a Grid<T>.
pub struct IterRectMut<'a, T: 'a> {
    // Iterator over the subrect
    ri: RectIter,
    grid_width: usize,
    // XXX: can this be `&mut [T]` safely?
    // XXX: if not, can/should it and len be replaced by `*mut [T]`?
    data: *mut T,
    len: usize,
    // Is this the right param?
    _marker: std::marker::PhantomData<&'a mut T>,
}

impl<T> Grid<T> {
    pub fn iter_rect_mut(&mut self, c: Coord, w: usize, h: usize) -> IterRectMut<T> {
        assert!(self.contains_entire_rect(c, w, h));
        IterRectMut {
            ri: rect_iter(c, w, h),
            grid_width: self.width,
            len: self.data.len(),
            data: self.data.as_mut_ptr(),
            _marker: std::marker::PhantomData,
        }
    }
}

impl<'a, T: 'a> Iterator for IterRectMut<'a, T> {
    type Item = (Coord, &'a mut T);
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let c = self.ri.next()?;
        let xu = c.x as usize;
        let yu = c.y as usize;
        assert!(xu < self.grid_width && yu < (self.len / self.grid_width));

        let idx = xu + yu * self.grid_width;
        assert!(idx < self.len);
        let item = unsafe { &mut *self.data.add(idx) };
        Some((c, item))
    }
}

// Misc details below, not really what I'm asking about but included to make
// things compile and for clarity. I've cut out as much as I reasonably could.
// at the bottom there's a (not super relevant) example

impl<T> Grid<T> {
    pub fn contains_entire_rect(&self, c: Coord, w: usize, h: usize) -> bool {
        if c.x < 0 || c.y < 0 {
            return false;
        }
        let right = (c.x as usize).saturating_add(w);
        let bottom = (c.y as usize).saturating_add(h);
        right <= self.width && bottom <= self.height
    }

    pub fn new(width: usize, height: usize, data: Box<[T]>) -> Self {
        assert_eq!(width * height, data.len());
        Self { width, height, data }
    }

    pub fn build<F: FnMut(Coord) -> T>(width: usize, height: usize, mut builder: F) -> Grid<T> {
        let mut data = Vec::with_capacity(width * height);
        for y in 0..height {
            for x in 0..width {
                data.push(builder(Coord::new(x as i32, y as i32)));
            }
        }
        Grid::new(width, height, data.into())
    }
}
// Several things omitted for simplicity
#[derive(Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord, Debug, Default)]
pub struct Coord { pub x: i32, pub y: i32 }
impl Coord {
    pub fn new(x: i32, y: i32) -> Self { Self { x, y } }
}

// Several things omitted for simplicity
#[derive(Copy, Clone, Eq, Hash, PartialEq, PartialOrd, Ord, Debug)]
pub struct RectIter {
    ix: usize, iy: usize,
    w: usize, h: usize,
    c: Coord
}

#[inline]
pub fn rect_iter(c: Coord, w: usize, h: usize) -> RectIter {
    let h = if w == 0 { 0 } else { h };
    RectIter { ix: 0, iy: 0, w, h, c }
}

impl Iterator for RectIter {
    type Item = Coord;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.iy >= self.h {
            return None;
        }
        // Checked on construction
        debug_assert!(self.w != 0);
        let item = Coord::new(
            self.ix as i32 + self.c.x,
            self.iy as i32 + self.c.y
        );
        self.ix += 1;
        if self.ix >= self.w {
            self.ix = 0;
            self.iy += 1;
        }
        Some(item)
    }
    // more crap omitted here
}


// not super relevant example
fn main() {
    let mut g = Grid::build(5, 5, |c| (c, 0u8));

    for (coord, cell) in g.iter_rect_mut(Coord::new(1, 1), 3, 3) {
        assert_eq!(coord, cell.0);
        cell.1 += 1;
    }
    assert_eq!(&g.data.iter().map(|(_, n)| *n).collect::<Vec<_>>(), &[
        0, 0, 0, 0, 0,
        0, 1, 1, 1, 0,
        0, 1, 1, 1, 0,
        0, 1, 1, 1, 0,
        0, 0, 0, 0, 0,
    ]);

    for (coord, cell) in g.iter_rect_mut(Coord::new(0, 0), 5, 5) {
        assert_eq!(coord, cell.0);
        cell.1 += 1;
    }

    assert_eq!(&g.data.iter().map(|(_, n)| *n).collect::<Vec<_>>(), &[
        1, 1, 1, 1, 1,
        1, 2, 2, 2, 1,
        1, 2, 2, 2, 1,
        1, 2, 2, 2, 1,
        1, 1, 1, 1, 1,
    ]);
}