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=a7af9ca1d84892a390a6342c859be9a3a0bbd3c8;hb=HEAD;hpb=b52fc015957bcfa65d2e8fbb8d4ea44f4923e3a8

diff --git a/src/index_heap.rs b/src/index_heap.rs
index a7af9ca..2c6f613 100644
--- a/src/index_heap.rs
+++ b/src/index_heap.rs
@@ -23,15 +23,13 @@
 //!     }
 //! }
 //!
-//! fn main() {
-//!     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 }));
-//! }
+//! 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 }));
 //!
 //! ```
 
@@ -55,7 +53,7 @@ pub trait Indexing {
 #[derive(Debug)]
 pub struct IndexdMinHeap<T: Ord + Indexing> {
     positions: Vec<usize>,
-    data: Vec<T>
+    data: Vec<T>,
 }
 
 const TREE_ARITY: usize = 4;
@@ -68,7 +66,7 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
     pub fn new(max_index: usize) -> IndexdMinHeap<T> {
         IndexdMinHeap {
             positions: vec![INVALID_POSITION; max_index],
-            data: Vec::new()
+            data: Vec::new(),
         }
     }
 
@@ -125,19 +123,19 @@ impl<T: Ord + Indexing> IndexdMinHeap<T> {
     }
 
     /// 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.
+    /// 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.
-    /// Panics if the element is not part of the queue.
+    /// 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);
     }
@@ -194,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.
 
-
 /// 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
@@ -219,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.