extern crate alloc;
use alloc::boxed::Box;
use core::fmt;
use crate::fixedvec::FixedVec;
pub struct FibonacciHeap<T, const MAX_TREES: usize = 64> {
trees: FixedVec<Option<Box<Node<T>>>, MAX_TREES>,
min_index: Option<usize>,
size: usize,
}
struct Node<T> {
key: T,
marked: bool,
}
impl<T> Node<T> {
fn new(key: T) -> Self {
Node { key, marked: false }
}
}
impl<T: Ord, const MAX_TREES: usize> FibonacciHeap<T, MAX_TREES> {
pub const fn new() -> Self {
Self {
trees: FixedVec::new(),
min_index: None,
size: 0,
}
}
#[inline]
pub const fn len(&self) -> usize {
self.size
}
#[inline]
pub const fn is_empty(&self) -> bool {
self.size == 0
}
pub fn peek(&self) -> Option<&T> {
self.min_index
.and_then(|idx| self.trees.get(idx))
.and_then(|tree| tree.as_ref())
.map(|node| &node.key)
}
pub fn push(&mut self, key: T) -> Result<(), FibonacciHeapError> {
let new_node = Box::new(Node::new(key));
let insert_index = self.find_empty_slot()?;
let is_new_min = match self.min_index {
None => true,
Some(min_idx) => {
if let Some(Some(min_node)) = self.trees.get(min_idx) {
new_node.key < min_node.key
} else {
true
}
}
};
while insert_index >= self.trees.len() {
self.trees
.push(None)
.map_err(|_| FibonacciHeapError::Full)?;
}
self.trees[insert_index] = Some(new_node);
self.size += 1;
if is_new_min {
self.min_index = Some(insert_index);
}
Ok(())
}
pub fn pop(&mut self) -> Result<T, FibonacciHeapError> {
let min_idx = self.min_index.ok_or(FibonacciHeapError::Empty)?;
let min_node = self.trees[min_idx]
.take()
.ok_or(FibonacciHeapError::Empty)?;
let min_key = min_node.key;
self.size -= 1;
if self.size == 0 {
self.min_index = None;
self.trees.clear();
} else {
self.update_min();
}
Ok(min_key)
}
pub fn merge(&mut self, mut other: Self) -> Result<(), FibonacciHeapError> {
if other.is_empty() {
return Ok(());
}
if self.is_empty() {
*self = other;
return Ok(());
}
for tree in other.trees.iter_mut() {
if let Some(node) = tree.take() {
let insert_index = self.find_empty_slot()?;
while insert_index >= self.trees.len() {
self.trees
.push(None)
.map_err(|_| FibonacciHeapError::Full)?;
}
self.trees[insert_index] = Some(node);
}
}
self.size += other.size;
self.update_min();
Ok(())
}
fn find_empty_slot(&self) -> Result<usize, FibonacciHeapError> {
for (i, tree) in self.trees.iter().enumerate() {
if tree.is_none() {
return Ok(i);
}
}
if self.trees.len() < MAX_TREES {
Ok(self.trees.len())
} else {
Err(FibonacciHeapError::Full)
}
}
fn update_min(&mut self) {
self.min_index = None;
for (i, tree) in self.trees.iter().enumerate() {
if let Some(node) = tree {
match self.min_index {
None => self.min_index = Some(i),
Some(current_min) => {
if let Some(Some(min_node)) = self.trees.get(current_min) {
if node.key < min_node.key {
self.min_index = Some(i);
}
}
}
}
}
}
}
}
impl<T: Ord, const MAX_TREES: usize> Default for FibonacciHeap<T, MAX_TREES> {
fn default() -> Self {
Self::new()
}
}
impl<T: fmt::Debug + Ord, const MAX_TREES: usize> fmt::Debug for FibonacciHeap<T, MAX_TREES> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("FibonacciHeap")
.field("len", &self.size)
.field("min", &self.peek())
.finish()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum FibonacciHeapError {
Empty,
Full,
}
#[cfg(test)]
mod tests {
use crate::fixedvec;
use super::*;
use alloc::string::String;
#[test]
fn test_new_heap() {
let heap: FibonacciHeap<i32, 64> = FibonacciHeap::new();
assert_eq!(heap.len(), 0);
assert!(heap.is_empty());
assert!(heap.peek().is_none());
}
#[test]
fn test_push_peek() {
let mut heap: FibonacciHeap<i32, 64> = FibonacciHeap::new();
heap.push(5).unwrap();
assert_eq!(heap.len(), 1);
assert!(!heap.is_empty());
assert_eq!(heap.peek(), Some(&5));
heap.push(3).unwrap();
assert_eq!(heap.len(), 2);
assert_eq!(heap.peek(), Some(&3));
heap.push(7).unwrap();
assert_eq!(heap.len(), 3);
assert_eq!(heap.peek(), Some(&3));
}
#[test]
fn test_pop() {
let mut heap: FibonacciHeap<i32, 64> = FibonacciHeap::new();
assert_eq!(heap.pop(), Err(FibonacciHeapError::Empty));
heap.push(5).unwrap();
heap.push(3).unwrap();
heap.push(7).unwrap();
heap.push(1).unwrap();
assert_eq!(heap.pop().unwrap(), 1);
assert_eq!(heap.len(), 3);
assert_eq!(heap.peek(), Some(&3));
assert_eq!(heap.pop().unwrap(), 3);
assert_eq!(heap.pop().unwrap(), 5);
assert_eq!(heap.pop().unwrap(), 7);
assert!(heap.is_empty());
assert_eq!(heap.pop(), Err(FibonacciHeapError::Empty));
}
#[test]
fn test_heap_property() {
let mut heap: FibonacciHeap<i32, 64> = FibonacciHeap::new();
let values: FixedVec<i32, 16> = fixedvec![15, 3, 17, 8, 12, 9, 6, 1, 4, 11];
for &val in values.iter() {
heap.push(val).unwrap();
}
let mut sorted: FixedVec<i32, 16> = FixedVec::new();
while !heap.is_empty() {
sorted.push(heap.pop().unwrap()).unwrap();
}
let expected: FixedVec<i32, 16> = fixedvec![1, 3, 4, 6, 8, 9, 11, 12, 15, 17];
assert_eq!(sorted.as_slice(), expected.as_slice());
}
#[test]
fn test_merge() {
let mut heap1: FibonacciHeap<i32, 64> = FibonacciHeap::new();
let mut heap2: FibonacciHeap<i32, 64> = FibonacciHeap::new();
heap1.push(5).unwrap();
heap1.push(3).unwrap();
heap2.push(7).unwrap();
heap2.push(1).unwrap();
heap1.merge(heap2).unwrap();
assert_eq!(heap1.len(), 4);
assert_eq!(heap1.peek(), Some(&1));
let mut result: FixedVec<i32, 8> = FixedVec::new();
while !heap1.is_empty() {
result.push(heap1.pop().unwrap()).unwrap();
}
let expected: FixedVec<i32, 8> = fixedvec![1, 3, 5, 7];
assert_eq!(result.as_slice(), expected.as_slice());
}
#[test]
fn test_merge_empty() {
let mut heap1: FibonacciHeap<i32, 64> = FibonacciHeap::new();
let heap2: FibonacciHeap<i32, 64> = FibonacciHeap::new();
heap1.push(5).unwrap();
heap1.merge(heap2).unwrap();
assert_eq!(heap1.len(), 1);
assert_eq!(heap1.peek(), Some(&5));
let mut heap3: FibonacciHeap<i32, 64> = FibonacciHeap::new();
heap3.merge(heap1).unwrap();
assert_eq!(heap3.len(), 1);
assert_eq!(heap3.peek(), Some(&5));
}
#[test]
fn test_large_heap() {
let mut heap: FibonacciHeap<usize, 64> = FibonacciHeap::new();
let n = 50;
for i in (0..n).rev() {
heap.push(i).unwrap();
}
assert_eq!(heap.len(), n);
assert_eq!(heap.peek(), Some(&0));
for i in 0..n {
assert_eq!(heap.pop().unwrap(), i);
}
assert!(heap.is_empty());
}
#[test]
fn test_with_strings() {
let mut heap: FibonacciHeap<String, 64> = FibonacciHeap::new();
heap.push(String::from("zebra")).unwrap();
heap.push(String::from("apple")).unwrap();
heap.push(String::from("banana")).unwrap();
assert_eq!(heap.pop().unwrap(), "apple");
assert_eq!(heap.pop().unwrap(), "banana");
assert_eq!(heap.pop().unwrap(), "zebra");
}
}