src/libcollections/dlist.rs

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