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_3d::index_3d::*;
use crate::mesh_3d::shape_3d::*;

/// A fully connected true 3D rectangular volume mesh.
///
/// `Full3D` represents a true 3D volume where all cells are walkable and each cell
/// can connect to all 26 neighboring cells. This includes diagonal connections across
/// layers, unlike [`mesh_25d::Full25D`](crate::mesh_25d::Full25D) which only supports
/// vertical movement directly up/down.
///
/// This is the simplest true 3D mesh implementation with no obstacles or walls.
///
/// # Connectivity
///
/// Each cell has up to 26 neighbors organized in three layers:
///
/// **Current layer (z=0):** 8 neighbors
/// - 4 orthogonal (N, S, E, W) with distance [`DISTANCE_STRAIGHT`] (1.0)
/// - 4 diagonal (NE, NW, SE, SW) with distance [`DISTANCE_DIAGONAL`] (√2)
///
/// **Layer above (z=+1):** 9 neighbors
/// - 1 directly above with distance [`DISTANCE_STRAIGHT`] (1.0)
/// - 4 orthogonal diagonals (N+up, S+up, E+up, W+up) with distance [`DISTANCE_DIAGONAL`] (√2)
/// - 4 full diagonals (NE+up, NW+up, SE+up, SW+up) with distance [`DISTANCE_DIAGONAL_3D`] (√3)
///
/// **Layer below (z=-1):** 9 neighbors (same pattern as above)
///
/// Edge, face, and corner cells have fewer neighbors.
///
/// # Memory
///
/// This mesh has minimal memory overhead - it only stores width, height, and depth,
/// computing successors on the fly.
///
/// # Example
///
/// ```
/// use shortestpath::{Mesh, Gradient, mesh_3d::Full3D};
///
/// // Create a 5x5x5 volume
/// let mesh = Full3D::new(5, 5, 5);
/// assert_eq!(mesh.len(), 125);
///
/// // Use it for pathfinding
/// let mut gradient = Gradient::from_mesh(&mesh);
/// gradient.set_distance(62, 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 Full3D {
    /// Width of the volume (number of columns)
    width: usize,
    /// Height of the volume (number of rows)
    height: usize,
    /// Depth of the volume (number of layers)
    depth: usize,
}

impl Full3D {
    /// Creates a new fully connected true 3D volume.
    ///
    /// # Arguments
    ///
    /// * `width` - Number of columns in the volume
    /// * `height` - Number of rows in the volume
    /// * `depth` - Number of layers in the volume
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::mesh_3d::Full3D;
    ///
    /// let mesh = Full3D::new(10, 8, 6);
    /// ```
    pub fn new(width: usize, height: usize, depth: usize) -> Self {
        Self {
            width,
            height,
            depth,
        }
    }

    /// 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_3d::Full3D};
    ///
    /// let mesh = Full3D::new(5, 5, 5);
    /// let same_mesh: Full3D = mesh.unique(); // Returns Self, not FilteredMesh
    /// assert_eq!(same_mesh.len(), 125);
    /// ```
    pub fn unique(self) -> Self {
        self
    }

