condor-pathfinding-grid 0.4.0

//! Private candidate contract: iterative-deepening DFS for static 4-connected grids.
//!
//! **Hypothesis:** repeated depth-limited DFS reproduces BFS hop-optimal paths
//! with O(depth) frontier memory, which can matter on very large open grids
//! where a BFS frontier ring dominates memory.
//!
//! **Non-negotiable behavior:** hop-optimal results identical in cost to
//! [`super::bfs::Bfs`], standard invalid/found/no-path outcome, and budget
//! enforcement counting cumulative node visits across deepening rounds.
//!
//! **Evidence and promotion:** ordinary `grid_core` route
//! (`just test-fast grid_core`, `just clippy-target grid_core`); promotion
//! requires memory-vs-work evidence against the BFS baseline. This remains
//! private: no feature, fixture, target, or separate harness route.

use crate::{
    grid::Grid,
    path::Path,
    point::Point,
    search::{BudgetWatch, Pathfinder, SearchRequest, SearchResult},
};

/// Online [`Pathfinder`] candidate: unweighted iterative-deepening DFS.
///
/// Cost model: unit hop count; ignores `traversal_cost`. Hop-optimal like BFS,
/// trading repeated re-expansion for a depth-bounded memory footprint.
#[derive(Debug, Default, Clone, Copy)]
pub struct IterativeDeepeningDfs;

impl Pathfinder for IterativeDeepeningDfs {
    fn name(&self) -> &'static str {
        "iddfs"
    }

    fn search(&self, grid: &Grid, request: SearchRequest) -> SearchResult {
        crate::search::validate_request(grid, request)?;

        if !grid.is_reachable(request.start, request.goal) {
            return crate::search::not_found(0);
        }

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

        let watch = BudgetWatch::start(request.budget);
        let mut visited_nodes = 0usize;
        // Reachability holds, so a shortest path of at most cell_count - 1 hops exists.
        let max_depth = grid.cell_count().saturating_sub(1);

        for depth_limit in 1..=max_depth {
            let mut on_path = vec![request.start];
            if depth_limited(
                grid,
                request.goal,
                depth_limit,
                &mut on_path,
                &mut visited_nodes,
                &watch,
            )? {
                return crate::search::found(
                    Path::from_steps(on_path).expect("path contains at least one point"),
                    visited_nodes,
                );
            }
        }

        crate::search::not_found(visited_nodes)
    }
}

/// Depth-limited DFS extending `on_path`; returns whether the goal was reached.
fn depth_limited(
    grid: &Grid,
    goal: Point,
    depth_limit: usize,
    on_path: &mut Vec<Point>,
    visited_nodes: &mut usize,
    watch: &BudgetWatch,
) -> Result<bool, crate::search::GridSearchError> {
    let current = *on_path.last().expect("path always holds the start");
    *visited_nodes += 1;

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

    if current == goal {
        return Ok(true);
    }

    if on_path.len() > depth_limit {
        return Ok(false);
    }

    for neighbor in grid.neighbors4(current) {
        if on_path.contains(&neighbor) {
            continue;
        }

        on_path.push(neighbor);
        if depth_limited(grid, goal, depth_limit, on_path, visited_nodes, watch)? {
            return Ok(true);
        }
        on_path.pop();
    }

    Ok(false)
}

#[cfg(test)]
mod tests {
    use crate::{
        algorithms::{bfs::Bfs, iterative_deepening_dfs::IterativeDeepeningDfs},
        grid::{Cell, Grid},
        point::Point,
        search::{BudgetExhausted, GridSearchError, Pathfinder, SearchBudget, SearchRequest},
    };

    #[test]
    fn matches_bfs_hop_cost_through_the_only_gap() {
        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 request = SearchRequest::new(Point::new(0, 0), Point::new(4, 4));

        let iddfs = IterativeDeepeningDfs
            .search(&grid, request)
            .expect("endpoints are walkable");
        let bfs = Bfs.search(&grid, request).expect("endpoints are walkable");

        assert!(iddfs.is_found());
        assert_eq!(iddfs.cost(), bfs.cost());
    }

    #[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 result = IterativeDeepeningDfs
            .search(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");
        assert!(!result.is_found());
    }

    #[test]
    fn expansion_budget_stops_before_goal() {
        let grid = Grid::new(8, 1).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(7, 0))
            .with_budget(SearchBudget::max_expansions(3));
        let error = IterativeDeepeningDfs
            .search(&grid, request)
            .expect_err("budget should exhaust across deepening rounds");
        assert_eq!(
            error,
            GridSearchError::BudgetExhausted(BudgetExhausted::Expansions {
                limit: 3,
                expansions: 3
            })
        );
    }
}