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