rollup merge of #17355 : gamazeps/issue17210

[rust.git] / src / libcollections / priority_queue.rs

diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
index 28283cdbc51097d089b88871486d20f9d3272170..68e2086d042a36e45789949d7c10c096bf79ab3c 100644 (file)
--- a/src/libcollections/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
@@ -10,6 +10,11 @@
 
 //! A priority queue implemented with a binary heap.
 //!
+//! Insertions have `O(log n)` time complexity and checking or popping the largest element is
+//! `O(1)`. Converting a vector to a priority queue can be done in-place, and has `O(n)`
+//! complexity. A priority queue can also be converted to a sorted vector in-place, allowing it to
+//! be used for an `O(n log n)` in-place heapsort.
+//!
 //! # Example
 //!
 //! This is a larger example which implements [Dijkstra's algorithm][dijkstra]
@@ -167,12 +172,12 @@ pub struct PriorityQueue<T> {
 }
 
 impl<T: Ord> Collection for PriorityQueue<T> {
-    /// Returns the length of the queue
+    /// Returns the length of the queue.
     fn len(&self) -> uint { self.data.len() }
 }
 
 impl<T: Ord> Mutable for PriorityQueue<T> {
-    /// Drop all items from the queue
+    /// Drops all items from the queue.
     fn clear(&mut self) { self.data.truncate(0) }
 }
 
@@ -182,7 +187,7 @@ fn default() -> PriorityQueue<T> { PriorityQueue::new() }
 }
 
 impl<T: Ord> PriorityQueue<T> {
-    /// Create an empty PriorityQueue as a max-heap.
+    /// Creates an empty `PriorityQueue` as a max-heap.
     ///
     /// # Example
     ///
@@ -192,9 +197,9 @@ impl<T: Ord> PriorityQueue<T> {
     /// ```
     pub fn new() -> PriorityQueue<T> { PriorityQueue{data: vec!(),} }
 
-    /// Create an empty PriorityQueue with a specific capacity.
+    /// Creates an empty `PriorityQueue` with a specific capacity.
     /// This preallocates enough memory for `capacity` elements,
-    /// so that the PriorityQueue does not have to be reallocated
+    /// so that the `PriorityQueue` does not have to be reallocated
     /// until it contains at least that many values.
     ///
     /// # Example
@@ -207,7 +212,7 @@ pub fn with_capacity(capacity: uint) -> PriorityQueue<T> {
         PriorityQueue { data: Vec::with_capacity(capacity) }
     }
 
-    /// Create a PriorityQueue from a vector. This is sometimes called
+    /// Creates a `PriorityQueue` from a vector. This is sometimes called
     /// `heapifying` the vector.
     ///
     /// # Example
@@ -244,7 +249,7 @@ pub fn iter<'a>(&'a self) -> Items<'a, T> {
         Items { iter: self.data.iter() }
     }
 
-    /// Returns the greatest item in a queue or `None` if it is empty.
+    /// Returns the greatest item in a queue, or `None` if it is empty.
     ///
     /// # Example
     ///
@@ -279,7 +284,7 @@ pub fn maybe_top<'a>(&'a self) -> Option<&'a T> { self.top() }
     /// ```
     pub fn capacity(&self) -> uint { self.data.capacity() }
 
-    /// Reserve capacity for exactly `n` elements in the PriorityQueue.
+    /// Reserves capacity for exactly `n` elements in the `PriorityQueue`.
     /// Do nothing if the capacity is already sufficient.
     ///
     /// # Example
@@ -293,7 +298,7 @@ pub fn capacity(&self) -> uint { self.data.capacity() }
     /// ```
     pub fn reserve_exact(&mut self, n: uint) { self.data.reserve_exact(n) }
 
-    /// Reserve capacity for at least `n` elements in the PriorityQueue.
+    /// Reserves capacity for at least `n` elements in the `PriorityQueue`.
     /// Do nothing if the capacity is already sufficient.
     ///
     /// # Example
@@ -309,8 +314,8 @@ pub fn reserve(&mut self, n: uint) {
         self.data.reserve(n)
     }
 
-    /// Remove the greatest item from a queue and return it, or `None` if it is
-    /// empty.
+    /// Removes the greatest item from a queue and returns it, or `None` if it
+    /// is empty.
     ///
     /// # Example
     ///
@@ -339,7 +344,7 @@ pub fn pop(&mut self) -> Option<T> {
     #[deprecated="renamed to `pop`"]
     pub fn maybe_pop(&mut self) -> Option<T> { self.pop() }
 
-    /// Push an item onto the queue.
+    /// Pushes an item onto the queue.
     ///
     /// # Example
     ///
@@ -360,7 +365,8 @@ pub fn push(&mut self, item: T) {
         self.siftup(0, new_len);
     }
 
-    /// Optimized version of a push followed by a pop.
+    /// Pushes an item onto a queue then pops the greatest item off the queue in
+    /// an optimized fashion.
     ///
     /// # Example
     ///
@@ -384,8 +390,9 @@ pub fn push_pop(&mut self, mut item: T) -> T {
         item
     }
 
-    /// Optimized version of a pop followed by a push. The push is done
-    /// regardless of whether the queue is empty.
+    /// Pops the greatest item off a queue then pushes an item onto the queue in
+    /// an optimized fashion. The push is done regardless of whether the queue
+    /// was empty.
     ///
     /// # Example
     ///
@@ -418,7 +425,7 @@ fn to_vec(self) -> Vec<T> { self.into_vec() }
     #[deprecated="renamed to `into_sorted_vec`"]
     fn to_sorted_vec(self) -> Vec<T> { self.into_sorted_vec() }
 
-    /// Consume the PriorityQueue and return the underlying vector
+    /// Consumes the `PriorityQueue` and returns the underlying vector
     /// in arbitrary order.
     ///
     /// # Example
@@ -436,7 +443,7 @@ fn to_sorted_vec(self) -> Vec<T> { self.into_sorted_vec() }
     /// ```
     pub fn into_vec(self) -> Vec<T> { let PriorityQueue{data: v} = self; v }
 
-    /// Consume the PriorityQueue and return a vector in sorted
+    /// Consumes the `PriorityQueue` and returns a vector in sorted
     /// (ascending) order.
     ///
     /// # Example
@@ -513,8 +520,8 @@ fn siftdown(&mut self, pos: uint) {
     }
 }
 
-/// PriorityQueue iterator.
-pub struct Items <'a, T> {
+/// `PriorityQueue` iterator.
+pub struct Items <'a, T:'a> {
     iter: slice::Items<'a, T>,
 }