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

use crate::errors::*;
use crate::gate::*;
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)]
#[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).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);
            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],
                })
                .collect();
            successors_map.push(successors);
        }

        Ok(Self {
            width,
            height,
            full_to_compact,
            compact_to_full,
            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) -> std::vec::IntoIter<Gate> {
        self.successors_map[from].clone().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::gradient::*;
    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]
    #[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));
    }
}
