#[derive(Debug)]
pub struct BucketQueue {
buckets: Vec<Vec<u32>>,
ring_len: u64,
cursor: u64,
len: usize,
}
impl BucketQueue {
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,
}
}
#[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;
}
#[inline]
pub fn pop(&mut self) -> Option<(u64, u32)> {
if self.len == 0 {
return None;
}
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;
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len == 0
}
#[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() {
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() {
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;
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() {
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);
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)));
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() {
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]);
}
}