dlist: Use a DoubleEndedIterator for .mut_iter() and .mut_rev_iter()

Unify the mutable iterators too. Switch the ListInsertion trait to use
method .insert_next() and .peek_next() for list mutation. .insert_next()
inserts an element into the list that will not appear in iteration, of
course; so the length of the iteration can not change during iteration.

1 files changed, 109 insertions, 79 deletions

diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs
index 60850654607..283a726988b 100644
--- a/src/libextra/dlist.rs
+++ b/src/libextra/dlist.rs
@@ -53,17 +53,11 @@ pub struct DListIterator<'self, T> {
     priv nelem: uint,
 }
 
-/// DList mutable iterator
-pub struct MutForwardIterator<'self, T> {
+/// Double-ended mutable DList iterator
+pub struct MutDListIterator<'self, T> {
     priv list: &'self mut DList<T>,
-    priv curs: Rawlink<Node<T>>,
-    priv nelem: uint,
-}
-
-/// DList mutable reverse iterator
-pub struct MutReverseIterator<'self, T> {
-    priv list: &'self mut DList<T>,
-    priv next: Rawlink<Node<T>>,
+    priv head: Rawlink<Node<T>>,
+    priv tail: Rawlink<Node<T>>,
     priv nelem: uint,
 }
 
@@ -279,13 +273,14 @@ impl<T> DList<T> {
         {
             let mut it = self.mut_iter();
             loop {
-                match it.next() {
+                match it.peek_next() {
                     None => break,
-                    Some(x) => if f(x, &elt) { it.insert_before(elt); return }
+                    Some(x) => if f(x, &elt) { break }
                 }
+                it.next();
             }
+            it.insert_next(elt);
         }
-        self.push_back(elt);
     }
 
     /// Merge DList `other` into this DList, using the function `f`.
@@ -296,17 +291,16 @@ impl<T> DList<T> {
     pub fn merge(&mut self, mut other: DList<T>, f: &fn(&T, &T) -> bool) {
         {
             let mut it = self.mut_iter();
-            let mut elt = it.next();
             loop {
-                let take_a = match (&mut elt, other.front()) {
-                    (_    , None) => return,
-                    (&None, _   ) => break,
-                    (&Some(ref mut x), Some(y)) => f(*x, y),
+                let take_a = match (it.peek_next(), other.front()) {
+                    (_   , None) => return,
+                    (None, _   ) => break,
+                    (Some(ref mut x), Some(y)) => f(*x, y),
                 };
                 if take_a {
-                    elt = it.next()
+                    it.next();
                 } else {
-                    it.insert_before(other.pop_front().unwrap());
+                    it.insert_next(other.pop_front().unwrap());
                 }
             }
         }
@@ -325,13 +319,22 @@ impl<T> DList<T> {
     }
 
     /// Provide a forward iterator with mutable references
-    pub fn mut_iter<'a>(&'a mut self) -> MutForwardIterator<'a, T> {
-        MutForwardIterator{nelem: self.len(), list: self, curs: Rawlink::none()}
+    pub fn mut_iter<'a>(&'a mut self) -> MutDListIterator<'a, T> {
+        let head_raw = match self.list_head {
+            Some(ref mut h) => Rawlink::some(*h),
+            None => Rawlink::none(),
+        };
+        MutDListIterator{
+            nelem: self.len(),
+            head: head_raw,
+            tail: self.list_tail,
+            list: self
+        }
     }
-
     /// Provide a reverse iterator with mutable references
-    pub fn mut_rev_iter<'a>(&'a mut self) -> MutReverseIterator<'a, T> {
-        MutReverseIterator{nelem: self.len(), list: self, next: self.list_tail}
+    pub fn mut_rev_iter<'a>(&'a mut self) -> InvertIterator<&'a mut T,
+                                                MutDListIterator<'a, T>> {
+        self.mut_iter().invert()
     }
 
 
@@ -392,31 +395,21 @@ impl<'self, A> DoubleEndedIterator<&'self A> for DListIterator<'self, A> {
     }
 }
 
-// MutForwardIterator is different because it implements ListInsertion,
-// and can modify the list during traversal, used in insert_when and merge.
-impl<'self, A> Iterator<&'self mut A> for MutForwardIterator<'self, A> {
+impl<'self, A> Iterator<&'self mut A> for MutDListIterator<'self, A> {
     #[inline]
     fn next(&mut self) -> Option<&'self mut A> {
