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

// from https://docs.rs/pathfinding/4.8.0/pathfinding/directed/dijkstra/fn.dijkstra.html
//
// pub fn dijkstra<N, C, FN, IN, FS>(
//     start: &N,
//     successors: FN,
//     success: FS
// ) -> Option<(Vec<N>, C)>
// where
//     N: Eq + Hash + Clone,
//     C: Zero + Ord + Copy,
//     FN: FnMut(&N) -> IN,
//     IN: IntoIterator<Item = (N, C)>,
//     FS: FnMut(&N) -> bool,

use crate::gate::*;
use std::iter::Iterator;

/// Trait representing a graph structure for pathfinding.
///
/// A `Mesh` defines the connectivity and structure of a graph used for pathfinding.
/// It abstracts over different types of graphs (2D grids, 3D volumes, arbitrary graphs)
/// and provides the core interface needed by the gradient-based pathfinding algorithm.
///
/// # Design
///
/// The mesh trait is designed to work with Dijkstra-style algorithms (see reference
/// implementation from the pathfinding crate above). Each node is identified by a
/// `usize` index, and the mesh provides:
/// - The total number of nodes
/// - The neighbors (successors) reachable from any given node
///
/// # Implementations
///
/// This crate provides several implementations:
/// - `mesh_2d::Full2D` - Fully connected 2D rectangular grid
/// - `mesh_2d::Compact2D` - 2D grid with walls/obstacles
/// - `mesh_3d::Full3D` - Fully connected 3D rectangular volume
/// - `mesh_3d::Compact3D` - 3D volume with walls/obstacles
/// - `mesh_topo::MeshWithTopology` - Graph with custom topology
///
/// # Example
///
/// ```
/// use shortestpath::{Mesh, Gate, mesh_2d::Full2D};
///
/// // Create a 3x3 grid
/// let mesh = Full2D::new(3, 3);
///
/// // Query mesh properties
/// assert_eq!(mesh.len(), 9); // 3x3 = 9 nodes
///
/// // Get successors (neighbors) of node 4 (center of grid)
/// let neighbors: Vec<Gate> = mesh.successors(4).collect();
/// // Center node has 8 neighbors (all surrounding cells)
/// assert_eq!(neighbors.len(), 8);
/// ```
pub trait Mesh {
    /// The iterator type returned by `successors()`.
    ///
    /// This must be an iterator that yields `Gate` objects representing
    /// reachable neighboring nodes and their distances.
    type IntoIter: Iterator<Item = Gate>;

    /// Returns an iterator over the successors (neighbors) of a given node.
    ///
    /// Each successor is represented as a `Gate` containing the neighbor's
    /// index and the distance/cost to reach it from the current node.
    ///
    /// # Arguments
    ///
    /// * `from` - The index of the node to query
    ///
    /// # Returns
    ///
    /// An iterator yielding `Gate` objects for each reachable neighbor
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Full2D};
    ///
    /// let mesh = Full2D::new(3, 3);
    ///
    /// // Get neighbors of top-left corner (index 0)
    /// let neighbors: Vec<_> = mesh.successors(0).collect();
    /// // Corner has 3 neighbors: right, down, and diagonal
    /// assert_eq!(neighbors.len(), 3);
    /// ```
    fn successors(&self, from: usize) -> Self::IntoIter;

    /// Returns the total number of nodes in the mesh.
    ///
    /// # Returns
    ///
    /// The total count of nodes/cells in this mesh
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Full2D};
    ///
    /// let mesh = Full2D::new(5, 4);
    /// assert_eq!(mesh.len(), 20); // 5 * 4 = 20 nodes
    /// ```
    fn len(&self) -> usize;

    /// Returns `true` if the mesh contains no nodes.
    ///
    /// # Example
    ///
    /// ```
    /// use shortestpath::{Mesh, mesh_2d::Full2D};
    ///
    /// let empty_mesh = Full2D::new(0, 0);
    /// assert!(empty_mesh.is_empty());
    ///
    /// let mesh = Full2D::new(5, 4);
    /// assert!(!mesh.is_empty());
    /// ```
    fn is_empty(&self) -> bool {
        self.len() == 0
    }
}
