shortestpath 0.10.0

// Copyright (C) 2025 Christian Mauduit <ufoot@ufoot.org>

use crate::distance::*;
use crate::errors::*;
use crate::gate::*;
use crate::mesh::*;
use crate::mesh_2d::index_2d::*;
use crate::mesh_2d::shape_2d::*;

/// A fully connected 2D rectangular grid mesh.
///
/// `Full2D` represents a 2D grid where all cells are walkable and each cell
/// can connect to its 8 neighbors (4 orthogonal directions + 4 diagonal directions).
/// This is the simplest 2D mesh implementation with no obstacles or walls.
///
/// # Connectivity
///
/// Each cell has up to 8 neighbors:
/// - 4 orthogonal (north, south, east, west) with distance [`DISTANCE_STRAIGHT`] (1.0)
/// - 4 diagonal (NE, NW, SE, SW) with distance [`DISTANCE_DIAGONAL`] (√2)
///
/// Edge and corner cells have fewer neighbors (3 for corners, 5 for edges).
///
/// # Memory
///
/// This mesh has minimal memory overhead - it only stores width and height,
/// computing successors on the fly.
///
/// # Example
///
/// ```
/// use shortestpath::{Mesh, Gradient, mesh_2d::Full2D};
///
/// // Create a 5x5 grid
/// let mesh = Full2D::new(5, 5);
/// assert_eq!(mesh.len(), 25);
///
/// // Use it for pathfinding
/// let mut gradient = Gradient::from_mesh(&mesh);
/// gradient.set_distance(12, 0.0); // Center cell as target
/// gradient.spread(&mesh);
///
/// // All cells now have shortest path to center
/// assert!(gradient.get_distance(0) > 0.0);
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Full2D {
    /// Width of the grid (number of columns)
    width: usize,
    /// Height of the grid (number of rows)
    height: usize,
}

impl Full2D {
    /// Creates a new fully connected 2D grid.
    ///
    /// # Arguments
    ///
    /// * `width` - Number of columns in the grid
    /// * `height` - Number of rows in the grid
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::mesh_2d::Full2D;
    ///
    /// let mesh = Full2D::new(10, 8);
    /// ```
    pub fn new(width: usize, height: usize) -> Self {
        Self { width, height }
    }

    /// Returns self unchanged since a full mesh has no disconnected zones.
    ///
    /// This method shadows [`Mesh::unique()`] to avoid the overhead of
    /// [`FilteredMesh`] when all nodes are already connected.
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Full2D};
    ///
    /// let mesh = Full2D::new(5, 5);
    /// let same_mesh: Full2D = mesh.unique(); // Returns Self, not FilteredMesh
    /// assert_eq!(same_mesh.len(), 25);
    /// ```
    pub fn unique(self) -> Self {
        self
    }

    #[inline]
    pub(crate) fn successors(width: usize, height: usize, from: usize, backward: bool) -> std::vec::IntoIter<Gate> {
        let mut peers = Vec::<Gate>::with_capacity(8);
        if let Ok(xy) = Self::index_to_xy(width, height, from) {
            let (x, y) = xy;
            if x < width - 1 {
                peers.push(Gate::new(from + 1, DISTANCE_STRAIGHT));
                if y < height - 1 {
                    peers.push(Gate::new(from + 1 + width, DISTANCE_DIAGONAL));
                }
            }
            if y < height - 1 {
                peers.push(Gate::new(from + width, DISTANCE_STRAIGHT));
                if x > 0 {
                    peers.push(Gate::new(from - 1 + width, DISTANCE_DIAGONAL));
                }
            }
            if x > 0 {
                peers.push(Gate::new(from - 1, DISTANCE_STRAIGHT));
                if y > 0 {
                    peers.push(Gate::new(from - 1 - width, DISTANCE_DIAGONAL));
                }
            }
            if y > 0 {
                peers.push(Gate::new(from - width, DISTANCE_STRAIGHT));
                if x < width - 1 {
                    peers.push(Gate::new(from + 1 - width, DISTANCE_DIAGONAL));
                }
            }
        }
        if backward {
            peers.reverse();
        }
        peers.into_iter()
    }

    #[inline]
    pub(crate) fn len(width: usize, height: usize) -> usize {
        width * height
    }

    #[inline]
    pub(crate) fn index_to_xy(width: usize, height: usize, index: usize) -> Result<(usize, usize)> {
        if index >= width * height {
            return Err(Error::invalid_index(index));
        }
        Ok((index % width, index / width))
    }

    #[inline]
    pub(crate) fn xy_to_index(width: usize, height: usize, x: usize, y: usize) -> Result<usize> {
        if x >= width || y >= height {
            return Err(Error::invalid_xy(x, y));
        }
        Ok(y * width + x)
    }

    #[inline]
    pub(crate) fn shape(width: usize, height: usize) -> (usize, usize) {
        (width, height)
    }
}

