condor-pathfinding-grid 0.4.0

//! Private candidate contract: all-optimal-paths enumeration for static weighted grids.
//!
//! **Hypothesis:** enumerating every cost-optimal path (the `astar_bag`
//! analogue) from one exact Dijkstra pass plus backward optimal-DAG walking
//! gives tie-analysis and path-diversity evidence that single-path solvers
//! cannot expose.
//!
//! **Non-negotiable behavior:** every returned path has exactly the established
//! Dijkstra/A* optimal cost; enumeration is deterministic in fixed axis order
//! and hard-capped by `max_paths` so symmetric open rooms cannot explode; the
//! standard invalid/found/no-path outcome and [`BudgetWatch`] enforcement apply.
//!
//! **Evidence and promotion:** ordinary `grid_core` route
//! (`just test-fast grid_core`, `just clippy-target grid_core`). Not a
//! [`crate::Pathfinder`], so grid conformance and the bench lane do not cover
//! it directly: promotion is a product-need decision (G-GRID sign-off) plus a
//! small bench-lane extension bounding enumeration overhead against a single
//! Dijkstra query. This remains
//! private: no feature, fixture, target, or separate harness route.

use std::{cmp::Ordering, collections::BinaryHeap};

use crate::{
    grid::Grid,
    path::Path,
    search::{BudgetWatch, GridSearchError, SearchOutcome, SearchRequest, SearchStats},
};

/// Result type for optimal-path enumeration: all paths or no-path, with stats.
pub type AllOptimalPathsResult = Result<SearchOutcome<Vec<Path>, SearchStats>, GridSearchError>;

/// Candidate enumerator of **every** cost-optimal path between two cells.
///
/// Cost model: sums per-cell `traversal_cost` on 4-connected edges, matching
/// [`super::dijkstra::Dijkstra`]. Enumeration stops at `max_paths` paths.
#[derive(Debug, Clone, Copy)]
pub struct AllOptimalPaths {
    /// Hard cap on returned paths; symmetric rooms grow combinatorially.
    pub max_paths: usize,
}

impl Default for AllOptimalPaths {
    fn default() -> Self {
        Self { max_paths: 64 }
    }
}

impl AllOptimalPaths {
    /// Stable algorithm identifier for logs and future portfolio wiring.
    pub const NAME: &str = "astar-bag";

    /// Enumerates all optimal paths for `request`, capped at `max_paths`.
    pub fn enumerate(&self, grid: &Grid, request: SearchRequest) -> AllOptimalPathsResult {
        crate::search::validate_request(grid, request)?;
        let Some(start_index) = grid.index_of(request.start) else {
            return Ok(SearchOutcome::no_path(SearchStats { visited_nodes: 0 }));
        };
        let Some(goal_index) = grid.index_of(request.goal) else {
            return Ok(SearchOutcome::no_path(SearchStats { visited_nodes: 0 }));
        };

        if request.start == request.goal {
            let path =
                Path::from_steps(vec![request.start]).expect("path contains at least one point");
            return Ok(SearchOutcome::found(
                vec![path],
                SearchStats { visited_nodes: 1 },
            ));
        }

        let watch = BudgetWatch::start(request.budget);
        let (best_costs, visited_nodes) = exact_costs_from_start(grid, start_index, &watch)?;

        let Some(goal_cost) = best_costs[goal_index] else {
            return Ok(SearchOutcome::no_path(SearchStats { visited_nodes }));
        };

        let paths = enumerate_backward(
            grid,
            &best_costs,
            start_index,
            goal_index,
            goal_cost,
            self.max_paths,
        );

        Ok(SearchOutcome::found(paths, SearchStats { visited_nodes }))
    }
}

/// Full Dijkstra sweep from `start_index`; returns exact costs for every cell.
fn exact_costs_from_start(
    grid: &Grid,
    start_index: usize,
    watch: &BudgetWatch,
) -> Result<(Vec<Option<usize>>, usize), GridSearchError> {
    let mut frontier = BinaryHeap::from([FrontierEntry {
        cost_so_far: 0,
        index: start_index,
    }]);
    let mut best_costs: Vec<Option<usize>> = vec![None; grid.cell_count()];
    let mut visited_nodes = 0usize;
    best_costs[start_index] = Some(0);

    while let Some(entry) = frontier.pop() {
        if best_costs[entry.index] != Some(entry.cost_so_far) {
            continue;
        }

        visited_nodes += 1;
        if let Err(reason) = watch.check(visited_nodes) {
            return Err(crate::search::budget_error(reason));
        }

        let current = grid.point_from_index(entry.index);
        for neighbor in grid.neighbors4(current) {
            let neighbor_index = grid
                .index_of(neighbor)
                .expect("walkable neighbors must exist inside the grid");
            let edge_cost = grid
                .traversal_cost(neighbor)
                .expect("walkable neighbors must have a traversal cost");
            let Some(next_cost) = entry.cost_so_far.checked_add(edge_cost) else {
                continue;
            };

            if best_costs[neighbor_index].is_some_and(|best| next_cost >= best) {
                continue;
            }

            best_costs[neighbor_index] = Some(next_cost);
            frontier.push(FrontierEntry {
                cost_so_far: next_cost,
                index: neighbor_index,
            });
        }
    }

    Ok((best_costs, visited_nodes))
}

