src/libcollections/dlist.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A doubly-linked list with owned nodes.
  12 //!
  13 //! The `DList` allows pushing and popping elements at either end and is thus
  14 //! efficiently usable as a double-ended queue.
  15
  16 // DList is constructed like a singly-linked list over the field `next`.
  17 // including the last link being None; each Node owns its `next` field.
  18 //
  19 // Backlinks over DList::prev are raw pointers that form a full chain in
  20 // the reverse direction.
  21
  22 use core::prelude::*;
  23
  24 use alloc::boxed::Box;
  25 use core::default::Default;
  26 use core::fmt;
  27 use core::iter;
  28 use core::mem;
  29 use core::ptr;
  30 use std::hash::{Writer, Hash};
  31
  32 /// A doubly-linked list.
  33 pub struct DList<T> {
  34     length: uint,
  35     list_head: Link<T>,
  36     list_tail: Rawlink<Node<T>>,
  37 }
  38
  39 type Link<T> = Option<Box<Node<T>>>;
  40
  41 struct Rawlink<T> {
  42     p: *mut T,
  43 }
  44
  45 impl<T> Copy for Rawlink<T> {}
  46 unsafe impl<T:'static+Send> Send for Rawlink<T> {}
  47 unsafe impl<T:Send+Sync> Sync 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 Iter<'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 Iter<'a, T> {
  64     fn clone(&self) -> Iter<'a, T> { *self }
  65 }
  66
  67 impl<'a,T> Copy for Iter<'a,T> {}
  68
  69 /// An iterator over mutable references to the items of a `DList`.
  70 pub struct IterMut<'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 IntoIter<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             mem::transmute(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 #[stable]
 198 impl<T> Default for DList<T> {
 199     #[inline]
 200     #[stable]
 201     fn default() -> DList<T> { DList::new() }
 202 }
 203
 204 impl<T> DList<T> {
 205     /// Creates an empty `DList`.
 206     #[inline]
 207     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 208     pub fn new() -> DList<T> {
 209         DList{list_head: None, list_tail: Rawlink::none(), length: 0}
 210     }
 211
 212     /// Moves the last element to the front of the list.
 213     ///
 214     /// If the list is empty, does nothing.
 215     ///
 216     /// # Examples
 217     ///
 218     /// ```rust
 219     /// use std::collections::DList;
 220     ///
 221     /// let mut dl = DList::new();
 222     /// dl.push_back(1i);
 223     /// dl.push_back(2);
 224     /// dl.push_back(3);
 225     ///
 226     /// dl.rotate_forward();
 227     ///
 228     /// for e in dl.iter() {
 229     ///     println!("{}", e); // prints 3, then 1, then 2
 230     /// }
 231     /// ```
 232     #[inline]
 233     pub fn rotate_forward(&mut self) {
 234         self.pop_back_node().map(|tail| {
 235             self.push_front_node(tail)
 236         });
 237     }
 238
 239     /// Moves the first element to the back of the list.
 240     ///
 241     /// If the list is empty, does nothing.
 242     ///
 243     /// # Examples
 244     ///
 245     /// ```rust
 246     /// use std::collections::DList;
 247     ///
 248     /// let mut dl = DList::new();
 249     /// dl.push_back(1i);
 250     /// dl.push_back(2);
 251     /// dl.push_back(3);
 252     ///
 253     /// dl.rotate_backward();
 254     ///
 255     /// for e in dl.iter() {
 256     ///     println!("{}", e); // prints 2, then 3, then 1
 257     /// }
 258     /// ```
 259     #[inline]
 260     pub fn rotate_backward(&mut self) {
 261         self.pop_front_node().map(|head| {
 262             self.push_back_node(head)
 263         });
 264     }
 265
 266     /// Adds all elements from `other` to the end of the list.
 267     ///
 268     /// This operation should compute in O(1) time.
 269     ///
 270     /// # Examples
 271     ///
 272     /// ```rust
 273     /// use std::collections::DList;
 274     ///
 275     /// let mut a = DList::new();
 276     /// let mut b = DList::new();
 277     /// a.push_back(1i);
 278     /// a.push_back(2);
 279     /// b.push_back(3i);
 280     /// b.push_back(4);
 281     ///
 282     /// a.append(b);
 283     ///
 284     /// for e in a.iter() {
 285     ///     println!("{}", e); // prints 1, then 2, then 3, then 4
 286     /// }
 287     /// ```
 288     pub fn append(&mut self, mut other: DList<T>) {
 289         match self.list_tail.resolve() {
 290             None => *self = other,
 291             Some(tail) => {
 292                 // Carefully empty `other`.
 293                 let o_tail = other.list_tail.take();
 294                 let o_length = other.length;
 295                 match other.list_head.take() {
 296                     None => return,
 297                     Some(node) => {
 298                         tail.next = link_with_prev(node, self.list_tail);
 299                         self.list_tail = o_tail;
 300                         self.length += o_length;
 301                     }
 302                 }
 303             }
 304         }
 305     }
 306
 307     /// Adds all elements from `other` to the beginning of the list.
 308     ///
 309     /// This operation should compute in O(1) time.
 310     ///
 311     /// # Examples
 312     ///
 313     /// ```rust
 314     /// use std::collections::DList;
 315     ///
 316     /// let mut a = DList::new();
 317     /// let mut b = DList::new();
 318     /// a.push_back(1i);
 319     /// a.push_back(2);
 320     /// b.push_back(3i);
 321     /// b.push_back(4);
 322     ///
 323     /// a.prepend(b);
 324     ///
 325     /// for e in a.iter() {
 326     ///     println!("{}", e); // prints 3, then 4, then 1, then 2
 327     /// }
 328     /// ```
 329     #[inline]
 330     pub fn prepend(&mut self, mut other: DList<T>) {
 331         mem::swap(self, &mut other);
 332         self.append(other);
 333     }
 334
 335     /// Inserts `elt` before the first `x` in the list where `f(x, elt)` is
 336     /// true, or at the end.
 337     ///
 338     /// This operation should compute in O(N) time.
 339     ///
 340     /// # Examples
 341     ///
 342     /// ```rust
 343     /// use std::collections::DList;
 344     ///
 345     /// let mut a: DList<int> = DList::new();
 346     /// a.push_back(2i);
 347     /// a.push_back(4);
 348     /// a.push_back(7);
 349     /// a.push_back(8);
 350     ///
 351     /// // insert 11 before the first odd number in the list
 352     /// a.insert_when(11, |&e, _| e % 2 == 1);
 353     ///
 354     /// for e in a.iter() {
 355     ///     println!("{}", e); // prints 2, then 4, then 11, then 7, then 8
 356     /// }
 357     /// ```
 358     pub fn insert_when<F>(&mut self, elt: T, mut f: F) where F: FnMut(&T, &T) -> bool {
 359         let mut it = self.iter_mut();
 360         loop {
 361             match it.peek_next() {
 362                 None => break,
 363                 Some(x) => if f(x, &elt) { break }
 364             }
 365             it.next();
 366         }
 367         it.insert_next(elt);
 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<F>(&mut self, mut other: DList<T>, mut f: F) where F: FnMut(&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) -> Iter<'a, T> {
 400         Iter{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) -> IterMut<'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         IterMut{
 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) -> IntoIter<T> {
 423         IntoIter{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     #[stable]
 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     #[stable]
 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     #[stable]
 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     #[stable]
 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     /// # Examples
 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     /// # Examples
 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 Iter<'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 Iter<'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 Iter<'a, A> {}
 618
 619 impl<'a, A> Iterator<&'a mut A> for IterMut<'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 IterMut<'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 IterMut<'a, A> {}
 656
 657 /// Allows mutating a `DList` while iterating.
 658 #[deprecated = "Trait is deprecated, use inherent methods on the iterator instead"]
 659 pub trait ListInsertion<A> {
 660     /// Inserts `elt` just after to the element most recently returned by
 661     /// `.next()`
 662     ///
 663     /// The inserted element does not appear in the iteration.
 664     fn insert_next(&mut self, elt: A);
 665
 666     /// Provides a reference to the next element, without changing the iterator
 667     fn peek_next<'a>(&'a mut self) -> Option<&'a mut A>;
 668 }
 669
 670 // private methods for IterMut
 671 impl<'a, A> IterMut<'a, A> {
 672     fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
 673         // Insert before `self.head` so that it is between the
 674         // previously yielded element and self.head.
 675         //
 676         // The inserted node will not appear in further iteration.
 677         match self.head.resolve() {
 678             None => { self.list.push_back_node(ins_node); }
 679             Some(node) => {
 680                 let prev_node = match node.prev.resolve() {
 681                     None => return self.list.push_front_node(ins_node),
 682                     Some(prev) => prev,
 683                 };
 684                 let node_own = prev_node.next.take().unwrap();
 685                 ins_node.next = link_with_prev(node_own, Rawlink::some(&mut *ins_node));
 686                 prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
 687                 self.list.length += 1;
 688             }
 689         }
 690     }
 691 }
 692
 693 impl<'a, A> IterMut<'a, A> {
 694     /// Inserts `elt` just after the element most recently returned by `.next()`.
 695     /// The inserted element does not appear in the iteration.
 696     ///
 697     /// # Examples
 698     ///
 699     /// ```rust
 700     /// use std::collections::DList;
 701     ///
 702     /// let mut list: DList<int> = vec![1, 3, 4].into_iter().collect();
 703     ///
 704     /// {
 705     ///     let mut it = list.iter_mut();
 706     ///     assert_eq!(it.next().unwrap(), &1);
 707     ///     // insert `2` after `1`
 708     ///     it.insert_next(2);
 709     /// }
 710     /// {
 711     ///     let vec: Vec<int> = list.into_iter().collect();
 712     ///     assert_eq!(vec, vec![1i, 2, 3, 4]);
 713     /// }
 714     /// ```
 715     #[inline]
 716     pub fn insert_next(&mut self, elt: A) {
 717         self.insert_next_node(box Node::new(elt))
 718     }
 719
 720     /// Provides a reference to the next element, without changing the iterator.
 721     ///
 722     /// # Examples
 723     ///
 724     /// ```rust
 725     /// use std::collections::DList;
 726     ///
 727     /// let mut list: DList<int> = vec![1, 2, 3].into_iter().collect();
 728     ///
 729     /// let mut it = list.iter_mut();
 730     /// assert_eq!(it.next().unwrap(), &1);
 731     /// assert_eq!(it.peek_next().unwrap(), &2);
 732     /// // We just peeked at 2, so it was not consumed from the iterator.
 733     /// assert_eq!(it.next().unwrap(), &2);
 734     /// ```
 735     #[inline]
 736     pub fn peek_next(&mut self) -> Option<&mut A> {
 737         if self.nelem == 0 {
 738             return None
 739         }
 740         self.head.resolve().map(|head| &mut head.value)
 741     }
 742 }
 743
 744 impl<A> Iterator<A> for IntoIter<A> {
 745     #[inline]
 746     fn next(&mut self) -> Option<A> { self.list.pop_front() }
 747
 748     #[inline]
 749     fn size_hint(&self) -> (uint, Option<uint>) {
 750         (self.list.length, Some(self.list.length))
 751     }
 752 }
 753
 754 impl<A> DoubleEndedIterator<A> for IntoIter<A> {
 755     #[inline]
 756     fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
 757 }
 758
 759 impl<A> FromIterator<A> for DList<A> {
 760     fn from_iter<T: Iterator<A>>(iterator: T) -> DList<A> {
 761         let mut ret = DList::new();
 762         ret.extend(iterator);
 763         ret
 764     }
 765 }
 766
 767 impl<A> Extend<A> for DList<A> {
 768     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
 769         for elt in iterator { self.push_back(elt); }
 770     }
 771 }
 772
 773 #[stable]
 774 impl<A: PartialEq> PartialEq for DList<A> {
 775     fn eq(&self, other: &DList<A>) -> bool {
 776         self.len() == other.len() &&
 777             iter::order::eq(self.iter(), other.iter())
 778     }
 779
 780     fn ne(&self, other: &DList<A>) -> bool {
 781         self.len() != other.len() ||
 782             iter::order::ne(self.iter(), other.iter())
 783     }
 784 }
 785
 786 #[stable]
 787 impl<A: Eq> Eq for DList<A> {}
 788
 789 #[stable]
 790 impl<A: PartialOrd> PartialOrd for DList<A> {
 791     fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> {
 792         iter::order::partial_cmp(self.iter(), other.iter())
 793     }
 794 }
 795
 796 #[stable]
 797 impl<A: Ord> Ord for DList<A> {
 798     #[inline]
 799     fn cmp(&self, other: &DList<A>) -> Ordering {
 800         iter::order::cmp(self.iter(), other.iter())
 801     }
 802 }
 803
 804 #[stable]
 805 impl<A: Clone> Clone for DList<A> {
 806     fn clone(&self) -> DList<A> {
 807         self.iter().map(|x| x.clone()).collect()
 808     }
 809 }
 810
 811 impl<A: fmt::Show> fmt::Show for DList<A> {
 812     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 813         try!(write!(f, "["));
 814
 815         for (i, e) in self.iter().enumerate() {
 816             if i != 0 { try!(write!(f, ", ")); }
 817             try!(write!(f, "{}", *e));
 818         }
 819
 820         write!(f, "]")
 821     }
 822 }
 823
 824 impl<S: Writer, A: Hash<S>> Hash<S> for DList<A> {
 825     fn hash(&self, state: &mut S) {
 826         self.len().hash(state);
 827         for elt in self.iter() {
 828             elt.hash(state);
 829         }
 830     }
 831 }
 832
 833 #[cfg(test)]
 834 mod tests {
 835     use prelude::*;
 836     use std::rand;
 837     use std::hash;
 838     use std::task::spawn;
 839     use test::Bencher;
 840     use test;
 841
 842     use super::{DList, Node};
 843
 844     pub fn check_links<T>(list: &DList<T>) {
 845         let mut len = 0u;
 846         let mut last_ptr: Option<&Node<T>> = None;
 847         let mut node_ptr: &Node<T>;
 848         match list.list_head {
 849             None => { assert_eq!(0u, list.length); return }
 850             Some(ref node) => node_ptr = &**node,
 851         }
 852         loop {
 853             match (last_ptr, node_ptr.prev.resolve_immut()) {
 854                 (None   , None      ) => {}
 855                 (None   , _         ) => panic!("prev link for list_head"),
 856                 (Some(p), Some(pptr)) => {
 857                     assert_eq!(p as *const Node<T>, pptr as *const Node<T>);
 858                 }
 859                 _ => panic!("prev link is none, not good"),
 860             }
 861             match node_ptr.next {
 862                 Some(ref next) => {
 863                     last_ptr = Some(node_ptr);
 864                     node_ptr = &**next;
 865                     len += 1;
 866                 }
 867                 None => {
 868                     len += 1;
 869                     break;
 870                 }
 871             }
 872         }
 873         assert_eq!(len, list.length);
 874     }
 875
 876     #[test]
 877     fn test_basic() {
 878         let mut m: DList<Box<int>> = DList::new();
 879         assert_eq!(m.pop_front(), None);
 880         assert_eq!(m.pop_back(), None);
 881         assert_eq!(m.pop_front(), None);
 882         m.push_front(box 1);
 883         assert_eq!(m.pop_front(), Some(box 1));
 884         m.push_back(box 2);
 885         m.push_back(box 3);
 886         assert_eq!(m.len(), 2);
 887         assert_eq!(m.pop_front(), Some(box 2));
 888         assert_eq!(m.pop_front(), Some(box 3));
 889         assert_eq!(m.len(), 0);
 890         assert_eq!(m.pop_front(), None);
 891         m.push_back(box 1);
 892         m.push_back(box 3);
 893         m.push_back(box 5);
 894         m.push_back(box 7);
 895         assert_eq!(m.pop_front(), Some(box 1));
 896
 897         let mut n = DList::new();
 898         n.push_front(2i);
 899         n.push_front(3);
 900         {
 901             assert_eq!(n.front().unwrap(), &3);
 902             let x = n.front_mut().unwrap();
 903             assert_eq!(*x, 3);
 904             *x = 0;
 905         }
 906         {
 907             assert_eq!(n.back().unwrap(), &2);
 908             let y = n.back_mut().unwrap();
 909             assert_eq!(*y, 2);
 910             *y = 1;
 911         }
 912         assert_eq!(n.pop_front(), Some(0));
 913         assert_eq!(n.pop_front(), Some(1));
 914     }
 915
 916     #[cfg(test)]
 917     fn generate_test() -> DList<int> {
 918         list_from(&[0i,1,2,3,4,5,6])
 919     }
 920
 921     #[cfg(test)]
 922     fn list_from<T: Clone>(v: &[T]) -> DList<T> {
 923         v.iter().map(|x| (*x).clone()).collect()
 924     }
 925
 926     #[test]
 927     #[allow(deprecated)]
 928     fn test_append() {
 929         {
 930             let mut m = DList::new();
 931             let mut n = DList::new();
 932             n.push_back(2i);
 933             m.append(n);
 934             assert_eq!(m.len(), 1);
 935             assert_eq!(m.pop_back(), Some(2));
 936             check_links(&m);
 937         }
 938         {
 939             let mut m = DList::new();
 940             let n = DList::new();
 941             m.push_back(2i);
 942             m.append(n);
 943             assert_eq!(m.len(), 1);
 944             assert_eq!(m.pop_back(), Some(2));
 945             check_links(&m);
 946         }
 947
 948         let v = vec![1i,2,3,4,5];
 949         let u = vec![9i,8,1,2,3,4,5];
 950         let mut m = list_from(v.as_slice());
 951         m.append(list_from(u.as_slice()));
 952         check_links(&m);
 953         let mut sum = v;
 954         sum.push_all(u.as_slice());
 955         assert_eq!(sum.len(), m.len());
 956         for elt in sum.into_iter() {
 957             assert_eq!(m.pop_front(), Some(elt))
 958         }
 959     }
 960
 961     #[test]
 962     fn test_prepend() {
 963         {
 964             let mut m = DList::new();
 965             let mut n = DList::new();
 966             n.push_back(2i);
 967             m.prepend(n);
 968             assert_eq!(m.len(), 1);
 969             assert_eq!(m.pop_back(), Some(2));
 970             check_links(&m);
 971         }
 972
 973         let v = vec![1i,2,3,4,5];
 974         let mut u = vec![9i,8,1,2,3,4,5];
 975         let mut m = list_from(v.as_slice());
 976         m.prepend(list_from(u.as_slice()));
 977         check_links(&m);
 978         u.extend(v.iter().map(|&b| b));
 979         assert_eq!(u.len(), m.len());
 980         for elt in u.into_iter() {
 981             assert_eq!(m.pop_front(), Some(elt))
 982         }
 983     }
 984
 985     #[test]
 986     fn test_rotate() {
 987         let mut n: DList<int> = DList::new();
 988         n.rotate_backward(); check_links(&n);
 989         assert_eq!(n.len(), 0);
 990         n.rotate_forward(); check_links(&n);
 991         assert_eq!(n.len(), 0);
 992
 993         let v = vec![1i,2,3,4,5];
 994         let mut m = list_from(v.as_slice());
 995         m.rotate_backward(); check_links(&m);
 996         m.rotate_forward(); check_links(&m);
 997         assert_eq!(v.iter().collect::<Vec<&int>>(), m.iter().collect::<Vec<_>>());
 998         m.rotate_forward(); check_links(&m);
 999         m.rotate_forward(); check_links(&m);
1000         m.pop_front(); check_links(&m);
1001         m.rotate_forward(); check_links(&m);
1002         m.rotate_backward(); check_links(&m);
1003         m.push_front(9); check_links(&m);
1004         m.rotate_forward(); check_links(&m);
1005         assert_eq!(vec![3i,9,5,1,2], m.into_iter().collect::<Vec<_>>());
1006     }
1007
1008     #[test]
1009     fn test_iterator() {
1010         let m = generate_test();
1011         for (i, elt) in m.iter().enumerate() {
1012             assert_eq!(i as int, *elt);
1013         }
1014         let mut n = DList::new();
1015         assert_eq!(n.iter().next(), None);
1016         n.push_front(4i);
1017         let mut it = n.iter();
1018         assert_eq!(it.size_hint(), (1, Some(1)));
1019         assert_eq!(it.next().unwrap(), &4);
1020         assert_eq!(it.size_hint(), (0, Some(0)));
1021         assert_eq!(it.next(), None);
1022     }
1023
1024     #[test]
1025     fn test_iterator_clone() {
1026         let mut n = DList::new();
1027         n.push_back(2i);
1028         n.push_back(3);
1029         n.push_back(4);
1030         let mut it = n.iter();
1031         it.next();
1032         let mut jt = it.clone();
1033         assert_eq!(it.next(), jt.next());
1034         assert_eq!(it.next_back(), jt.next_back());
1035         assert_eq!(it.next(), jt.next());
1036     }
1037
1038     #[test]
1039     fn test_iterator_double_end() {
1040         let mut n = DList::new();
1041         assert_eq!(n.iter().next(), None);
1042         n.push_front(4i);
1043         n.push_front(5);
1044         n.push_front(6);
1045         let mut it = n.iter();
1046         assert_eq!(it.size_hint(), (3, Some(3)));
1047         assert_eq!(it.next().unwrap(), &6);
1048         assert_eq!(it.size_hint(), (2, Some(2)));
1049         assert_eq!(it.next_back().unwrap(), &4);
1050         assert_eq!(it.size_hint(), (1, Some(1)));
1051         assert_eq!(it.next_back().unwrap(), &5);
1052         assert_eq!(it.next_back(), None);
1053         assert_eq!(it.next(), None);
1054     }
1055
1056     #[test]
1057     fn test_rev_iter() {
1058         let m = generate_test();
1059         for (i, elt) in m.iter().rev().enumerate() {
1060             assert_eq!((6 - i) as int, *elt);
1061         }
1062         let mut n = DList::new();
1063         assert_eq!(n.iter().rev().next(), None);
1064         n.push_front(4i);
1065         let mut it = n.iter().rev();
1066         assert_eq!(it.size_hint(), (1, Some(1)));
1067         assert_eq!(it.next().unwrap(), &4);
1068         assert_eq!(it.size_hint(), (0, Some(0)));
1069         assert_eq!(it.next(), None);
1070     }
1071
1072     #[test]
1073     fn test_mut_iter() {
1074         let mut m = generate_test();
1075         let mut len = m.len();
1076         for (i, elt) in m.iter_mut().enumerate() {
1077             assert_eq!(i as int, *elt);
1078             len -= 1;
1079         }
1080         assert_eq!(len, 0);
1081         let mut n = DList::new();
1082         assert!(n.iter_mut().next().is_none());
1083         n.push_front(4i);
1084         n.push_back(5);
1085         let mut it = n.iter_mut();
1086         assert_eq!(it.size_hint(), (2, Some(2)));
1087         assert!(it.next().is_some());
1088         assert!(it.next().is_some());
1089         assert_eq!(it.size_hint(), (0, Some(0)));
1090         assert!(it.next().is_none());
1091     }
1092
1093     #[test]
1094     fn test_iterator_mut_double_end() {
1095         let mut n = DList::new();
1096         assert!(n.iter_mut().next_back().is_none());
1097         n.push_front(4i);
1098         n.push_front(5);
1099         n.push_front(6);
1100         let mut it = n.iter_mut();
1101         assert_eq!(it.size_hint(), (3, Some(3)));
1102         assert_eq!(*it.next().unwrap(), 6);
1103         assert_eq!(it.size_hint(), (2, Some(2)));
1104         assert_eq!(*it.next_back().unwrap(), 4);
1105         assert_eq!(it.size_hint(), (1, Some(1)));
1106         assert_eq!(*it.next_back().unwrap(), 5);
1107         assert!(it.next_back().is_none());
1108         assert!(it.next().is_none());
1109     }
1110
1111     #[test]
1112     fn test_insert_prev() {
1113         let mut m = list_from(&[0i,2,4,6,8]);
1114         let len = m.len();
1115         {
1116             let mut it = m.iter_mut();
1117             it.insert_next(-2);
1118             loop {
1119                 match it.next() {
1120                     None => break,
1121                     Some(elt) => {
1122                         it.insert_next(*elt + 1);
1123                         match it.peek_next() {
1124                             Some(x) => assert_eq!(*x, *elt + 2),
1125                             None => assert_eq!(8, *elt),
1126                         }
1127                     }
1128                 }
1129             }
1130             it.insert_next(0);
1131             it.insert_next(1);
1132         }
1133         check_links(&m);
1134         assert_eq!(m.len(), 3 + len * 2);
1135         assert_eq!(m.into_iter().collect::<Vec<int>>(), vec![-2,0,1,2,3,4,5,6,7,8,9,0,1]);
1136     }
1137
1138     #[test]
1139     fn test_merge() {
1140         let mut m = list_from(&[0i, 1, 3, 5, 6, 7, 2]);
1141         let n = list_from(&[-1i, 0, 0, 7, 7, 9]);
1142         let len = m.len() + n.len();
1143         m.merge(n, |a, b| a <= b);
1144         assert_eq!(m.len(), len);
1145         check_links(&m);
1146         let res = m.into_iter().collect::<Vec<int>>();
1147         assert_eq!(res, vec![-1, 0, 0, 0, 1, 3, 5, 6, 7, 2, 7, 7, 9]);
1148     }
1149
1150     #[test]
1151     fn test_insert_ordered() {
1152         let mut n = DList::new();
1153         n.insert_ordered(1i);
1154         assert_eq!(n.len(), 1);
1155         assert_eq!(n.pop_front(), Some(1));
1156
1157         let mut m = DList::new();
1158         m.push_back(2i);
1159         m.push_back(4);
1160         m.insert_ordered(3);
1161         check_links(&m);
1162         assert_eq!(vec![2,3,4], m.into_iter().collect::<Vec<int>>());
1163     }
1164
1165     #[test]
1166     fn test_mut_rev_iter() {
1167         let mut m = generate_test();
1168         for (i, elt) in m.iter_mut().rev().enumerate() {
1169             assert_eq!((6-i) as int, *elt);
1170         }
1171         let mut n = DList::new();
1172         assert!(n.iter_mut().rev().next().is_none());
1173         n.push_front(4i);
1174         let mut it = n.iter_mut().rev();
1175         assert!(it.next().is_some());
1176         assert!(it.next().is_none());
1177     }
1178
1179     #[test]
1180     fn test_send() {
1181         let n = list_from(&[1i,2,3]);
1182         spawn(move || {
1183             check_links(&n);
1184             let a: &[_] = &[&1,&2,&3];
1185             assert_eq!(a, n.iter().collect::<Vec<&int>>());
1186         });
1187     }
1188
1189     #[test]
1190     fn test_eq() {
1191         let mut n: DList<u8> = list_from(&[]);
1192         let mut m = list_from(&[]);
1193         assert!(n == m);
1194         n.push_front(1);
1195         assert!(n != m);
1196         m.push_back(1);
1197         assert!(n == m);
1198
1199         let n = list_from(&[2i,3,4]);
1200         let m = list_from(&[1i,2,3]);
1201         assert!(n != m);
1202     }
1203
1204     #[test]
1205     fn test_hash() {
1206       let mut x = DList::new();
1207       let mut y = DList::new();
1208
1209       assert!(hash::hash(&x) == hash::hash(&y));
1210
1211       x.push_back(1i);
1212       x.push_back(2);
1213       x.push_back(3);
1214
1215       y.push_front(3i);
1216       y.push_front(2);
1217       y.push_front(1);
1218
1219       assert!(hash::hash(&x) == hash::hash(&y));
1220     }
1221
1222     #[test]
1223     fn test_ord() {
1224         let n: DList<int> = list_from(&[]);
1225         let m = list_from(&[1i,2,3]);
1226         assert!(n < m);
1227         assert!(m > n);
1228         assert!(n <= n);
1229         assert!(n >= n);
1230     }
1231
1232     #[test]
1233     fn test_ord_nan() {
1234         let nan = 0.0f64/0.0;
1235         let n = list_from(&[nan]);
1236         let m = list_from(&[nan]);
1237         assert!(!(n < m));
1238         assert!(!(n > m));
1239         assert!(!(n <= m));
1240         assert!(!(n >= m));
1241
1242         let n = list_from(&[nan]);
1243         let one = list_from(&[1.0f64]);
1244         assert!(!(n < one));
1245         assert!(!(n > one));
1246         assert!(!(n <= one));
1247         assert!(!(n >= one));
1248
1249         let u = list_from(&[1.0f64,2.0,nan]);
1250         let v = list_from(&[1.0f64,2.0,3.0]);
1251         assert!(!(u < v));
1252         assert!(!(u > v));
1253         assert!(!(u <= v));
1254         assert!(!(u >= v));
1255
1256         let s = list_from(&[1.0f64,2.0,4.0,2.0]);
1257         let t = list_from(&[1.0f64,2.0,3.0,2.0]);
1258         assert!(!(s < t));
1259         assert!(s > one);
1260         assert!(!(s <= one));
1261         assert!(s >= one);
1262     }
1263
1264     #[test]
1265     fn test_fuzz() {
1266         for _ in range(0u, 25) {
1267             fuzz_test(3);
1268             fuzz_test(16);
1269             fuzz_test(189);
1270         }
1271     }
1272
1273     #[test]
1274     fn test_show() {
1275         let list: DList<int> = range(0i, 10).collect();
1276         assert!(list.to_string() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1277
1278         let list: DList<&str> = vec!["just", "one", "test", "more"].iter()
1279                                                                    .map(|&s| s)
1280                                                                    .collect();
1281         assert!(list.to_string() == "[just, one, test, more]");
1282     }
1283
1284     #[cfg(test)]
1285     fn fuzz_test(sz: int) {
1286         let mut m: DList<int> = DList::new();
1287         let mut v = vec![];
1288         for i in range(0, sz) {
1289             check_links(&m);
1290             let r: u8 = rand::random();
1291             match r % 6 {
1292                 0 => {
1293                     m.pop_back();
1294                     v.pop();
1295                 }
1296                 1 => {
1297                     m.pop_front();
1298                     v.remove(0);
1299                 }
1300                 2 | 4 =>  {
1301                     m.push_front(-i);
1302                     v.insert(0, -i);
1303                 }
1304                 3 | 5 | _ => {
1305                     m.push_back(i);
1306                     v.push(i);
1307                 }
1308             }
1309         }
1310
1311         check_links(&m);
1312
1313         let mut i = 0u;
1314         for (a, &b) in m.into_iter().zip(v.iter()) {
1315             i += 1;
1316             assert_eq!(a, b);
1317         }
1318         assert_eq!(i, v.len());
1319     }
1320
1321     #[bench]
1322     fn bench_collect_into(b: &mut test::Bencher) {
1323         let v = &[0i, ..64];
1324         b.iter(|| {
1325             let _: DList<int> = v.iter().map(|x| *x).collect();
1326         })
1327     }
1328
1329     #[bench]
1330     fn bench_push_front(b: &mut test::Bencher) {
1331         let mut m: DList<int> = DList::new();
1332         b.iter(|| {
1333             m.push_front(0);
1334         })
1335     }
1336
1337     #[bench]
1338     fn bench_push_back(b: &mut test::Bencher) {
1339         let mut m: DList<int> = DList::new();
1340         b.iter(|| {
1341             m.push_back(0);
1342         })
1343     }
1344
1345     #[bench]
1346     fn bench_push_back_pop_back(b: &mut test::Bencher) {
1347         let mut m: DList<int> = DList::new();
1348         b.iter(|| {
1349             m.push_back(0);
1350             m.pop_back();
1351         })
1352     }
1353
1354     #[bench]
1355     fn bench_push_front_pop_front(b: &mut test::Bencher) {
1356         let mut m: DList<int> = DList::new();
1357         b.iter(|| {
1358             m.push_front(0);
1359             m.pop_front();
1360         })
1361     }
1362
1363     #[bench]
1364     fn bench_rotate_forward(b: &mut test::Bencher) {
1365         let mut m: DList<int> = DList::new();
1366         m.push_front(0i);
1367         m.push_front(1);
1368         b.iter(|| {
1369             m.rotate_forward();
1370         })
1371     }
1372
1373     #[bench]
1374     fn bench_rotate_backward(b: &mut test::Bencher) {
1375         let mut m: DList<int> = DList::new();
1376         m.push_front(0i);
1377         m.push_front(1);
1378         b.iter(|| {
1379             m.rotate_backward();
1380         })
1381     }
1382
1383     #[bench]
1384     fn bench_iter(b: &mut test::Bencher) {
1385         let v = &[0i, ..128];
1386         let m: DList<int> = v.iter().map(|&x|x).collect();
1387         b.iter(|| {
1388             assert!(m.iter().count() == 128);
1389         })
1390     }
1391     #[bench]
1392     fn bench_iter_mut(b: &mut test::Bencher) {
1393         let v = &[0i, ..128];
1394         let mut m: DList<int> = v.iter().map(|&x|x).collect();
1395         b.iter(|| {
1396             assert!(m.iter_mut().count() == 128);
1397         })
1398     }
1399     #[bench]
1400     fn bench_iter_rev(b: &mut test::Bencher) {
1401         let v = &[0i, ..128];
1402         let m: DList<int> = v.iter().map(|&x|x).collect();
1403         b.iter(|| {
1404             assert!(m.iter().rev().count() == 128);
1405         })
1406     }
1407     #[bench]
1408     fn bench_iter_mut_rev(b: &mut test::Bencher) {
1409         let v = &[0i, ..128];
1410         let mut m: DList<int> = v.iter().map(|&x|x).collect();
1411         b.iter(|| {
1412             assert!(m.iter_mut().rev().count() == 128);
1413         })
1414     }
1415 }