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

use crate::distance::*;
use crate::gate::*;
use crate::mesh::*;
use std::fmt;
use std::iter::Iterator;

/// Stores pathfinding results as a gradient field over a mesh.
///
/// A `Gradient` represents the solution to a pathfinding problem using Dijkstra's algorithm.
/// It maintains, for each node in a mesh, the shortest distance to a target and which
/// neighboring node to move to in order to reach that target.
///
/// # How it works
///
/// The gradient is computed by "spreading" distance values across the mesh:
/// 1. Initialize all nodes with maximum distance except the target(s) which have distance 0
/// 2. Iteratively update each node's distance based on its neighbors' distances
/// 3. Continue until no more updates occur (convergence)
///
/// Once computed, the gradient provides a complete pathfinding solution where any node
/// can follow its target pointer to eventually reach the goal.
///
/// # Fields
///
/// * `slots` - A vector of `Gate` objects, one per node in the mesh. Each gate stores
///   the target index (next node on the shortest path) and the total distance to the goal.
///
/// # Example
///
/// ```
/// use shortestpath::{Gradient, mesh_2d::Full2D};
///
/// // Create a 5x5 grid
/// let mesh = Full2D::new(5, 5);
/// let mut gradient = Gradient::from_mesh(&mesh);
///
/// // Set the center node (index 12) as the target with distance 0
/// gradient.set_distance(12, 0.0);
///
/// // Compute the gradient (spread distances to all nodes)
/// gradient.spread(&mesh);
///
/// // Now any node can query its distance to the target
/// let distance_to_target = gradient.get_distance(0);
/// // And which neighbor to move toward
/// let next_step = gradient.get_target(0);
/// ```
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Gradient {
    /// Vector of gates, one per mesh node. Each gate contains the next step
    /// toward the target and the total distance to reach it.
    slots: Vec<Gate>,
}

impl Gradient {
    /// Creates a new gradient with the specified number of nodes.
    ///
    /// All nodes are initialized with maximum distance and point to themselves.
    /// This represents an unsolved pathfinding problem.
    ///
    /// # Arguments
    ///
    /// * `len` - The number of nodes in the gradient
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::Gradient;
    ///
    /// let gradient = Gradient::with_len(25);
    /// ```
    pub fn with_len(len: usize) -> Self {
        let mut slots = Vec::with_capacity(len);
        for i in 0..len {
            slots.push(Gate::new(i, DISTANCE_MAX));
        }
        Gradient { slots }
    }

