use core::prelude::*;
-use alloc::owned::Box;
+use alloc::boxed::Box;
use core::default::Default;
use core::fmt;
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> {
}
/// Convert the `Rawlink` into an Option value
- fn resolve_immut(&self) -> Option<&T> {
- unsafe { self.p.to_option() }
+ fn resolve_immut<'a>(&self) -> Option<&'a T> {
+ unsafe {
+ mem::transmute(self.p.to_option())
+ }
}
/// Convert the `Rawlink` into an Option value
- fn resolve(&mut self) -> Option<&mut T> {
+ fn resolve<'a>(&mut self) -> Option<&'a mut T> {
if self.p.is_null() {
None
} else {
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)
}
}
/// Move the last element to the front of the list.
///
/// If the list is empty, do nothing.
+ ///
+ /// # Example
+ ///
+ /// ```rust
+ /// use std::collections::DList;
+ ///
+ /// let mut dl = DList::new();
+ /// dl.push(1i);
+ /// dl.push(2);
+ /// dl.push(3);
+ ///
+ /// dl.rotate_forward();
+ ///
+ /// for e in dl.iter() {
+ /// println!("{}", e); // prints 3, then 1, then 2
+ /// }
+ /// ```
#[inline]
pub fn rotate_forward(&mut self) {
self.pop_back_node().map(|tail| {
/// Move the first element to the back of the list.
///
/// If the list is empty, do nothing.
+ ///
+ /// # Example
+ ///
+ /// ```rust
+ /// use std::collections::DList;
+ ///
+ /// let mut dl = DList::new();
+ /// dl.push(1i);
+ /// dl.push(2);
+ /// dl.push(3);
+ ///
+ /// dl.rotate_backward();
+ ///
+ /// for e in dl.iter() {
+ /// println!("{}", e); // prints 2, then 3, then 1
+ /// }
+ /// ```
#[inline]
pub fn rotate_backward(&mut self) {
self.pop_front_node().map(|head| {
/// Add all elements from `other` to the end of the list
///
/// O(1)
+ ///
+ /// # Example
+ ///
+ /// ```rust
+ /// use std::collections::DList;
+ ///
+ /// let mut a = DList::new();
+ /// let mut b = DList::new();
+ /// a.push(1i);
+ /// a.push(2);
+ /// b.push(3i);
+ /// b.push(4);
+ ///
+ /// a.append(b);
+ ///
+ /// for e in a.iter() {
+ /// println!("{}", e); // prints 1, then 2, then 3, then 4
+ /// }
+ /// ```
pub fn append(&mut self, mut other: DList<T>) {
match self.list_tail.resolve() {
None => *self = other,
/// Add all elements from `other` to the beginning of the list
///
/// O(1)
+ ///
+ /// # Example
+ ///
+ /// ```rust
+ /// use std::collections::DList;
+ ///
+ /// let mut a = DList::new();
+ /// let mut b = DList::new();
+ /// a.push(1i);
+ /// a.push(2);
+ /// b.push(3i);
+ /// b.push(4);
+ ///
+ /// a.prepend(b);
+ ///
+ /// for e in a.iter() {
+ /// println!("{}", e); // prints 3, then 4, then 1, then 2
+ /// }
+ /// ```
#[inline]
pub fn prepend(&mut self, mut other: DList<T>) {
mem::swap(self, &mut other);
/// or at the end.
///
/// O(N)
+ ///
+ /// # Example
+ ///
+ /// ```rust
+ /// use std::collections::DList;
+ ///
+ /// let mut a: DList<int> = DList::new();
+ /// 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);
+ ///
+ /// for e in a.iter() {
+ /// println!("{}", e); // prints 2, then 4, then 11, then 7, then 8
+ /// }
+ /// ```
pub fn insert_when(&mut self, elt: T, f: |&T, &T| -> bool) {
{
let mut it = self.mut_iter();
}
impl<A: PartialOrd> PartialOrd for DList<A> {
- fn lt(&self, other: &DList<A>) -> bool {
- iter::order::lt(self.iter(), other.iter())
- }
- fn le(&self, other: &DList<A>) -> bool {
- iter::order::le(self.iter(), other.iter())
- }
- fn gt(&self, other: &DList<A>) -> bool {
- iter::order::gt(self.iter(), other.iter())
- }
- fn ge(&self, other: &DList<A>) -> bool {
- iter::order::ge(self.iter(), other.iter())
+ fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> {
+ iter::order::partial_cmp(self.iter(), other.iter())
}
}
}
}
+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;
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([]);
#[test]
fn test_show() {
let list: DList<int> = range(0i, 10).collect();
- assert!(list.to_str().as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+ assert!(list.to_string().as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
let list: DList<&str> = vec!["just", "one", "test", "more"].iter()
.map(|&s| s)
.collect();
- assert!(list.to_str().as_slice() == "[just, one, test, more]");
+ assert!(list.to_string().as_slice() == "[just, one, test, more]");
}
#[cfg(test)]
projects / rust.git / blobdiff