-        match self.curs.resolve() {
-            None => {
-                match self.list.list_head {
-                    None => None,
-                    Some(ref mut head) => {
-                        self.nelem -= 1;
-                        self.curs = Rawlink::some(*head);
-                        Some(&mut head.value)
-                    }
-                }
-            }
-            Some(curs) => {
-                match curs.next {
-                    None => None,
-                    Some(ref mut head) => {
-                        self.nelem -= 1;
-                        self.curs = Rawlink::some(*head);
-                        Some(&mut head.value)
-                    }
-                }
+        if self.nelem == 0 {
+            return None;
+        }
+        match self.head.resolve() {
+            None => None,
+            Some(next) => {
+                self.nelem -= 1;
+                self.head = match next.next {
+                    Some(ref mut node) => Rawlink::some(&mut **node),
+                    None => Rawlink::none(),
+                };
+                Some(&mut next.value)
             }
         }
     }
@@ -426,37 +419,39 @@ impl<'self, A> Iterator<&'self mut A> for MutForwardIterator<'self, A> {
     }
 }
 
-impl<'self, A> Iterator<&'self mut A> for MutReverseIterator<'self, A> {
+impl<'self, A> DoubleEndedIterator<&'self mut A> for MutDListIterator<'self, A> {
     #[inline]
-    fn next(&mut self) -> Option<&'self mut A> {
-        match self.next.resolve() {
+    fn next_back(&mut self) -> Option<&'self mut A> {
+        if self.nelem == 0 {
+            return None;
+        }
+        match self.tail.resolve() {
             None => None,
             Some(prev) => {
                 self.nelem -= 1;
-                self.next = prev.prev;
+                self.tail = prev.prev;
                 Some(&mut prev.value)
             }
         }
     }
-
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.nelem, Some(self.nelem))
-    }
 }
 
+
 /// Allow mutating the DList while iterating
 pub trait ListInsertion<A> {
-    /// Insert `elt` just previous to the most recently yielded element
-    fn insert_before(&mut self, elt: A);
+    /// Insert `elt` just after to the most recently yielded element
+    fn insert_next(&mut self, elt: A);
 
     /// Provide a reference to the next element, without changing the iterator
     fn peek_next<'a>(&'a mut self) -> Option<&'a mut A>;
 }
 
