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