impl Mesh for Full2D {
    type IntoIter = std::vec::IntoIter<Gate>;
    fn successors(&self, from: usize, backward: bool) -> std::vec::IntoIter<Gate> {
        Self::successors(self.width, self.height, from, backward)
    }

    fn len(&self) -> usize {
        Self::len(self.width, self.height)
    }
}

impl Index2D for Full2D {
    fn index_to_xy(&self, index: usize) -> Result<(usize, usize)> {
        Self::index_to_xy(self.width, self.height, index)
    }

    fn xy_to_index(&self, x: usize, y: usize) -> Result<usize> {
        Self::xy_to_index(self.width, self.height, x, y)
    }
}

impl Shape2D for Full2D {
    fn shape(&self) -> (usize, usize) {
        Self::shape(self.width, self.height)
    }
}

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

    #[test]
    fn test_xy_w0() {
        let r = Full2D::new(0, 10);
        r.xy_to_index(0, 0).expect_err("out of bound");
        r.xy_to_index(0, 1).expect_err("out of bound");
        r.xy_to_index(1, 0).expect_err("out of bound");
        r.xy_to_index(1, 1).expect_err("out of bound");
    }

    #[test]
    fn test_xy_h0() {
        let r = Full2D::new(10, 0);
        r.xy_to_index(0, 0).expect_err("out of bound");
        r.xy_to_index(0, 1).expect_err("out of bound");
        r.xy_to_index(1, 0).expect_err("out of bound");
        r.xy_to_index(1, 1).expect_err("out of bound");
    }

    #[test]
    fn test_xy_w0h0() {
        let r = Full2D::new(0, 0);
        r.xy_to_index(0, 0).expect_err("out of bound");
        r.xy_to_index(0, 1).expect_err("out of bound");
        r.xy_to_index(1, 0).expect_err("out of bound");
        r.xy_to_index(1, 1).expect_err("out of bound");
    }

    #[test]
    fn test_xy_w4h3() {
        let r = Full2D::new(4, 3);
        assert_eq!(0, r.xy_to_index(0, 0).expect("out of bound"));
        assert_eq!(11, r.xy_to_index(3, 2).expect("out of bound"));
        assert_eq!(3, r.xy_to_index(3, 0).expect("out of bound"));
        assert_eq!(8, r.xy_to_index(0, 2).expect("out of bound"));
        r.xy_to_index(4, 0).expect_err("out of bound");
        r.xy_to_index(0, 3).expect_err("out of bound");
    }

    #[test]
    fn test_index_w0() {
        let r = Full2D::new(0, 10);
        r.index_to_xy(0).expect_err("out of bound");
        r.index_to_xy(1).expect_err("out of bound");
    }

    #[test]
    fn test_index_h0() {
        let r = Full2D::new(10, 0);
        r.index_to_xy(0).expect_err("out of bound");
        r.index_to_xy(1).expect_err("out of bound");
    }

    #[test]
    fn test_index_w0h0() {
        let r = Full2D::new(0, 0);
        r.index_to_xy(0).expect_err("out of bound");
        r.index_to_xy(1).expect_err("out of bound");
    }

    #[test]
    fn test_index_w4h3() {
        let r = Full2D::new(4, 3);
        assert_eq!((0, 0), r.index_to_xy(0).expect("out of bound"));
        assert_eq!((3, 2), r.index_to_xy(11).expect("out of bound"));
        assert_eq!((3, 0), r.index_to_xy(3).expect("out of bound"));
        assert_eq!((0, 2), r.index_to_xy(8).expect("out of bound"));
        r.index_to_xy(12).expect_err("out of bound");
    }

    #[test]
    fn test_full_rectangle_basic_w4h3() {
        let r = Full2D::new(4, 3);
        assert_eq!(
            vec![
                Gate::new(1, DISTANCE_STRAIGHT),
                Gate::new(5, DISTANCE_DIAGONAL),
                Gate::new(4, DISTANCE_STRAIGHT)
            ],
            r.successors(0, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(2, DISTANCE_STRAIGHT),
                Gate::new(6, DISTANCE_DIAGONAL),
                Gate::new(5, DISTANCE_STRAIGHT),
                Gate::new(4, DISTANCE_DIAGONAL),
                Gate::new(0, DISTANCE_STRAIGHT)
            ],
            r.successors(1, false).collect::<Vec<Gate>>(),
        );
        assert_eq!(
            vec![
                Gate::new(3, DISTANCE_STRAIGHT),
                Gate::new(7, DISTANCE_DIAGONAL),
                Gate::new(6, DISTANCE_STRAIGHT),
                Gate::new(5, DISTANCE_DIAGONAL),
                Gate::new(1, DISTANCE_STRAIGHT)
            ],
            r.successors(2, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(7, DISTANCE_STRAIGHT),
                Gate::new(6, DISTANCE_DIAGONAL),
                Gate::new(2, DISTANCE_STRAIGHT)
            ],
            r.successors(3, false).collect::<Vec<Gate>>()
        );

        assert_eq!(
            vec![
                Gate::new(5, DISTANCE_STRAIGHT),
                Gate::new(9, DISTANCE_DIAGONAL),
                Gate::new(8, DISTANCE_STRAIGHT),
                Gate::new(0, DISTANCE_STRAIGHT),
                Gate::new(1, DISTANCE_DIAGONAL)
            ],
            r.successors(4, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(6, DISTANCE_STRAIGHT),
                Gate::new(10, DISTANCE_DIAGONAL),
                Gate::new(9, DISTANCE_STRAIGHT),
                Gate::new(8, DISTANCE_DIAGONAL),
                Gate::new(4, DISTANCE_STRAIGHT),
                Gate::new(0, DISTANCE_DIAGONAL),
                Gate::new(1, DISTANCE_STRAIGHT),
                Gate::new(2, DISTANCE_DIAGONAL)
            ],
            r.successors(5, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(7, DISTANCE_STRAIGHT),
                Gate::new(11, DISTANCE_DIAGONAL),
                Gate::new(10, DISTANCE_STRAIGHT),
                Gate::new(9, DISTANCE_DIAGONAL),
                Gate::new(5, DISTANCE_STRAIGHT),
                Gate::new(1, DISTANCE_DIAGONAL),
                Gate::new(2, DISTANCE_STRAIGHT),
                Gate::new(3, DISTANCE_DIAGONAL)
            ],
            r.successors(6, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(11, DISTANCE_STRAIGHT),
                Gate::new(10, DISTANCE_DIAGONAL),
                Gate::new(6, DISTANCE_STRAIGHT),
                Gate::new(2, DISTANCE_DIAGONAL),
                Gate::new(3, DISTANCE_STRAIGHT)
            ],
            r.successors(7, false).collect::<Vec<Gate>>()
        );

        assert_eq!(
            vec![
                Gate::new(9, DISTANCE_STRAIGHT),
                Gate::new(4, DISTANCE_STRAIGHT),
                Gate::new(5, DISTANCE_DIAGONAL)
            ],
            r.successors(8, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(10, DISTANCE_STRAIGHT),
                Gate::new(8, DISTANCE_STRAIGHT),
                Gate::new(4, DISTANCE_DIAGONAL),
                Gate::new(5, DISTANCE_STRAIGHT),
                Gate::new(6, DISTANCE_DIAGONAL)
            ],
            r.successors(9, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(11, DISTANCE_STRAIGHT),
                Gate::new(9, DISTANCE_STRAIGHT),
                Gate::new(5, DISTANCE_DIAGONAL),
                Gate::new(6, DISTANCE_STRAIGHT),
                Gate::new(7, DISTANCE_DIAGONAL)
            ],
            r.successors(10, false).collect::<Vec<Gate>>()
        );
        assert_eq!(
            vec![
                Gate::new(10, DISTANCE_STRAIGHT),
                Gate::new(6, DISTANCE_DIAGONAL),
                Gate::new(7, DISTANCE_STRAIGHT)
            ],
            r.successors(11, false).collect::<Vec<Gate>>()
        );
    }

    #[test]
    fn test_successors_backward() {
        let r = Full2D::new(4, 3);

        // Test that backward=false and backward=true return same items in reverse order
        let forward = r.successors(5, false).collect::<Vec<Gate>>();
        let backward = r.successors(5, true).collect::<Vec<Gate>>();

        // Should have same length
        assert_eq!(forward.len(), backward.len());
        assert_eq!(forward.len(), 8); // Center node has 8 neighbors

        // Backward should be the reverse of forward
        let mut forward_reversed = forward.clone();
        forward_reversed.reverse();
        assert_eq!(forward_reversed, backward);

        // Test with a corner node (node 0)
        let forward_corner = r.successors(0, false).collect::<Vec<Gate>>();
        let backward_corner = r.successors(0, true).collect::<Vec<Gate>>();

        assert_eq!(forward_corner.len(), backward_corner.len());
        assert_eq!(forward_corner.len(), 3); // Corner has 3 neighbors

        let mut forward_corner_reversed = forward_corner.clone();
        forward_corner_reversed.reverse();
        assert_eq!(forward_corner_reversed, backward_corner);
    }

    #[test]
    #[cfg(feature = "serde")]
    fn test_serde() {
        let mesh = Full2D::new(10, 8);
        let json = serde_json::to_string(&mesh).unwrap();
        let deserialized: Full2D = serde_json::from_str(&json).unwrap();

        assert_eq!(mesh.len(), deserialized.len());
        assert_eq!(mesh.shape(), deserialized.shape());
    }
}