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_2d::full_2d::*;
use crate::mesh_2d::index_2d::*;
use crate::mesh_2d::shape_2d::*;
use crate::mesh_source::*;

/// A memory-optimized 2D grid mesh with support for walls and obstacles.
///
/// `Compact2D` represents a 2D grid 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 grids with many obstacles.
///
/// # Representation
///
/// The mesh maintains two index spaces:
/// - **Full indices**: Map to the original (width × height) grid, including walls
/// - **Compact indices**: Map only to walkable cells (used for pathfinding)
///
/// This compression can significantly reduce memory usage for sparse grids.
/// For example, a 100×100 grid with 50% walls uses only ~5000 nodes instead of 10000.
///
/// # Pre-computation
///
/// Unlike [`Full2D`], this mesh pre-computes and stores all successor relationships,
/// trading memory for faster successor lookups during pathfinding.
///
/// # Example
///
/// ```
/// use shortestpath::{Mesh, Gradient, mesh_2d::Compact2D};
///
/// // Create a grid from ASCII art (. = walkable, # = wall)
/// let map = "\
/// .....
/// .###.
/// .#.#.
/// .###.
/// .....";
///
/// let mesh = Compact2D::from_text(map)?;
/// // 17 walkable cells (25 total - 8 walls)
/// assert_eq!(mesh.len(), 17);
///
/// // Use for pathfinding
/// let mut gradient = Gradient::from_mesh(&mesh);
/// gradient.set_distance(8, 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 Compact2D {
    /// Width of the original grid
    width: usize,
    /// Height of the original grid
    height: usize,
    /// Maps full grid indices to compact indices (walls map to grid size)
    full_to_compact: Vec<usize>,
    /// Maps compact indices back to full grid indices
    compact_to_full: Vec<usize>,
    /// Pre-computed successors for each compact index
    successors_map: Vec<Vec<Gate>>,
}

