condor-pathfinding-grid 0.4.0

//! Private candidate: bidirectional BFS with packed reachability bitsets.
//!
//! **Hypothesis (aspirational):** packed frontier expansion from both endpoints
//! can reduce unit-cost four-connected search work on wide static grids while
//! retaining the canonical shortest-path answer.
//!
//! **Current implementation:** layered bidirectional BFS (same control flow as
//! [`super::bidirectional_bfs::BidirectionalBfs`]) with `u64` reachability
//! bitsets as a membership mirror of distance labels. Expansion still uses only
//! [`Grid::neighbors4`] — not word-shift wavefront operators. Performance claims
//! for true bit-parallel expansion are not established.
//!
//! **Non-negotiable behavior:** frontier meeting, parent reconstruction, and
//! disconnected grids must retain BFS-equivalent cost, witness, no-path, and
//! deterministic behavior. Reach bitsets and distance labels must never invent
//! diagonal adjacency, bit-leak edges, or a partial meeting as a path.
//!
//! **Failure memory:** relaxed cardinal JPS branch skipping previously accepted
//! an invalid route of cost `472` where the exact answer was `400`. This
//! candidate must not inherit relaxed pruning or skip rules without a proof of
//! complete cardinal successor coverage.
//!
//! **Evidence and promotion:** ordinary `grid_core` route while implementing;
//! exact owner conformance and later bench evidence. Remains private: no
//! feature, fixture, target, or separate harness route.

use std::collections::VecDeque;

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

/// Online [`Pathfinder`] candidate: packed bidirectional unit-cost wavefront.
///
/// Cost model: unit hop count (ignores `traversal_cost`), matching
/// [`super::bfs::Bfs`] / [`super::bidirectional_bfs::BidirectionalBfs`].
/// Reachability is stored in packed `u64` words; expansions still walk only
/// four-connected neighbors so diagonal adjacency and bit leakage cannot invent
/// a path.
#[derive(Debug, Default, Clone, Copy)]
pub struct BidirectionalBitParallelWavefront;

impl BidirectionalBitParallelWavefront {
    /// Stable source-local candidate identity.
    pub const CANDIDATE_ID: &str = "static-unweighted-grid/bit-parallel-bidirectional-wavefront";
}

