src/libextra/dlist.rs

   1 // Copyright 2012-2013 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 //! extra::container::Deque`.
  17
  18
  19 // DList is constructed like a singly-linked list over the field `next`.
  20 // including the last link being None; each Node owns its `next` field.
  21 //
  22 // Backlinks over DList::prev are raw pointers that form a full chain in
  23 // the reverse direction.
  24
  25 use std::cast;
  26 use std::ptr;
  27 use std::util;
  28 use std::iterator::{FromIterator, InvertIterator};
  29
  30 use container::Deque;
  31
  32 /// A doubly-linked list.
  33 pub struct DList<T> {
  34     priv length: uint,
  35     priv list_head: Link<T>,
  36     priv list_tail: Rawlink<Node<T>>,
  37 }
  38
  39 type Link<T> = Option<~Node<T>>;
  40 struct Rawlink<T> { priv p: *mut T }
  41
  42 struct Node<T> {
  43     priv next: Link<T>,
  44     priv prev: Rawlink<Node<T>>,
  45     priv value: T,
  46 }
  47
  48 /// Double-ended DList iterator
  49 #[deriving(Clone)]
  50 pub struct DListIterator<'self, T> {
  51     priv head: &'self Link<T>,
  52     priv tail: Rawlink<Node<T>>,
  53     priv nelem: uint,
  54 }
  55
  56 /// Double-ended mutable DList iterator
  57 pub struct MutDListIterator<'self, T> {
  58     priv list: &'self mut DList<T>,
  59     priv head: Rawlink<Node<T>>,
  60     priv tail: Rawlink<Node<T>>,
  61     priv nelem: uint,
  62 }
  63
  64 /// DList consuming iterator
  65 #[deriving(Clone)]
  66 pub struct ConsumeIterator<T> {
  67     priv list: DList<T>
  68 }
  69
  70 /// Rawlink is a type like Option<T> but for holding a raw pointer
  71 impl<T> Rawlink<T> {
  72     /// Like Option::None for Rawlink
  73     fn none() -> Rawlink<T> {
  74         Rawlink{p: ptr::mut_null()}
  75     }
  76
  77     /// Like Option::Some for Rawlink
  78     fn some(n: &mut T) -> Rawlink<T> {
  79         Rawlink{p: ptr::to_mut_unsafe_ptr(n)}
  80     }
  81
  82     /// Convert the `Rawlink` into an Option value
  83     fn resolve_immut(&self) -> Option<&T> {
  84         unsafe { self.p.to_option() }
  85     }
  86
  87     /// Convert the `Rawlink` into an Option value
  88     fn resolve(&mut self) -> Option<&mut T> {
  89         if self.p.is_null() {
  90             None
  91         } else {
  92             Some(unsafe { cast::transmute(self.p) })
  93         }
  94     }
  95 }
  96
  97 impl<T> Clone for Rawlink<T> {
  98     #[inline]
  99     fn clone(&self) -> Rawlink<T> {
 100         Rawlink{p: self.p}
 101     }
 102 }
 103
 104 impl<T> Node<T> {
 105     fn new(v: T) -> Node<T> {
 106         Node{value: v, next: None, prev: Rawlink::none()}
 107     }
 108 }
 109
 110 /// Set the .prev field on `next`, then return `Some(next)`
 111 fn link_with_prev<T>(mut next: ~Node<T>, prev: Rawlink<Node<T>>) -> Link<T> {
 112     next.prev = prev;
 113     Some(next)
 114 }
 115
 116 impl<T> Container for DList<T> {
 117     /// O(1)
 118     #[inline]
 119     fn is_empty(&self) -> bool {
 120         self.list_head.is_none()
 121     }
 122     /// O(1)
 123     #[inline]
 124     fn len(&self) -> uint {
 125         self.length
 126     }
 127 }
 128
 129 impl<T> Mutable for DList<T> {
 130     /// Remove all elements from the DList
 131     ///
 132     /// O(N)
 133     #[inline]
 134     fn clear(&mut self) {
 135         *self = DList::new()
 136     }
 137 }
 138
 139 // private methods
 140 impl<T> DList<T> {
 141     /// Add a Node first in the list
 142     #[inline]
 143     fn push_front_node(&mut self, mut new_head: ~Node<T>) {
 144         match self.list_head {
 145             None => {
 146                 self.list_tail = Rawlink::some(new_head);
 147                 self.list_head = link_with_prev(new_head, Rawlink::none());
 148             }
 149             Some(ref mut head) => {
 150                 new_head.prev = Rawlink::none();
 151                 head.prev = Rawlink::some(new_head);
 152                 util::swap(head, &mut new_head);
 153                 head.next = Some(new_head);
 154             }
 155         }
 156         self.length += 1;
 157     }
 158
 159     /// Remove the first Node and return it, or None if the list is empty
 160     #[inline]
 161     fn pop_front_node(&mut self) -> Option<~Node<T>> {
 162         do self.list_head.take().map_consume |mut front_node| {
 163             self.length -= 1;
 164             match front_node.next.take() {
 165                 Some(node) => self.list_head = link_with_prev(node, Rawlink::none()),
 166                 None => self.list_tail = Rawlink::none()
 167             }
 168             front_node
 169         }
 170     }
 171
 172     /// Add a Node last in the list
 173     #[inline]
 174     fn push_back_node(&mut self, mut new_tail: ~Node<T>) {
 175         match self.list_tail.resolve() {
 176             None => return self.push_front_node(new_tail),
 177             Some(tail) => {
 178                 self.list_tail = Rawlink::some(new_tail);
 179                 tail.next = link_with_prev(new_tail, Rawlink::some(tail));
 180             }
 181         }
 182         self.length += 1;
 183     }
 184
 185     /// Remove the last Node and return it, or None if the list is empty
 186     #[inline]
 187     fn pop_back_node(&mut self) -> Option<~Node<T>> {
 188         do self.list_tail.resolve().map_consume_default(None) |tail| {
 189             self.length -= 1;
 190             self.list_tail = tail.prev;
 191             match tail.prev.resolve() {
 192                 None => self.list_head.take(),
 193                 Some(tail_prev) => tail_prev.next.take()
 194             }
 195         }
 196     }
 197 }
 198
 199 impl<T> Deque<T> for DList<T> {
 200     /// Provide a reference to the front element, or None if the list is empty
 201     #[inline]
 202     fn front<'a>(&'a self) -> Option<&'a T> {
 203         self.list_head.map(|head| &head.value)
 204     }
 205
 206     /// Provide a mutable reference to the front element, or None if the list is empty
 207     #[inline]
 208     fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
 209         self.list_head.map_mut(|head| &mut head.value)
 210     }
 211
 212     /// Provide a reference to the back element, or None if the list is empty
 213     #[inline]
 214     fn back<'a>(&'a self) -> Option<&'a T> {
 215         self.list_tail.resolve_immut().map(|tail| &tail.value)
 216     }
 217
 218     /// Provide a mutable reference to the back element, or None if the list is empty
 219     #[inline]
 220     fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
 221         self.list_tail.resolve().map_mut(|tail| &mut tail.value)
 222     }
 223
 224     /// Add an element first in the list
 225     ///
 226     /// O(1)
 227     fn push_front(&mut self, elt: T) {
 228         self.push_front_node(~Node::new(elt))
 229     }
 230
 231     /// Remove the first element and return it, or None if the list is empty
 232     ///
 233     /// O(1)
 234     fn pop_front(&mut self) -> Option<T> {
 235         self.pop_front_node().map_consume(|~Node{value, _}| value)
 236     }
 237
 238     /// Add an element last in the list
 239     ///
 240     /// O(1)
 241     fn push_back(&mut self, elt: T) {
 242         self.push_back_node(~Node::new(elt))
 243     }
 244
 245     /// Remove the last element and return it, or None if the list is empty
 246     ///
 247     /// O(1)
 248     fn pop_back(&mut self) -> Option<T> {
 249         self.pop_back_node().map_consume(|~Node{value, _}| value)
 250     }
 251 }
 252
 253 impl<T> DList<T> {
 254     /// Create an empty DList
 255     #[inline]
 256     pub fn new() -> DList<T> {
 257         DList{list_head: None, list_tail: Rawlink::none(), length: 0}
 258     }
 259
 260     /// Move the last element to the front of the list.
 261     ///
 262     /// If the list is empty, do nothing.
 263     #[inline]
 264     pub fn rotate_to_front(&mut self) {
 265         do self.pop_back_node().map_consume |tail| {
 266             self.push_front_node(tail)
 267         };
 268     }
 269
 270     /// Move the first element to the back of the list.
 271     ///
 272     /// If the list is empty, do nothing.
 273     #[inline]
 274     pub fn rotate_to_back(&mut self) {
 275         do self.pop_front_node().map_consume |head| {
 276             self.push_back_node(head)
 277         };
 278     }
 279
 280     /// Add all elements from `other` to the end of the list
 281     ///
 282     /// O(1)
 283     pub fn append(&mut self, other: DList<T>) {
 284         match self.list_tail.resolve() {
 285             None => *self = other,
 286             Some(tail) => {
 287                 match other {
 288                     DList{list_head: None, _} => return,
 289                     DList{list_head: Some(node), list_tail: o_tail, length: o_length} => {
 290                         tail.next = link_with_prev(node, self.list_tail);
 291                         self.list_tail = o_tail;
 292                         self.length += o_length;
 293                     }
 294                 }
 295             }
 296         }
 297     }
 298
 299     /// Add all elements from `other` to the beginning of the list
 300     ///
 301     /// O(1)
 302     #[inline]
 303     pub fn prepend(&mut self, mut other: DList<T>) {
 304         util::swap(self, &mut other);
 305         self.append(other);
 306     }
 307
 308     /// Insert `elt` before the first `x` in the list where `f(x, elt)` is true,
 309     /// or at the end.
 310     ///
 311     /// O(N)
 312     pub fn insert_when(&mut self, elt: T, f: &fn(&T, &T) -> bool) {
 313         {
 314             let mut it = self.mut_iter();
 315             loop {
 316                 match it.peek_next() {
 317                     None => break,
 318                     Some(x) => if f(x, &elt) { break }
 319                 }
 320                 it.next();
 321             }
 322             it.insert_next(elt);
 323         }
 324     }
 325
 326     /// Merge DList `other` into this DList, using the function `f`.
 327     /// Iterate the both DList with `a` from self and `b` from `other`, and
 328     /// put `a` in the result if `f(a, b)` is true, else `b`.
 329     ///
 330     /// O(max(N, M))
 331     pub fn merge(&mut self, mut other: DList<T>, f: &fn(&T, &T) -> bool) {
 332         {
 333             let mut it = self.mut_iter();
 334             loop {
 335                 let take_a = match (it.peek_next(), other.front()) {
 336                     (_   , None) => return,
 337                     (None, _   ) => break,
 338                     (Some(ref mut x), Some(y)) => f(*x, y),
 339                 };
 340                 if take_a {
 341                     it.next();
 342                 } else {
 343                     it.insert_next_node(other.pop_front_node().unwrap());
 344                 }
 345             }
 346         }
 347         self.append(other);
 348     }
 349
 350
 351     /// Provide a forward iterator
 352     #[inline]
 353     pub fn iter<'a>(&'a self) -> DListIterator<'a, T> {
 354         DListIterator{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
 355     }
 356
 357     /// Provide a reverse iterator
 358     #[inline]
 359     pub fn rev_iter<'a>(&'a self) -> InvertIterator<&'a T, DListIterator<'a, T>> {
 360         self.iter().invert()
 361     }
 362
 363     /// Provide a forward iterator with mutable references
 364     #[inline]
 365     pub fn mut_iter<'a>(&'a mut self) -> MutDListIterator<'a, T> {
 366         let head_raw = match self.list_head {
 367             Some(ref mut h) => Rawlink::some(*h),
 368             None => Rawlink::none(),
 369         };
 370         MutDListIterator{
 371             nelem: self.len(),
 372             head: head_raw,
 373             tail: self.list_tail,
 374             list: self
 375         }
 376     }
 377     /// Provide a reverse iterator with mutable references
 378     #[inline]
 379     pub fn mut_rev_iter<'a>(&'a mut self) -> InvertIterator<&'a mut T,
 380                                                 MutDListIterator<'a, T>> {
 381         self.mut_iter().invert()
 382     }
 383
 384
 385     /// Consume the list into an iterator yielding elements by value
 386     #[inline]
 387     pub fn consume_iter(self) -> ConsumeIterator<T> {
 388         ConsumeIterator{list: self}
 389     }
 390
 391     /// Consume the list into an iterator yielding elements by value, in reverse
 392     #[inline]
 393     pub fn consume_rev_iter(self) -> InvertIterator<T, ConsumeIterator<T>> {
 394         self.consume_iter().invert()
 395     }
 396 }
 397
 398 impl<T: Ord> DList<T> {
 399     /// Insert `elt` sorted in ascending order
 400     ///
 401     /// O(N)
 402     #[inline]
 403     pub fn insert_ordered(&mut self, elt: T) {
 404         self.insert_when(elt, |a, b| a >= b)
 405     }
 406 }
 407
 408 impl<'self, A> Iterator<&'self A> for DListIterator<'self, A> {
 409     #[inline]
 410     fn next(&mut self) -> Option<&'self A> {
 411         if self.nelem == 0 {
 412             return None;
 413         }
 414         do self.head.map |head| {
 415             self.nelem -= 1;
 416             self.head = &head.next;
 417             &head.value
 418         }
 419     }
 420
 421     #[inline]
 422     fn size_hint(&self) -> (uint, Option<uint>) {
 423         (self.nelem, Some(self.nelem))
 424     }
 425 }
 426
 427 impl<'self, A> DoubleEndedIterator<&'self A> for DListIterator<'self, A> {
 428     #[inline]
 429     fn next_back(&mut self) -> Option<&'self A> {
 430         if self.nelem == 0 {
 431             return None;
 432         }
 433         do self.tail.resolve().map_consume |prev| {
 434             self.nelem -= 1;
 435             self.tail = prev.prev;
 436             &prev.value
 437         }
 438     }
 439 }
 440
 441 impl<'self, A> Iterator<&'self mut A> for MutDListIterator<'self, A> {
 442     #[inline]
 443     fn next(&mut self) -> Option<&'self mut A> {
 444         if self.nelem == 0 {
 445             return None;
 446         }
 447         do self.head.resolve().map_consume |next| {
 448             self.nelem -= 1;
 449             self.head = match next.next {
 450                 Some(ref mut node) => Rawlink::some(&mut **node),
 451                 None => Rawlink::none(),
 452             };
 453             &mut next.value
 454         }
 455     }
 456
 457     #[inline]
 458     fn size_hint(&self) -> (uint, Option<uint>) {
 459         (self.nelem, Some(self.nelem))
 460     }
 461 }
 462
 463 impl<'self, A> DoubleEndedIterator<&'self mut A> for MutDListIterator<'self, A> {
 464     #[inline]
 465     fn next_back(&mut self) -> Option<&'self mut A> {
 466         if self.nelem == 0 {
 467             return None;
 468         }
 469         do self.tail.resolve().map_consume |prev| {
 470             self.nelem -= 1;
 471             self.tail = prev.prev;
 472             &mut prev.value
 473         }
 474     }
 475 }
 476
 477
 478 /// Allow mutating the DList while iterating
 479 pub trait ListInsertion<A> {
 480     /// Insert `elt` just after to the element most recently returned by `.next()`
 481     ///
 482     /// The inserted element does not appear in the iteration.
 483     fn insert_next(&mut self, elt: A);
 484
 485     /// Provide a reference to the next element, without changing the iterator
 486     fn peek_next<'a>(&'a mut self) -> Option<&'a mut A>;
 487 }
 488
 489 // private methods for MutDListIterator
 490 impl<'self, A> MutDListIterator<'self, A> {
 491     fn insert_next_node(&mut self, mut ins_node: ~Node<A>) {
 492         // Insert before `self.head` so that it is between the
 493         // previously yielded element and self.head.
 494         //
 495         // The inserted node will not appear in further iteration.
 496         match self.head.resolve() {
 497             None => { self.list.push_back_node(ins_node); }
 498             Some(node) => {
 499                 let prev_node = match node.prev.resolve() {
 500                     None => return self.list.push_front_node(ins_node),
 501                     Some(prev) => prev,
 502                 };
 503                 let node_own = prev_node.next.take_unwrap();
 504                 ins_node.next = link_with_prev(node_own, Rawlink::some(ins_node));
 505                 prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
 506                 self.list.length += 1;
 507             }
 508         }
 509     }
 510 }
 511
 512 impl<'self, A> ListInsertion<A> for MutDListIterator<'self, A> {
 513     #[inline]
 514     fn insert_next(&mut self, elt: A) {
 515         self.insert_next_node(~Node::new(elt))
 516     }
 517
 518     #[inline]
 519     fn peek_next<'a>(&'a mut self) -> Option<&'a mut A> {
 520         if self.nelem == 0 {
 521             return None
 522         }
 523         self.head.resolve().map_consume(|head| &mut head.value)
 524     }
 525 }
 526
 527 impl<A> Iterator<A> for ConsumeIterator<A> {
 528     #[inline]
 529     fn next(&mut self) -> Option<A> { self.list.pop_front() }
 530
 531     #[inline]
 532     fn size_hint(&self) -> (uint, Option<uint>) {
 533         (self.list.length, Some(self.list.length))
 534     }
 535 }
 536
 537 impl<A> DoubleEndedIterator<A> for ConsumeIterator<A> {
 538     #[inline]
 539     fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
 540 }
 541
 542 impl<A, T: Iterator<A>> FromIterator<A, T> for DList<A> {
 543     fn from_iterator(iterator: &mut T) -> DList<A> {
 544         let mut ret = DList::new();
 545         for iterator.advance |elt| { ret.push_back(elt); }
 546         ret
 547     }
 548 }
 549
 550 impl<A: Eq> Eq for DList<A> {
 551     fn eq(&self, other: &DList<A>) -> bool {
 552         self.len() == other.len() &&
 553             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
 554     }
 555
 556     #[inline]
 557     fn ne(&self, other: &DList<A>) -> bool {
 558         !self.eq(other)
 559     }
 560 }
 561
 562 impl<A: Clone> Clone for DList<A> {
 563     fn clone(&self) -> DList<A> {
 564         self.iter().transform(|x| x.clone()).collect()
 565     }
 566 }
 567
 568 #[cfg(test)]
 569 pub fn check_links<T>(list: &DList<T>) {
 570     let mut len = 0u;
 571     let mut last_ptr: Option<&Node<T>> = None;
 572     let mut node_ptr: &Node<T>;
 573     match list.list_head {
 574         None => { assert_eq!(0u, list.length); return }
 575         Some(ref node) => node_ptr = &**node,
 576     }
 577     loop {
 578         match (last_ptr, node_ptr.prev.resolve_immut()) {
 579             (None   , None      ) => {}
 580             (None   , _         ) => fail!("prev link for list_head"),
 581             (Some(p), Some(pptr)) => {
 582                 assert_eq!(p as *Node<T>, pptr as *Node<T>);
 583             }
 584             _ => fail!("prev link is none, not good"),
 585         }
 586         match node_ptr.next {
 587             Some(ref next) => {
 588                 last_ptr = Some(node_ptr);
 589                 node_ptr = &**next;
 590                 len += 1;
 591             }
 592             None => {
 593                 len += 1;
 594                 break;
 595             }
 596         }
 597     }
 598     assert_eq!(len, list.length);
 599 }
 600
 601 #[cfg(test)]
 602 mod tests {
 603     use super::*;
 604     use std::rand;
 605     use std::int;
 606     use extra::test;
 607
 608     #[test]
 609     fn test_basic() {
 610         let mut m = DList::new::<~int>();
 611         assert_eq!(m.pop_front(), None);
 612         assert_eq!(m.pop_back(), None);
 613         assert_eq!(m.pop_front(), None);
 614         m.push_front(~1);
 615         assert_eq!(m.pop_front(), Some(~1));
 616         m.push_back(~2);
 617         m.push_back(~3);
 618         assert_eq!(m.len(), 2);
 619         assert_eq!(m.pop_front(), Some(~2));
 620         assert_eq!(m.pop_front(), Some(~3));
 621         assert_eq!(m.len(), 0);
 622         assert_eq!(m.pop_front(), None);
 623         m.push_back(~1);
 624         m.push_back(~3);
 625         m.push_back(~5);
 626         m.push_back(~7);
 627         assert_eq!(m.pop_front(), Some(~1));
 628
 629         let mut n = DList::new();
 630         n.push_front(2);
 631         n.push_front(3);
 632         {
 633             assert_eq!(n.front().unwrap(), &3);
 634             let x = n.front_mut().unwrap();
 635             assert_eq!(*x, 3);
 636             *x = 0;
 637         }
 638         {
 639             assert_eq!(n.back().unwrap(), &2);
 640             let y = n.back_mut().unwrap();
 641             assert_eq!(*y, 2);
 642             *y = 1;
 643         }
 644         assert_eq!(n.pop_front(), Some(0));
 645         assert_eq!(n.pop_front(), Some(1));
 646     }
 647
 648     #[cfg(test)]
 649     fn generate_test() -> DList<int> {
 650         list_from(&[0,1,2,3,4,5,6])
 651     }
 652
 653     #[cfg(test)]
 654     fn list_from<T: Clone>(v: &[T]) -> DList<T> {
 655         v.iter().transform(|x| (*x).clone()).collect()
 656     }
 657
 658     #[test]
 659     fn test_append() {
 660         {
 661             let mut m = DList::new();
 662             let mut n = DList::new();
 663             n.push_back(2);
 664             m.append(n);
 665             assert_eq!(m.len(), 1);
 666             assert_eq!(m.pop_back(), Some(2));
 667             check_links(&m);
 668         }
 669         {
 670             let mut m = DList::new();
 671             let n = DList::new();
 672             m.push_back(2);
 673             m.append(n);
 674             assert_eq!(m.len(), 1);
 675             assert_eq!(m.pop_back(), Some(2));
 676             check_links(&m);
 677         }
 678
 679         let v = ~[1,2,3,4,5];
 680         let u = ~[9,8,1,2,3,4,5];
 681         let mut m = list_from(v);
 682         m.append(list_from(u));
 683         check_links(&m);
 684         let sum = v + u;
 685         assert_eq!(sum.len(), m.len());
 686         for sum.consume_iter().advance |elt| {
 687             assert_eq!(m.pop_front(), Some(elt))
 688         }
 689     }
 690
 691     #[test]
 692     fn test_prepend() {
 693         {
 694             let mut m = DList::new();
 695             let mut n = DList::new();
 696             n.push_back(2);
 697             m.prepend(n);
 698             assert_eq!(m.len(), 1);
 699             assert_eq!(m.pop_back(), Some(2));
 700             check_links(&m);
 701         }
 702
 703         let v = ~[1,2,3,4,5];
 704         let u = ~[9,8,1,2,3,4,5];
 705         let mut m = list_from(v);
 706         m.prepend(list_from(u));
 707         check_links(&m);
 708         let sum = u + v;
 709         assert_eq!(sum.len(), m.len());
 710         for sum.consume_iter().advance |elt| {
 711             assert_eq!(m.pop_front(), Some(elt))
 712         }
 713     }
 714
 715     #[test]
 716     fn test_rotate() {
 717         let mut n = DList::new::<int>();
 718         n.rotate_to_back(); check_links(&n);
 719         assert_eq!(n.len(), 0);
 720         n.rotate_to_front(); check_links(&n);
 721         assert_eq!(n.len(), 0);
 722
 723         let v = ~[1,2,3,4,5];
 724         let mut m = list_from(v);
 725         m.rotate_to_back(); check_links(&m);
 726         m.rotate_to_front(); check_links(&m);
 727         assert_eq!(v.iter().collect::<~[&int]>(), m.iter().collect());
 728         m.rotate_to_front(); check_links(&m);
 729         m.rotate_to_front(); check_links(&m);
 730         m.pop_front(); check_links(&m);
 731         m.rotate_to_front(); check_links(&m);
 732         m.rotate_to_back(); check_links(&m);
 733         m.push_front(9); check_links(&m);
 734         m.rotate_to_front(); check_links(&m);
 735         assert_eq!(~[3,9,5,1,2], m.consume_iter().collect());
 736     }
 737
 738     #[test]
 739     fn test_iterator() {
 740         let m = generate_test();
 741         for m.iter().enumerate().advance |(i, elt)| {
 742             assert_eq!(i as int, *elt);
 743         }
 744         let mut n = DList::new();
 745         assert_eq!(n.iter().next(), None);
 746         n.push_front(4);
 747         let mut it = n.iter();
 748         assert_eq!(it.size_hint(), (1, Some(1)));
 749         assert_eq!(it.next().unwrap(), &4);
 750         assert_eq!(it.size_hint(), (0, Some(0)));
 751         assert_eq!(it.next(), None);
 752     }
 753
 754     #[test]
 755     fn test_iterator_clone() {
 756         let mut n = DList::new();
 757         n.push_back(2);
 758         n.push_back(3);
 759         n.push_back(4);
 760         let mut it = n.iter();
 761         it.next();
 762         let mut jt = it.clone();
 763         assert_eq!(it.next(), jt.next());
 764         assert_eq!(it.next_back(), jt.next_back());
 765         assert_eq!(it.next(), jt.next());
 766     }
 767
 768     #[test]
 769     fn test_iterator_double_end() {
 770         let mut n = DList::new();
 771         assert_eq!(n.iter().next(), None);
 772         n.push_front(4);
 773         n.push_front(5);
 774         n.push_front(6);
 775         let mut it = n.iter();
 776         assert_eq!(it.size_hint(), (3, Some(3)));
 777         assert_eq!(it.next().unwrap(), &6);
 778         assert_eq!(it.size_hint(), (2, Some(2)));
 779         assert_eq!(it.next_back().unwrap(), &4);
 780         assert_eq!(it.size_hint(), (1, Some(1)));
 781         assert_eq!(it.next_back().unwrap(), &5);
 782         assert_eq!(it.next_back(), None);
 783         assert_eq!(it.next(), None);
 784     }
 785
 786     #[test]
 787     fn test_rev_iter() {
 788         let m = generate_test();
 789         for m.rev_iter().enumerate().advance |(i, elt)| {
 790             assert_eq!((6 - i) as int, *elt);
 791         }
 792         let mut n = DList::new();
 793         assert_eq!(n.rev_iter().next(), None);
 794         n.push_front(4);
 795         let mut it = n.rev_iter();
 796         assert_eq!(it.size_hint(), (1, Some(1)));
 797         assert_eq!(it.next().unwrap(), &4);
 798         assert_eq!(it.size_hint(), (0, Some(0)));
 799         assert_eq!(it.next(), None);
 800     }
 801
 802     #[test]
 803     fn test_mut_iter() {
 804         let mut m = generate_test();
 805         let mut len = m.len();
 806         for m.mut_iter().enumerate().advance |(i, elt)| {
 807             assert_eq!(i as int, *elt);
 808             len -= 1;
 809         }
 810         assert_eq!(len, 0);
 811         let mut n = DList::new();
 812         assert!(n.mut_iter().next().is_none());
 813         n.push_front(4);
 814         n.push_back(5);
 815         let mut it = n.mut_iter();
 816         assert_eq!(it.size_hint(), (2, Some(2)));
 817         assert!(it.next().is_some());
 818         assert!(it.next().is_some());
 819         assert_eq!(it.size_hint(), (0, Some(0)));
 820         assert!(it.next().is_none());
 821     }
 822
 823     #[test]
 824     fn test_iterator_mut_double_end() {
 825         let mut n = DList::new();
 826         assert!(n.mut_iter().next_back().is_none());
 827         n.push_front(4);
 828         n.push_front(5);
 829         n.push_front(6);
 830         let mut it = n.mut_iter();
 831         assert_eq!(it.size_hint(), (3, Some(3)));
 832         assert_eq!(*it.next().unwrap(), 6);
 833         assert_eq!(it.size_hint(), (2, Some(2)));
 834         assert_eq!(*it.next_back().unwrap(), 4);
 835         assert_eq!(it.size_hint(), (1, Some(1)));
 836         assert_eq!(*it.next_back().unwrap(), 5);
 837         assert!(it.next_back().is_none());
 838         assert!(it.next().is_none());
 839     }
 840
 841     #[test]
 842     fn test_insert_prev() {
 843         let mut m = list_from(&[0,2,4,6,8]);
 844         let len = m.len();
 845         {
 846             let mut it = m.mut_iter();
 847             it.insert_next(-2);
 848             loop {
 849                 match it.next() {
 850                     None => break,
 851                     Some(elt) => {
 852                         it.insert_next(*elt + 1);
 853                         match it.peek_next() {
 854                             Some(x) => assert_eq!(*x, *elt + 2),
 855                             None => assert_eq!(8, *elt),
 856                         }
 857                     }
 858                 }
 859             }
 860             it.insert_next(0);
 861             it.insert_next(1);
 862         }
 863         check_links(&m);
 864         assert_eq!(m.len(), 3 + len * 2);
 865         assert_eq!(m.consume_iter().collect::<~[int]>(), ~[-2,0,1,2,3,4,5,6,7,8,9,0,1]);
 866     }
 867
 868     #[test]
 869     fn test_merge() {
 870         let mut m = list_from([0, 1, 3, 5, 6, 7, 2]);
 871         let n = list_from([-1, 0, 0, 7, 7, 9]);
 872         let len = m.len() + n.len();
 873         m.merge(n, |a, b| a <= b);
 874         assert_eq!(m.len(), len);
 875         check_links(&m);
 876         let res = m.consume_iter().collect::<~[int]>();
 877         assert_eq!(res, ~[-1, 0, 0, 0, 1, 3, 5, 6, 7, 2, 7, 7, 9]);
 878     }
 879
 880     #[test]
 881     fn test_insert_ordered() {
 882         let mut n = DList::new();
 883         n.insert_ordered(1);
 884         assert_eq!(n.len(), 1);
 885         assert_eq!(n.pop_front(), Some(1));
 886
 887         let mut m = DList::new();
 888         m.push_back(2);
 889         m.push_back(4);
 890         m.insert_ordered(3);
 891         check_links(&m);
 892         assert_eq!(~[2,3,4], m.consume_iter().collect::<~[int]>());
 893     }
 894
 895     #[test]
 896     fn test_mut_rev_iter() {
 897         let mut m = generate_test();
 898         for m.mut_rev_iter().enumerate().advance |(i, elt)| {
 899             assert_eq!((6-i) as int, *elt);
 900         }
 901         let mut n = DList::new();
 902         assert!(n.mut_rev_iter().next().is_none());
 903         n.push_front(4);
 904         let mut it = n.mut_rev_iter();
 905         assert!(it.next().is_some());
 906         assert!(it.next().is_none());
 907     }
 908
 909     #[test]
 910     fn test_send() {
 911         let n = list_from([1,2,3]);
 912         do spawn {
 913             check_links(&n);
 914             assert_eq!(~[&1,&2,&3], n.iter().collect::<~[&int]>());
 915         }
 916     }
 917
 918     #[test]
 919     fn test_eq() {
 920         let mut n: DList<u8> = list_from([]);
 921         let mut m = list_from([]);
 922         assert_eq!(&n, &m);
 923         n.push_front(1);
 924         assert!(n != m);
 925         m.push_back(1);
 926         assert_eq!(&n, &m);
 927     }
 928
 929     #[test]
 930     fn test_fuzz() {
 931         for 25.times {
 932             fuzz_test(3);
 933             fuzz_test(16);
 934             fuzz_test(189);
 935         }
 936     }
 937
 938     #[cfg(test)]
 939     fn fuzz_test(sz: int) {
 940         let mut m = DList::new::<int>();
 941         let mut v = ~[];
 942         for int::range(0i, sz) |i| {
 943             check_links(&m);
 944             let r: u8 = rand::random();
 945             match r % 6 {
 946                 0 => {
 947                     m.pop_back();
 948                     if v.len() > 0 { v.pop(); }
 949                 }
 950                 1 => {
 951                     m.pop_front();
 952                     if v.len() > 0 { v.shift(); }
 953                 }
 954                 2 | 4 =>  {
 955                     m.push_front(-i);
 956                     v.unshift(-i);
 957                 }
 958                 3 | 5 | _ => {
 959                     m.push_back(i);
 960                     v.push(i);
 961                 }
 962             }
 963         }
 964
 965         check_links(&m);
 966
 967         let mut i = 0u;
 968         for m.consume_iter().zip(v.iter()).advance |(a, &b)| {
 969             i += 1;
 970             assert_eq!(a, b);
 971         }
 972         assert_eq!(i, v.len());
 973     }
 974
 975     #[bench]
 976     fn bench_collect_into(b: &mut test::BenchHarness) {
 977         let v = &[0, ..64];
 978         do b.iter {
 979             let _: DList<int> = v.iter().transform(|x| *x).collect();
 980         }
 981     }
 982
 983     #[bench]
 984     fn bench_push_front(b: &mut test::BenchHarness) {
 985         let mut m = DList::new::<int>();
 986         do b.iter {
 987             m.push_front(0);
 988         }
 989     }
 990
 991     #[bench]
 992     fn bench_push_back(b: &mut test::BenchHarness) {
 993         let mut m = DList::new::<int>();
 994         do b.iter {
 995             m.push_back(0);
 996         }
 997     }
 998
 999     #[bench]
1000     fn bench_push_back_pop_back(b: &mut test::BenchHarness) {
1001         let mut m = DList::new::<int>();
1002         do b.iter {
1003             m.push_back(0);
1004             m.pop_back();
1005         }
1006     }
1007
1008     #[bench]
1009     fn bench_push_front_pop_front(b: &mut test::BenchHarness) {
1010         let mut m = DList::new::<int>();
1011         do b.iter {
1012             m.push_front(0);
1013             m.pop_front();
1014         }
1015     }
1016
1017     #[bench]
1018     fn bench_rotate_to_front(b: &mut test::BenchHarness) {
1019         let mut m = DList::new::<int>();
1020         m.push_front(0);
1021         m.push_front(1);
1022         do b.iter {
1023             m.rotate_to_front();
1024         }
1025     }
1026
1027     #[bench]
1028     fn bench_rotate_to_back(b: &mut test::BenchHarness) {
1029         let mut m = DList::new::<int>();
1030         m.push_front(0);
1031         m.push_front(1);
1032         do b.iter {
1033             m.rotate_to_back();
1034         }
1035     }
1036
1037     #[bench]
1038     fn bench_iter(b: &mut test::BenchHarness) {
1039         let v = &[0, ..128];
1040         let m: DList<int> = v.iter().transform(|&x|x).collect();
1041         do b.iter {
1042             assert!(m.iter().len_() == 128);
1043         }
1044     }
1045     #[bench]
1046     fn bench_iter_mut(b: &mut test::BenchHarness) {
1047         let v = &[0, ..128];
1048         let mut m: DList<int> = v.iter().transform(|&x|x).collect();
1049         do b.iter {
1050             assert!(m.mut_iter().len_() == 128);
1051         }
1052     }
1053     #[bench]
1054     fn bench_iter_rev(b: &mut test::BenchHarness) {
1055         let v = &[0, ..128];
1056         let m: DList<int> = v.iter().transform(|&x|x).collect();
1057         do b.iter {
1058             assert!(m.rev_iter().len_() == 128);
1059         }
1060     }
1061     #[bench]
1062     fn bench_iter_mut_rev(b: &mut test::BenchHarness) {
1063         let v = &[0, ..128];
1064         let mut m: DList<int> = v.iter().transform(|&x|x).collect();
1065         do b.iter {
1066             assert!(m.mut_rev_iter().len_() == 128);
1067         }
1068     }
1069 }
1070