priority_queue: implement simple iterator

Remove PriorityQueue::each and replace it with PriorityQueue::iter,
which ultimately calls into vec::VecIterator via PriorityQueueIterator.
Implement iterator::Iterator for PriorityQueueIterator.  Now you should
be able to do:

  extern mod extra;
  let mut pq = extra::priority_queue::PriorityQueue::new();
  pq.push(5);
  pq.push(6);
  pq.push(3);
  for pq.iter().advance |el| {
      println(fmt!("%d", *el));
  }

just like you iterate over vectors, hashmaps, hashsets etc.  Note that
the iteration order is arbitrary (as before with PriorityQueue::each),
and _not_ the order you get when you pop() repeatedly.

Add an in-file test to guard this.

Reported-by: Daniel Micay <danielmicay@gmail.com>
Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>

1 files changed, 27 insertions, 4 deletions

diff --git a/src/libextra/priority_queue.rs b/src/libextra/priority_queue.rs
index 4e201a6538b..af891edf9e5 100644
--- a/src/libextra/priority_queue.rs
+++ b/src/libextra/priority_queue.rs
@@ -37,10 +37,11 @@ impl<T:Ord> Mutable for PriorityQueue<T> {
 }
 
 impl<T:Ord> PriorityQueue<T> {
-    /// Visit all values in the underlying vector.
-    ///
-    /// The values are **not** visited in order.
-    pub fn each(&self, f: &fn(&T) -> bool) -> bool { self.data.iter().advance(f) }
+    /// An iterator visiting all values in underlying vector, in
+    /// arbitrary order.
+    pub fn iter<'a>(&'a self) -> PriorityQueueIterator<'a, T> {
+        PriorityQueueIterator { iter: self.data.iter() }
+    }
 
     /// Returns the greatest item in the queue - fails if empty
     pub fn top<'a>(&'a self) -> &'a T { &self.data[0] }
@@ -178,12 +179,34 @@ impl<T:Ord> PriorityQueue<T> {
     }
 }
 
+/// PriorityQueue iterator
+pub struct PriorityQueueIterator <'self, T> {
+    priv iter: vec::VecIterator<'self, T>,
+}
+
+impl<'self, T> Iterator<&'self T> for PriorityQueueIterator<'self, T> {
+    #[inline]
+    fn next(&mut self) -> Option<(&'self T)> { self.iter.next() }
+}
+
 #[cfg(test)]
 mod tests {
     use sort::merge_sort;
     use priority_queue::PriorityQueue;
 
     #[test]
+    fn test_iterator() {
+        let data = ~[5, 9, 3];
+        let iterout = ~[9, 5, 3];
+        let pq = PriorityQueue::from_vec(data);
+        let mut i = 0;
+        for pq.iter().advance |el| {
+            assert_eq!(*el, iterout[i]);
+            i += 1;
+        }
+    }
+
+    #[test]
     fn test_top_and_pop() {
         let data = ~[2u, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
         let mut sorted = merge_sort(data, |x, y| x.le(y));