//! Data structure for handling (dense) 2D grids
use std::cmp;

/// 2D grid
#[derive(Debug, Clone)]
pub struct Grid2D<T> {
    width: usize,
    height: usize,
    grid: Vec<T>,
}

/// Immutable iterator over a Grid2D
#[derive(Debug)]
pub struct GridIter<'a, T> {
    owner: &'a Grid2D<T>,
    x: i32,
    y: i32,
    ofs: usize,
    /// distance between end of one span and beginning of another
    stride: usize,
    x1: i32,
    x2: i32,
    y2: i32,
}

/// Mutable iterator over a Grid2D
#[derive(Debug)]
pub struct MutGridIter<'a, T> {
    owner: &'a mut Grid2D<T>,
    x: i32,
    y: i32,
    ofs: usize,
    /// distance between end of one span and beginning of another
    stride: usize,
    x1: i32,
    x2: i32,
    y2: i32,
}

impl<T: Clone> Grid2D<T> {
    /// New empty grid
    pub fn new() -> Grid2D<T> {
        Grid2D {
            width: 0,
            height: 0,
            grid: Vec::new(),
        }
    }

    /// New sized grid, filled in with value
    pub fn new_sized(width: usize, height: usize, val: &T) -> Grid2D<T> {
        Grid2D {
            width,
            height,
            grid: vec![val.clone(); width * height],
        }
    }

    /// Coordinates to offset in array
    fn to_offset(&self, x: i32, y: i32) -> Option<usize> {
        // This makes use of the fact that negative values casted to usize
        // will be larger than the width/height.
        if (x as usize) < self.width && (y as usize) < self.height {
            Some((y as usize) * self.width + (x as usize))
        } else {
            None
        }
    }

    /// 2D map lookup
    pub fn get(&self, x: i32, y: i32) -> Option<&T> {
        self.to_offset(x, y).map(|ofs| &self.grid[ofs])
    }

    /// 2D map lookup (mutable)
    #[allow(dead_code)]
    pub fn get_mut(&mut self, x: i32, y: i32) -> Option<&mut T> {
        // Cannot use the following:
        // self.to_offset(x, y).map(|ofs| &mut self.grid[ofs])
        //   error[E0373]: closure may outlive the current function, but it borrows `self`, which is
        //   owned by the current function
        if let Some(ofs) = self.to_offset(x, y) {
            Some(&mut self.grid[ofs])
        } else {
            None
        }
    }

    /// 2D map put
    pub fn set(&mut self, x: i32, y: i32, tile_in: T) -> bool {
        if let Some(ofs) = self.to_offset(x, y) {
            self.grid[ofs] = tile_in;
            true
        } else {
            false
        }
    }

    /// Return width of grid
    pub fn width(&self) -> usize {
        self.width
    }

    /// Return height of grid
    pub fn height(&self) -> usize {
        self.height
    }

    /// Clip a rectangle against grid boundaries
    fn clip_rect(&self, x1: i32, y1: i32, x2: i32, y2: i32) -> (i32, i32, i32, i32) {
        let x1 = cmp::min(cmp::max(x1, 0), self.width as i32);
        let x2 = cmp::min(cmp::max(x2, 0), self.width as i32);
        let y1 = cmp::min(cmp::max(y1, 0), self.height as i32);
        let y2 = cmp::min(cmp::max(y2, 0), self.height as i32);
        (x1, y1, x2, y2)
    }

    /// Iterate over a rectangle
    pub fn iter_region(&self, x1: i32, y1: i32, x2: i32, y2: i32) -> GridIter<T> {
        let (x1, y1, x2, y2) = self.clip_rect(x1, y1, x2, y2);
        let ofs = self.to_offset(x1, y1).unwrap_or(0);
        let stride = self.width - cmp::max(x2 - x1, 0) as usize;
        GridIter {
            owner: self,
            x: x1,
            y: y1,
            ofs: ofs,
            stride,
            x1,
            x2,
            y2,
        }
    }