impl Compact2D {
    /// Creates a new fully walkable compact 2D grid.
    ///
    /// This creates a grid with no walls, equivalent to [`Full2D`] but
    /// with pre-computed successors.
    ///
    /// # Arguments
    ///
    /// * `width` - Number of columns in the grid
    /// * `height` - Number of rows in the grid
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Compact2D};
    ///
    /// let mesh = Compact2D::new_full(10, 10);
    /// assert_eq!(mesh.len(), 100);
    /// ```
    pub fn new_full(width: usize, height: usize) -> Self {
        let size = width * height;
        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 = Full2D::successors(width, height, i, false).collect();
            successors_map.push(successors);
        }
        let compact_to_full = full_to_compact.clone();
        Self {
            width,
            height,
            full_to_compact,
            compact_to_full,
            successors_map,
        }
    }

    /// Creates a compact 2D grid from a source.
    ///
    /// This is the primary constructor for creating grids with obstacles.
    /// It compresses the grid to only include walkable cells and computes
    /// their connectivity.
    ///
    /// # Arguments
    ///
    /// * `source` - An object implementing [`Source2D`] that defines which cells are walls
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Compact2D};
    /// use shortestpath::mesh_source::Source2DFromText;
    ///
    /// let source = Source2DFromText::from_text("...\n.#.\n...");
    /// let mesh = Compact2D::from_source(&source)?;
    /// assert_eq!(mesh.len(), 8); // 9 cells - 1 wall = 8 walkable
    /// # Ok::<(), shortestpath::Error>(())
    /// ```
    pub fn from_source(source: &impl Source2D) -> Result<Self> {
        let width = source.width();
        let height = source.height();
        let size = width * height;
        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 y in 0..height {
            for x in 0..width {
                let can_go = source.get(x, y)?.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 = Full2D::successors(width, height, full_index, false);
            let successors = possible_successors
                .filter_map(|s| {
                    // keep only gates opening to some place that is possible
                    let (x, y) = Full2D::index_to_xy(width, height, s.target()).ok()?;
                    if source.get(x, y).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,
            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 `Compact2D` containing only the nodes reachable from index 0.
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Compact2D};
    ///
    /// // Grid with two separate zones divided by a wall
    /// let mesh = Compact2D::from_text("##########\n#    #   #\n#    #   #\n##########\n")
    ///     .unwrap()
    ///     .unique();
    /// // Only the left zone (8 cells) is kept, right zone (6 cells) is removed
    /// assert_eq!(mesh.len(), 8);
    /// ```
    pub fn unique(self) -> Self {
        if self.compact_to_full.is_empty() {
            return self;
        }

        let size = self.width * self.height;

        // 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,
            full_to_compact: new_full_to_compact,
            compact_to_full: new_compact_to_full,
            successors_map: new_successors_map,
        }
    }

    /// Creates a compact 2D grid from a text string.
    ///
    /// This is a convenience constructor that parses an ASCII art map where
    /// `.` represents walkable cells and `#` represents walls.
    ///
    /// # Arguments
    ///
    /// * `input` - A string with newline-separated rows (`.` = free, `#` = wall)
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::mesh_2d::Compact2D;
    ///
    /// let mesh = Compact2D::from_text("\
    /// .....
    /// .###.
    /// .....
    /// ")?;
    /// # Ok::<(), shortestpath::Error>(())
    /// ```
    pub fn from_text(input: &str) -> Result<Self> {
        let source = Source2DFromText::from_text(input);
        Self::from_source(&source)
    }

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

    pub fn from_vec_string(input: &[String]) -> Result<Self> {
        let source = Source2DFromText::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 = Source2DFromText::from_lines(input);
        Self::from_source(&source)
    }

    /// Creates a compact 2D grid from an image file.
    ///
    /// This is a convenience constructor that loads an image and converts it to a grid.
    /// Pixels are converted to FREE or WALL cells based on their brightness.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `path` - Path to the image file
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_2d::Compact2D;
    ///
    /// let mesh = Compact2D::from_path("map.png").unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_path<P: AsRef<std::path::Path>>(path: P) -> Result<Self> {
        let source = Source2DFromImage::from_path(path)?;
        Self::from_source(&source)
    }

    /// Creates a compact 2D grid from an image file with a custom brightness threshold.
    ///
    /// This is a convenience constructor that loads an image and converts it to a grid.
    /// Pixels with brightness below the threshold are considered walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `path` - Path to the image file
    /// * `threshold` - Brightness threshold (0.0-1.0). Pixels darker than this are walls.
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_2d::Compact2D;
    ///
    /// let mesh = Compact2D::from_path_with_threshold("map.png", 0.5).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_path_with_threshold<P: AsRef<std::path::Path>>(
        path: P,
        threshold: f32,
    ) -> Result<Self> {
        let source = Source2DFromImage::from_path_with_threshold(path, threshold)?;
        Self::from_source(&source)
    }

    /// Creates a compact 2D grid from a DynamicImage with a custom brightness threshold.
    ///
    /// This is a convenience constructor that converts an already-loaded image to a grid.
    /// Pixels with brightness below the threshold are considered walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `image` - The image to convert
    /// * `threshold` - Brightness threshold (0.0-1.0). Pixels darker than this are walls.
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_2d::Compact2D;
    /// use image::DynamicImage;
    ///
    /// let img = image::open("map.png").unwrap();
    /// let mesh = Compact2D::from_image_with_threshold(&img, 0.5).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_image_with_threshold(image: &image::DynamicImage, threshold: f32) -> Result<Self> {
        let source = Source2DFromImage::from_image(image, threshold)?;
        Self::from_source(&source)
    }

    /// Creates a compact 2D grid from a DynamicImage.
    ///
    /// This is a convenience constructor that converts an already-loaded image to a grid.
    /// Uses the default threshold (0.5).
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `image` - The image to convert
    ///
    /// # Example
    ///
    /// ```no_run
    /// use shortestpath::mesh_2d::Compact2D;
    ///
    /// let img = image::open("map.png").unwrap();
    /// let mesh = Compact2D::from_image(&img).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_image(image: &image::DynamicImage) -> Result<Self> {
        Self::from_image_with_threshold(image, Source2DFromImage::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 Compact2D {
    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 Index2D for Compact2D {
    fn index_to_xy(&self, index: usize) -> Result<(usize, usize)> {
        let full_index = self.compact_to_full_index(index)?;
        Full2D::index_to_xy(self.width, self.height, full_index)
    }

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

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

impl std::str::FromStr for Compact2D {
    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_2d::repr_2d::*;

    #[test]
    fn test_compact_2d_full_basic() {
        let mesh = Compact2D::new_full(3, 2);
        assert_eq!((3, 2), mesh.shape());
        assert_eq!(6, mesh.len());
        let mut grad = Gradient::from_mesh(&mesh);
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
        assert_eq!(
            String::from("012\n112\n"),
            repr_mesh_with_gradient_2d(&mesh, &grad)
        );
    }

    #[test]
    fn test_compact_2d_with_str_small() {
        let mesh = Compact2D::from_text(" # \n   \n").unwrap();
        assert_eq!((3, 2), mesh.shape());
        assert_eq!(5, mesh.len());
        let mut grad = Gradient::from_mesh(&mesh);
        assert_eq!(
            String::from("?#?\n???\n"),
            repr_mesh_with_gradient_2d(&mesh, &grad)
        );
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
        assert_eq!(
            String::from("0#3\n112\n"),
            repr_mesh_with_gradient_2d(&mesh, &grad)
        );
    }

    #[test]
    fn test_compact_2d_with_str_medium() {
        let mesh =
            Compact2D::from_text("  #                 \n\n\n ####\n\n##\n\n\n     #####\n\n")
                .unwrap();
        assert_eq!((20, 10), mesh.shape());
        assert_eq!(188, mesh.len());
        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_2d(&mesh, &grad)
        );
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
        assert_eq!(
            String::from( "01#45678901234567890\n11234567890123456789\n22345678901234567890\n3####678901234567890\n44567789012345678901\n##678899012345678901\n87778900012345678901\n98889011123456789012\n09990#####3456789012\n10001123454567890123\n"),
            repr_mesh_with_gradient_2d(&mesh, &grad)
        );
    }

    #[test]
    fn test_compact_2d_with_str_multiple_zones() {
        // First, verify from_text returns all zones (14 walkable cells total)
        let mesh_all =
            Compact2D::from_text("##########\n#    #   #\n#    #   #\n##########\n").unwrap();
        assert_eq!((10, 4), mesh_all.shape());
        assert_eq!(14, mesh_all.len()); // 8 left + 6 right

        // Then, verify unique() filters to only the connected zone
        // IMPORTANT: The explicit type annotation `Compact2D` 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: Compact2D = mesh_all.unique();
        assert_eq!((10, 4), mesh.shape()); // shape() only exists on Compact2D, not FilteredMesh
        assert_eq!(8, mesh.len()); // Only left zone
        let mut grad = Gradient::from_mesh(&mesh);
        assert_eq!(
            String::from("##########\n#????#####\n#????#####\n##########\n"),
            repr_mesh_with_gradient_2d(&mesh, &grad)
        );
        grad.set_distance(0, 0.0);
        grad.spread(&mesh);
    }

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

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

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

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

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

    #[test]
    #[cfg(feature = "serde")]
    fn test_serde_with_gradient_workflow() {
        use crate::Gradient;

        // Create a mesh
        let mesh = Compact2D::from_text(".....\n.###.\n.....\n").unwrap();

        // Create and compute gradient
        let mut gradient = Gradient::from_mesh(&mesh);
        gradient.set_distance(6, 0.0);
        gradient.spread(&mesh);

        // Serialize mesh and gradient
        let mesh_json = serde_json::to_string(&mesh).unwrap();
        let gradient_json = serde_json::to_string(&gradient).unwrap();

        // Deserialize
        let deserialized_mesh: Compact2D = serde_json::from_str(&mesh_json).unwrap();
        let deserialized_gradient: Gradient = serde_json::from_str(&gradient_json).unwrap();

        // Verify they work the same
        assert_eq!(mesh.len(), deserialized_mesh.len());
        assert_eq!(
            gradient.get_distance(0),
            deserialized_gradient.get_distance(0)
        );
        assert_eq!(gradient.get_target(0), deserialized_gradient.get_target(0));
    }
}