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