shortestpath 0.10.0

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

//! Utility functions for finding optimal or worst positions relative to a set of indices.
//!
//! These functions compute the cell that minimizes or maximizes the sum of squared
//! distances to a given set of target indices. This is useful for:
//! - Finding optimal meeting points (centroid)
//! - Finding spawn points furthest from players (anti-centroid)
//! - Balancing positions in game scenarios
//!
//! # Example
//!
//! ```
//! use shortestpath::{best_for_indexes, worst_for_indexes, mesh_2d::Full2D};
//!
//! let mesh = Full2D::new(5, 5);
//!
//! // Find optimal meeting point for players at corners
//! let players = vec![0, 4, 20, 24];
//! let meeting_point = best_for_indexes(&mesh, &players);
//! assert_eq!(meeting_point, Some(12)); // Center
//!
//! // Find spawn point furthest from a single player
//! let spawn = worst_for_indexes(&mesh, &[0]);
//! assert_eq!(spawn, Some(24)); // Opposite corner
//! ```

use crate::distance::*;
use crate::gradient::*;
use crate::mesh::*;

/// Finds the mesh index that minimizes the sum of squared distances to a set of target indices.
///
/// This function computes, for each cell in the mesh, the sum of squared distances to all
/// provided target indices. It then returns the index of the cell with the minimum sum.
/// This effectively finds the "centroid" or optimal meeting point for the given targets.
///
/// # Algorithm
///
/// For each target index:
/// 1. Create a gradient with that index as the source (distance 0)
/// 2. Spread the gradient to compute distances to all cells
///
/// For each cell in the mesh:
/// 1. Sum the squared distances from all targets to this cell
/// 2. Track the cell with the minimum sum
///
/// # Arguments
///
/// * `mesh` - The mesh to search over
/// * `indexes` - A slice of target indices to minimize distance from
///
/// # Returns
///
/// - `Some(index)` - The index of the cell that minimizes the sum of squared distances
/// - `None` - If the mesh is empty, no indices are provided, or no cell is reachable from all targets
///
/// # Example
///
/// ```
/// use shortestpath::{best_for_indexes, mesh_2d::Full2D};
///
/// let mesh = Full2D::new(5, 5);
///
/// // Find the best meeting point for corners
/// let corners = vec![0, 4, 20, 24];
/// let best = best_for_indexes(&mesh, &corners);
///
/// // The center (index 12) minimizes total squared distance to corners
/// assert_eq!(best, Some(12));
/// ```
pub fn best_for_indexes(mesh: &impl Mesh, indexes: &[usize]) -> Option<usize> {
    if mesh.is_empty() || indexes.is_empty() {
        return None;
    }

    let len = mesh.len();

    // Compute gradients from each target index
    let mut gradients: Vec<Gradient> = Vec::with_capacity(indexes.len());
    for &idx in indexes {
        let mut gradient = Gradient::from_mesh(mesh);
        gradient.set_distance(idx, 0.0);
        gradient.spread(mesh);
        gradients.push(gradient);
    }

    // For each cell, compute sum of squared distances
    let mut best_index: Option<usize> = None;
    let mut best_sum = f32::MAX;

    for cell in 0..len {
        let mut sum_squared: f32 = 0.0;
        let mut all_reachable = true;

        for gradient in &gradients {
            let dist = gradient.get_distance(cell);
            if dist >= DISTANCE_MAX {
                all_reachable = false;
                break;
            }
            sum_squared += dist * dist;
        }

        if all_reachable && sum_squared < best_sum {
            best_sum = sum_squared;
            best_index = Some(cell);
        }
    }

    best_index
}

