auto merge of #15999 : Kimundi/rust/fix_folder, r=nikomatsakis

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

diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index 48ea1bd1c0150d72fcd641c600c88dfcac9f5ac5..5e3ce75eb9586bc56a085d28536b4bf3df4780ec 100644 (file)
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -29,8 +29,9 @@
 use core::iter;
 use core::mem;
 use core::ptr;
+use std::hash::{Writer, Hash};
 
-use {Collection, Mutable, Deque};
+use {Collection, Mutable, Deque, MutableSeq};
 
 /// A doubly-linked list.
 pub struct DList<T> {
@@ -249,18 +250,13 @@ fn push_front(&mut self, elt: T) {
     fn pop_front(&mut self) -> Option<T> {
         self.pop_front_node().map(|box Node{value, ..}| value)
     }
+}
 
-    /// Add an element last in the list
-    ///
-    /// O(1)
-    fn push_back(&mut self, elt: T) {
+impl<T> MutableSeq<T> for DList<T> {
+    fn push(&mut self, elt: T) {
         self.push_back_node(box Node::new(elt))
     }
-
-    /// Remove the last element and return it, or None if the list is empty
-    ///
-    /// O(1)
-    fn pop_back(&mut self) -> Option<T> {
+    fn pop(&mut self) -> Option<T> {
         self.pop_back_node().map(|box Node{value, ..}| value)
     }
 }
@@ -284,12 +280,12 @@ pub fn new() -> DList<T> {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut dl = DList::new();
-    /// dl.push_back(1i);
-    /// dl.push_back(2);
-    /// dl.push_back(3);
+    /// dl.push(1i);
+    /// dl.push(2);
+    /// dl.push(3);
     ///
     /// dl.rotate_forward();
     ///
@@ -311,12 +307,12 @@ pub fn rotate_forward(&mut self) {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut dl = DList::new();
-    /// dl.push_back(1i);
-    /// dl.push_back(2);
-    /// dl.push_back(3);
+    /// dl.push(1i);
+    /// dl.push(2);
+    /// dl.push(3);
     ///
     /// dl.rotate_backward();
     ///
@@ -338,14 +334,14 @@ pub fn rotate_backward(&mut self) {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut a = DList::new();
     /// let mut b = DList::new();
-    /// a.push_back(1i);
-    /// a.push_back(2);
-    /// b.push_back(3i);
-    /// b.push_back(4);
+    /// a.push(1i);
+    /// a.push(2);
+    /// b.push(3i);
+    /// b.push(4);
     ///
     /// a.append(b);
     ///
@@ -379,14 +375,14 @@ pub fn append(&mut self, mut other: DList<T>) {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut a = DList::new();
     /// let mut b = DList::new();
-    /// a.push_back(1i);
-    /// a.push_back(2);
-    /// b.push_back(3i);
-    /// b.push_back(4);
+    /// a.push(1i);
+    /// a.push(2);
+    /// b.push(3i);
+    /// b.push(4);
     ///
     /// a.prepend(b);
     ///
@@ -408,13 +404,13 @@ pub fn prepend(&mut self, mut other: DList<T>) {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut a: DList<int> = DList::new();
-    /// a.push_back(2i);
-    /// a.push_back(4);
-    /// a.push_back(7);
-    /// a.push_back(8);
+    /// a.push(2i);
+    /// a.push(4);
+    /// a.push(7);
+    /// a.push(8);
     ///
     /// // insert 11 before the first odd number in the list
     /// a.insert_when(11, |&e, _| e % 2 == 1);
@@ -712,14 +708,24 @@ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
     }
 }
 
+impl<S: Writer, A: Hash<S>> Hash<S> for DList<A> {
+    fn hash(&self, state: &mut S) {
+        self.len().hash(state);
+        for elt in self.iter() {
+            elt.hash(state);
+        }
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use std::prelude::*;
     use std::rand;
+    use std::hash;
     use test::Bencher;
     use test;
 
-    use Deque;
+    use {Deque, MutableSeq};
     use super::{DList, Node, ListInsertion};
     use vec::Vec;
 
@@ -1080,6 +1086,24 @@ fn test_eq() {
         assert!(n != m);
     }
 
+    #[test]
+    fn test_hash() {
+      let mut x = DList::new();
+      let mut y = DList::new();
+
+      assert!(hash::hash(&x) == hash::hash(&y));
+
+      x.push_back(1i);
+      x.push_back(2);
+      x.push_back(3);
+
+      y.push_front(3i);
+      y.push_front(2);
+      y.push_front(1);
+
+      assert!(hash::hash(&x) == hash::hash(&y));
+    }
+
     #[test]
     fn test_ord() {
         let n: DList<int> = list_from([]);