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