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 impl<A: PartialEq> PartialEq for DList<A> {
 774     fn eq(&self, other: &DList<A>) -> bool {
 775         self.len() == other.len() &&
 776             iter::order::eq(self.iter(), other.iter())
 777     }
 778
 779     fn ne(&self, other: &DList<A>) -> bool {
 780         self.len() != other.len() ||
 781             iter::order::ne(self.iter(), other.iter())
 782     }
 783 }
 784
 785 impl<A: Eq> Eq for DList<A> {}
 786
 787 impl<A: PartialOrd> PartialOrd for DList<A> {
 788     fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> {
 789         iter::order::partial_cmp(self.iter(), other.iter())
 790     }
 791 }
 792
 793 impl<A: Ord> Ord for DList<A> {
 794     #[inline]
 795     fn cmp(&self, other: &DList<A>) -> Ordering {
 796         iter::order::cmp(self.iter(), other.iter())
 797     }
 798 }
 799
 800 #[stable]
 801 impl<A: Clone> Clone for DList<A> {
 802     fn clone(&self) -> DList<A> {
 803         self.iter().map(|x| x.clone()).collect()
 804     }
 805 }
 806
 807 impl<A: fmt::Show> fmt::Show for DList<A> {
 808     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 809         try!(write!(f, "["));
 810
 811         for (i, e) in self.iter().enumerate() {
 812             if i != 0 { try!(write!(f, ", ")); }
 813             try!(write!(f, "{}", *e));
 814         }
 815
 816         write!(f, "]")
 817     }
 818 }
 819
 820 impl<S: Writer, A: Hash<S>> Hash<S> for DList<A> {
 821     fn hash(&self, state: &mut S) {
 822         self.len().hash(state);
 823         for elt in self.iter() {
 824             elt.hash(state);
 825         }
 826     }
 827 }
 828
 829 #[cfg(test)]
 830 mod tests {
 831     use prelude::*;
 832     use std::rand;
 833     use std::hash;
 834     use std::task::spawn;
 835     use test::Bencher;
 836     use test;
 837
 838     use super::{DList, Node};
 839
 840     pub fn check_links<T>(list: &DList<T>) {
 841         let mut len = 0u;
 842         let mut last_ptr: Option<&Node<T>> = None;
 843         let mut node_ptr: &Node<T>;
 844         match list.list_head {
 845             None => { assert_eq!(0u, list.length); return }
 846             Some(ref node) => node_ptr = &**node,
 847         }
 848         loop {
 849             match (last_ptr, node_ptr.prev.resolve_immut()) {
 850                 (None   , None      ) => {}
 851                 (None   , _         ) => panic!("prev link for list_head"),
 852                 (Some(p), Some(pptr)) => {
 853                     assert_eq!(p as *const Node<T>, pptr as *const Node<T>);
 854                 }
 855                 _ => panic!("prev link is none, not good"),
 856             }
 857             match node_ptr.next {
 858                 Some(ref next) => {
 859                     last_ptr = Some(node_ptr);
 860                     node_ptr = &**next;
 861                     len += 1;
 862                 }
 863                 None => {
 864                     len += 1;
 865                     break;
 866                 }
 867             }
 868         }
 869         assert_eq!(len, list.length);
 870     }
 871
 872     #[test]
 873     fn test_basic() {
 874         let mut m: DList<Box<int>> = DList::new();
 875         assert_eq!(m.pop_front(), None);
 876         assert_eq!(m.pop_back(), None);
 877         assert_eq!(m.pop_front(), None);
 878         m.push_front(box 1);
 879         assert_eq!(m.pop_front(), Some(box 1));
 880         m.push_back(box 2);
 881         m.push_back(box 3);
 882         assert_eq!(m.len(), 2);
 883         assert_eq!(m.pop_front(), Some(box 2));
 884         assert_eq!(m.pop_front(), Some(box 3));
 885         assert_eq!(m.len(), 0);
 886         assert_eq!(m.pop_front(), None);
 887         m.push_back(box 1);
 888         m.push_back(box 3);
 889         m.push_back(box 5);
 890         m.push_back(box 7);
 891         assert_eq!(m.pop_front(), Some(box 1));
 892
 893         let mut n = DList::new();
 894         n.push_front(2i);
 895         n.push_front(3);
 896         {
 897             assert_eq!(n.front().unwrap(), &3);
 898             let x = n.front_mut().unwrap();
 899             assert_eq!(*x, 3);
 900             *x = 0;
 901         }
 902         {
 903             assert_eq!(n.back().unwrap(), &2);
 904             let y = n.back_mut().unwrap();
 905             assert_eq!(*y, 2);
 906             *y = 1;
 907         }
 908         assert_eq!(n.pop_front(), Some(0));
 909         assert_eq!(n.pop_front(), Some(1));
 910     }
 911
 912     #[cfg(test)]
 913     fn generate_test() -> DList<int> {
 914         list_from(&[0i,1,2,3,4,5,6])
 915     }
 916
 917     #[cfg(test)]
 918     fn list_from<T: Clone>(v: &[T]) -> DList<T> {
 919         v.iter().map(|x| (*x).clone()).collect()
 920     }
 921
 922     #[test]
 923     #[allow(deprecated)]
 924     fn test_append() {
 925         {
 926             let mut m = DList::new();
 927             let mut n = DList::new();
 928             n.push_back(2i);
 929             m.append(n);
 930             assert_eq!(m.len(), 1);
 931             assert_eq!(m.pop_back(), Some(2));
 932             check_links(&m);
 933         }
 934         {
 935             let mut m = DList::new();
 936             let n = DList::new();
 937             m.push_back(2i);
 938             m.append(n);
 939             assert_eq!(m.len(), 1);
 940             assert_eq!(m.pop_back(), Some(2));
 941             check_links(&m);
 942         }
 943
 944         let v = vec![1i,2,3,4,5];
 945         let u = vec![9i,8,1,2,3,4,5];
 946         let mut m = list_from(v.as_slice());
 947         m.append(list_from(u.as_slice()));
 948         check_links(&m);
 949         let mut sum = v;
 950         sum.push_all(u.as_slice());
 951         assert_eq!(sum.len(), m.len());
 952         for elt in sum.into_iter() {
 953             assert_eq!(m.pop_front(), Some(elt))
 954         }
 955     }
 956
 957     #[test]
 958     fn test_prepend() {
 959         {
 960             let mut m = DList::new();
 961             let mut n = DList::new();
 962             n.push_back(2i);
 963             m.prepend(n);
 964             assert_eq!(m.len(), 1);
 965             assert_eq!(m.pop_back(), Some(2));
 966             check_links(&m);
 967         }
 968
 969         let v = vec![1i,2,3,4,5];
 970         let mut u = vec![9i,8,1,2,3,4,5];
 971         let mut m = list_from(v.as_slice());
 972         m.prepend(list_from(u.as_slice()));
 973         check_links(&m);
 974         u.extend(v.iter().map(|&b| b));
 975         assert_eq!(u.len(), m.len());
 976         for elt in u.into_iter() {
 977             assert_eq!(m.pop_front(), Some(elt))
 978         }
 979     }
 980
 981     #[test]
 982     fn test_rotate() {
 983         let mut n: DList<int> = DList::new();
 984         n.rotate_backward(); check_links(&n);
 985         assert_eq!(n.len(), 0);
 986         n.rotate_forward(); check_links(&n);
 987         assert_eq!(n.len(), 0);
 988
 989         let v = vec![1i,2,3,4,5];
 990         let mut m = list_from(v.as_slice());
 991         m.rotate_backward(); check_links(&m);
 992         m.rotate_forward(); check_links(&m);
 993         assert_eq!(v.iter().collect::<Vec<&int>>(), m.iter().collect::<Vec<_>>());
 994         m.rotate_forward(); check_links(&m);
 995         m.rotate_forward(); check_links(&m);
 996         m.pop_front(); check_links(&m);
 997         m.rotate_forward(); check_links(&m);
 998         m.rotate_backward(); check_links(&m);
 999         m.push_front(9); check_links(&m);
1000         m.rotate_forward(); check_links(&m);
1001         assert_eq!(vec![3i,9,5,1,2], m.into_iter().collect::<Vec<_>>());
1002     }
1003
1004     #[test]
1005     fn test_iterator() {
1006         let m = generate_test();
1007         for (i, elt) in m.iter().enumerate() {
1008             assert_eq!(i as int, *elt);
1009         }
1010         let mut n = DList::new();
1011         assert_eq!(n.iter().next(), None);
1012         n.push_front(4i);
1013         let mut it = n.iter();
1014         assert_eq!(it.size_hint(), (1, Some(1)));
1015         assert_eq!(it.next().unwrap(), &4);
1016         assert_eq!(it.size_hint(), (0, Some(0)));
1017         assert_eq!(it.next(), None);
1018     }
1019
1020     #[test]
1021     fn test_iterator_clone() {
1022         let mut n = DList::new();
1023         n.push_back(2i);
1024         n.push_back(3);
1025         n.push_back(4);
1026         let mut it = n.iter();
1027         it.next();
1028         let mut jt = it.clone();
1029         assert_eq!(it.next(), jt.next());
1030         assert_eq!(it.next_back(), jt.next_back());
1031         assert_eq!(it.next(), jt.next());
1032     }
1033
1034     #[test]
1035     fn test_iterator_double_end() {
1036         let mut n = DList::new();
1037         assert_eq!(n.iter().next(), None);
1038         n.push_front(4i);
1039         n.push_front(5);
1040         n.push_front(6);
1041         let mut it = n.iter();
1042         assert_eq!(it.size_hint(), (3, Some(3)));
1043         assert_eq!(it.next().unwrap(), &6);
1044         assert_eq!(it.size_hint(), (2, Some(2)));
1045         assert_eq!(it.next_back().unwrap(), &4);
1046         assert_eq!(it.size_hint(), (1, Some(1)));
1047         assert_eq!(it.next_back().unwrap(), &5);
1048         assert_eq!(it.next_back(), None);
1049         assert_eq!(it.next(), None);
1050     }
1051
1052     #[test]
1053     fn test_rev_iter() {
1054         let m = generate_test();
1055         for (i, elt) in m.iter().rev().enumerate() {
1056             assert_eq!((6 - i) as int, *elt);
1057         }
1058         let mut n = DList::new();
1059         assert_eq!(n.iter().rev().next(), None);
1060         n.push_front(4i);
1061         let mut it = n.iter().rev();
1062         assert_eq!(it.size_hint(), (1, Some(1)));
1063         assert_eq!(it.next().unwrap(), &4);
1064         assert_eq!(it.size_hint(), (0, Some(0)));
1065         assert_eq!(it.next(), None);
1066     }
1067
1068     #[test]
1069     fn test_mut_iter() {
1070         let mut m = generate_test();
1071         let mut len = m.len();
1072         for (i, elt) in m.iter_mut().enumerate() {
1073             assert_eq!(i as int, *elt);
1074             len -= 1;
1075         }
1076         assert_eq!(len, 0);
1077         let mut n = DList::new();
1078         assert!(n.iter_mut().next().is_none());
1079         n.push_front(4i);
1080         n.push_back(5);
1081         let mut it = n.iter_mut();
1082         assert_eq!(it.size_hint(), (2, Some(2)));
1083         assert!(it.next().is_some());
1084         assert!(it.next().is_some());
1085         assert_eq!(it.size_hint(), (0, Some(0)));
1086         assert!(it.next().is_none());
1087     }
1088
1089     #[test]
1090     fn test_iterator_mut_double_end() {
1091         let mut n = DList::new();
1092         assert!(n.iter_mut().next_back().is_none());
1093         n.push_front(4i);
1094         n.push_front(5);
1095         n.push_front(6);
1096         let mut it = n.iter_mut();
1097         assert_eq!(it.size_hint(), (3, Some(3)));
1098         assert_eq!(*it.next().unwrap(), 6);
1099         assert_eq!(it.size_hint(), (2, Some(2)));
1100         assert_eq!(*it.next_back().unwrap(), 4);
1101         assert_eq!(it.size_hint(), (1, Some(1)));
1102         assert_eq!(*it.next_back().unwrap(), 5);
1103         assert!(it.next_back().is_none());
1104         assert!(it.next().is_none());
1105     }
1106
1107     #[test]
1108     fn test_insert_prev() {
1109         let mut m = list_from(&[0i,2,4,6,8]);
1110         let len = m.len();
1111         {
1112             let mut it = m.iter_mut();
1113             it.insert_next(-2);
1114             loop {
1115                 match it.next() {
1116                     None => break,
1117                     Some(elt) => {
1118                         it.insert_next(*elt + 1);
1119                         match it.peek_next() {
1120                             Some(x) => assert_eq!(*x, *elt + 2),
1121                             None => assert_eq!(8, *elt),
1122                         }
1123                     }
1124                 }
1125             }
1126             it.insert_next(0);
1127             it.insert_next(1);
1128         }
1129         check_links(&m);
1130         assert_eq!(m.len(), 3 + len * 2);
1131         assert_eq!(m.into_iter().collect::<Vec<int>>(), vec![-2,0,1,2,3,4,5,6,7,8,9,0,1]);
1132     }
1133
1134     #[test]
1135     fn test_merge() {
1136         let mut m = list_from(&[0i, 1, 3, 5, 6, 7, 2]);
1137         let n = list_from(&[-1i, 0, 0, 7, 7, 9]);
1138         let len = m.len() + n.len();
1139         m.merge(n, |a, b| a <= b);
1140         assert_eq!(m.len(), len);
1141         check_links(&m);
1142         let res = m.into_iter().collect::<Vec<int>>();
1143         assert_eq!(res, vec![-1, 0, 0, 0, 1, 3, 5, 6, 7, 2, 7, 7, 9]);
1144     }
1145
1146     #[test]
1147     fn test_insert_ordered() {
1148         let mut n = DList::new();
1149         n.insert_ordered(1i);
1150         assert_eq!(n.len(), 1);
1151         assert_eq!(n.pop_front(), Some(1));
1152
1153         let mut m = DList::new();
1154         m.push_back(2i);
1155         m.push_back(4);
1156         m.insert_ordered(3);
1157         check_links(&m);
1158         assert_eq!(vec![2,3,4], m.into_iter().collect::<Vec<int>>());
1159     }
1160
1161     #[test]
1162     fn test_mut_rev_iter() {
1163         let mut m = generate_test();
1164         for (i, elt) in m.iter_mut().rev().enumerate() {
1165             assert_eq!((6-i) as int, *elt);
1166         }
1167         let mut n = DList::new();
1168         assert!(n.iter_mut().rev().next().is_none());
1169         n.push_front(4i);
1170         let mut it = n.iter_mut().rev();
1171         assert!(it.next().is_some());
1172         assert!(it.next().is_none());
1173     }
1174
1175     #[test]
1176     fn test_send() {
1177         let n = list_from(&[1i,2,3]);
1178         spawn(move || {
1179             check_links(&n);
1180             let a: &[_] = &[&1,&2,&3];
1181             assert_eq!(a, n.iter().collect::<Vec<&int>>());
1182         });
1183     }
1184
1185     #[test]
1186     fn test_eq() {
1187         let mut n: DList<u8> = list_from(&[]);
1188         let mut m = list_from(&[]);
1189         assert!(n == m);
1190         n.push_front(1);
1191         assert!(n != m);
1192         m.push_back(1);
1193         assert!(n == m);
1194
1195         let n = list_from(&[2i,3,4]);
1196         let m = list_from(&[1i,2,3]);
1197         assert!(n != m);
1198     }
1199
1200     #[test]
1201     fn test_hash() {
1202       let mut x = DList::new();
1203       let mut y = DList::new();
1204
1205       assert!(hash::hash(&x) == hash::hash(&y));
1206
1207       x.push_back(1i);
1208       x.push_back(2);
1209       x.push_back(3);
1210
1211       y.push_front(3i);
1212       y.push_front(2);
1213       y.push_front(1);
1214
1215       assert!(hash::hash(&x) == hash::hash(&y));
1216     }
1217
1218     #[test]
1219     fn test_ord() {
1220         let n: DList<int> = list_from(&[]);
1221         let m = list_from(&[1i,2,3]);
1222         assert!(n < m);
1223         assert!(m > n);
1224         assert!(n <= n);
1225         assert!(n >= n);
1226     }
1227
1228     #[test]
1229     fn test_ord_nan() {
1230         let nan = 0.0f64/0.0;
1231         let n = list_from(&[nan]);
1232         let m = list_from(&[nan]);
1233         assert!(!(n < m));
1234         assert!(!(n > m));
1235         assert!(!(n <= m));
1236         assert!(!(n >= m));
1237
1238         let n = list_from(&[nan]);
1239         let one = list_from(&[1.0f64]);
1240         assert!(!(n < one));
1241         assert!(!(n > one));
1242         assert!(!(n <= one));
1243         assert!(!(n >= one));
1244
1245         let u = list_from(&[1.0f64,2.0,nan]);
1246         let v = list_from(&[1.0f64,2.0,3.0]);
1247         assert!(!(u < v));
1248         assert!(!(u > v));
1249         assert!(!(u <= v));
1250         assert!(!(u >= v));
1251
1252         let s = list_from(&[1.0f64,2.0,4.0,2.0]);
1253         let t = list_from(&[1.0f64,2.0,3.0,2.0]);
1254         assert!(!(s < t));
1255         assert!(s > one);
1256         assert!(!(s <= one));
1257         assert!(s >= one);
1258     }
1259
1260     #[test]
1261     fn test_fuzz() {
1262         for _ in range(0u, 25) {
1263             fuzz_test(3);
1264             fuzz_test(16);
1265             fuzz_test(189);
1266         }
1267     }
1268
1269     #[test]
1270     fn test_show() {
1271         let list: DList<int> = range(0i, 10).collect();
1272         assert!(list.to_string() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1273
1274         let list: DList<&str> = vec!["just", "one", "test", "more"].iter()
1275                                                                    .map(|&s| s)
1276                                                                    .collect();
1277         assert!(list.to_string() == "[just, one, test, more]");
1278     }
1279
1280     #[cfg(test)]
1281     fn fuzz_test(sz: int) {
1282         let mut m: DList<int> = DList::new();
1283         let mut v = vec![];
1284         for i in range(0, sz) {
1285             check_links(&m);
1286             let r: u8 = rand::random();
1287             match r % 6 {
1288                 0 => {
1289                     m.pop_back();
1290                     v.pop();
1291                 }
1292                 1 => {
1293                     m.pop_front();
1294                     v.remove(0);
1295                 }
1296                 2 | 4 =>  {
1297                     m.push_front(-i);
1298                     v.insert(0, -i);
1299                 }
1300                 3 | 5 | _ => {
1301                     m.push_back(i);
1302                     v.push(i);
1303                 }
1304             }
1305         }
1306
1307         check_links(&m);
1308
1309         let mut i = 0u;
1310         for (a, &b) in m.into_iter().zip(v.iter()) {
1311             i += 1;
1312             assert_eq!(a, b);
1313         }
1314         assert_eq!(i, v.len());
1315     }
1316
1317     #[bench]
1318     fn bench_collect_into(b: &mut test::Bencher) {
1319         let v = &[0i, ..64];
1320         b.iter(|| {
1321             let _: DList<int> = v.iter().map(|x| *x).collect();
1322         })
1323     }
1324
1325     #[bench]
1326     fn bench_push_front(b: &mut test::Bencher) {
1327         let mut m: DList<int> = DList::new();
1328         b.iter(|| {
1329             m.push_front(0);
1330         })
1331     }
1332
1333     #[bench]
1334     fn bench_push_back(b: &mut test::Bencher) {
1335         let mut m: DList<int> = DList::new();
1336         b.iter(|| {
1337             m.push_back(0);
1338         })
1339     }
1340
1341     #[bench]
1342     fn bench_push_back_pop_back(b: &mut test::Bencher) {
1343         let mut m: DList<int> = DList::new();
1344         b.iter(|| {
1345             m.push_back(0);
1346             m.pop_back();
1347         })
1348     }
1349
1350     #[bench]
1351     fn bench_push_front_pop_front(b: &mut test::Bencher) {
1352         let mut m: DList<int> = DList::new();
1353         b.iter(|| {
1354             m.push_front(0);
1355             m.pop_front();
1356         })
1357     }
1358
1359     #[bench]
1360     fn bench_rotate_forward(b: &mut test::Bencher) {
1361         let mut m: DList<int> = DList::new();
1362         m.push_front(0i);
1363         m.push_front(1);
1364         b.iter(|| {
1365             m.rotate_forward();
1366         })
1367     }
1368
1369     #[bench]
1370     fn bench_rotate_backward(b: &mut test::Bencher) {
1371         let mut m: DList<int> = DList::new();
1372         m.push_front(0i);
1373         m.push_front(1);
1374         b.iter(|| {
1375             m.rotate_backward();
1376         })
1377     }
1378
1379     #[bench]
1380     fn bench_iter(b: &mut test::Bencher) {
1381         let v = &[0i, ..128];
1382         let m: DList<int> = v.iter().map(|&x|x).collect();
1383         b.iter(|| {
1384             assert!(m.iter().count() == 128);
1385         })
1386     }
1387     #[bench]
1388     fn bench_iter_mut(b: &mut test::Bencher) {
1389         let v = &[0i, ..128];
1390         let mut m: DList<int> = v.iter().map(|&x|x).collect();
1391         b.iter(|| {
1392             assert!(m.iter_mut().count() == 128);
1393         })
1394     }
1395     #[bench]
1396     fn bench_iter_rev(b: &mut test::Bencher) {
1397         let v = &[0i, ..128];
1398         let m: DList<int> = v.iter().map(|&x|x).collect();
1399         b.iter(|| {
1400             assert!(m.iter().rev().count() == 128);
1401         })
1402     }
1403     #[bench]
1404     fn bench_iter_mut_rev(b: &mut test::Bencher) {
1405         let v = &[0i, ..128];
1406         let mut m: DList<int> = v.iter().map(|&x|x).collect();
1407         b.iter(|| {
1408             assert!(m.iter_mut().rev().count() == 128);
1409         })
1410     }
1411 }