+//! A priority queue implemented with a 4-ary heap.
+//!
+//! Insertion and popping the minimal element have `O(log n)` time complexity.
+//! Checking the minimal element is `O(1)`. Keys of elements in the heap can
+//! also be increased or decreased
+//!
+//! # Examples
+//!
+//! ```
+//! use stud_rust_base::index_heap::{Indexing, IndexdMinHeap};
+//!
+//! #[derive(Copy, Clone, Eq, PartialEq, Debug, Ord, PartialOrd)]
+//! pub struct State {
+//! pub distance: usize,
+//! pub node: usize,
+//! }
+//!
+//!
+//! // The `Indexing` traits needs to be implemented as well, so we can find elements to decrease their key.
+//! impl Indexing for State {
+//! fn as_index(&self) -> usize {
+//! self.node as usize
+//! }
+//! }
+//!
+//! let mut heap = IndexdMinHeap::new(3);
+//! heap.push(State { node: 0, distance: 42 });
+//! heap.push(State { node: 1, distance: 23 });
+//! heap.push(State { node: 2, distance: 50000 });
+//! assert_eq!(heap.peek().cloned(), Some(State { node: 1, distance: 23 }));
+//! heap.decrease_key(State { node: 0, distance: 1 });
+//! assert_eq!(heap.pop(), Some(State { node: 0, distance: 1 }));
+//!
+//! ```
+
use std;
use std::cmp::min;
use std::mem::swap;
use std::ptr;
+/// A trait to map elements in a heap to a unique index.
+/// The element type of the `IndexdMinHeap` has to implement this trait.
pub trait Indexing {
+ /// This method has to map a heap element to a unique `usize` index.
fn as_index(&self) -> usize;
}
-// A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
-// The elements are sorted by integer keys.
+/// A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
+/// The elements are sorted ascending by the ordering defined by the `Ord` trait.
+/// The interface mirros the standard library BinaryHeap (except for the reversed order).
+/// Only the methods necessary for dijkstras algorithm are implemented.
+/// In addition, `increase_key` and `decrease_key` methods are available.
#[derive(Debug)]
pub struct IndexdMinHeap<T: Ord + Indexing> {
positions: Vec<usize>,
- data: Vec<T>
+ data: Vec<T>,
}
const TREE_ARITY: usize = 4;
const INVALID_POSITION: usize = std::usize::MAX;
impl<T: Ord + Indexing> IndexdMinHeap<T> {
- #[allow(dead_code)]
- pub fn new(max_id: usize) -> IndexdMinHeap<T> {
+ /// Creates an empty `IndexdMinHeap` as a min-heap.
+ /// The indices (as defined by the `Indexing` trait) of all inserted elements
+ /// will have to be between in `[0, max_index)`
+ pub fn new(max_index: usize) -> IndexdMinHeap<T> {
IndexdMinHeap {
- positions: vec![INVALID_POSITION; max_id],
- data: Vec::new()
+ positions: vec![INVALID_POSITION; max_index],
+ data: Vec::new(),
}
}
+ /// Returns the length of the binary heap.
pub fn len(&self) -> usize {
self.data.len()
}
+ /// Checks if the binary heap is empty.
pub fn is_empty(&self) -> bool {
self.len() == 0
}
- #[allow(dead_code)]
+ /// Checks if the heap already contains an element mapped to the given index
pub fn contains_index(&self, id: usize) -> bool {
self.positions[id] != INVALID_POSITION
}
- #[allow(dead_code)]
+ /// Drops all items from the heap.
pub fn clear(&mut self) {
for element in &self.data {
self.positions[element.as_index()] = INVALID_POSITION;
self.data.clear();
}
- #[allow(dead_code)]
+ /// Returns a reference to the smallest item in the heap, or None if it is empty.
pub fn peek(&self) -> Option<&T> {
self.data.first()
}
- #[allow(dead_code)]
+ /// Removes the greatest item from the binary heap and returns it, or None if it is empty.
pub fn pop(&mut self) -> Option<T> {
self.data.pop().map(|mut item| {
self.positions[item.as_index()] = INVALID_POSITION;
})
}
- #[allow(dead_code)]
+ /// Pushes an item onto the binary heap.
+ /// Panics if an element with the same index already exists.
pub fn push(&mut self, element: T) {
assert!(!self.contains_index(element.as_index()));
let insert_position = self.len();
self.move_up_in_tree(insert_position);
}
- // Updates the key of an element if the new key is smaller than the old key.
- // Does nothing if the new key is larger.
- // Undefined if the element is not part of the queue.
- #[allow(dead_code)]
+ /// Updates the key of an element if the new key is smaller than the old key.
+ /// Does nothing if the new key is larger.
+ /// Panics if the element is not part of the queue.
pub fn decrease_key(&mut self, element: T) {
let position = self.positions[element.as_index()];
self.data[position] = element;
self.move_up_in_tree(position);
}
- // Updates the key of an element if the new key is larger than the old key.
- // Does nothing if the new key is smaller.
- // Undefined if the element is not part of the queue.
- #[allow(dead_code)]
+ /// Updates the key of an element if the new key is larger than the old key.
+ /// Does nothing if the new key is smaller.
+ /// Panics if the element is not part of the queue.
pub fn increase_key(&mut self, element: T) {
let position = self.positions[element.as_index()];
self.data[position] = element;
let mut hole = Hole::new(&mut self.data, position);
loop {
- if let Some(smallest_child) = IndexdMinHeap::<T>::children_index_range(position, heap_size).min_by_key(|&child_index| hole.get(child_index)) {
+ if let Some(smallest_child) =
+ IndexdMinHeap::<T>::children_index_range(position, heap_size)
+ .min_by_key(|&child_index| hole.get(child_index))
+ {
if hole.get(smallest_child) >= hole.element() {
self.positions[hole.element().as_index()] = position;
return; // no child is smaller
}
}
-
// This is an optimization copied straight from the rust stdlib binary heap
// it allows to avoid always swapping elements pairwise and rather
// move each element only once.
-
/// Hole represents a hole in a slice i.e. an index without valid value
/// (because it was moved from or duplicated).
/// In drop, `Hole` will restore the slice by filling the hole
projects / Mitarbeiter / Tim-Zeitz / stud-rust-base.git / blobdiff