-impl<'self, A> ListInsertion<A> for MutForwardIterator<'self, A> {
-    fn insert_before(&mut self, elt: A) {
-        match self.curs.resolve() {
-            None => { self.list.push_front(elt); self.next(); }
+impl<'self, A> ListInsertion<A> for MutDListIterator<'self, A> {
+    fn insert_next(&mut self, elt: A) {
+        // Insert an element before `self.head` so that it is between the
+        // previously yielded element and self.head.
+        match self.head.resolve() {
+            None => { self.list.push_back(elt); }
             Some(node) => {
                 let prev_node = match node.prev.resolve() {
                     None => return self.list.push_front(elt),
@@ -472,12 +467,9 @@ impl<'self, A> ListInsertion<A> for MutForwardIterator<'self, A> {
     }
 
     fn peek_next<'a>(&'a mut self) -> Option<&'a mut A> {
-        match self.curs.resolve() {
-            None => self.list.front_mut(),
-            Some(curs) => match curs.next {
-                None => None,
-                Some(ref mut node) => Some(&mut node.value),
-            }
+        match self.head.resolve() {
+            None => None,
+            Some(head) => Some(&mut head.value),
         }
     }
 }
@@ -681,6 +673,24 @@ mod tests {
     }
 
     #[test]
+    fn test_iterator_double_end() {
+        let mut n = DList::new();
+        assert_eq!(n.iter().next(), None);
+        n.push_front(4);
+        n.push_front(5);
+        n.push_front(6);
+        let mut it = n.iter();
+        assert_eq!(it.size_hint(), (3, Some(3)));
+        assert_eq!(it.next().unwrap(), &6);
+        assert_eq!(it.size_hint(), (2, Some(2)));
+        assert_eq!(it.next_back().unwrap(), &4);
+        assert_eq!(it.size_hint(), (1, Some(1)));
+        assert_eq!(it.next_back().unwrap(), &5);
+        assert_eq!(it.next_back(), None);
+        assert_eq!(it.next(), None);
+    }
+
+    #[test]
     fn test_rev_iter() {
         let m = generate_test();
         for m.rev_iter().enumerate().advance |(i, elt)| {
@@ -708,25 +718,45 @@ mod tests {
         let mut n = DList::new();
         assert!(n.mut_iter().next().is_none());
         n.push_front(4);
+        n.push_back(5);
         let mut it = n.mut_iter();
-        assert_eq!(it.size_hint(), (1, Some(1)));
+        assert_eq!(it.size_hint(), (2, Some(2)));
+        assert!(it.next().is_some());
         assert!(it.next().is_some());
         assert_eq!(it.size_hint(), (0, Some(0)));
         assert!(it.next().is_none());
     }
 
     #[test]
+    fn test_iterator_mut_double_end() {
+        let mut n = DList::new();
+        assert!(n.mut_iter().next_back().is_none());
+        n.push_front(4);
+        n.push_front(5);
+        n.push_front(6);
+        let mut it = n.mut_iter();
+        assert_eq!(it.size_hint(), (3, Some(3)));
+        assert_eq!(*it.next().unwrap(), 6);
+        assert_eq!(it.size_hint(), (2, Some(2)));
+        assert_eq!(*it.next_back().unwrap(), 4);
+        assert_eq!(it.size_hint(), (1, Some(1)));
+        assert_eq!(*it.next_back().unwrap(), 5);
+        assert!(it.next_back().is_none());
+        assert!(it.next().is_none());
+    }
+
+    #[test]
     fn test_insert_prev() {
         let mut m = list_from(&[0,2,4,6,8]);
         let len = m.len();
         {
             let mut it = m.mut_iter();
-            it.insert_before(-2);
+            it.insert_next(-2);
             loop {
                 match it.next() {
                     None => break,
                     Some(elt) => {
-                        it.insert_before(*elt + 1);
+                        it.insert_next(*elt + 1);
                         match it.peek_next() {
                             Some(x) => assert_eq!(*x, *elt + 2),
                             None => assert_eq!(8, *elt),
@@ -734,12 +764,12 @@ mod tests {
                     }
                 }
             }
-            it.insert_before(0);
-            it.insert_before(1);
+            it.insert_next(0);
+            it.insert_next(1);
         }
         check_links(&m);
         assert_eq!(m.len(), 3 + len * 2);
-        assert_eq!(m.consume_iter().collect::<~[int]>(), ~[-2,1,0,3,2,5,4,7,6,9,0,1,8]);
+        assert_eq!(m.consume_iter().collect::<~[int]>(), ~[-2,0,1,2,3,4,5,6,7,8,9,0,1]);
     }
 
     #[test]
@@ -853,7 +883,7 @@ mod tests {
     fn bench_collect_into(b: &mut test::BenchHarness) {
         let v = &[0, ..64];
         do b.iter {
-            let _: DList<int> = v.iter().transform(|&x|x).collect();
+            let _: DList<int> = v.iter().transform(|x| *x).collect();
         }
     }
     #[bench]
@@ -917,7 +947,7 @@ mod tests {
         let v = &[0, ..128];
         let m: DList<int> = v.iter().transform(|&x|x).collect();
         do b.iter {
-            for m.iter().advance |_| {}
+            assert!(m.iter().len_() == 128);
         }
     }
     #[bench]
@@ -925,7 +955,7 @@ mod tests {
         let v = &[0, ..128];
         let mut m: DList<int> = v.iter().transform(|&x|x).collect();
         do b.iter {
-            for m.mut_iter().advance |_| {}
+            assert!(m.mut_iter().len_() == 128);
         }
     }
     #[bench]
@@ -933,7 +963,7 @@ mod tests {
         let v = &[0, ..128];
         let m: DList<int> = v.iter().transform(|&x|x).collect();
         do b.iter {
-            for m.rev_iter().advance |_| {}
+            assert!(m.rev_iter().len_() == 128);
         }
     }
     #[bench]
@@ -941,7 +971,7 @@ mod tests {
         let v = &[0, ..128];
         let mut m: DList<int> = v.iter().transform(|&x|x).collect();
         do b.iter {
-            for m.mut_rev_iter().advance |_| {}
+            assert!(m.mut_rev_iter().len_() == 128);
         }
     }
     #[bench]