dlist: Add .rotate_to_front(), .rotate_to_back()

Add methods to move back element to front or front element to back,
without reallocating nodes.

1 files changed, 43 insertions, 0 deletions

diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs
index 9e8982ecf8d..189f20c9740 100644
--- a/src/libextra/dlist.rs
+++ b/src/libextra/dlist.rs
@@ -258,6 +258,26 @@ impl<T> DList<T> {
         DList{list_head: None, list_tail: Rawlink::none(), length: 0}
     }
 
+    /// Move the last element to the front of the list.
+    ///
+    /// If the list is empty, do nothing.
+    #[inline]
+    pub fn rotate_to_front(&mut self) {
+        do self.pop_back_node().map_consume |tail| {
+            self.push_front_node(tail)
+        };
+    }
+
+    /// Move the first element to the back of the list.
+    ///
+    /// If the list is empty, do nothing.
+    #[inline]
+    pub fn rotate_to_back(&mut self) {
+        do self.pop_front_node().map_consume |head| {
+            self.push_back_node(head)
+        };
+    }
+
     /// Add all elements from `other` to the end of the list
     ///
     /// O(1)
@@ -689,6 +709,29 @@ mod tests {
     }
 
     #[test]
+    fn test_rotate() {
+        let mut n = DList::new::<int>();
+        n.rotate_to_back(); check_links(&n);
+        assert_eq!(n.len(), 0);
+        n.rotate_to_front(); check_links(&n);
+        assert_eq!(n.len(), 0);
+
+        let v = ~[1,2,3,4,5];
+        let mut m = list_from(v);
+        m.rotate_to_back(); check_links(&m);
+        m.rotate_to_front(); check_links(&m);
+        assert_eq!(v.iter().collect::<~[&int]>(), m.iter().collect());
+        m.rotate_to_front(); check_links(&m);
+        m.rotate_to_front(); check_links(&m);
+        m.pop_front(); check_links(&m);
+        m.rotate_to_front(); check_links(&m);
+        m.rotate_to_back(); check_links(&m);
+        m.push_front(9); check_links(&m);
+        m.rotate_to_front(); check_links(&m);
+        assert_eq!(~[3,9,5,1,2], m.consume_iter().collect());
+    }
+
+    #[test]
     fn test_iterator() {
         let m = generate_test();
         for m.iter().enumerate().advance |(i, elt)| {