src/libcollections/dlist.rs

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