/// Finds the mesh index that maximizes the sum of squared distances to a set of target indices.
///
/// This function computes, for each cell in the mesh, the sum of squared distances to all
/// provided target indices. It then returns the index of the cell with the maximum sum.
/// This effectively finds the "anti-centroid" or the point furthest from all targets.
///
/// # Algorithm
///
/// For each target index:
/// 1. Create a gradient with that index as the source (distance 0)
/// 2. Spread the gradient to compute distances to all cells
///
/// For each cell in the mesh:
/// 1. Sum the squared distances from all targets to this cell
/// 2. Track the cell with the maximum sum
///
/// # Arguments
///
/// * `mesh` - The mesh to search over
/// * `indexes` - A slice of target indices to maximize distance from
///
/// # Returns
///
/// - `Some(index)` - The index of the cell that maximizes the sum of squared distances
/// - `None` - If the mesh is empty, no indices are provided, or no cell is reachable from all targets
///
/// # Example
///
/// ```
/// use shortestpath::{worst_for_indexes, mesh_2d::Full2D};
///
/// let mesh = Full2D::new(5, 5);
///
/// // Find the point furthest from the center
/// let center = vec![12];
/// let worst = worst_for_indexes(&mesh, &center);
///
/// // A corner (0, 4, 20, or 24) maximizes distance from center
/// assert!(worst == Some(0) || worst == Some(4) || worst == Some(20) || worst == Some(24));
/// ```
pub fn worst_for_indexes(mesh: &impl Mesh, indexes: &[usize]) -> Option<usize> {
    if mesh.is_empty() || indexes.is_empty() {
        return None;
    }

    let len = mesh.len();

    // Compute gradients from each target index
    let mut gradients: Vec<Gradient> = Vec::with_capacity(indexes.len());
    for &idx in indexes {
        let mut gradient = Gradient::from_mesh(mesh);
        gradient.set_distance(idx, 0.0);
        gradient.spread(mesh);
        gradients.push(gradient);
    }

    // For each cell, compute sum of squared distances
    let mut worst_index: Option<usize> = None;
    let mut worst_sum = f32::MIN;

    for cell in 0..len {
        let mut sum_squared: f32 = 0.0;
        let mut all_reachable = true;

        for gradient in &gradients {
            let dist = gradient.get_distance(cell);
            if dist >= DISTANCE_MAX {
                all_reachable = false;
                break;
            }
            sum_squared += dist * dist;
        }

        if all_reachable && sum_squared > worst_sum {
            worst_sum = sum_squared;
            worst_index = Some(cell);
        }
    }

    worst_index
}

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

    #[test]
    fn test_best_for_indexes_center() {
        // On a 5x5 grid, the center (12) should minimize distance to all 4 corners
        let rect = Full2D::new(5, 5);
        let corners = vec![0, 4, 20, 24];

        let best = best_for_indexes(&rect, &corners);
        assert_eq!(best, Some(12), "Center should minimize distance to corners");
    }

    #[test]
    fn test_best_for_indexes_single() {
        // With a single target, the best is the target itself (distance 0)
        let rect = Full2D::new(5, 5);
        let single = vec![7];

        let best = best_for_indexes(&rect, &single);
        assert_eq!(best, Some(7), "Best should be the target itself");
    }

    #[test]
    fn test_best_for_indexes_empty() {
        let rect = Full2D::new(5, 5);

        // Empty mesh
        let empty_mesh = Full2D::new(0, 0);
        assert_eq!(best_for_indexes(&empty_mesh, &[0]), None);

        // Empty indexes
        assert_eq!(best_for_indexes(&rect, &[]), None);
    }

    #[test]
    fn test_worst_for_indexes_from_center() {
        // From the center, corners should be furthest
        let rect = Full2D::new(5, 5);
        let center = vec![12];

        let worst = worst_for_indexes(&rect, &center);
        // One of the 4 corners should be furthest
        assert!(
            worst == Some(0) || worst == Some(4) || worst == Some(20) || worst == Some(24),
            "Worst should be a corner, got {:?}",
            worst
        );
    }

    #[test]
    fn test_worst_for_indexes_from_corners() {
        // From all corners, the center should still not be the worst
        // (corners are equidistant from center, but some edges might be further from some corners)
        let rect = Full2D::new(5, 5);
        let corners = vec![0, 4, 20, 24];

        let worst = worst_for_indexes(&rect, &corners);
        assert!(worst.is_some(), "Should find a worst index");

        // The worst should not be the center (which minimizes distance)
        assert_ne!(worst, Some(12), "Center should not be the worst");
    }

    #[test]
    fn test_worst_for_indexes_single() {
        // With single target, worst is furthest point
        let rect = Full2D::new(5, 5);
        let corner = vec![0];

        let worst = worst_for_indexes(&rect, &corner);
        // Opposite corner should be furthest
        assert_eq!(worst, Some(24), "Opposite corner should be furthest");
    }

    #[test]
    fn test_worst_for_indexes_empty() {
        let rect = Full2D::new(5, 5);

        // Empty mesh
        let empty_mesh = Full2D::new(0, 0);
        assert_eq!(worst_for_indexes(&empty_mesh, &[0]), None);

        // Empty indexes
        assert_eq!(worst_for_indexes(&rect, &[]), None);
    }

    #[test]
    fn test_best_worst_with_walls() {
        // Create a grid with walls
        let map = "\
.....
.###.
.....";
        let mesh = Compact2D::from_text(map).unwrap();

        // Get corner indices
        // (0,0) and (4,0) are top corners, (0,2) and (4,2) are bottom corners
        let corners: Vec<usize> = vec![
            mesh.xy_to_index(0, 0).unwrap(),
            mesh.xy_to_index(4, 0).unwrap(),
            mesh.xy_to_index(0, 2).unwrap(),
            mesh.xy_to_index(4, 2).unwrap(),
        ];

        let best = best_for_indexes(&mesh, &corners);
        assert!(best.is_some(), "Should find a best index even with walls");

        let worst = worst_for_indexes(&mesh, &corners);
        assert!(worst.is_some(), "Should find a worst index even with walls");
    }
}