condor-pathfinding-grid 0.4.0

//! Interval state arena, f-key heap ordering, and generation-based stale detection.
//!
//! [`StateArena`] allocates dense [`StateId`]s; [`HeapEntry`] freezes float interval
//! geometry to integer tie-break fields so max-heap pops remain deterministic across
//! rebuilds. Stale pops are rejected when the arena generation for an id advances.

use std::cmp::Ordering;

use condor_core::Point2;

use super::geometry::{IntervalKind, compare_f64_total};

/// Dense identifier for an allocated interval state.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct StateId(pub u32);

/// One row-interval search state.
#[derive(Debug, Clone, Copy, PartialEq)]
pub(crate) struct IntervalState {
    pub row: i32,
    pub left: f64,
    pub right: f64,
    pub root: Point2,
    pub root_g: f64,
    pub predecessor: Option<StateId>,
    pub kind: IntervalKind,
    pub generation: u32,
}

/// Open-set entry for interval Anya: f-key plus deterministic tie-break coordinates.
///
/// Ordered so a max-heap pops the lowest key first; integer fields freeze float
/// interval geometry for stable comparisons across rebuilds.
#[derive(Debug, Clone, Copy)]
pub struct HeapEntry {
    pub state_id: StateId,
    pub key: f64,
    pub row: i32,
    pub left: i32,
    pub right: i32,
    pub root_x: i32,
    pub root_y: i32,
    pub kind: IntervalKind,
}

impl PartialEq for HeapEntry {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

impl Eq for HeapEntry {}

impl Ord for HeapEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        // `BinaryHeap` is a max-heap; reverse the key so lowest f-values pop first.
        compare_f64_total(other.key, self.key)
            .then_with(|| self.row.cmp(&other.row))
            .then_with(|| self.left.cmp(&other.left))
            .then_with(|| self.right.cmp(&other.right))
            .then_with(|| self.root_x.cmp(&other.root_x))
            .then_with(|| self.root_y.cmp(&other.root_y))
            .then_with(|| self.kind.cmp(&other.kind))
            .then_with(|| other.state_id.0.cmp(&self.state_id.0))
    }
}

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

/// Predecessor arena and generation tracking for stale-pop rejection.
#[derive(Debug, Default)]
pub struct StateArena {
    states: Vec<IntervalState>,
    generations: Vec<u32>,
}

impl StateArena {
    /// Allocates a state and records its generation for later stale-pop checks.
    pub fn push(&mut self, state: IntervalState) -> StateId {
        let id = StateId(self.states.len() as u32);
        self.states.push(state);
        self.generations.push(state.generation);
        id
    }

    /// Returns the state stored at `id`.
    ///
    /// # Panics
    ///
    /// Panics if `id` was not produced by this arena.
    pub fn get(&self, id: StateId) -> &IntervalState {
        &self.states[id.0 as usize]
    }

    /// Generation stamp stored when `id` was allocated (stale-pop filter input).
    ///
    /// # Panics
    ///
    /// Panics if `id` was not produced by this arena.
    pub fn generation(&self, id: StateId) -> u32 {
        self.generations[id.0 as usize]
    }

    /// Approximate retained bytes for diagnostics (arena vectors only).
    pub fn bytes(&self) -> usize {
        self.states.len() * std::mem::size_of::<IntervalState>()
            + self.generations.len() * std::mem::size_of::<u32>()
    }
}

/// Builds a heap entry from interval geometry with integerized coordinates.
pub fn heap_entry_for(state_id: StateId, state: &IntervalState, key: f64) -> HeapEntry {
    HeapEntry {
        state_id,
        key,
        row: state.row,
        left: state.left.round() as i32,
        right: state.right.round() as i32,
        root_x: state.root.x.round() as i32,
        root_y: state.root.y.round() as i32,
        kind: state.kind,
    }
}