    #[inline]
    pub(crate) fn successors(
        width: usize,
        height: usize,
        depth: usize,
        from: usize,
        backward: bool,
    ) -> std::vec::IntoIter<Gate> {
        let mut peers = Vec::<Gate>::with_capacity(26);
        if let Ok(xyz) = Self::index_to_xyz(width, height, depth, from) {
            let (x, y, z) = xyz;
            let layer_size = width * height;

            // Current layer (z=0): 8 neighbors
            // East
            if x < width - 1 {
                peers.push(Gate::new(from + 1, DISTANCE_STRAIGHT));
            }
            // West
            if x > 0 {
                peers.push(Gate::new(from - 1, DISTANCE_STRAIGHT));
            }
            // South
            if y < height - 1 {
                peers.push(Gate::new(from + width, DISTANCE_STRAIGHT));
            }
            // North
            if y > 0 {
                peers.push(Gate::new(from - width, DISTANCE_STRAIGHT));
            }
            // Southeast
            if x < width - 1 && y < height - 1 {
                peers.push(Gate::new(from + 1 + width, DISTANCE_DIAGONAL));
            }
            // Southwest
            if x > 0 && y < height - 1 {
                peers.push(Gate::new(from - 1 + width, DISTANCE_DIAGONAL));
            }
            // Northeast
            if x < width - 1 && y > 0 {
                peers.push(Gate::new(from + 1 - width, DISTANCE_DIAGONAL));
            }
            // Northwest
            if x > 0 && y > 0 {
                peers.push(Gate::new(from - 1 - width, DISTANCE_DIAGONAL));
            }

            // Layer above (z=+1): 9 neighbors
            if z < depth - 1 {
                let up_offset = layer_size;
                // Directly up
                peers.push(Gate::new(from + up_offset, DISTANCE_STRAIGHT));

                // Orthogonal diagonals (up + horizontal)
                if x < width - 1 {
                    peers.push(Gate::new(from + up_offset + 1, DISTANCE_DIAGONAL));
                }
                if x > 0 {
                    peers.push(Gate::new(from + up_offset - 1, DISTANCE_DIAGONAL));
                }
                if y < height - 1 {
                    peers.push(Gate::new(from + up_offset + width, DISTANCE_DIAGONAL));
                }
                if y > 0 {
                    peers.push(Gate::new(from + up_offset - width, DISTANCE_DIAGONAL));
                }

                // Full 3D diagonals (up + 2D diagonal)
                if x < width - 1 && y < height - 1 {
                    peers.push(Gate::new(from + up_offset + 1 + width, DISTANCE_DIAGONAL_3D));
                }
                if x > 0 && y < height - 1 {
                    peers.push(Gate::new(from + up_offset - 1 + width, DISTANCE_DIAGONAL_3D));
                }
                if x < width - 1 && y > 0 {
                    peers.push(Gate::new(from + up_offset + 1 - width, DISTANCE_DIAGONAL_3D));
                }
                if x > 0 && y > 0 {
                    peers.push(Gate::new(from + up_offset - 1 - width, DISTANCE_DIAGONAL_3D));
                }
            }

            // Layer below (z=-1): 9 neighbors
            if z > 0 {
                let down_offset = layer_size;
                // Directly down
                peers.push(Gate::new(from - down_offset, DISTANCE_STRAIGHT));

                // Orthogonal diagonals (down + horizontal)
                if x < width - 1 {
                    peers.push(Gate::new(from - down_offset + 1, DISTANCE_DIAGONAL));
                }
                if x > 0 {
                    peers.push(Gate::new(from - down_offset - 1, DISTANCE_DIAGONAL));
                }
                if y < height - 1 {
                    peers.push(Gate::new(from - down_offset + width, DISTANCE_DIAGONAL));
                }
                if y > 0 {
                    peers.push(Gate::new(from - down_offset - width, DISTANCE_DIAGONAL));
                }

                // Full 3D diagonals (down + 2D diagonal)
                if x < width - 1 && y < height - 1 {
                    peers.push(Gate::new(from - down_offset + 1 + width, DISTANCE_DIAGONAL_3D));
                }
                if x > 0 && y < height - 1 {
                    peers.push(Gate::new(from - down_offset - 1 + width, DISTANCE_DIAGONAL_3D));
                }
                if x < width - 1 && y > 0 {
                    peers.push(Gate::new(from - down_offset + 1 - width, DISTANCE_DIAGONAL_3D));
                }
                if x > 0 && y > 0 {
                    peers.push(Gate::new(from - down_offset - 1 - width, DISTANCE_DIAGONAL_3D));
                }
            }
        }
        if backward {
            peers.reverse();
        }
        peers.into_iter()
    }

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

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

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

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

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

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

impl Index3D for Full3D {
    fn index_to_xyz(&self, index: usize) -> Result<(usize, usize, usize)> {
        Self::index_to_xyz(self.width, self.height, self.depth, index)
    }

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

impl Shape3D for Full3D {
    fn shape(&self) -> (usize, usize, usize) {
        Self::shape(self.width, self.height, self.depth)
    }
}

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

    #[test]
    fn test_full_rectangle_basic_w4h3() {
        let depth = 2;
        let width = 4;
        let height = 3;
        let r = Full3D::new(width, height, depth);
        assert_eq!(width * height * depth, r.len());
    }

    #[test]
    fn test_index_w0() {
        let r = Full3D::new(0, 10, 10);
        assert_eq!(r.len(), 0);
    }

    #[test]
    fn test_index_h0() {
        let r = Full3D::new(10, 0, 10);
        assert_eq!(r.len(), 0);
    }

    #[test]
    fn test_index_d0() {
        let r = Full3D::new(10, 10, 0);
        assert_eq!(r.len(), 0);
    }

    #[test]
    fn test_index_w0h0d0() {
        let r = Full3D::new(0, 0, 0);
        assert_eq!(r.len(), 0);
    }

    #[test]
    fn test_index_w4h3d2() {
        let r = Full3D::new(4, 3, 2);
        assert!(r.index_to_xyz(0).is_ok());
        assert!(r.index_to_xyz(11).is_ok());
        assert!(r.index_to_xyz(23).is_ok());
        assert!(r.index_to_xyz(24).is_err());
    }

    #[test]
    fn test_xyz_w0h0d0() {
        let r = Full3D::new(0, 0, 0);
        assert!(r.xyz_to_index(0, 0, 0).is_err());
    }

    #[test]
    fn test_xyz_w0() {
        let r = Full3D::new(0, 10, 10);
        assert!(r.xyz_to_index(0, 0, 0).is_err());
    }

    #[test]
    fn test_xyz_h0() {
        let r = Full3D::new(10, 0, 10);
        assert!(r.xyz_to_index(0, 0, 0).is_err());
    }

    #[test]
    fn test_xyz_d0() {
        let r = Full3D::new(10, 10, 0);
        assert!(r.xyz_to_index(0, 0, 0).is_err());
    }

    #[test]
    fn test_xyz_w4h3d2() {
        let r = Full3D::new(4, 3, 2);
        assert_eq!(r.xyz_to_index(0, 0, 0).unwrap(), 0);
        assert_eq!(r.xyz_to_index(1, 0, 0).unwrap(), 1);
        assert_eq!(r.xyz_to_index(3, 2, 1).unwrap(), 23);
        assert!(r.xyz_to_index(4, 0, 0).is_err());
        assert!(r.xyz_to_index(0, 3, 0).is_err());
        assert!(r.xyz_to_index(0, 0, 2).is_err());
    }

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

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