impl Pathfinder for BidirectionalBitParallelWavefront {
    fn name(&self) -> &'static str {
        "bit-parallel-bi-wavefront"
    }

    fn search(&self, grid: &Grid, request: SearchRequest) -> SearchResult {
        crate::search::validate_request(grid, request)?;
        let Some(start_index) = grid.index_of(request.start) else {
            return crate::search::not_found(0);
        };
        let Some(goal_index) = grid.index_of(request.goal) else {
            return crate::search::not_found(0);
        };

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

        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 word_count = words_for(grid.cell_count());
        let mut reached_from_start = vec![0u64; word_count];
        let mut reached_from_goal = vec![0u64; word_count];
        let mut start_frontier = VecDeque::from([start_index]);
        let mut goal_frontier = VecDeque::from([goal_index]);
        let mut distances_from_start = vec![None; grid.cell_count()];
        let mut distances_from_goal = vec![None; grid.cell_count()];
        let mut parents_from_start = vec![None; grid.cell_count()];
        let mut parents_from_goal = vec![None; grid.cell_count()];
        let mut settled_any = vec![false; grid.cell_count()];
        let mut visited_nodes = 0usize;
        let mut expand_from_start = true;
        let watch = BudgetWatch::start(request.budget);

        set_bit(&mut reached_from_start, start_index);
        set_bit(&mut reached_from_goal, goal_index);
        distances_from_start[start_index] = Some(0);
        distances_from_goal[goal_index] = Some(0);

        while !start_frontier.is_empty() && !goal_frontier.is_empty() {
            let meeting = if expand_from_start {
                expand_frontier(
                    grid,
                    &mut start_frontier,
                    &mut reached_from_start,
                    &reached_from_goal,
                    &mut distances_from_start,
                    &distances_from_goal,
                    &mut parents_from_start,
                    &mut settled_any,
                    &mut visited_nodes,
                )
            } else {
                expand_frontier(
                    grid,
                    &mut goal_frontier,
                    &mut reached_from_goal,
                    &reached_from_start,
                    &mut distances_from_goal,
                    &distances_from_start,
                    &mut parents_from_goal,
                    &mut settled_any,
                    &mut visited_nodes,
                )
            };

            if let Some(meeting_index) = meeting {
                // Only accept a meeting when both sides have settled the cell
                // with complete parent chains (never a partial frontier touch).
                if distances_from_start[meeting_index].is_some()
                    && distances_from_goal[meeting_index].is_some()
                {
                    return crate::search::found(
                        reconstruct_path(
                            grid,
                            &parents_from_start,
                            &parents_from_goal,
                            start_index,
                            goal_index,
                            meeting_index,
                        ),
                        visited_nodes,
                    );
                }
            }

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

            expand_from_start = !expand_from_start;
        }

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

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

#[allow(
    clippy::too_many_arguments,
    reason = "frontier expansion keeps sides explicit rather than a latent context struct"
)]
fn expand_frontier(
    grid: &Grid,
    frontier: &mut VecDeque<usize>,
    reached: &mut [u64],
    other_reached: &[u64],
    distances: &mut [Option<usize>],
    other_distances: &[Option<usize>],
    parents: &mut [Option<usize>],
    settled_any: &mut [bool],
    visited_nodes: &mut usize,
) -> Option<usize> {
    let layer_len = frontier.len();
    let mut best_meeting = None;

    for _ in 0..layer_len {
        let current_index = frontier
            .pop_front()
            .expect("frontier layer length must match queued entries");

        if !settled_any[current_index] {
            settled_any[current_index] = true;
            *visited_nodes += 1;
        }

        let current_distance =
            distances[current_index].expect("queued nodes must have a known distance");
        if test_bit(other_reached, current_index)
            && let Some(other_distance) = other_distances[current_index]
        {
            update_meeting_candidate(
                &mut best_meeting,
                current_index,
                current_distance + other_distance,
            );
        }

        let current = grid.point_from_index(current_index);
        // Expand only through explicit four-connected neighbors. Never invent
        // diagonal adjacency from packed word shifts.
        for neighbor in grid.neighbors4(current) {
            let neighbor_index = grid
                .index_of(neighbor)
                .expect("walkable neighbors must exist inside the grid");

            if test_bit(reached, neighbor_index) {
                continue;
            }

            set_bit(reached, neighbor_index);
            let next_distance = current_distance + 1;
            distances[neighbor_index] = Some(next_distance);
            parents[neighbor_index] = Some(current_index);
            frontier.push_back(neighbor_index);

            if test_bit(other_reached, neighbor_index)
                && let Some(other_distance) = other_distances[neighbor_index]
            {
                update_meeting_candidate(
                    &mut best_meeting,
                    neighbor_index,
                    next_distance + other_distance,
                );
            }
        }
    }

    best_meeting.map(|candidate| candidate.index)
}

fn update_meeting_candidate(
    best_meeting: &mut Option<MeetingCandidate>,
    index: usize,
    total_cost: usize,
) {
    let should_replace = best_meeting
        .is_none_or(|current| (total_cost, index) < (current.total_cost, current.index));

    if should_replace {
        *best_meeting = Some(MeetingCandidate { index, total_cost });
    }
}

fn reconstruct_path(
    grid: &Grid,
    parents_from_start: &[Option<usize>],
    parents_from_goal: &[Option<usize>],
    start_index: usize,
    goal_index: usize,
    meeting_index: usize,
) -> Path {
    let mut steps = vec![grid.point_from_index(meeting_index)];

    let mut current_index = meeting_index;
    while current_index != start_index {
        current_index = parents_from_start[current_index]
            .expect("meeting node must have a complete start-side parent chain");
        steps.push(grid.point_from_index(current_index));
    }
    steps.reverse();

    current_index = meeting_index;
    while current_index != goal_index {
        current_index = parents_from_goal[current_index]
            .expect("meeting node must have a complete goal-side parent chain");
        steps.push(grid.point_from_index(current_index));
    }

    Path::from_steps(steps).expect("path contains at least one point")
}

fn words_for(cell_count: usize) -> usize {
    cell_count.div_ceil(64)
}

fn set_bit(words: &mut [u64], index: usize) {
    let word = index / 64;
    let bit = index % 64;
    words[word] |= 1u64 << bit;
}

