dijkstra3d-core 0.1.0

Voxel-grid Dijkstra and rolling-ball invalidation, ported from seung-lab/dijkstra3d and seung-lab/kimimaro
Documentation
//! Binary-heap-backed priority queue (general fallback).

use crate::queue::PriorityQueue;
use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug)]
struct Entry<P, T> {
    priority: P,
    payload: T,
}

impl<P: PartialOrd, T> PartialEq for Entry<P, T> {
    fn eq(&self, other: &Self) -> bool {
        self.priority.partial_cmp(&other.priority) == Some(Ordering::Equal)
    }
}

impl<P: PartialOrd, T> Eq for Entry<P, T> {}

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

impl<P: PartialOrd, T> Ord for Entry<P, T> {
    fn cmp(&self, other: &Self) -> Ordering {
        // Reverse so BinaryHeap (max-heap) behaves as min-heap.
        // Equal priorities intentionally have no payload-based tie-breaker. Callers must
        // not supply unordered priorities such as NaN.
        other
            .priority
            .partial_cmp(&self.priority)
            .unwrap_or(Ordering::Equal)
    }
}

/// Standard binary-heap priority queue.
#[derive(Debug, Default)]
pub struct BinaryHeapQueue<P: PartialOrd, T> {
    inner: BinaryHeap<Entry<P, T>>,
}

impl<P: PartialOrd, T> BinaryHeapQueue<P, T> {
    /// Construct an empty queue.
    pub fn new() -> Self {
        Self {
            inner: BinaryHeap::new(),
        }
    }

    /// Drop all entries, keeping the backing allocation for reuse across
    /// repeated searches (the workspace-reuse engine). A `clear`ed heap and a
    /// freshly `new`ed heap are behaviorally identical for subsequent
    /// push/pop sequences (both start empty), so path outputs are unaffected.
    #[inline]
    pub fn clear(&mut self) {
        self.inner.clear();
    }
}

impl<P, T> PriorityQueue<P, T> for BinaryHeapQueue<P, T>
where
    P: PartialOrd + Copy,
{
    fn push(&mut self, p: P, t: T) {
        self.inner.push(Entry {
            priority: p,
            payload: t,
        });
    }

    fn pop(&mut self) -> Option<(P, T)> {
        self.inner.pop().map(|e| (e.priority, e.payload))
    }

    fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    fn reserve(&mut self, n: usize) {
        self.inner.reserve(n);
    }

    fn peek(&self) -> Option<(P, &T)> {
        self.inner.peek().map(|e| (e.priority, &e.payload))
    }
}

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

    #[test]
    fn test_min_heap_ordering() {
        let mut queue = BinaryHeapQueue::<u32, &str>::new();

        queue.push(10, "ten");
        queue.push(5, "five");
        queue.push(20, "twenty");
        queue.push(5, "five-dup"); // Duplicate priority

        // Should pop in ascending order
        assert_eq!(queue.pop(), Some((5, "five")));
        assert_eq!(queue.pop(), Some((5, "five-dup")));
        assert_eq!(queue.pop(), Some((10, "ten")));
        assert_eq!(queue.pop(), Some((20, "twenty")));
        assert_eq!(queue.pop(), None);
    }

    #[test]
    fn test_equal_priorities_handled() {
        let mut queue = BinaryHeapQueue::<u32, usize>::new();

        // Push multiple entries with same priority
        for i in 0..5 {
            queue.push(100, i);
        }

        // All should be popped (order within same priority is unspecified)
        let mut results = vec![];
        while let Some((pri, val)) = queue.pop() {
            assert_eq!(pri, 100);
            results.push(val);
        }
        assert_eq!(results.len(), 5);
    }
}