/// Walks the optimal DAG backwards from the goal, materializing each path.
fn enumerate_backward(
    grid: &Grid,
    best_costs: &[Option<usize>],
    start_index: usize,
    goal_index: usize,
    goal_cost: usize,
    max_paths: usize,
) -> Vec<Path> {
    let mut paths = Vec::new();
    let mut suffix = vec![goal_index];
    let mut choice_stack: Vec<Vec<usize>> =
        vec![optimal_predecessors(grid, best_costs, goal_index)];

    while let Some(alternatives) = choice_stack.last_mut() {
        if paths.len() >= max_paths {
            break;
        }

        let Some(predecessor) = alternatives.pop() else {
            choice_stack.pop();
            suffix.pop();
            continue;
        };

        suffix.push(predecessor);
        if predecessor == start_index {
            let steps: Vec<_> = suffix
                .iter()
                .rev()
                .map(|&index| grid.point_from_index(index))
                .collect();
            paths.push(
                Path::from_steps_with_cost(steps, goal_cost)
                    .expect("path contains at least one point"),
            );
            suffix.pop();
        } else {
            choice_stack.push(optimal_predecessors(grid, best_costs, predecessor));
        }
    }

    paths
}

/// Neighbors `u` of `v` on some optimal path: `cost(u) + enter(v) == cost(v)`.
fn optimal_predecessors(grid: &Grid, best_costs: &[Option<usize>], index: usize) -> Vec<usize> {
    let Some(cost) = best_costs[index] else {
        return Vec::new();
    };
    let enter_cost = grid
        .traversal_cost(grid.point_from_index(index))
        .expect("cells with a best cost are walkable");

    grid.neighbors4(grid.point_from_index(index))
        .into_iter()
        .filter_map(|neighbor| grid.index_of(neighbor))
        .filter(|&neighbor_index| {
            best_costs[neighbor_index]
                .and_then(|neighbor_cost| neighbor_cost.checked_add(enter_cost))
                == Some(cost)
        })
        .collect()
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct FrontierEntry {
    cost_so_far: usize,
    index: usize,
}

impl Ord for FrontierEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .cost_so_far
            .cmp(&self.cost_so_far)
            .then_with(|| other.index.cmp(&self.index))
    }
}

impl PartialOrd for FrontierEntry {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[cfg(test)]
mod tests {
    use crate::{
        algorithms::astar_all_optimal::AllOptimalPaths,
        grid::{Cell, Grid},
        point::Point,
        search::SearchRequest,
    };

    #[test]
    fn open_rectangle_yields_all_lattice_optimal_paths() {
        let grid = Grid::new(3, 3).expect("grid dimensions are valid");
        let outcome = AllOptimalPaths::default()
            .enumerate(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");

        let paths = outcome.path().expect("open grid has optimal paths");
        // C(4, 2) monotone lattice paths on a 3x3 open grid.
        assert_eq!(paths.len(), 6);
        for path in paths {
            assert_eq!(path.cost(), 4);
            assert_eq!(path.start(), Point::new(0, 0));
            assert_eq!(path.goal(), Point::new(2, 2));
        }
    }

    #[test]
    fn cap_limits_enumeration() {
        let grid = Grid::new(4, 4).expect("grid dimensions are valid");
        let outcome = AllOptimalPaths { max_paths: 3 }
            .enumerate(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(3, 3)),
            )
            .expect("endpoints are walkable");
        assert_eq!(outcome.path().map(Vec::len), Some(3));
    }

    #[test]
    fn corridor_has_exactly_one_optimal_path() {
        let mut grid = Grid::new(5, 5).expect("grid dimensions are valid");
        for y in 0..5 {
            if y != 2 {
                grid.set_cell(Point::new(2, y), Cell::Blocked)
                    .expect("valid grid edit");
            }
        }
        let outcome = AllOptimalPaths::default()
            .enumerate(
                &grid,
                SearchRequest::new(Point::new(0, 2), Point::new(4, 2)),
            )
            .expect("endpoints are walkable");
        assert_eq!(outcome.path().map(Vec::len), Some(1));
    }

    #[test]
    fn reports_when_no_path_exists() {
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        for x in 0..3 {
            grid.set_cell(Point::new(x, 1), Cell::Blocked)
                .expect("valid grid edit");
        }
        let outcome = AllOptimalPaths::default()
            .enumerate(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");
        assert!(!outcome.is_found());
    }
}