fn test_bit(words: &[u64], index: usize) -> bool {
    let word = index / 64;
    let bit = index % 64;
    (words[word] & (1u64 << bit)) != 0
}

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

    #[test]
    fn matches_bfs_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 candidate = BidirectionalBitParallelWavefront
            .search(&grid, request)
            .expect("endpoints are walkable");
        let bfs = Bfs.search(&grid, request).expect("endpoints are walkable");

        assert!(candidate.is_found());
        assert_eq!(candidate.cost(), bfs.cost());
        assert_eq!(candidate.cost(), Some(8));
    }

    #[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 = BidirectionalBitParallelWavefront
            .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(6, 1).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(5, 0))
            .with_budget(SearchBudget::max_expansions(2));
        let error = BidirectionalBitParallelWavefront
            .search(&grid, request)
            .expect_err("budget should exhaust on a long corridor");
        assert_eq!(
            error,
            GridSearchError::BudgetExhausted(BudgetExhausted::Expansions {
                limit: 2,
                expansions: 2
            })
        );
    }

    #[test]
    fn rejects_diagonal_adjacency_and_bit_leakage() {
        // Only diagonal walkable cells between start and goal: four-connected
        // search must report no path (packing must not bridge diagonals).
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        for point in [
            Point::new(1, 0),
            Point::new(0, 1),
            Point::new(2, 1),
            Point::new(1, 2),
        ] {
            grid.set_cell(point, Cell::Blocked)
                .expect("valid grid edit");
        }
        // Start (0,0) and goal (2,2) are walkable; only diagonal steps exist.
        let result = BidirectionalBitParallelWavefront
            .search(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");
        assert!(
            !result.is_found(),
            "diagonal-only adjacency must not become a path via packing"
        );
    }

    #[test]
    fn partial_meeting_is_not_a_path() {
        // Disconnected components: start-side packing must not fabricate a meet.
        let mut grid = Grid::new(4, 1).expect("grid dimensions are valid");
        grid.set_cell(Point::new(1, 0), Cell::Blocked)
            .expect("valid grid edit");
        grid.set_cell(Point::new(2, 0), Cell::Blocked)
            .expect("valid grid edit");

        let result = BidirectionalBitParallelWavefront
            .search(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(3, 0)),
            )
            .expect("endpoints are walkable");
        assert!(!result.is_found());
    }

    #[test]
    fn connected_path_steps_are_four_connected_neighbors() {
        // Connected open field — search must run (not early is_reachable bail)
        // and every consecutive step must be a real neighbors4 edge.
        let grid = Grid::new(8, 8).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(7, 7));
        let candidate = BidirectionalBitParallelWavefront
            .search(&grid, request)
            .expect("endpoints are walkable");
        let bfs = Bfs.search(&grid, request).expect("endpoints are walkable");
        assert!(candidate.is_found());
        assert_eq!(candidate.cost(), bfs.cost());

        let path = candidate.path().expect("found path");
        let steps = path.steps();
        assert!(steps.len() >= 2);
        for window in steps.windows(2) {
            let a = window[0];
            let b = window[1];
            let neighbors = grid.neighbors4(a);
            assert!(
                neighbors.contains(&b),
                "path edge {a:?}->{b:?} must be 4-connected (no diagonal invent)"
            );
        }
    }

    #[test]
    fn word_boundary_indices_do_not_invent_row_wrap_edges() {
        // Width 65 so indices 63 and 64 sit on a u64 word seam but are not
        // 4-neighbors on a row wrap. Path from (63,0) to (0,1) must not jump via
        // bit adjacency; only true neighbors4 may appear.
        let grid = Grid::new(65, 2).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(63, 0), Point::new(0, 1));
        let candidate = BidirectionalBitParallelWavefront
            .search(&grid, request)
            .expect("endpoints are walkable");
        assert!(candidate.is_found());
        let path = candidate.path().expect("found");
        for window in path.steps().windows(2) {
            let a = window[0];
            let b = window[1];
            let neighbors = grid.neighbors4(a);
            assert!(
                neighbors.contains(&b),
                "word-boundary packing must not create {a:?}->{b:?}"
            );
        }
        // Cost must still match BFS hop count.
        let bfs = Bfs.search(&grid, request).expect("walkable");
        assert_eq!(candidate.cost(), bfs.cost());
    }

    #[test]
    fn retains_candidate_id() {
        assert_eq!(
            BidirectionalBitParallelWavefront::CANDIDATE_ID,
            "static-unweighted-grid/bit-parallel-bidirectional-wavefront"
        );
    }
}