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 {
other
.priority
.partial_cmp(&self.priority)
.unwrap_or(Ordering::Equal)
}
}
#[derive(Debug, Default)]
pub struct BinaryHeapQueue<P: PartialOrd, T> {
inner: BinaryHeap<Entry<P, T>>,
}
impl<P: PartialOrd, T> BinaryHeapQueue<P, T> {
pub fn new() -> Self {
Self {
inner: BinaryHeap::new(),
}
}
#[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");
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();
for i in 0..5 {
queue.push(100, i);
}
let mut results = vec![];
while let Some((pri, val)) = queue.pop() {
assert_eq!(pri, 100);
results.push(val);
}
assert_eq!(results.len(), 5);
}
}