dijkstra3d-core 0.1.0

Voxel-grid Dijkstra and rolling-ball invalidation, ported from seung-lab/dijkstra3d and seung-lab/kimimaro
Documentation
//! Bucket-queue priority queue (Dial's algorithm) for bounded-integer weights.

/// Monotone bucket (Dial) priority queue with `u64` priorities and `u32`
/// payloads.
/// # Usage contract
/// - Priorities passed to [`push`](Self::push) must be non-decreasing relative
///   to the last popped priority (i.e. `priority >= cursor`), and within
///   `max_edge_weight` of the current cursor. Dijkstra relaxation satisfies this
///   automatically. Violating it corrupts ordering.
#[derive(Debug)]
pub struct BucketQueue {
    /// Ring of buckets; `buckets[p % ring_len]` holds payloads with priority `p`.
    buckets: Vec<Vec<u32>>,

    ring_len: u64,

    cursor: u64,

    len: usize,
}

impl BucketQueue {
    /// Construct a queue sized for priorities whose *increments* are bounded by
    /// `max_edge_weight`. The ring holds `max_edge_weight + 1` buckets.
    pub fn with_capacity(max_edge_weight: u32) -> Self {
        let ring_len = max_edge_weight as u64 + 1;
        let mut buckets = Vec::with_capacity(ring_len as usize);
        buckets.resize_with(ring_len as usize, Vec::new);
        Self {
            buckets,
            ring_len,
            cursor: 0,
            len: 0,
        }
    }

    /// Push `payload` with the given `priority`.
    #[inline]
    pub fn push(&mut self, priority: u64, payload: u32) {
        let idx = (priority % self.ring_len) as usize;
        self.buckets[idx].push(payload);
        self.len += 1;
    }

    /// Pop the entry with the smallest priority, or `None` if empty.
    #[inline]
    pub fn pop(&mut self) -> Option<(u64, u32)> {
        if self.len == 0 {
            return None;
        }
        // len > 0 guarantees a live entry exists within one ring window, so this
        // loop terminates in at most `ring_len` iterations.
        loop {
            let idx = (self.cursor % self.ring_len) as usize;
            if let Some(payload) = self.buckets[idx].pop() {
                self.len -= 1;
                return Some((self.cursor, payload));
            }
            self.cursor += 1;
        }
    }

    #[inline]
    pub fn peek_key(&mut self) -> Option<u64> {
        if self.len == 0 {
            return None;
        }
        loop {
            let idx = (self.cursor % self.ring_len) as usize;
            if !self.buckets[idx].is_empty() {
                return Some(self.cursor);
            }
            self.cursor += 1;
        }
    }

    #[inline]
    pub fn reset(&mut self) {
        for b in &mut self.buckets {
            b.clear();
        }
        self.cursor = 0;
        self.len = 0;
    }

    /// Whether the queue holds no live entries. O(1).
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Number of live entries.
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }
}

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

    #[test]
    fn empty_pop_returns_none() {
        let mut q = BucketQueue::with_capacity(4);
        assert!(q.is_empty());
        assert_eq!(q.pop(), None);
    }

    #[test]
    fn single_element_roundtrip() {
        let mut q = BucketQueue::with_capacity(4);
        q.push(3, 42);
        assert!(!q.is_empty());
        assert_eq!(q.len(), 1);
        assert_eq!(q.pop(), Some((3, 42)));
        assert!(q.is_empty());
        assert_eq!(q.pop(), None);
    }

    #[test]
    fn ordering_ascending_priorities() {
        // max increment 5; push in scrambled order within a window.
        let mut q = BucketQueue::with_capacity(5);
        q.push(2, 20);
        q.push(0, 0);
        q.push(5, 50);
        q.push(1, 10);
        q.push(3, 30);

        let mut got = Vec::new();
        while let Some((p, v)) = q.pop() {
            got.push((p, v));
        }
        assert_eq!(got, vec![(0, 0), (1, 10), (2, 20), (3, 30), (5, 50)]);
    }

    #[test]
    fn duplicates_same_priority_all_returned() {
        let mut q = BucketQueue::with_capacity(3);
        for i in 0..5u32 {
            q.push(2, i);
        }
        assert_eq!(q.len(), 5);
        let mut vals = Vec::new();
        while let Some((p, v)) = q.pop() {
            assert_eq!(p, 2);
            vals.push(v);
        }
        vals.sort_unstable();
        assert_eq!(vals, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn monotone_pops_are_non_decreasing() {
        // Simulate Dijkstra-style usage: after popping p, push p + w with
        // 0 <= w <= max_edge_weight, keeping the live window bounded.
        let max_w = 4u32;
        let mut q = BucketQueue::with_capacity(max_w);
        q.push(0, 1000);
        let mut last = 0u64;
        let mut count = 0;
        while let Some((p, _payload)) = q.pop() {
            assert!(p >= last, "pop priority {p} < previous {last}");
            last = p;
            count += 1;
            // Relax a few "edges" with weights in [0, max_w].
            if count < 50 {
                for w in [0u64, 1, 3, max_w as u64] {
                    q.push(p + w, count as u32);
                }
            }
        }
        assert!(count >= 50);
    }

    #[test]
    fn wraparound_across_ring() {
        // ring_len = 3. Walk the cursor far past ring_len so residues wrap.
        let mut q = BucketQueue::with_capacity(2);
        q.push(0, 0);
        let mut expected = 0u64;
        while let Some((p, _)) = q.pop() {
            assert_eq!(p, expected);
            // Chain forward by +2 (== max_edge_weight) to force wraparound.
            if expected < 20 {
                expected += 2;
                q.push(expected, expected as u32);
            } else {
                break;
            }
        }
        assert_eq!(expected, 20);
    }

    #[test]
    fn interleaved_push_pop_within_window() {
        let mut q = BucketQueue::with_capacity(3);
        q.push(1, 1);
        q.push(2, 2);
        assert_eq!(q.pop(), Some((1, 1)));
        // Push within [cursor=1, cursor+3]
        q.push(4, 4);
        q.push(3, 3);
        assert_eq!(q.pop(), Some((2, 2)));
        assert_eq!(q.pop(), Some((3, 3)));
        assert_eq!(q.pop(), Some((4, 4)));
        assert_eq!(q.pop(), None);
    }

    #[test]
    fn zero_max_weight_all_same_priority() {
        // ring_len = 1: every entry has priority 0.
        let mut q = BucketQueue::with_capacity(0);
        q.push(0, 7);
        q.push(0, 8);
        q.push(0, 9);
        let mut vals = Vec::new();
        while let Some((p, v)) = q.pop() {
            assert_eq!(p, 0);
            vals.push(v);
        }
        vals.sort_unstable();
        assert_eq!(vals, vec![7, 8, 9]);
    }
}