shortestpath 0.10.0

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

use crate::distance::*;
use crate::errors::*;
use crate::gate::*;
use crate::gradient::*;
use crate::mesh::*;
use crate::mesh_25d::full_25d::*;
use crate::mesh_3d::Index3D;
use crate::mesh_3d::Shape3D;

use crate::mesh_source::*;

/// A memory-optimized 2.5D volume mesh with support for walls and obstacles.
///
/// `Compact25D` represents a 2.5D volume where some cells may be walls (impassable).
/// It compresses the representation by only storing walkable cells and pre-computes
/// their neighbor relationships, making it efficient for volumes with many obstacles.
///
/// # Representation
///
/// The mesh maintains two index spaces:
/// - **Full indices**: Map to the original (width × height × depth) volume, including walls
/// - **Compact indices**: Map only to walkable cells (used for pathfinding)
///
/// This compression can significantly reduce memory usage for sparse volumes.
/// For example, a 50×50×50 volume with 50% walls uses only ~62,500 nodes instead of 125,000.
///
/// # Pre-computation
///
/// Unlike [`Full25D`], this mesh pre-computes and stores all successor relationships,
/// trading memory for faster successor lookups during pathfinding.
///
/// # Example
///
/// ```
/// use shortestpath::{Mesh, Gradient, mesh_25d::Compact25D};
///
/// // Create a volume from ASCII art layers (. = walkable, # = wall)
/// // Layers separated by "---"
/// let map = "\
/// ...
/// .#.
/// ...
/// ---
/// ...
/// ###
/// ...";
///
/// let mesh = Compact25D::from_text(map)?;
/// // Only 15 walkable cells (18 total - 3 walls)
/// assert_eq!(mesh.len(), 15);
///
/// // Use for pathfinding
/// let mut gradient = Gradient::from_mesh(&mesh);
/// gradient.set_distance(7, 0.0); // A center walkable cell
/// gradient.spread(&mesh);
/// # Ok::<(), shortestpath::Error>(())
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Compact25D {
    /// Width of the original volume
    width: usize,
    /// Height of the original volume
    height: usize,
    /// Depth of the original volume
    depth: usize,
    /// Maps full volume indices to compact indices (walls map to volume size)
    full_to_compact: Vec<usize>,
    /// Maps compact indices back to full volume indices
    compact_to_full: Vec<usize>,
    /// Pre-computed successors for each compact index
    successors_map: Vec<Vec<Gate>>,
}

impl Compact25D {
    /// Creates a new fully walkable compact 2.5D volume.
    ///
    /// This creates a volume with no walls, equivalent to [`Full25D`] but
    /// with pre-computed successors.
    ///
    /// # 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, mesh_25d::Compact25D};
    ///
    /// let mesh = Compact25D::new_full(10, 10, 10);
    /// assert_eq!(mesh.len(), 1000);
    /// ```
    pub fn new_full(width: usize, height: usize, depth: usize) -> Self {
        let size = width * height * depth;
        let mut full_to_compact = Vec::with_capacity(size);
        let mut successors_map = Vec::with_capacity(size);
        for i in 0..size {
            full_to_compact.push(i);
            let successors = Full25D::successors(width, height, depth, i, false).collect();
            successors_map.push(successors);
        }
        let compact_to_full = full_to_compact.clone();
        Self {
            width,
            height,
            depth,
            full_to_compact,
            compact_to_full,
            successors_map,
        }
    }