    /// Creates a new gradient sized to match the given mesh.
    ///
    /// This is a convenience constructor that creates a gradient with the same
    /// number of nodes as the mesh.
    ///
    /// # Arguments
    ///
    /// * `mesh` - The mesh to create a gradient for
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Gradient, mesh_2d::Full2D};
    ///
    /// let mesh = Full2D::new(10, 10);
    /// let gradient = Gradient::from_mesh(&mesh);
    /// ```
    pub fn from_mesh(mesh: &impl Mesh) -> Self {
        Self::with_len(mesh.len())
    }

    /// Spreads distance values forward through the mesh (from index 0 to end).
    ///
    /// Updates each node's distance based on its neighbors, iterating from the
    /// first node to the last. This is one iteration of the gradient computation.
    ///
    /// # Arguments
    ///
    /// * `mesh` - The mesh to spread across
    /// * `incr` - Distance increment added to unchanged nodes (0.0 for standard pathfinding)
    ///
    /// # Returns
    ///
    /// The number of nodes that were updated during this pass
    ///
    /// # Panics
    ///
    /// Panics if the gradient size doesn't match the mesh size
    pub fn spread_forward(&mut self, mesh: &impl Mesh, incr: f64) -> usize {
        if self.slots.len() != mesh.len() {
            panic!(
                "slots len {} does not match mesh len {}",
                self.slots.len(),
                mesh.len()
            )
        }
        (0..(mesh.len()))
            .map(|i| self.spread_slot(i, mesh, incr))
            .filter(|ok| *ok)
            .count()
    }

    /// Spreads distance values backward through the mesh (from end to index 0).
    ///
    /// Updates each node's distance based on its neighbors, iterating from the
    /// last node to the first. This is one iteration of the gradient computation.
    ///
    /// # Arguments
    ///
    /// * `mesh` - The mesh to spread across
    /// * `incr` - Distance increment added to unchanged nodes (0.0 for standard pathfinding)
    ///
    /// # Returns
    ///
    /// The number of nodes that were updated during this pass
    ///
    /// # Panics
    ///
    /// Panics if the gradient size doesn't match the mesh size
    pub fn spread_backward(&mut self, mesh: &impl Mesh, incr: f64) -> usize {
        if self.slots.len() != mesh.len() {
            panic!(
                "slots len {} does not match mesh len {}",
                self.slots.len(),
                mesh.len()
            )
        }
        (0..(mesh.len()))
            .rev()
            .map(|i| self.spread_slot(i, mesh, incr))
            .filter(|ok| *ok)
            .count()
    }

    /// Spreads distance values in both directions through the mesh.
    ///
    /// Performs one forward pass followed by one backward pass. This can
    /// converge faster than spreading in only one direction.
    ///
    /// # Arguments
    ///
    /// * `mesh` - The mesh to spread across
    /// * `incr` - Distance increment added to unchanged nodes (0.0 for standard pathfinding)
    ///
    /// # Returns
    ///
    /// The total number of nodes updated in both passes
    ///
    /// # Panics
    ///
    /// Panics if the gradient size doesn't match the mesh size
    pub fn spread_both(&mut self, mesh: &impl Mesh, incr: f64) -> usize {
        self.spread_forward(mesh, incr) + self.spread_backward(mesh, incr)
    }

    /// Updates a single node's distance based on its neighbors.
    ///
    /// This is the core operation of Dijkstra's algorithm. It examines all neighbors
    /// of the given node and selects the one that provides the shortest path to the target.
    ///
    /// # Arguments
    ///
    /// * `here_index` - The index of the node to update
    /// * `mesh` - The mesh providing neighbor connectivity
    /// * `incr` - Distance increment for unchanged nodes (used to invalidate old paths)
    ///
    /// # Returns
    ///
    /// `true` if the node's distance or target was updated, `false` otherwise
    pub fn spread_slot(&mut self, here_index: usize, mesh: &impl Mesh, incr: f64) -> bool {
        let here = Gate::new(here_index, 0.0);
        let best = mesh.successors(here_index).fold(here, |a, b| {
            if self.slots[a.target].distance + a.distance
                <= self.slots[b.target].distance + b.distance
            {
                a
            } else {
                b
            }
        });
        if best.target != here_index {
            self.slots[here_index] = Gate::new(
                best.target,
                self.slots[best.target].distance + best.distance,
            );
            true
        } else {
            // If nothing has changed, consider we're farther by "incr" which
            // avoids old paths to remain valid when they should not be.
            if incr != 0.0 {
                self.slots[here_index].distance += incr;
            }
            false
        }
    }

    /// Increments all distances in the gradient by a fixed amount.
    ///
    /// This can be used to invalidate or age existing pathfinding results,
    /// particularly useful in dynamic environments where the target moves.
    ///
    /// # Arguments
    ///
    /// * `incr` - The amount to add to each node's distance
    pub fn incr(&mut self, incr: f64) {
        self.slots.iter_mut().for_each(|i| i.distance += incr);
    }

    /// Computes the complete gradient by spreading until convergence.
    ///
    /// This repeatedly calls `spread_both()` until no nodes are updated,
    /// ensuring all nodes have their optimal distance and target values.
    /// This is the main method to use for computing a pathfinding solution.
    ///
    /// # Arguments
    ///
    /// * `mesh` - The mesh to compute the gradient over
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Gradient, mesh_2d::Full2D};
    ///
    /// let mesh = Full2D::new(10, 10);
    /// let mut gradient = Gradient::from_mesh(&mesh);
    ///
    /// // Set target at center
    /// gradient.set_distance(55, 0.0);
    ///
    /// // Compute complete solution
    /// gradient.spread(&mesh);
    ///
    /// // Query results
    /// println!("Distance from corner: {}", gradient.get_distance(0));
    /// ```
    pub fn spread(&mut self, mesh: &impl Mesh) {
        while self.spread_both(mesh, 0.0) > 0 {}
    }

    /// Sets the distance for a specific node.
    ///
    /// Typically used to initialize target nodes with distance 0.0 before
    /// spreading the gradient.
    ///
    /// # Arguments
    ///
    /// * `slot_index` - The node index to set
    /// * `value` - The distance value to assign
    pub fn set_distance(&mut self, slot_index: usize, value: f64) {
        self.slots[slot_index].distance = value
    }

    /// Gets the distance value for a specific node.
    ///
    /// After spreading, this returns the shortest distance from this node
    /// to the nearest target.
    ///
    /// # Arguments
    ///
    /// * `slot_index` - The node index to query
    ///
    /// # Returns
    ///
    /// The distance to the nearest target
    pub fn get_distance(&self, slot_index: usize) -> f64 {
        self.slots[slot_index].distance
    }

    /// Gets the target index for a specific node.
    ///
    /// After spreading, this returns which neighboring node to move to
    /// in order to follow the shortest path to the target.
    ///
    /// # Arguments
    ///
    /// * `slot_index` - The node index to query
    ///
    /// # Returns
    ///
    /// The index of the next node on the shortest path
    pub fn get_target(&self, slot_index: usize) -> usize {
        self.slots[slot_index].target
    }

    /// Gets the complete gate information for a specific node.
    ///
    /// Returns a reference to the `Gate` containing both the target index
    /// and distance for this node.
    ///
    /// # Arguments
    ///
    /// * `slot_index` - The node index to query
    ///
    /// # Returns
    ///
    /// A reference to the gate at this node
    pub fn get(&self, slot_index: usize) -> &Gate {
        &self.slots[slot_index]
    }
}

