src/libcollections/dlist.rs

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