    /// Iterate over a rectangle (mutable)
    #[allow(dead_code)]
    pub fn iter_region_mut(&mut self, x1: i32, y1: i32, x2: i32, y2: i32) -> MutGridIter<T> {
        let (x1, y1, x2, y2) = self.clip_rect(x1, y1, x2, y2);
        let ofs = self.to_offset(x1, y1).unwrap_or(0);
        let stride = self.width - cmp::max(x2 - x1, 0) as usize;
        MutGridIter {
            owner: self,
            x: x1,
            y: y1,
            ofs,
            stride,
            x1,
            x2,
            y2,
        }
    }

    /// Iterate over entire grid
    #[allow(dead_code)]
    pub fn iter(&mut self) -> GridIter<T> {
        let (x2, y2) = (self.width as i32, self.height as i32);
        GridIter {
            owner: self,
            x: 0,
            y: 0,
            ofs: 0,
            stride: 0,
            x1: 0,
            x2,
            y2,
        }
    }

    /// Iterate over entire grid (mutable)
    pub fn iter_mut(&mut self) -> MutGridIter<T> {
        let (x2, y2) = (self.width as i32, self.height as i32);
        MutGridIter {
            owner: self,
            x: 0,
            y: 0,
            ofs: 0,
            stride: 0,
            x1: 0,
            x2,
            y2,
        }
    }

    // TODO: consuming iterator iter_into() ? would be useful for operations that create
    // a new structure and throw away the old one.
}

impl<'a, T> Iterator for GridIter<'a, T> {
    type Item = ((i32, i32), &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        if self.y < self.y2 && self.x < self.x2 {
            // This assumes no out-of-bounds access as the original rectangle
            // was clipped against the owner extents.
            let ret = Some(((self.x, self.y), &self.owner.grid[self.ofs]));

            // Advance
            self.x += 1;
            self.ofs += 1;
            if self.x >= self.x2 {
                self.x = self.x1;
                self.y += 1;
                self.ofs += self.stride;
            }

            ret
        } else {
            // out of range
            None
        }
    }
}