impl std::fmt::Display for Gradient {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "TODO")
    }
}

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

    #[test]
    fn test_spread_forward() {
        let rect = Full2D::new(5, 5);
        let mut grad = Gradient::from_mesh(&rect);
        grad.set_distance(12, 0.0);
        grad.spread_forward(&rect, 0.0);
        // row 0
        assert_eq!(DISTANCE_MAX, grad.get_distance(0));
        assert_eq!(0, grad.get_target(0));
        assert_eq!(DISTANCE_MAX, grad.get_distance(1));
        assert_eq!(1, grad.get_target(1));
        assert_eq!(DISTANCE_MAX, grad.get_distance(2));
        assert_eq!(2, grad.get_target(2));
        assert_eq!(DISTANCE_MAX, grad.get_distance(3));
        assert_eq!(3, grad.get_target(3));
        assert_eq!(DISTANCE_MAX, grad.get_distance(4));
        assert_eq!(4, grad.get_target(4));
        // row 1
        assert_eq!(DISTANCE_MAX, grad.get_distance(5));
        assert_eq!(5, grad.get_target(5));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(6));
        assert_eq!(12, grad.get_target(6));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(7));
        assert_eq!(12, grad.get_target(7));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(8));
        assert_eq!(12, grad.get_target(8));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(9));
        assert_eq!(8, grad.get_target(9));
        // row 2
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(10));
        assert_eq!(6, grad.get_target(10));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(11));
        assert_eq!(12, grad.get_target(11));
        assert_eq!(DISTANCE_MIN, grad.get_distance(12));
        assert_eq!(12, grad.get_target(12));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(13));
        assert_eq!(12, grad.get_target(13));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(14));
        assert_eq!(13, grad.get_target(14));
        // row 3
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(15));
        assert_eq!(11, grad.get_target(15));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(16));
        assert_eq!(12, grad.get_target(16));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(17));
        assert_eq!(12, grad.get_target(17));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(18));
        assert_eq!(12, grad.get_target(18));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(19));
        assert_eq!(18, grad.get_target(19));
        // row 4
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(20));
        assert_eq!(16, grad.get_target(20));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(21));
        assert_eq!(16, grad.get_target(21));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(22));
        assert_eq!(17, grad.get_target(22));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(23));
        assert_eq!(17, grad.get_target(23));
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(24));
        assert_eq!(18, grad.get_target(24));
    }

    #[test]
    fn test_spread_backward() {
        let rect = Full2D::new(5, 5);
        let mut grad = Gradient::from_mesh(&rect);
        grad.set_distance(12, 0.0);
        grad.spread_backward(&rect, 0.0);
        // row 5
        assert_eq!(DISTANCE_MAX, grad.get_distance(23));
        assert_eq!(24, grad.get_target(24));
        assert_eq!(DISTANCE_MAX, grad.get_distance(23));
        assert_eq!(23, grad.get_target(23));
        assert_eq!(DISTANCE_MAX, grad.get_distance(22));
        assert_eq!(22, grad.get_target(22));
        assert_eq!(DISTANCE_MAX, grad.get_distance(21));
        assert_eq!(21, grad.get_target(21));
        assert_eq!(DISTANCE_MAX, grad.get_distance(20));
        assert_eq!(20, grad.get_target(20));
        // row 4
        assert_eq!(DISTANCE_MAX, grad.get_distance(19));
        assert_eq!(19, grad.get_target(19));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(18));
        assert_eq!(12, grad.get_target(18));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(17));
        assert_eq!(12, grad.get_target(17));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(16));
        assert_eq!(12, grad.get_target(16));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(15));
        assert_eq!(16, grad.get_target(15));
        // row 3
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(14));
        assert_eq!(18, grad.get_target(14));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(13));
        assert_eq!(12, grad.get_target(13));
        assert_eq!(DISTANCE_MIN, grad.get_distance(12));
        assert_eq!(12, grad.get_target(12));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(11));
        assert_eq!(12, grad.get_target(11));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(10));
        assert_eq!(11, grad.get_target(10));
        // row 1
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(9));
        assert_eq!(13, grad.get_target(9));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(8));
        assert_eq!(12, grad.get_target(8));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(7));
        assert_eq!(12, grad.get_target(7));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(6));
        assert_eq!(12, grad.get_target(6));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(5));
        assert_eq!(6, grad.get_target(5));
        // row 0
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(4));
        assert_eq!(8, grad.get_target(4));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(3));
        assert_eq!(8, grad.get_target(3));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(2));
        assert_eq!(7, grad.get_target(2));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(1));
        assert_eq!(7, grad.get_target(1));
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(0));
        assert_eq!(6, grad.get_target(0));
    }

    #[test]
    fn test_spread() {
        let rect = Full2D::new(5, 5);
        let mut grad = Gradient::from_mesh(&rect);
        grad.set_distance(12, 0.0);
        grad.spread(&rect);
        // row 0
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(0));
        assert_eq!(6, grad.get_target(0));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(1));
        assert_eq!(7, grad.get_target(1));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(2));
        assert_eq!(7, grad.get_target(2));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(3));
        assert_eq!(8, grad.get_target(3));
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(4));
        assert_eq!(8, grad.get_target(4));
        // row 1
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(5));
        assert_eq!(6, grad.get_target(5));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(6));
        assert_eq!(12, grad.get_target(6));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(7));
        assert_eq!(12, grad.get_target(7));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(8));
        assert_eq!(12, grad.get_target(8));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(9));
        assert_eq!(8, grad.get_target(9));
        // row 2
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(10));
        assert_eq!(11, grad.get_target(10));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(11));
        assert_eq!(12, grad.get_target(11));
        assert_eq!(DISTANCE_MIN, grad.get_distance(12));
        assert_eq!(12, grad.get_target(12));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(13));
        assert_eq!(12, grad.get_target(13));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(14));
        assert_eq!(13, grad.get_target(14));
        // row 3
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(15));
        assert_eq!(11, grad.get_target(15));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(16));
        assert_eq!(12, grad.get_target(16));
        assert_eq!(DISTANCE_STRAIGHT, grad.get_distance(17));
        assert_eq!(12, grad.get_target(17));
        assert_eq!(DISTANCE_DIAGONAL, grad.get_distance(18));
        assert_eq!(12, grad.get_target(18));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(19));
        assert_eq!(18, grad.get_target(19));
        // row 4
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(20));
        assert_eq!(16, grad.get_target(20));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(21));
        assert_eq!(16, grad.get_target(21));
        assert_eq!(2.0 * DISTANCE_STRAIGHT, grad.get_distance(22));
        assert_eq!(17, grad.get_target(22));
        assert_eq!(DISTANCE_STRAIGHT + DISTANCE_DIAGONAL, grad.get_distance(23));
        assert_eq!(17, grad.get_target(23));
        assert_eq!(2.0 * DISTANCE_DIAGONAL, grad.get_distance(24));
        assert_eq!(18, grad.get_target(24));
    }

    #[test]
    #[cfg(feature = "serde")]
    fn test_serde() {
        let mut gradient = Gradient::with_len(10);
        gradient.set_distance(5, 3.14);

        let json = serde_json::to_string(&gradient).unwrap();
        let deserialized: Gradient = serde_json::from_str(&json).unwrap();

        assert_eq!(gradient.get_distance(5), deserialized.get_distance(5));
        assert_eq!(gradient.get_target(5), deserialized.get_target(5));
    }
}
