shortestpath 0.10.0

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

use crate::gradient::Gradient;
use crate::mesh::Mesh;

/// Returns all mesh indexes ordered by their gradient distance, from closest to furthest.
///
/// This function sorts all indexes based on their distance values in the gradient.
/// The `backward` parameter affects tie-breaking: when two indexes have equal distances,
/// `backward` determines whether lower or higher indexes come first.
///
/// # Arguments
///
/// * `mesh` - The mesh to get the total number of indexes from
/// * `gradient` - The computed gradient containing distance values for each node
/// * `backward` - If `false`, lower indexes come first when distances are equal.
///   If `true`, higher indexes come first when distances are equal.
///
/// # Returns
///
/// A `Vec<usize>` containing all mesh indexes sorted by distance (closest first).
/// Unreachable nodes (with `DISTANCE_MAX`) will appear at the end.
///
/// # Example
///
/// ```
/// use shortestpath::{Gradient, mesh_2d::Full2D, ordered_indexes};
///
/// let mesh = Full2D::new(5, 5);
/// let mut gradient = Gradient::from_mesh(&mesh);
///
/// // Set the center node as target
/// gradient.set_distance(12, 0.0);
/// gradient.spread(&mesh);
///
/// // Get all indexes ordered from closest to furthest
/// let ordered = ordered_indexes(&mesh, &gradient, false);
///
/// // First index should be the target (distance 0)
/// assert_eq!(ordered[0], 12);
/// ```
pub fn ordered_indexes(mesh: &impl Mesh, gradient: &Gradient, backward: bool) -> Vec<usize> {
    let mut indexes: Vec<usize> = (0..mesh.len()).collect();

    indexes.sort_by(|&a, &b| {
        let dist_a = gradient.get_distance(a);
        let dist_b = gradient.get_distance(b);

        match dist_a.partial_cmp(&dist_b) {
            Some(std::cmp::Ordering::Equal) => {
                // Tie-breaking: use index order based on backward flag
                if backward {
                    b.cmp(&a) // Higher indexes first
                } else {
                    a.cmp(&b) // Lower indexes first
                }
            }
            Some(ord) => ord,
            None => std::cmp::Ordering::Equal,
        }
    });

    indexes
}

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

    #[test]
    fn test_ordered_indexes_basic() {
        let mesh = Full2D::new(5, 5);
        let mut gradient = Gradient::from_mesh(&mesh);

        // Set center as target
        gradient.set_distance(12, 0.0);
        gradient.spread(&mesh);

        let ordered = ordered_indexes(&mesh, &gradient, false);

        // Should have all 25 indexes
        assert_eq!(ordered.len(), 25);

        // First should be the target (distance 0)
        assert_eq!(ordered[0], 12);

        // Verify ordering: each subsequent index should have >= distance
        for i in 0..ordered.len() - 1 {
            let dist_curr = gradient.get_distance(ordered[i]);
            let dist_next = gradient.get_distance(ordered[i + 1]);
            assert!(
                dist_curr <= dist_next,
                "Index {} (dist {}) should come before index {} (dist {})",
                ordered[i],
                dist_curr,
                ordered[i + 1],
                dist_next
            );
        }
    }

    #[test]
    fn test_ordered_indexes_backward_tiebreaking() {
        // Use a 3x1 grid where nodes 0 and 2 have the same distance to node 1
        let mesh = Full2D::new(3, 1);
        let mut gradient = Gradient::from_mesh(&mesh);

        // Set middle node as target
        gradient.set_distance(1, 0.0);
        gradient.spread(&mesh);

        // Nodes 0 and 2 both have distance 1.0 to node 1
        assert_eq!(gradient.get_distance(0), DISTANCE_STRAIGHT);
        assert_eq!(gradient.get_distance(2), DISTANCE_STRAIGHT);

        let ordered_forward = ordered_indexes(&mesh, &gradient, false);
        let ordered_backward = ordered_indexes(&mesh, &gradient, true);

        // First should always be the target
        assert_eq!(ordered_forward[0], 1);
        assert_eq!(ordered_backward[0], 1);

        // Forward: lower index first when tied (0 before 2)
        assert_eq!(ordered_forward[1], 0);
        assert_eq!(ordered_forward[2], 2);

        // Backward: higher index first when tied (2 before 0)
        assert_eq!(ordered_backward[1], 2);
        assert_eq!(ordered_backward[2], 0);
    }

    #[test]
    fn test_ordered_indexes_unreachable_at_end() {
        use crate::mesh_2d::Compact2D;

        // Create a mesh with disconnected regions
        // Two 2x2 regions separated by walls
        let map = "\
.#.
.#.";
        let mesh = Compact2D::from_text(map).expect("Failed to parse map");

        let mut gradient = Gradient::from_mesh(&mesh);

        // Set node 0 as target (left side)
        gradient.set_distance(0, 0.0);
        gradient.spread(&mesh);

        let ordered = ordered_indexes(&mesh, &gradient, false);

        // The reachable nodes should come first, unreachable at end
        // Node 0 is the target, node 1 is connected to it
        // Node 2 is unreachable (on the other side of the wall)
        let last_idx = ordered.len() - 1;
        assert_eq!(
            gradient.get_distance(ordered[last_idx]),
            DISTANCE_MAX,
            "Last index should be unreachable"
        );
    }

    #[test]
    fn test_ordered_indexes_single_node() {
        let mesh = Full2D::new(1, 1);
        let gradient = Gradient::from_mesh(&mesh);

        let ordered = ordered_indexes(&mesh, &gradient, false);

        assert_eq!(ordered.len(), 1);
        assert_eq!(ordered[0], 0);
    }
}