    /// Creates a compact 2.5D volume from a source.
    ///
    /// This is the primary constructor for creating volumes with obstacles.
    /// It compresses the volume to only include walkable cells and computes
    /// their connectivity.
    ///
    /// # Arguments
    ///
    /// * `source` - An object implementing [`Source3D`] that defines which cells are walls
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_25d::Compact25D};
    /// use shortestpath::mesh_source::Source3DFromText;
    ///
    /// let source = Source3DFromText::from_text("...\n.#.\n...");
    /// let mesh = Compact25D::from_source(&source)?;
    /// assert_eq!(mesh.len(), 8); // 9 cells - 1 wall = 8 walkable
    /// # Ok::<(), shortestpath::Error>(())
    /// ```
    pub fn from_source(source: &impl Source3D) -> Result<Self> {
        let width = source.width();
        let height = source.height();
        let depth = source.depth();
        let size = width * height * depth;
        let mut full_to_compact = Vec::with_capacity(size);
        let mut compact_to_full = Vec::with_capacity(size);

        let mut current_full = 0;
        let mut current_compact = 0;
        for z in 0..depth {
            for y in 0..height {
                for x in 0..width {
                    let can_go = source.get(x, y, z)?.can_go();
                    if can_go {
                        compact_to_full.push(current_full);
                        full_to_compact.push(current_compact);
                        current_full += 1;
                        current_compact += 1;
                    } else {
                        full_to_compact.push(size);
                        current_full += 1;
                    }
                }
            }
        }
        let mut successors_map = Vec::with_capacity(compact_to_full.len());
        for &full_index in &compact_to_full {
            let possible_successors = Full25D::successors(width, height, depth, full_index, false);
            let successors = possible_successors
                .filter_map(|s| {
                    // keep only gates opening to some place that is possible
                    let (x, y, z) = Full25D::index_to_xyz(width, height, depth, s.target()).ok()?;
                    if source.get(x, y, z).ok()?.can_go() {
                        Some(s)
                    } else {
                        None
                    }
                })
                .map(|s| Gate {
                    // translate the full index to a compact index
                    distance: s.distance,
                    target: full_to_compact[s.target()] as u32,
                })
                .collect();
            successors_map.push(successors);
        }

        Ok(Self {
            width,
            height,
            depth,
            full_to_compact,
            compact_to_full,
            successors_map,
        })
    }

    /// Filters the mesh to keep only the zone connected to index 0.
    ///
    /// When a mesh contains multiple disconnected zones (areas separated by walls),
    /// this method removes all zones except the one containing the first walkable cell
    /// (compact index 0). This ensures the mesh is fully interconnected.
    ///
    /// # Returns
    ///
    /// A new `Compact25D` containing only the nodes reachable from index 0.
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_25d::Compact25D};
    ///
    /// // Volume with two separate zones divided by a wall, across two layers
    /// let mesh = Compact25D::from_text(
    ///     "##########\n#    #   #\n#    #   #\n##########\n====\n##########\n#    #   #\n#    #   #\n##########\n===="
    /// ).unwrap().unique();
    /// // Only the left zone (16 cells) is kept
    /// assert_eq!(mesh.len(), 16);
    /// ```
    pub fn unique(self) -> Self {
        if self.compact_to_full.is_empty() {
            return self;
        }

        let size = self.width * self.height * self.depth;

        // Spread gradient from index 0 to find reachable nodes
        let mut gradient = Gradient::from_mesh(&self);
        gradient.set_distance(0, 0.0);
        gradient.spread(&self);

        // Find which compact indices are reachable (distance < DISTANCE_MAX)
        let reachable: Vec<usize> = (0..self.len())
            .filter(|&i| gradient.get_distance(i) < DISTANCE_MAX)
            .collect();

        // If all nodes are reachable, return self unchanged
        if reachable.len() == self.len() {
            return self;
        }

        // Rebuild the data structures with only reachable nodes
        let mut new_full_to_compact = vec![size; size];
        let mut new_compact_to_full = Vec::with_capacity(reachable.len());
        let mut old_to_new_compact: Vec<usize> = vec![size; self.len()];

        for (new_idx, &old_idx) in reachable.iter().enumerate() {
            let full_idx = self.compact_to_full[old_idx];
            new_compact_to_full.push(full_idx);
            new_full_to_compact[full_idx] = new_idx;
            old_to_new_compact[old_idx] = new_idx;
        }

        // Rebuild successors_map with updated indices
        let mut new_successors_map = Vec::with_capacity(reachable.len());
        for &old_idx in &reachable {
            let old_successors = &self.successors_map[old_idx];
            let new_successors: Vec<Gate> = old_successors
                .iter()
                .filter(|s| old_to_new_compact[s.target()] < size)
                .map(|s| Gate {
                    distance: s.distance,
                    target: old_to_new_compact[s.target()] as u32,
                })
                .collect();
            new_successors_map.push(new_successors);
        }

        Self {
            width: self.width,
            height: self.height,
            depth: self.depth,
            full_to_compact: new_full_to_compact,
            compact_to_full: new_compact_to_full,
            successors_map: new_successors_map,
        }
    }

    /// Creates a compact 2.5D volume from a text string.
    ///
    /// This is a convenience constructor that parses an ASCII art map where
    /// `.` represents walkable cells and `#` represents walls. Layers are
    /// separated by lines containing `---`.
    ///
    /// # Arguments
    ///
    /// * `input` - A string with layers separated by "---" (`.` = free, `#` = wall)
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::mesh_25d::Compact25D;
    ///
    /// let mesh = Compact25D::from_text("\
    /// .....
    /// .###.
    /// .....
    /// ---
    /// .....
    /// .....
    /// .....
    /// ");
    /// ```
    pub fn from_text(input: &str) -> Result<Self> {
        let source = Source3DFromText::from_text(input);
        Self::from_source(&source)
    }

    pub fn from_vec_str(input: &Vec<&str>) -> Result<Self> {
        let source = Source3DFromText::from_slice(input);
        Self::from_source(&source)
    }

    pub fn from_vec_string(input: &[String]) -> Result<Self> {
        let source = Source3DFromText::from_strings(input);
        Self::from_source(&source)
    }

    pub fn from_iter_str<'a, I>(input: I) -> Result<Self>
    where
        I: Iterator<Item = &'a str>,
    {
        let source = Source3DFromText::from_lines(input);
        Self::from_source(&source)
    }

    /// Creates a compact 2.5D volume from a vector of image file paths.
    ///
    /// Each image file represents one layer (z-level) in the volume.
    /// Pixels are converted to FREE or WALL cells based on their brightness.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `paths` - Vector of file paths, one per layer (ordered from z=0 to z=depth-1)
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_25d::Compact25D;
    ///
    /// let paths = vec!["layer0.png", "layer1.png", "layer2.png"];
    /// let mesh = Compact25D::from_paths(&paths).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_paths<P: AsRef<std::path::Path>>(paths: &[P]) -> Result<Self> {
        let source = Source3DFromImage::from_paths(paths, Source3DFromImage::DEFAULT_THRESHOLD)?;
        Self::from_source(&source)
    }

    /// Creates a compact 2.5D volume from image paths with a custom brightness threshold.
    ///
    /// Each image file represents one layer (z-level) in the volume.
    /// Pixels with brightness below the threshold are considered walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `paths` - Vector of file paths, one per layer
    /// * `threshold` - Brightness threshold (0.0-1.0). Pixels darker than this are walls.
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_25d::Compact25D;
    ///
    /// let paths = vec!["layer0.png", "layer1.png"];
    /// let mesh = Compact25D::from_paths_with_threshold(&paths, 0.5).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_paths_with_threshold<P: AsRef<std::path::Path>>(
        paths: &[P],
        threshold: f32,
    ) -> Result<Self> {
        let source = Source3DFromImage::from_paths(paths, threshold)?;
        Self::from_source(&source)
    }

    /// Creates a compact 2.5D volume from a slice of DynamicImages with a custom brightness threshold.
    ///
    /// Each image represents one layer (z-level) in the volume.
    /// All images must have the same dimensions.
    /// Pixels with brightness below the threshold are considered walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `images` - Slice of images, one per layer
    /// * `threshold` - Brightness threshold (0.0-1.0). Pixels darker than this are walls.
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_25d::Compact25D;
    /// use image::DynamicImage;
    ///
    /// let layer0 = image::open("layer0.png").unwrap();
    /// let layer1 = image::open("layer1.png").unwrap();
    /// let mesh = Compact25D::from_images_with_threshold(&[layer0, layer1], 0.5).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_images_with_threshold(
        images: &[image::DynamicImage],
        threshold: f32,
    ) -> Result<Self> {
        let source = Source3DFromImage::from_images(images, threshold)?;
        Self::from_source(&source)
    }

    /// Creates a compact 2.5D volume from a slice of DynamicImages.
    ///
    /// Each image represents one layer (z-level) in the volume.
    /// All images must have the same dimensions.
    /// Uses the default threshold (0.5).
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `images` - Slice of images, one per layer
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_25d::Compact25D;
    ///
    /// let layer0 = image::open("layer0.png").unwrap();
    /// let layer1 = image::open("layer1.png").unwrap();
    /// let mesh = Compact25D::from_images(&[layer0, layer1]).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_images(images: &[image::DynamicImage]) -> Result<Self> {
        Self::from_images_with_threshold(images, Source3DFromImage::DEFAULT_THRESHOLD)
    }

    fn compact_to_full_index(&self, compact_index: usize) -> Result<usize> {
        if compact_index >= self.compact_to_full.len() {
            return Err(Error::invalid_index(compact_index));
        }
        let full_index = self.compact_to_full[compact_index];
        if full_index >= self.full_to_compact.len() {
            return Err(Error::invalid_index(full_index));
        }
        Ok(full_index)
    }

    fn full_to_compact_index(&self, full_index: usize) -> Result<usize> {
        if full_index >= self.full_to_compact.len() {
            return Err(Error::invalid_index(full_index));
        }
        let compact_index = self.full_to_compact[full_index];
        if compact_index >= self.compact_to_full.len() {
            return Err(Error::invalid_index(compact_index));
        }
        Ok(compact_index)
    }
}

