src/libcollections/dlist.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A doubly-linked list with owned nodes.
  12 //!
  13 //! The `DList` allows pushing and popping elements at either end and is thus
  14 //! efficiently usable as a double-ended queue.
  15
  16 // DList is constructed like a singly-linked list over the field `next`.
  17 // including the last link being None; each Node owns its `next` field.
  18 //
  19 // Backlinks over DList::prev are raw pointers that form a full chain in
  20 // the reverse direction.
  21
  22 #![stable]
  23
  24 use core::prelude::*;
  25
  26 use alloc::boxed::Box;
  27 use core::cmp::Ordering;
  28 use core::default::Default;
  29 use core::fmt;
  30 use core::hash::{Writer, Hasher, Hash};
  31 use core::iter::{self, FromIterator};
  32 use core::mem;
  33 use core::ptr;
  34
  35 /// A doubly-linked list.
  36 #[stable]
  37 pub struct DList<T> {
  38     length: uint,
  39     list_head: Link<T>,
  40     list_tail: Rawlink<Node<T>>,
  41 }
  42
  43 type Link<T> = Option<Box<Node<T>>>;
  44
  45 struct Rawlink<T> {
  46     p: *mut T,
  47 }
  48
  49 impl<T> Copy for Rawlink<T> {}
  50 unsafe impl<T:'static+Send> Send for Rawlink<T> {}
  51 unsafe impl<T:Send+Sync> Sync for Rawlink<T> {}
  52
  53 struct Node<T> {
  54     next: Link<T>,
  55     prev: Rawlink<Node<T>>,
  56     value: T,
  57 }
  58
  59 /// An iterator over references to the items of a `DList`.
  60 #[stable]
  61 pub struct Iter<'a, T:'a> {
  62     head: &'a Link<T>,
  63     tail: Rawlink<Node<T>>,
  64     nelem: uint,
  65 }
  66
  67 // FIXME #19839: deriving is too aggressive on the bounds (T doesn't need to be Clone).
  68 #[stable]
  69 impl<'a, T> Clone for Iter<'a, T> {
  70     fn clone(&self) -> Iter<'a, T> {
  71         Iter {
  72             head: self.head.clone(),
  73             tail: self.tail,
  74             nelem: self.nelem,
  75         }
  76     }
  77 }
  78
  79 /// An iterator over mutable references to the items of a `DList`.
  80 #[stable]
  81 pub struct IterMut<'a, T:'a> {
  82     list: &'a mut DList<T>,
  83     head: Rawlink<Node<T>>,
  84     tail: Rawlink<Node<T>>,
  85     nelem: uint,
  86 }
  87
  88 /// An iterator over mutable references to the items of a `DList`.
  89 #[derive(Clone)]
  90 #[stable]
  91 pub struct IntoIter<T> {
  92     list: DList<T>
  93 }
  94
  95 /// Rawlink is a type like Option<T> but for holding a raw pointer
  96 impl<T> Rawlink<T> {
  97     /// Like Option::None for Rawlink
  98     fn none() -> Rawlink<T> {
  99         Rawlink{p: ptr::null_mut()}
 100     }
 101
 102     /// Like Option::Some for Rawlink
 103     fn some(n: &mut T) -> Rawlink<T> {
 104         Rawlink{p: n}
 105     }
 106
 107     /// Convert the `Rawlink` into an Option value
 108     fn resolve_immut<'a>(&self) -> Option<&'a T> {
 109         unsafe {
 110             mem::transmute(self.p.as_ref())
 111         }
 112     }
 113
 114     /// Convert the `Rawlink` into an Option value
 115     fn resolve<'a>(&mut self) -> Option<&'a mut T> {
 116         if self.p.is_null() {
 117             None
 118         } else {
 119             Some(unsafe { mem::transmute(self.p) })
 120         }
 121     }
 122
 123     /// Return the `Rawlink` and replace with `Rawlink::none()`
 124     fn take(&mut self) -> Rawlink<T> {
 125         mem::replace(self, Rawlink::none())
 126     }
 127 }
 128
 129 impl<T> Clone for Rawlink<T> {
 130     #[inline]
 131     fn clone(&self) -> Rawlink<T> {
 132         Rawlink{p: self.p}
 133     }
 134 }
 135
 136 impl<T> Node<T> {
 137     fn new(v: T) -> Node<T> {
 138         Node{value: v, next: None, prev: Rawlink::none()}
 139     }
 140 }
 141
 142 /// Set the .prev field on `next`, then return `Some(next)`
 143 fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
 144                   -> Link<T> {
 145     next.prev = prev;
 146     Some(next)
 147 }
 148
 149 // private methods
 150 impl<T> DList<T> {
 151     /// Add a Node first in the list
 152     #[inline]
 153     fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
 154         match self.list_head {
 155             None => {
 156                 self.list_tail = Rawlink::some(&mut *new_head);
 157                 self.list_head = link_with_prev(new_head, Rawlink::none());
 158             }
 159             Some(ref mut head) => {
 160                 new_head.prev = Rawlink::none();
 161                 head.prev = Rawlink::some(&mut *new_head);
 162                 mem::swap(head, &mut new_head);
 163                 head.next = Some(new_head);
 164             }
 165         }
 166         self.length += 1;
 167     }
 168
 169     /// Remove the first Node and return it, or None if the list is empty
 170     #[inline]
 171     fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
 172         self.list_head.take().map(|mut front_node| {
 173             self.length -= 1;
 174             match front_node.next.take() {
 175                 Some(node) => self.list_head = link_with_prev(node, Rawlink::none()),
 176                 None => self.list_tail = Rawlink::none()
 177             }
 178             front_node
 179         })
 180     }
 181
 182     /// Add a Node last in the list
 183     #[inline]
 184     fn push_back_node(&mut self, mut new_tail: Box<Node<T>>) {
 185         match self.list_tail.resolve() {
 186             None => return self.push_front_node(new_tail),
 187             Some(tail) => {
 188                 self.list_tail = Rawlink::some(&mut *new_tail);
 189                 tail.next = link_with_prev(new_tail, Rawlink::some(tail));
 190             }
 191         }
 192         self.length += 1;
 193     }
 194
 195     /// Remove the last Node and return it, or None if the list is empty
 196     #[inline]
 197     fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
 198         self.list_tail.resolve().map_or(None, |tail| {
 199             self.length -= 1;
 200             self.list_tail = tail.prev;
 201             match tail.prev.resolve() {
 202                 None => self.list_head.take(),
 203                 Some(tail_prev) => tail_prev.next.take()
 204             }
 205         })
 206     }
 207 }
 208
 209 #[stable]
 210 impl<T> Default for DList<T> {
 211     #[inline]
 212     #[stable]
 213     fn default() -> DList<T> { DList::new() }
 214 }
 215
 216 impl<T> DList<T> {
 217     /// Creates an empty `DList`.
 218     #[inline]
 219     #[stable]
 220     pub fn new() -> DList<T> {
 221         DList{list_head: None, list_tail: Rawlink::none(), length: 0}
 222     }
 223
 224     /// Adds all elements from `other` to the end of the list.
 225     ///
 226     /// This operation should compute in O(1) time.
 227     ///
 228     /// # Examples
 229     ///
 230     /// ```rust
 231     /// use std::collections::DList;
 232     ///
 233     /// let mut a = DList::new();
 234     /// let mut b = DList::new();
 235     /// a.push_back(1i);
 236     /// a.push_back(2);
 237     /// b.push_back(3i);
 238     /// b.push_back(4);
 239     ///
 240     /// a.append(b);
 241     ///
 242     /// for e in a.iter() {
 243     ///     println!("{}", e); // prints 1, then 2, then 3, then 4
 244     /// }
 245     /// ```
 246     #[unstable = "append should be by-mutable-reference"]
 247     pub fn append(&mut self, mut other: DList<T>) {
 248         match self.list_tail.resolve() {
 249             None => *self = other,
 250             Some(tail) => {
 251                 // Carefully empty `other`.
 252                 let o_tail = other.list_tail.take();
 253                 let o_length = other.length;
 254                 match other.list_head.take() {
 255                     None => return,
 256                     Some(node) => {
 257                         tail.next = link_with_prev(node, self.list_tail);
 258                         self.list_tail = o_tail;
 259                         self.length += o_length;
 260                     }
 261                 }
 262             }
 263         }
 264     }
 265
 266     /// Provides a forward iterator.
 267     #[inline]
 268     #[stable]
 269     pub fn iter(&self) -> Iter<T> {
 270         Iter{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
 271     }
 272
 273     /// Provides a forward iterator with mutable references.
 274     #[inline]
 275     #[stable]
 276     pub fn iter_mut(&mut self) -> IterMut<T> {
 277         let head_raw = match self.list_head {
 278             Some(ref mut h) => Rawlink::some(&mut **h),
 279             None => Rawlink::none(),
 280         };
 281         IterMut{
 282             nelem: self.len(),
 283             head: head_raw,
 284             tail: self.list_tail,
 285             list: self
 286         }
 287     }
 288
 289     /// Consumes the list into an iterator yielding elements by value.
 290     #[inline]
 291     #[stable]
 292     pub fn into_iter(self) -> IntoIter<T> {
 293         IntoIter{list: self}
 294     }
 295
 296     /// Returns `true` if the `DList` is empty.
 297     ///
 298     /// This operation should compute in O(1) time.
 299     #[inline]
 300     #[stable]
 301     pub fn is_empty(&self) -> bool {
 302         self.list_head.is_none()
 303     }
 304
 305     /// Returns the length of the `DList`.
 306     ///
 307     /// This operation should compute in O(1) time.
 308     #[inline]
 309     #[stable]
 310     pub fn len(&self) -> uint {
 311         self.length
 312     }
 313
 314     /// Removes all elements from the `DList`.
 315     ///
 316     /// This operation should compute in O(n) time.
 317     #[inline]
 318     #[stable]
 319     pub fn clear(&mut self) {
 320         *self = DList::new()
 321     }
 322
 323     /// Provides a reference to the front element, or `None` if the list is
 324     /// empty.
 325     #[inline]
 326     #[stable]
 327     pub fn front(&self) -> Option<&T> {
 328         self.list_head.as_ref().map(|head| &head.value)
 329     }
 330
 331     /// Provides a mutable reference to the front element, or `None` if the list
 332     /// is empty.
 333     #[inline]
 334     #[stable]
 335     pub fn front_mut(&mut self) -> Option<&mut T> {
 336         self.list_head.as_mut().map(|head| &mut head.value)
 337     }
 338
 339     /// Provides a reference to the back element, or `None` if the list is
 340     /// empty.
 341     #[inline]
 342     #[stable]
 343     pub fn back(&self) -> Option<&T> {
 344         self.list_tail.resolve_immut().as_ref().map(|tail| &tail.value)
 345     }
 346
 347     /// Provides a mutable reference to the back element, or `None` if the list
 348     /// is empty.
 349     #[inline]
 350     #[stable]
 351     pub fn back_mut(&mut self) -> Option<&mut T> {
 352         self.list_tail.resolve().map(|tail| &mut tail.value)
 353     }
 354
 355     /// Adds an element first in the list.
 356     ///
 357     /// This operation should compute in O(1) time.
 358     #[stable]
 359     pub fn push_front(&mut self, elt: T) {
 360         self.push_front_node(box Node::new(elt))
 361     }
 362
 363     /// Removes the first element and returns it, or `None` if the list is
 364     /// empty.
 365     ///
 366     /// This operation should compute in O(1) time.
 367     #[stable]
 368     pub fn pop_front(&mut self) -> Option<T> {
 369         self.pop_front_node().map(|box Node{value, ..}| value)
 370     }
 371
 372     /// Appends an element to the back of a list
 373     ///
 374     /// # Examples
 375     ///
 376     /// ```rust
 377     /// use std::collections::DList;
 378     ///
 379     /// let mut d = DList::new();
 380     /// d.push_back(1i);
 381     /// d.push_back(3);
 382     /// assert_eq!(3, *d.back().unwrap());
 383     /// ```
 384     #[stable]
 385     pub fn push_back(&mut self, elt: T) {
 386         self.push_back_node(box Node::new(elt))
 387     }
 388
 389     /// Removes the last element from a list and returns it, or `None` if
 390     /// it is empty.
 391     ///
 392     /// # Examples
 393     ///
 394     /// ```rust
 395     /// use std::collections::DList;
 396     ///
 397     /// let mut d = DList::new();
 398     /// assert_eq!(d.pop_back(), None);
 399     /// d.push_back(1i);
 400     /// d.push_back(3);
 401     /// assert_eq!(d.pop_back(), Some(3));
 402     /// ```
 403     #[stable]
 404     pub fn pop_back(&mut self) -> Option<T> {
 405         self.pop_back_node().map(|box Node{value, ..}| value)
 406     }
 407 }
 408
 409 #[unsafe_destructor]
 410 #[stable]
 411 impl<T> Drop for DList<T> {
 412     fn drop(&mut self) {
 413         // Dissolve the dlist in backwards direction
 414         // Just dropping the list_head can lead to stack exhaustion
 415         // when length is >> 1_000_000
 416         let mut tail = self.list_tail;
 417         loop {
 418             match tail.resolve() {
 419                 None => break,
 420                 Some(prev) => {
 421                     prev.next.take(); // release Box<Node<T>>
 422                     tail = prev.prev;
 423                 }
 424             }
 425         }
 426         self.length = 0;
 427         self.list_head = None;
 428         self.list_tail = Rawlink::none();
 429     }
 430 }
 431
 432 #[stable]
 433 impl<'a, A> Iterator for Iter<'a, A> {
 434     type Item = &'a A;
 435
 436     #[inline]
 437     fn next(&mut self) -> Option<&'a A> {
 438         if self.nelem == 0 {
 439             return None;
 440         }
 441         self.head.as_ref().map(|head| {
 442             self.nelem -= 1;
 443             self.head = &head.next;
 444             &head.value
 445         })
 446     }
 447
 448     #[inline]
 449     fn size_hint(&self) -> (uint, Option<uint>) {
 450         (self.nelem, Some(self.nelem))
 451     }
 452 }
 453
 454 #[stable]
 455 impl<'a, A> DoubleEndedIterator for Iter<'a, A> {
 456     #[inline]
 457     fn next_back(&mut self) -> Option<&'a A> {
 458         if self.nelem == 0 {
 459             return None;
 460         }
 461         self.tail.resolve_immut().as_ref().map(|prev| {
 462             self.nelem -= 1;
 463             self.tail = prev.prev;
 464             &prev.value
 465         })
 466     }
 467 }
 468
 469 #[stable]
 470 impl<'a, A> ExactSizeIterator for Iter<'a, A> {}
 471
 472 #[stable]
 473 impl<'a, A> Iterator for IterMut<'a, A> {
 474     type Item = &'a mut A;
 475     #[inline]
 476     fn next(&mut self) -> Option<&'a mut A> {
 477         if self.nelem == 0 {
 478             return None;
 479         }
 480         self.head.resolve().map(|next| {
 481             self.nelem -= 1;
 482             self.head = match next.next {
 483                 Some(ref mut node) => Rawlink::some(&mut **node),
 484                 None => Rawlink::none(),
 485             };
 486             &mut next.value
 487         })
 488     }
 489
 490     #[inline]
 491     fn size_hint(&self) -> (uint, Option<uint>) {
 492         (self.nelem, Some(self.nelem))
 493     }
 494 }
 495
 496 #[stable]
 497 impl<'a, A> DoubleEndedIterator for IterMut<'a, A> {
 498     #[inline]
 499     fn next_back(&mut self) -> Option<&'a mut A> {
 500         if self.nelem == 0 {
 501             return None;
 502         }
 503         self.tail.resolve().map(|prev| {
 504             self.nelem -= 1;
 505             self.tail = prev.prev;
 506             &mut prev.value
 507         })
 508     }
 509 }
 510
 511 #[stable]
 512 impl<'a, A> ExactSizeIterator for IterMut<'a, A> {}
 513
 514 // private methods for IterMut
 515 impl<'a, A> IterMut<'a, A> {
 516     fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
 517         // Insert before `self.head` so that it is between the
 518         // previously yielded element and self.head.
 519         //
 520         // The inserted node will not appear in further iteration.
 521         match self.head.resolve() {
 522             None => { self.list.push_back_node(ins_node); }
 523             Some(node) => {
 524                 let prev_node = match node.prev.resolve() {
 525                     None => return self.list.push_front_node(ins_node),
 526                     Some(prev) => prev,
 527                 };
 528                 let node_own = prev_node.next.take().unwrap();
 529                 ins_node.next = link_with_prev(node_own, Rawlink::some(&mut *ins_node));
 530                 prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
 531                 self.list.length += 1;
 532             }
 533         }
 534     }
 535 }
 536
 537 impl<'a, A> IterMut<'a, A> {
 538     /// Inserts `elt` just after the element most recently returned by `.next()`.
 539     /// The inserted element does not appear in the iteration.
 540     ///
 541     /// # Examples
 542     ///
 543     /// ```rust
 544     /// use std::collections::DList;
 545     ///
 546     /// let mut list: DList<int> = vec![1, 3, 4].into_iter().collect();
 547     ///
 548     /// {
 549     ///     let mut it = list.iter_mut();
 550     ///     assert_eq!(it.next().unwrap(), &1);
 551     ///     // insert `2` after `1`
 552     ///     it.insert_next(2);
 553     /// }
 554     /// {
 555     ///     let vec: Vec<int> = list.into_iter().collect();
 556     ///     assert_eq!(vec, vec![1i, 2, 3, 4]);
 557     /// }
 558     /// ```
 559     #[inline]
 560     #[unstable = "this is probably better handled by a cursor type -- we'll see"]
 561     pub fn insert_next(&mut self, elt: A) {
 562         self.insert_next_node(box Node::new(elt))
 563     }
 564
 565     /// Provides a reference to the next element, without changing the iterator.
 566     ///
 567     /// # Examples
 568     ///
 569     /// ```rust
 570     /// use std::collections::DList;
 571     ///
 572     /// let mut list: DList<int> = vec![1, 2, 3].into_iter().collect();
 573     ///
 574     /// let mut it = list.iter_mut();
 575     /// assert_eq!(it.next().unwrap(), &1);
 576     /// assert_eq!(it.peek_next().unwrap(), &2);
 577     /// // We just peeked at 2, so it was not consumed from the iterator.
 578     /// assert_eq!(it.next().unwrap(), &2);
 579     /// ```
 580     #[inline]
 581     #[unstable = "this is probably better handled by a cursor type -- we'll see"]
 582     pub fn peek_next(&mut self) -> Option<&mut A> {
 583         if self.nelem == 0 {
 584             return None
 585         }
 586         self.head.resolve().map(|head| &mut head.value)
 587     }
 588 }
 589
 590 #[stable]
 591 impl<A> Iterator for IntoIter<A> {
 592     type Item = A;
 593
 594     #[inline]
 595     fn next(&mut self) -> Option<A> { self.list.pop_front() }
 596
 597     #[inline]
 598     fn size_hint(&self) -> (uint, Option<uint>) {
 599         (self.list.length, Some(self.list.length))
 600     }
 601 }
 602
 603 #[stable]
 604 impl<A> DoubleEndedIterator for IntoIter<A> {
 605     #[inline]
 606     fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
 607 }
 608
 609 #[stable]
 610 impl<A> FromIterator<A> for DList<A> {
 611     fn from_iter<T: Iterator<Item=A>>(iterator: T) -> DList<A> {
 612         let mut ret = DList::new();
 613         ret.extend(iterator);
 614         ret
 615     }
 616 }
 617
 618 #[stable]
 619 impl<A> Extend<A> for DList<A> {
 620     fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
 621         for elt in iterator { self.push_back(elt); }
 622     }
 623 }
 624
 625 #[stable]
 626 impl<A: PartialEq> PartialEq for DList<A> {
 627     fn eq(&self, other: &DList<A>) -> bool {
 628         self.len() == other.len() &&
 629             iter::order::eq(self.iter(), other.iter())
 630     }
 631
 632     fn ne(&self, other: &DList<A>) -> bool {
 633         self.len() != other.len() ||
 634             iter::order::ne(self.iter(), other.iter())
 635     }
 636 }
 637
 638 #[stable]
 639 impl<A: Eq> Eq for DList<A> {}
 640
 641 #[stable]
 642 impl<A: PartialOrd> PartialOrd for DList<A> {
 643     fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> {
 644         iter::order::partial_cmp(self.iter(), other.iter())
 645     }
 646 }
 647
 648 #[stable]
 649 impl<A: Ord> Ord for DList<A> {
 650     #[inline]
 651     fn cmp(&self, other: &DList<A>) -> Ordering {
 652         iter::order::cmp(self.iter(), other.iter())
 653     }
 654 }
 655
 656 #[stable]
 657 impl<A: Clone> Clone for DList<A> {
 658     fn clone(&self) -> DList<A> {
 659         self.iter().map(|x| x.clone()).collect()
 660     }
 661 }
 662
 663 #[stable]
 664 impl<A: fmt::Show> fmt::Show for DList<A> {
 665     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 666         try!(write!(f, "DList ["));
 667
 668         for (i, e) in self.iter().enumerate() {
 669             if i != 0 { try!(write!(f, ", ")); }
 670             try!(write!(f, "{:?}", *e));
 671         }
 672
 673         write!(f, "]")
 674     }
 675 }
 676
 677 #[stable]
 678 impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for DList<A> {
 679     fn hash(&self, state: &mut S) {
 680         self.len().hash(state);
 681         for elt in self.iter() {
 682             elt.hash(state);
 683         }
 684     }
 685 }
 686
 687 #[cfg(test)]
 688 mod tests {
 689     use prelude::*;
 690     use std::rand;
 691     use std::hash::{self, SipHasher};
 692     use std::thread::Thread;
 693     use test::Bencher;
 694     use test;
 695
 696     use super::{DList, Node};
 697
 698     pub fn check_links<T>(list: &DList<T>) {
 699         let mut len = 0u;
 700         let mut last_ptr: Option<&Node<T>> = None;
 701         let mut node_ptr: &Node<T>;
 702         match list.list_head {
 703             None => { assert_eq!(0u, list.length); return }
 704             Some(ref node) => node_ptr = &**node,
 705         }
 706         loop {
 707             match (last_ptr, node_ptr.prev.resolve_immut()) {
 708                 (None   , None      ) => {}
 709                 (None   , _         ) => panic!("prev link for list_head"),
 710                 (Some(p), Some(pptr)) => {
 711                     assert_eq!(p as *const Node<T>, pptr as *const Node<T>);
 712                 }
 713                 _ => panic!("prev link is none, not good"),
 714             }
 715             match node_ptr.next {
 716                 Some(ref next) => {
 717                     last_ptr = Some(node_ptr);
 718                     node_ptr = &**next;
 719                     len += 1;
 720                 }
 721                 None => {
 722                     len += 1;
 723                     break;
 724                 }
 725             }
 726         }
 727         assert_eq!(len, list.length);
 728     }
 729
 730     #[test]
 731     fn test_basic() {
 732         let mut m: DList<Box<int>> = DList::new();
 733         assert_eq!(m.pop_front(), None);
 734         assert_eq!(m.pop_back(), None);
 735         assert_eq!(m.pop_front(), None);
 736         m.push_front(box 1);
 737         assert_eq!(m.pop_front(), Some(box 1));
 738         m.push_back(box 2);
 739         m.push_back(box 3);
 740         assert_eq!(m.len(), 2);
 741         assert_eq!(m.pop_front(), Some(box 2));
 742         assert_eq!(m.pop_front(), Some(box 3));
 743         assert_eq!(m.len(), 0);
 744         assert_eq!(m.pop_front(), None);
 745         m.push_back(box 1);
 746         m.push_back(box 3);
 747         m.push_back(box 5);
 748         m.push_back(box 7);
 749         assert_eq!(m.pop_front(), Some(box 1));
 750
 751         let mut n = DList::new();
 752         n.push_front(2i);
 753         n.push_front(3);
 754         {
 755             assert_eq!(n.front().unwrap(), &3);
 756             let x = n.front_mut().unwrap();
 757             assert_eq!(*x, 3);
 758             *x = 0;
 759         }
 760         {
 761             assert_eq!(n.back().unwrap(), &2);
 762             let y = n.back_mut().unwrap();
 763             assert_eq!(*y, 2);
 764             *y = 1;
 765         }
 766         assert_eq!(n.pop_front(), Some(0));
 767         assert_eq!(n.pop_front(), Some(1));
 768     }
 769
 770     #[cfg(test)]
 771     fn generate_test() -> DList<int> {
 772         list_from(&[0i,1,2,3,4,5,6])
 773     }
 774
 775     #[cfg(test)]
 776     fn list_from<T: Clone>(v: &[T]) -> DList<T> {
 777         v.iter().map(|x| (*x).clone()).collect()
 778     }
 779
 780     #[test]
 781     fn test_iterator() {
 782         let m = generate_test();
 783         for (i, elt) in m.iter().enumerate() {
 784             assert_eq!(i as int, *elt);
 785         }
 786         let mut n = DList::new();
 787         assert_eq!(n.iter().next(), None);
 788         n.push_front(4i);
 789         let mut it = n.iter();
 790         assert_eq!(it.size_hint(), (1, Some(1)));
 791         assert_eq!(it.next().unwrap(), &4);
 792         assert_eq!(it.size_hint(), (0, Some(0)));
 793         assert_eq!(it.next(), None);
 794     }
 795
 796     #[test]
 797     fn test_iterator_clone() {
 798         let mut n = DList::new();
 799         n.push_back(2i);
 800         n.push_back(3);
 801         n.push_back(4);
 802         let mut it = n.iter();
 803         it.next();
 804         let mut jt = it.clone();
 805         assert_eq!(it.next(), jt.next());
 806         assert_eq!(it.next_back(), jt.next_back());
 807         assert_eq!(it.next(), jt.next());
 808     }
 809
 810     #[test]
 811     fn test_iterator_double_end() {
 812         let mut n = DList::new();
 813         assert_eq!(n.iter().next(), None);
 814         n.push_front(4i);
 815         n.push_front(5);
 816         n.push_front(6);
 817         let mut it = n.iter();
 818         assert_eq!(it.size_hint(), (3, Some(3)));
 819         assert_eq!(it.next().unwrap(), &6);
 820         assert_eq!(it.size_hint(), (2, Some(2)));
 821         assert_eq!(it.next_back().unwrap(), &4);
 822         assert_eq!(it.size_hint(), (1, Some(1)));
 823         assert_eq!(it.next_back().unwrap(), &5);
 824         assert_eq!(it.next_back(), None);
 825         assert_eq!(it.next(), None);
 826     }
 827
 828     #[test]
 829     fn test_rev_iter() {
 830         let m = generate_test();
 831         for (i, elt) in m.iter().rev().enumerate() {
 832             assert_eq!((6 - i) as int, *elt);
 833         }
 834         let mut n = DList::new();
 835         assert_eq!(n.iter().rev().next(), None);
 836         n.push_front(4i);
 837         let mut it = n.iter().rev();
 838         assert_eq!(it.size_hint(), (1, Some(1)));
 839         assert_eq!(it.next().unwrap(), &4);
 840         assert_eq!(it.size_hint(), (0, Some(0)));
 841         assert_eq!(it.next(), None);
 842     }
 843
 844     #[test]
 845     fn test_mut_iter() {
 846         let mut m = generate_test();
 847         let mut len = m.len();
 848         for (i, elt) in m.iter_mut().enumerate() {
 849             assert_eq!(i as int, *elt);
 850             len -= 1;
 851         }
 852         assert_eq!(len, 0);
 853         let mut n = DList::new();
 854         assert!(n.iter_mut().next().is_none());
 855         n.push_front(4i);
 856         n.push_back(5);
 857         let mut it = n.iter_mut();
 858         assert_eq!(it.size_hint(), (2, Some(2)));
 859         assert!(it.next().is_some());
 860         assert!(it.next().is_some());
 861         assert_eq!(it.size_hint(), (0, Some(0)));
 862         assert!(it.next().is_none());
 863     }
 864
 865     #[test]
 866     fn test_iterator_mut_double_end() {
 867         let mut n = DList::new();
 868         assert!(n.iter_mut().next_back().is_none());
 869         n.push_front(4i);
 870         n.push_front(5);
 871         n.push_front(6);
 872         let mut it = n.iter_mut();
 873         assert_eq!(it.size_hint(), (3, Some(3)));
 874         assert_eq!(*it.next().unwrap(), 6);
 875         assert_eq!(it.size_hint(), (2, Some(2)));
 876         assert_eq!(*it.next_back().unwrap(), 4);
 877         assert_eq!(it.size_hint(), (1, Some(1)));
 878         assert_eq!(*it.next_back().unwrap(), 5);
 879         assert!(it.next_back().is_none());
 880         assert!(it.next().is_none());
 881     }
 882
 883     #[test]
 884     fn test_insert_prev() {
 885         let mut m = list_from(&[0i,2,4,6,8]);
 886         let len = m.len();
 887         {
 888             let mut it = m.iter_mut();
 889             it.insert_next(-2);
 890             loop {
 891                 match it.next() {
 892                     None => break,
 893                     Some(elt) => {
 894                         it.insert_next(*elt + 1);
 895                         match it.peek_next() {
 896                             Some(x) => assert_eq!(*x, *elt + 2),
 897                             None => assert_eq!(8, *elt),
 898                         }
 899                     }
 900                 }
 901             }
 902             it.insert_next(0);
 903             it.insert_next(1);
 904         }
 905         check_links(&m);
 906         assert_eq!(m.len(), 3 + len * 2);
 907         assert_eq!(m.into_iter().collect::<Vec<int>>(), vec![-2,0,1,2,3,4,5,6,7,8,9,0,1]);
 908     }
 909
 910     #[test]
 911     fn test_mut_rev_iter() {
 912         let mut m = generate_test();
 913         for (i, elt) in m.iter_mut().rev().enumerate() {
 914             assert_eq!((6-i) as int, *elt);
 915         }
 916         let mut n = DList::new();
 917         assert!(n.iter_mut().rev().next().is_none());
 918         n.push_front(4i);
 919         let mut it = n.iter_mut().rev();
 920         assert!(it.next().is_some());
 921         assert!(it.next().is_none());
 922     }
 923
 924     #[test]
 925     fn test_send() {
 926         let n = list_from(&[1i,2,3]);
 927         Thread::scoped(move || {
 928             check_links(&n);
 929             let a: &[_] = &[&1,&2,&3];
 930             assert_eq!(a, n.iter().collect::<Vec<&int>>());
 931         }).join().ok().unwrap();
 932     }
 933
 934     #[test]
 935     fn test_eq() {
 936         let mut n: DList<u8> = list_from(&[]);
 937         let mut m = list_from(&[]);
 938         assert!(n == m);
 939         n.push_front(1);
 940         assert!(n != m);
 941         m.push_back(1);
 942         assert!(n == m);
 943
 944         let n = list_from(&[2i,3,4]);
 945         let m = list_from(&[1i,2,3]);
 946         assert!(n != m);
 947     }
 948
 949     #[test]
 950     fn test_hash() {
 951       let mut x = DList::new();
 952       let mut y = DList::new();
 953
 954       assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
 955
 956       x.push_back(1i);
 957       x.push_back(2);
 958       x.push_back(3);
 959
 960       y.push_front(3i);
 961       y.push_front(2);
 962       y.push_front(1);
 963
 964       assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
 965     }
 966
 967     #[test]
 968     fn test_ord() {
 969         let n: DList<int> = list_from(&[]);
 970         let m = list_from(&[1i,2,3]);
 971         assert!(n < m);
 972         assert!(m > n);
 973         assert!(n <= n);
 974         assert!(n >= n);
 975     }
 976
 977     #[test]
 978     fn test_ord_nan() {
 979         let nan = 0.0f64/0.0;
 980         let n = list_from(&[nan]);
 981         let m = list_from(&[nan]);
 982         assert!(!(n < m));
 983         assert!(!(n > m));
 984         assert!(!(n <= m));
 985         assert!(!(n >= m));
 986
 987         let n = list_from(&[nan]);
 988         let one = list_from(&[1.0f64]);
 989         assert!(!(n < one));
 990         assert!(!(n > one));
 991         assert!(!(n <= one));
 992         assert!(!(n >= one));
 993
 994         let u = list_from(&[1.0f64,2.0,nan]);
 995         let v = list_from(&[1.0f64,2.0,3.0]);
 996         assert!(!(u < v));
 997         assert!(!(u > v));
 998         assert!(!(u <= v));
 999         assert!(!(u >= v));
1000
1001         let s = list_from(&[1.0f64,2.0,4.0,2.0]);
1002         let t = list_from(&[1.0f64,2.0,3.0,2.0]);
1003         assert!(!(s < t));
1004         assert!(s > one);
1005         assert!(!(s <= one));
1006         assert!(s >= one);
1007     }
1008
1009     #[test]
1010     fn test_fuzz() {
1011         for _ in range(0u, 25) {
1012             fuzz_test(3);
1013             fuzz_test(16);
1014             fuzz_test(189);
1015         }
1016     }
1017
1018     #[test]
1019     fn test_show() {
1020         let list: DList<int> = range(0i, 10).collect();
1021         assert_eq!(format!("{:?}", list), "DList [0i, 1i, 2i, 3i, 4i, 5i, 6i, 7i, 8i, 9i]");
1022
1023         let list: DList<&str> = vec!["just", "one", "test", "more"].iter()
1024                                                                    .map(|&s| s)
1025                                                                    .collect();
1026         assert_eq!(format!("{:?}", list), "DList [\"just\", \"one\", \"test\", \"more\"]");
1027     }
1028
1029     #[cfg(test)]
1030     fn fuzz_test(sz: int) {
1031         let mut m: DList<int> = DList::new();
1032         let mut v = vec![];
1033         for i in range(0, sz) {
1034             check_links(&m);
1035             let r: u8 = rand::random();
1036             match r % 6 {
1037                 0 => {
1038                     m.pop_back();
1039                     v.pop();
1040                 }
1041                 1 => {
1042                     if !v.is_empty() {
1043                         m.pop_front();
1044                         v.remove(0);
1045                     }
1046                 }
1047                 2 | 4 =>  {
1048                     m.push_front(-i);
1049                     v.insert(0, -i);
1050                 }
1051                 3 | 5 | _ => {
1052                     m.push_back(i);
1053                     v.push(i);
1054                 }
1055             }
1056         }
1057
1058         check_links(&m);
1059
1060         let mut i = 0u;
1061         for (a, &b) in m.into_iter().zip(v.iter()) {
1062             i += 1;
1063             assert_eq!(a, b);
1064         }
1065         assert_eq!(i, v.len());
1066     }
1067
1068     #[allow(deprecated)]
1069     #[test]
1070     fn test_append() {
1071         {
1072             let mut m = DList::new();
1073             let mut n = DList::new();
1074             n.push_back(2i);
1075             m.append(n);
1076             assert_eq!(m.len(), 1);
1077             assert_eq!(m.pop_back(), Some(2));
1078             check_links(&m);
1079         }
1080         {
1081             let mut m = DList::new();
1082             let n = DList::new();
1083             m.push_back(2i);
1084             m.append(n);
1085             assert_eq!(m.len(), 1);
1086             assert_eq!(m.pop_back(), Some(2));
1087             check_links(&m);
1088         }
1089
1090         let v = vec![1i,2,3,4,5];
1091         let u = vec![9i,8,1,2,3,4,5];
1092         let mut m = list_from(v.as_slice());
1093         m.append(list_from(u.as_slice()));
1094         check_links(&m);
1095         let mut sum = v;
1096         sum.push_all(u.as_slice());
1097         assert_eq!(sum.len(), m.len());
1098         for elt in sum.into_iter() {
1099             assert_eq!(m.pop_front(), Some(elt))
1100         }
1101     }
1102
1103     #[bench]
1104     fn bench_collect_into(b: &mut test::Bencher) {
1105         let v = &[0i; 64];
1106         b.iter(|| {
1107             let _: DList<int> = v.iter().map(|x| *x).collect();
1108         })
1109     }
1110
1111     #[bench]
1112     fn bench_push_front(b: &mut test::Bencher) {
1113         let mut m: DList<int> = DList::new();
1114         b.iter(|| {
1115             m.push_front(0);
1116         })
1117     }
1118
1119     #[bench]
1120     fn bench_push_back(b: &mut test::Bencher) {
1121         let mut m: DList<int> = DList::new();
1122         b.iter(|| {
1123             m.push_back(0);
1124         })
1125     }
1126
1127     #[bench]
1128     fn bench_push_back_pop_back(b: &mut test::Bencher) {
1129         let mut m: DList<int> = DList::new();
1130         b.iter(|| {
1131             m.push_back(0);
1132             m.pop_back();
1133         })
1134     }
1135
1136     #[bench]
1137     fn bench_push_front_pop_front(b: &mut test::Bencher) {
1138         let mut m: DList<int> = DList::new();
1139         b.iter(|| {
1140             m.push_front(0);
1141             m.pop_front();
1142         })
1143     }
1144
1145     #[bench]
1146     fn bench_iter(b: &mut test::Bencher) {
1147         let v = &[0i; 128];
1148         let m: DList<int> = v.iter().map(|&x|x).collect();
1149         b.iter(|| {
1150             assert!(m.iter().count() == 128);
1151         })
1152     }
1153     #[bench]
1154     fn bench_iter_mut(b: &mut test::Bencher) {
1155         let v = &[0i; 128];
1156         let mut m: DList<int> = v.iter().map(|&x|x).collect();
1157         b.iter(|| {
1158             assert!(m.iter_mut().count() == 128);
1159         })
1160     }
1161     #[bench]
1162     fn bench_iter_rev(b: &mut test::Bencher) {
1163         let v = &[0i; 128];
1164         let m: DList<int> = v.iter().map(|&x|x).collect();
1165         b.iter(|| {
1166             assert!(m.iter().rev().count() == 128);
1167         })
1168     }
1169     #[bench]
1170     fn bench_iter_mut_rev(b: &mut test::Bencher) {
1171         let v = &[0i; 128];
1172         let mut m: DList<int> = v.iter().map(|&x|x).collect();
1173         b.iter(|| {
1174             assert!(m.iter_mut().rev().count() == 128);
1175         })
1176     }
1177 }