X-Git-Url: https://i11git.iti.kit.edu/anon-gitweb/?p=Mitarbeiter%2FTim-Zeitz%2Fstud-rust-base.git;a=blobdiff_plain;f=src%2Findex_heap.rs;h=477dc879cf610d95dd8c2658bde1a3227a257cf1;hp=2f608d9d24760f339de13ea536d3b729cf1ca28f;hb=HEAD;hpb=dd14e61875eedc443d6004db819562a9b7f98a14;ds=sidebyside diff --git a/src/index_heap.rs b/src/index_heap.rs index 2f608d9..2c6f613 100644 --- a/src/index_heap.rs +++ b/src/index_heap.rs @@ -1,46 +1,91 @@ +//! 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 { positions: Vec, - data: Vec + data: Vec, } const TREE_ARITY: usize = 4; const INVALID_POSITION: usize = std::usize::MAX; impl IndexdMinHeap { - #[allow(dead_code)] - pub fn new(max_id: usize) -> IndexdMinHeap { + /// 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 { 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; @@ -48,12 +93,12 @@ impl IndexdMinHeap { 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 { self.data.pop().map(|mut item| { self.positions[item.as_index()] = INVALID_POSITION; @@ -67,7 +112,8 @@ impl IndexdMinHeap { }) } - #[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(); @@ -76,22 +122,20 @@ impl IndexdMinHeap { 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. + /// Panics if the element is not part of the queue or if the new key is larger. pub fn decrease_key(&mut self, element: T) { let position = self.positions[element.as_index()]; + assert!(element <= self.data[position]); 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. + /// Panics if the element is not part of the queue or if the new key is smaller. pub fn increase_key(&mut self, element: T) { let position = self.positions[element.as_index()]; + assert!(element >= self.data[position]); self.data[position] = element; self.move_down_in_tree(position); } @@ -148,12 +192,10 @@ impl IndexdMinHeap { } } - // 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 @@ -173,11 +215,7 @@ impl<'a, T> Hole<'a, T> { unsafe fn new(data: &'a mut [T], pos: usize) -> Self { debug_assert!(pos < data.len()); let elt = ptr::read(&data[pos]); - Hole { - data, - elt: Some(elt), - pos, - } + Hole { data, elt: Some(elt), pos } } /// Returns a reference to the element removed.