impl<'a, T> Iterator for MutGridIter<'a, T> {
    type Item = ((i32, i32), &'a mut T);

    fn next(&mut self) -> Option<Self::Item> {
        if self.y < self.y2 && self.x < self.x2 {
            // This assumes no out-of-bounds access as the original rectangle
            // was clipped against the owner extents.
            // TODO cannot get rid of the unsafe here?
            //   error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in
            //   function call due to conflicting requirements
            let ret = Some(((self.x, self.y), unsafe {
                &mut *(&mut self.owner.grid[self.ofs] as *mut T)
            }));

            // Advance
            self.x += 1;
            self.ofs += 1;
            if self.x >= self.x2 {
                self.x = self.x1;
                self.y += 1;
                self.ofs += self.stride;
            }

            ret
        } else {
            // out of range
            None
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_new() {
        let x = Grid2D::<i32>::new();
        assert_eq!(x.get(-1, -1), None);
        assert_eq!(x.get(0, 0), None);
        assert_eq!(x.get(1, 1), None);
    }

    #[test]
    fn test() {
        let mut x = Grid2D::new_sized(3, 3, &0);
        x.set(1, 1, 21);
        *(x.get_mut(2, 2).unwrap()) = 23;
        *(x.get_mut(2, 1).unwrap()) = 26;
        assert_eq!(x.get(0, 0), Some(&0));
        assert_eq!(x.get(0, 1), Some(&0));
        assert_eq!(x.get(0, 2), Some(&0));
        assert_eq!(x.get(1, 1), Some(&21));
        assert_eq!(x.get(2, 1), Some(&26));
        assert_eq!(x.get(2, 2), Some(&23));
    }

    #[test]
    fn test_iter_region() {
        let mut x = Grid2D::new_sized(3, 3, &0);
        x.set(1, 1, 21);
        x.set(2, 1, 23);
        let mut i = x.iter_region(-1, -1, 4, 4);
        assert_eq!(i.next(), Some(((0, 0), &0)));
        assert_eq!(i.next(), Some(((1, 0), &0)));
        assert_eq!(i.next(), Some(((2, 0), &0)));
        assert_eq!(i.next(), Some(((0, 1), &0)));
        assert_eq!(i.next(), Some(((1, 1), &21)));
        assert_eq!(i.next(), Some(((2, 1), &23)));
        assert_eq!(i.next(), Some(((0, 2), &0)));
        assert_eq!(i.next(), Some(((1, 2), &0)));
        assert_eq!(i.next(), Some(((2, 2), &0)));
        assert_eq!(i.next(), None);

        let mut i = x.iter_region(1, 1, 4, 4);
        assert_eq!(i.next(), Some(((1, 1), &21)));
        assert_eq!(i.next(), Some(((2, 1), &23)));
        assert_eq!(i.next(), Some(((1, 2), &0)));
        assert_eq!(i.next(), Some(((2, 2), &0)));
        assert_eq!(i.next(), None);

        let mut i = x.iter_region(-1, -1, 2, 2);
        assert_eq!(i.next(), Some(((0, 0), &0)));
        assert_eq!(i.next(), Some(((1, 0), &0)));
        assert_eq!(i.next(), Some(((0, 1), &0)));
        assert_eq!(i.next(), Some(((1, 1), &21)));

        let mut i = x.iter_region(1, 1, 1, 1);
        assert_eq!(i.next(), None);

        let mut i = x.iter_region(1, 1, -1, -1);
        assert_eq!(i.next(), None);
    }

    #[test]
    fn test_iter_region_mut() {
        let mut x = Grid2D::new_sized(3, 3, &0);
        x.set(1, 1, 21);
        {
            let mut i = x.iter_region_mut(-1, -1, 4, 4);
            assert_eq!(i.next(), Some(((0, 0), &mut 0)));
            assert_eq!(i.next(), Some(((1, 0), &mut 0)));
            assert_eq!(i.next(), Some(((2, 0), &mut 0)));
            assert_eq!(i.next(), Some(((0, 1), &mut 0)));
            assert_eq!(i.next(), Some(((1, 1), &mut 21)));
            assert_eq!(i.next(), Some(((2, 1), &mut 0)));
            assert_eq!(i.next(), Some(((0, 2), &mut 0)));
            assert_eq!(i.next(), Some(((1, 2), &mut 0)));
            assert_eq!(i.next(), Some(((2, 2), &mut 0)));
            assert_eq!(i.next(), None);
        }
        {
            let mut i = x.iter_region_mut(1, 1, 4, 4);
            assert_eq!(i.next(), Some(((1, 1), &mut 21)));
            assert_eq!(i.next(), Some(((2, 1), &mut 0)));
            assert_eq!(i.next(), Some(((1, 2), &mut 0)));
            assert_eq!(i.next(), Some(((2, 2), &mut 0)));
            assert_eq!(i.next(), None);
        }
        {
            let mut i = x.iter_region_mut(-1, -1, 2, 2);
            assert_eq!(i.next(), Some(((0, 0), &mut 0)));
            assert_eq!(i.next(), Some(((1, 0), &mut 0)));
            assert_eq!(i.next(), Some(((0, 1), &mut 0)));
            assert_eq!(i.next(), Some(((1, 1), &mut 21)));
        }
        {
            let mut i = x.iter_region_mut(1, 1, 1, 1);
            assert_eq!(i.next(), None);
        }
        {
            let mut i = x.iter_region_mut(1, 1, -1, -1);
            assert_eq!(i.next(), None);
        }
        {
            for (_, cell) in x.iter_region_mut(0, 0, 2, 2) {
                *cell = 111;
            }
            for (_, cell) in x.iter_region(0, 0, 2, 2) {
                assert_eq!(*cell, 111);
            }
        }
    }
}