updates, clippy, formatting

[Mitarbeiter/Tim-Zeitz/stud-rust-base.git] / src / index_heap.rs

diff --git a/src/index_heap.rs b/src/index_heap.rs
index c086dc31f158e71a4f8f9d292595a58f00e54d49..2c6f61397984a7719e9d3156440d3ea28adbee7a 100644 (file)
--- a/src/index_heap.rs
+++ b/src/index_heap.rs
@@ -1,43 +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;
 
 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 {
 pub trait Indexing {

+    /// This method has to map a heap element to a unique `usize` index.

     fn as_index(&self) -> usize;
 }
 
     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>,
 #[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> {
 }
 
 const TREE_ARITY: usize = 4;
 const INVALID_POSITION: usize = std::usize::MAX;
 
 impl<T: Ord + Indexing> IndexdMinHeap<T> {

-    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 {
         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()
     }
 
     pub fn len(&self) -> usize {
         self.data.len()
     }
 

+    /// Checks if the binary heap is empty.

     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
 
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
 

+    /// 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
     }
 
     pub fn contains_index(&self, id: usize) -> bool {
         self.positions[id] != INVALID_POSITION
     }
 

+    /// Drops all items from the heap.

     pub fn clear(&mut self) {
         for element in &self.data {
             self.positions[element.as_index()] = INVALID_POSITION;
     pub fn clear(&mut self) {
         for element in &self.data {
             self.positions[element.as_index()] = INVALID_POSITION;


@@ -45,10 +93,12 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
         self.data.clear();
     }
 
         self.data.clear();
     }
 

+    /// 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()
     }
 
     pub fn peek(&self) -> Option<&T> {
         self.data.first()
     }
 

+    /// 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;
     pub fn pop(&mut self) -> Option<T> {
         self.data.pop().map(|mut item| {
             self.positions[item.as_index()] = INVALID_POSITION;


@@ -62,6 +112,8 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
         })
     }
 
         })
     }
 

+    /// 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();
     pub fn push(&mut self, element: T) {
         assert!(!self.contains_index(element.as_index()));
         let insert_position = self.len();


@@ -70,20 +122,20 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
         self.move_up_in_tree(insert_position);
     }
 
         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.
+    /// 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()];
     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);
     }
 
         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.
+    /// 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()];
     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);
     }
         self.data[position] = element;
         self.move_down_in_tree(position);
     }


@@ -140,12 +192,10 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
     }
 }
 
     }
 }
 

-

 // 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.
 
 // 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
 /// 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


@@ -165,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]);
     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.
     }
 
     /// Returns a reference to the element removed.