impl Mesh for Compact25D {
    type IntoIter = std::vec::IntoIter<Gate>;
    fn successors(&self, from: usize, backward: bool) -> std::vec::IntoIter<Gate> {
        let mut peers = self.successors_map[from].clone();
        if backward {
            peers.reverse();
        }
        peers.into_iter()
    }

    fn len(&self) -> usize {
        self.compact_to_full.len()
    }
}

impl Index3D for Compact25D {
    fn index_to_xyz(&self, index: usize) -> Result<(usize, usize, usize)> {
        let full_index = self.compact_to_full_index(index)?;
        Full25D::index_to_xyz(self.width, self.height, self.depth, full_index)
    }

    fn xyz_to_index(&self, x: usize, y: usize, z: usize) -> Result<usize> {
        let full_index = Full25D::xyz_to_index(self.width, self.height, self.width, x, y, z)?;
        self.full_to_compact_index(full_index)
    }
}

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

impl std::str::FromStr for Compact25D {
    type Err = Error;

    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
        Self::from_text(s)
    }
}

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

    #[test]
    fn test_compact_3d_full_basic() {
        let mesh = Compact25D::new_full(4, 3, 2);
        assert_eq!((4, 3, 2), mesh.shape());
        assert_eq!(24, mesh.len());
        let mut grad = Gradient::from_mesh(&mesh);
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
        assert_eq!(
            String::from("0123\n1123\n2234\n----\n1234\n2234\n3345\n----\n"),
            repr_mesh_with_gradient_3d(&mesh, &grad)
        );
    }

    #[test]
    fn test_compact_3d_with_str_small() {
        let mesh = Compact25D::from_text(" ## \n    \n#  #\n====\n####\n\n\n====").unwrap();
        assert_eq!((4, 3, 2), mesh.shape());
        assert_eq!(16, mesh.len());
        let mut grad = Gradient::from_mesh(&mesh);
        assert_eq!(
            String::from("?##?\n????\n#??#\n----\n####\n????\n????\n----\n"),
            repr_mesh_with_gradient_3d(&mesh, &grad)
        );
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
        assert_eq!(
            String::from("0##4\n1123\n#23#\n----\n####\n2234\n3345\n----\n"),
            repr_mesh_with_gradient_3d(&mesh, &grad)
        );
    }

    #[test]
    fn test_compact_25d_with_str_multiple_zones() {
        // Two zones separated by a wall column in the middle, across two layers
        // Zone 1: left side (8 cells per layer x 2 layers = 16 cells)
        // Zone 2: right side (6 cells per layer x 2 layers = 12 cells)
        let mesh_all = Compact25D::from_text(
            "##########\n#    #   #\n#    #   #\n##########\n====\n##########\n#    #   #\n#    #   #\n##########\n====",
        )
        .unwrap();
        assert_eq!((10, 4, 2), mesh_all.shape());
        assert_eq!(28, mesh_all.len()); // 16 left + 12 right

        // Then, verify unique() filters to only the connected zone
        // IMPORTANT: The explicit type annotation `Compact25D` ensures we're using
        // the optimized inherent method (returns Self) not the trait method
        // (which would return FilteredMesh<Self> and fail to compile here)
        let mesh: Compact25D = mesh_all.unique();
        assert_eq!((10, 4, 2), mesh.shape()); // shape() only exists on Compact25D, not FilteredMesh
        assert_eq!(16, mesh.len()); // Only left zone
        let mut grad = Gradient::from_mesh(&mesh);
        assert_eq!(
            String::from(
                "##########\n#????#####\n#????#####\n##########\n----------\n##########\n#????#####\n#????#####\n##########\n----------\n"
            ),
            repr_mesh_with_gradient_3d(&mesh, &grad)
        );
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
    }

    #[test]
    fn test_compact_25d_empty_string() {
        let mesh = Compact25D::from_text("").unwrap();
        assert_eq!((0, 0, 0), mesh.shape());
        assert_eq!(0, mesh.len());
        assert!(mesh.is_empty());
    }

    #[test]
    fn test_compact_25d_all_walls() {
        // Single wall
        let mesh = Compact25D::from_text("#").unwrap();
        assert_eq!((1, 1, 1), mesh.shape());
        assert_eq!(0, mesh.len());
        assert!(mesh.is_empty());

        // Multiple walls across layers
        let mesh = Compact25D::from_text("###\n###\n---\n###\n###").unwrap();
        assert_eq!((3, 2, 2), mesh.shape());
        assert_eq!(0, mesh.len());
        assert!(mesh.is_empty());
    }

    #[test]
    #[cfg(feature = "serde")]
    fn test_serde() {
        let mesh = Compact25D::from_text("...\n.#.\n...\n---\n...\n...\n...").unwrap();
        let json = serde_json::to_string(&mesh).unwrap();
        let deserialized: Compact25D = serde_json::from_str(&json).unwrap();

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