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