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.
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.
11 //! A doubly-linked list with owned nodes.
13 //! The DList allows pushing and popping elements at either end.
15 //! DList implements the trait Deque. It should be imported with `use
16 //! collections::Deque`.
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.
21 // Backlinks over DList::prev are raw pointers that form a full chain in
22 // the reverse direction.
26 use alloc::boxed::Box;
27 use core::default::Default;
33 use {Collection, Mutable, Deque, MutableSeq};
35 /// A doubly-linked list.
39 list_tail: Rawlink<Node<T>>,
42 type Link<T> = Option<Box<Node<T>>>;
43 struct Rawlink<T> { p: *mut T }
47 prev: Rawlink<Node<T>>,
51 /// Double-ended DList iterator
52 pub struct Items<'a, T> {
54 tail: Rawlink<Node<T>>,
58 // FIXME #11820: the &'a Option<> of the Link stops clone working.
59 impl<'a, T> Clone for Items<'a, T> {
60 fn clone(&self) -> Items<'a, T> { *self }
63 /// Double-ended mutable DList iterator
64 pub struct MutItems<'a, T> {
65 list: &'a mut DList<T>,
66 head: Rawlink<Node<T>>,
67 tail: Rawlink<Node<T>>,
71 /// DList consuming iterator
73 pub struct MoveItems<T> {
77 /// Rawlink is a type like Option<T> but for holding a raw pointer
79 /// Like Option::None for Rawlink
80 fn none() -> Rawlink<T> {
81 Rawlink{p: ptr::mut_null()}
84 /// Like Option::Some for Rawlink
85 fn some(n: &mut T) -> Rawlink<T> {
89 /// Convert the `Rawlink` into an Option value
90 fn resolve_immut<'a>(&self) -> Option<&'a T> {
92 mem::transmute(self.p.to_option())
96 /// Convert the `Rawlink` into an Option value
97 fn resolve<'a>(&mut self) -> Option<&'a mut T> {
101 Some(unsafe { mem::transmute(self.p) })
105 /// Return the `Rawlink` and replace with `Rawlink::none()`
106 fn take(&mut self) -> Rawlink<T> {
107 mem::replace(self, Rawlink::none())
111 impl<T> Clone for Rawlink<T> {
113 fn clone(&self) -> Rawlink<T> {
119 fn new(v: T) -> Node<T> {
120 Node{value: v, next: None, prev: Rawlink::none()}
124 /// Set the .prev field on `next`, then return `Some(next)`
125 fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
131 impl<T> Collection for DList<T> {
134 fn is_empty(&self) -> bool {
135 self.list_head.is_none()
139 fn len(&self) -> uint {
144 impl<T> Mutable for DList<T> {
145 /// Remove all elements from the DList
149 fn clear(&mut self) {
156 /// Add a Node first in the list
158 fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
159 match self.list_head {
161 self.list_tail = Rawlink::some(&mut *new_head);
162 self.list_head = link_with_prev(new_head, Rawlink::none());
164 Some(ref mut head) => {
165 new_head.prev = Rawlink::none();
166 head.prev = Rawlink::some(&mut *new_head);
167 mem::swap(head, &mut new_head);
168 head.next = Some(new_head);
174 /// Remove the first Node and return it, or None if the list is empty
176 fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
177 self.list_head.take().map(|mut front_node| {
179 match front_node.next.take() {
180 Some(node) => self.list_head = link_with_prev(node, Rawlink::none()),
181 None => self.list_tail = Rawlink::none()
187 /// Add a Node last in the list
189 fn push_back_node(&mut self, mut new_tail: Box<Node<T>>) {
190 match self.list_tail.resolve() {
191 None => return self.push_front_node(new_tail),
193 self.list_tail = Rawlink::some(&mut *new_tail);
194 tail.next = link_with_prev(new_tail, Rawlink::some(tail));
200 /// Remove the last Node and return it, or None if the list is empty
202 fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
203 self.list_tail.resolve().map_or(None, |tail| {
205 self.list_tail = tail.prev;
206 match tail.prev.resolve() {
207 None => self.list_head.take(),
208 Some(tail_prev) => tail_prev.next.take()
214 impl<T> Deque<T> for DList<T> {
215 /// Provide a reference to the front element, or None if the list is empty
217 fn front<'a>(&'a self) -> Option<&'a T> {
218 self.list_head.as_ref().map(|head| &head.value)
221 /// Provide a mutable reference to the front element, or None if the list is empty
223 fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
224 self.list_head.as_mut().map(|head| &mut head.value)
227 /// Provide a reference to the back element, or None if the list is empty
229 fn back<'a>(&'a self) -> Option<&'a T> {
230 self.list_tail.resolve_immut().as_ref().map(|tail| &tail.value)
233 /// Provide a mutable reference to the back element, or None if the list is empty
235 fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
236 self.list_tail.resolve().map(|tail| &mut tail.value)
239 /// Add an element first in the list
242 fn push_front(&mut self, elt: T) {
243 self.push_front_node(box Node::new(elt))
246 /// Remove the first element and return it, or None if the list is empty
249 fn pop_front(&mut self) -> Option<T> {
250 self.pop_front_node().map(|box Node{value, ..}| value)
253 /// Add an element last in the list
256 fn push_back(&mut self, elt: T) {
257 self.push_back_node(box Node::new(elt))
260 /// Remove the last element and return it, or None if the list is empty
263 fn pop_back(&mut self) -> Option<T> {
264 self.pop_back_node().map(|box Node{value, ..}| value)
268 impl<T> MutableSeq<T> for DList<T> {
269 fn push(&mut self, elt: T) { self.push_back(elt) }
270 fn pop(&mut self) -> Option<T> { self.pop_back() }
273 impl<T> Default for DList<T> {
275 fn default() -> DList<T> { DList::new() }
279 /// Create an empty DList
281 pub fn new() -> DList<T> {
282 DList{list_head: None, list_tail: Rawlink::none(), length: 0}
285 /// Move the last element to the front of the list.
287 /// If the list is empty, do nothing.
292 /// use std::collections::{DList, Deque};
294 /// let mut dl = DList::new();
295 /// dl.push_back(1i);
299 /// dl.rotate_forward();
301 /// for e in dl.iter() {
302 /// println!("{}", e); // prints 3, then 1, then 2
306 pub fn rotate_forward(&mut self) {
307 self.pop_back_node().map(|tail| {
308 self.push_front_node(tail)
312 /// Move the first element to the back of the list.
314 /// If the list is empty, do nothing.
319 /// use std::collections::{DList, Deque};
321 /// let mut dl = DList::new();
322 /// dl.push_back(1i);
326 /// dl.rotate_backward();
328 /// for e in dl.iter() {
329 /// println!("{}", e); // prints 2, then 3, then 1
333 pub fn rotate_backward(&mut self) {
334 self.pop_front_node().map(|head| {
335 self.push_back_node(head)
339 /// Add all elements from `other` to the end of the list
346 /// use std::collections::{DList, Deque};
348 /// let mut a = DList::new();
349 /// let mut b = DList::new();
357 /// for e in a.iter() {
358 /// println!("{}", e); // prints 1, then 2, then 3, then 4
361 pub fn append(&mut self, mut other: DList<T>) {
362 match self.list_tail.resolve() {
363 None => *self = other,
365 // Carefully empty `other`.
366 let o_tail = other.list_tail.take();
367 let o_length = other.length;
368 match other.list_head.take() {
371 tail.next = link_with_prev(node, self.list_tail);
372 self.list_tail = o_tail;
373 self.length += o_length;
380 /// Add all elements from `other` to the beginning of the list
387 /// use std::collections::{DList, Deque};
389 /// let mut a = DList::new();
390 /// let mut b = DList::new();
398 /// for e in a.iter() {
399 /// println!("{}", e); // prints 3, then 4, then 1, then 2
403 pub fn prepend(&mut self, mut other: DList<T>) {
404 mem::swap(self, &mut other);
408 /// Insert `elt` before the first `x` in the list where `f(x, elt)` is true,
416 /// use std::collections::{DList, Deque};
418 /// let mut a: DList<int> = DList::new();
424 /// // insert 11 before the first odd number in the list
425 /// a.insert_when(11, |&e, _| e % 2 == 1);
427 /// for e in a.iter() {
428 /// println!("{}", e); // prints 2, then 4, then 11, then 7, then 8
431 pub fn insert_when(&mut self, elt: T, f: |&T, &T| -> bool) {
433 let mut it = self.mut_iter();
435 match it.peek_next() {
437 Some(x) => if f(x, &elt) { break }
445 /// Merge DList `other` into this DList, using the function `f`.
446 /// Iterate the both DList with `a` from self and `b` from `other`, and
447 /// put `a` in the result if `f(a, b)` is true, else `b`.
450 pub fn merge(&mut self, mut other: DList<T>, f: |&T, &T| -> bool) {
452 let mut it = self.mut_iter();
454 let take_a = match (it.peek_next(), other.front()) {
455 (_ , None) => return,
457 (Some(ref mut x), Some(y)) => f(*x, y),
462 it.insert_next_node(other.pop_front_node().unwrap());
470 /// Provide a forward iterator
472 pub fn iter<'a>(&'a self) -> Items<'a, T> {
473 Items{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
476 /// Provide a forward iterator with mutable references
478 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
479 let head_raw = match self.list_head {
480 Some(ref mut h) => Rawlink::some(&mut **h),
481 None => Rawlink::none(),
486 tail: self.list_tail,
492 /// Consume the list into an iterator yielding elements by value
494 pub fn move_iter(self) -> MoveItems<T> {
495 MoveItems{list: self}
499 impl<T: Ord> DList<T> {
500 /// Insert `elt` sorted in ascending order
504 pub fn insert_ordered(&mut self, elt: T) {
505 self.insert_when(elt, |a, b| a >= b)
510 impl<T> Drop for DList<T> {
512 // Dissolve the dlist in backwards direction
513 // Just dropping the list_head can lead to stack exhaustion
514 // when length is >> 1_000_000
515 let mut tail = self.list_tail;
517 match tail.resolve() {
520 prev.next.take(); // release Box<Node<T>>
526 self.list_head = None;
527 self.list_tail = Rawlink::none();
532 impl<'a, A> Iterator<&'a A> for Items<'a, A> {
534 fn next(&mut self) -> Option<&'a A> {
538 self.head.as_ref().map(|head| {
540 self.head = &head.next;
546 fn size_hint(&self) -> (uint, Option<uint>) {
547 (self.nelem, Some(self.nelem))
551 impl<'a, A> DoubleEndedIterator<&'a A> for Items<'a, A> {
553 fn next_back(&mut self) -> Option<&'a A> {
557 self.tail.resolve_immut().as_ref().map(|prev| {
559 self.tail = prev.prev;
565 impl<'a, A> ExactSize<&'a A> for Items<'a, A> {}
567 impl<'a, A> Iterator<&'a mut A> for MutItems<'a, A> {
569 fn next(&mut self) -> Option<&'a mut A> {
573 self.head.resolve().map(|next| {
575 self.head = match next.next {
576 Some(ref mut node) => Rawlink::some(&mut **node),
577 None => Rawlink::none(),
584 fn size_hint(&self) -> (uint, Option<uint>) {
585 (self.nelem, Some(self.nelem))
589 impl<'a, A> DoubleEndedIterator<&'a mut A> for MutItems<'a, A> {
591 fn next_back(&mut self) -> Option<&'a mut A> {
595 self.tail.resolve().map(|prev| {
597 self.tail = prev.prev;
603 impl<'a, A> ExactSize<&'a mut A> for MutItems<'a, A> {}
605 /// Allow mutating the DList while iterating
606 pub trait ListInsertion<A> {
607 /// Insert `elt` just after to the element most recently returned by `.next()`
609 /// The inserted element does not appear in the iteration.
610 fn insert_next(&mut self, elt: A);
612 /// Provide a reference to the next element, without changing the iterator
613 fn peek_next<'a>(&'a mut self) -> Option<&'a mut A>;
616 // private methods for MutItems
617 impl<'a, A> MutItems<'a, A> {
618 fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
619 // Insert before `self.head` so that it is between the
620 // previously yielded element and self.head.
622 // The inserted node will not appear in further iteration.
623 match self.head.resolve() {
624 None => { self.list.push_back_node(ins_node); }
626 let prev_node = match node.prev.resolve() {
627 None => return self.list.push_front_node(ins_node),
630 let node_own = prev_node.next.take_unwrap();
631 ins_node.next = link_with_prev(node_own, Rawlink::some(&mut *ins_node));
632 prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
633 self.list.length += 1;
639 impl<'a, A> ListInsertion<A> for MutItems<'a, A> {
641 fn insert_next(&mut self, elt: A) {
642 self.insert_next_node(box Node::new(elt))
646 fn peek_next<'a>(&'a mut self) -> Option<&'a mut A> {
650 self.head.resolve().map(|head| &mut head.value)
654 impl<A> Iterator<A> for MoveItems<A> {
656 fn next(&mut self) -> Option<A> { self.list.pop_front() }
659 fn size_hint(&self) -> (uint, Option<uint>) {
660 (self.list.length, Some(self.list.length))
664 impl<A> DoubleEndedIterator<A> for MoveItems<A> {
666 fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
669 impl<A> FromIterator<A> for DList<A> {
670 fn from_iter<T: Iterator<A>>(iterator: T) -> DList<A> {
671 let mut ret = DList::new();
672 ret.extend(iterator);
677 impl<A> Extendable<A> for DList<A> {
678 fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
679 for elt in iterator { self.push_back(elt); }
683 impl<A: PartialEq> PartialEq for DList<A> {
684 fn eq(&self, other: &DList<A>) -> bool {
685 self.len() == other.len() &&
686 iter::order::eq(self.iter(), other.iter())
689 fn ne(&self, other: &DList<A>) -> bool {
690 self.len() != other.len() ||
691 iter::order::ne(self.iter(), other.iter())
695 impl<A: PartialOrd> PartialOrd for DList<A> {
696 fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> {
697 iter::order::partial_cmp(self.iter(), other.iter())
701 impl<A: Clone> Clone for DList<A> {
702 fn clone(&self) -> DList<A> {
703 self.iter().map(|x| x.clone()).collect()
707 impl<A: fmt::Show> fmt::Show for DList<A> {
708 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
709 try!(write!(f, "["));
711 for (i, e) in self.iter().enumerate() {
712 if i != 0 { try!(write!(f, ", ")); }
713 try!(write!(f, "{}", *e));
727 use {Deque, MutableSeq};
728 use super::{DList, Node, ListInsertion};
731 pub fn check_links<T>(list: &DList<T>) {
733 let mut last_ptr: Option<&Node<T>> = None;
734 let mut node_ptr: &Node<T>;
735 match list.list_head {
736 None => { assert_eq!(0u, list.length); return }
737 Some(ref node) => node_ptr = &**node,
740 match (last_ptr, node_ptr.prev.resolve_immut()) {
742 (None , _ ) => fail!("prev link for list_head"),
743 (Some(p), Some(pptr)) => {
744 assert_eq!(p as *const Node<T>, pptr as *const Node<T>);
746 _ => fail!("prev link is none, not good"),
748 match node_ptr.next {
750 last_ptr = Some(node_ptr);
760 assert_eq!(len, list.length);
765 let mut m: DList<Box<int>> = DList::new();
766 assert_eq!(m.pop_front(), None);
767 assert_eq!(m.pop_back(), None);
768 assert_eq!(m.pop_front(), None);
770 assert_eq!(m.pop_front(), Some(box 1));
773 assert_eq!(m.len(), 2);
774 assert_eq!(m.pop_front(), Some(box 2));
775 assert_eq!(m.pop_front(), Some(box 3));
776 assert_eq!(m.len(), 0);
777 assert_eq!(m.pop_front(), None);
782 assert_eq!(m.pop_front(), Some(box 1));
784 let mut n = DList::new();
788 assert_eq!(n.front().unwrap(), &3);
789 let x = n.front_mut().unwrap();
794 assert_eq!(n.back().unwrap(), &2);
795 let y = n.back_mut().unwrap();
799 assert_eq!(n.pop_front(), Some(0));
800 assert_eq!(n.pop_front(), Some(1));
804 fn generate_test() -> DList<int> {
805 list_from(&[0i,1,2,3,4,5,6])
809 fn list_from<T: Clone>(v: &[T]) -> DList<T> {
810 v.iter().map(|x| (*x).clone()).collect()
816 let mut m = DList::new();
817 let mut n = DList::new();
820 assert_eq!(m.len(), 1);
821 assert_eq!(m.pop_back(), Some(2));
825 let mut m = DList::new();
826 let n = DList::new();
829 assert_eq!(m.len(), 1);
830 assert_eq!(m.pop_back(), Some(2));
834 let v = vec![1i,2,3,4,5];
835 let u = vec![9i,8,1,2,3,4,5];
836 let mut m = list_from(v.as_slice());
837 m.append(list_from(u.as_slice()));
839 let sum = v.append(u.as_slice());
840 assert_eq!(sum.len(), m.len());
841 for elt in sum.move_iter() {
842 assert_eq!(m.pop_front(), Some(elt))
849 let mut m = DList::new();
850 let mut n = DList::new();
853 assert_eq!(m.len(), 1);
854 assert_eq!(m.pop_back(), Some(2));
858 let v = vec![1i,2,3,4,5];
859 let u = vec![9i,8,1,2,3,4,5];
860 let mut m = list_from(v.as_slice());
861 m.prepend(list_from(u.as_slice()));
863 let sum = u.append(v.as_slice());
864 assert_eq!(sum.len(), m.len());
865 for elt in sum.move_iter() {
866 assert_eq!(m.pop_front(), Some(elt))
872 let mut n: DList<int> = DList::new();
873 n.rotate_backward(); check_links(&n);
874 assert_eq!(n.len(), 0);
875 n.rotate_forward(); check_links(&n);
876 assert_eq!(n.len(), 0);
878 let v = vec![1i,2,3,4,5];
879 let mut m = list_from(v.as_slice());
880 m.rotate_backward(); check_links(&m);
881 m.rotate_forward(); check_links(&m);
882 assert_eq!(v.iter().collect::<Vec<&int>>(), m.iter().collect());
883 m.rotate_forward(); check_links(&m);
884 m.rotate_forward(); check_links(&m);
885 m.pop_front(); check_links(&m);
886 m.rotate_forward(); check_links(&m);
887 m.rotate_backward(); check_links(&m);
888 m.push_front(9); check_links(&m);
889 m.rotate_forward(); check_links(&m);
890 assert_eq!(vec![3i,9,5,1,2], m.move_iter().collect());
895 let m = generate_test();
896 for (i, elt) in m.iter().enumerate() {
897 assert_eq!(i as int, *elt);
899 let mut n = DList::new();
900 assert_eq!(n.iter().next(), None);
902 let mut it = n.iter();
903 assert_eq!(it.size_hint(), (1, Some(1)));
904 assert_eq!(it.next().unwrap(), &4);
905 assert_eq!(it.size_hint(), (0, Some(0)));
906 assert_eq!(it.next(), None);
910 fn test_iterator_clone() {
911 let mut n = DList::new();
915 let mut it = n.iter();
917 let mut jt = it.clone();
918 assert_eq!(it.next(), jt.next());
919 assert_eq!(it.next_back(), jt.next_back());
920 assert_eq!(it.next(), jt.next());
924 fn test_iterator_double_end() {
925 let mut n = DList::new();
926 assert_eq!(n.iter().next(), None);
930 let mut it = n.iter();
931 assert_eq!(it.size_hint(), (3, Some(3)));
932 assert_eq!(it.next().unwrap(), &6);
933 assert_eq!(it.size_hint(), (2, Some(2)));
934 assert_eq!(it.next_back().unwrap(), &4);
935 assert_eq!(it.size_hint(), (1, Some(1)));
936 assert_eq!(it.next_back().unwrap(), &5);
937 assert_eq!(it.next_back(), None);
938 assert_eq!(it.next(), None);
943 let m = generate_test();
944 for (i, elt) in m.iter().rev().enumerate() {
945 assert_eq!((6 - i) as int, *elt);
947 let mut n = DList::new();
948 assert_eq!(n.iter().rev().next(), None);
950 let mut it = n.iter().rev();
951 assert_eq!(it.size_hint(), (1, Some(1)));
952 assert_eq!(it.next().unwrap(), &4);
953 assert_eq!(it.size_hint(), (0, Some(0)));
954 assert_eq!(it.next(), None);
959 let mut m = generate_test();
960 let mut len = m.len();
961 for (i, elt) in m.mut_iter().enumerate() {
962 assert_eq!(i as int, *elt);
966 let mut n = DList::new();
967 assert!(n.mut_iter().next().is_none());
970 let mut it = n.mut_iter();
971 assert_eq!(it.size_hint(), (2, Some(2)));
972 assert!(it.next().is_some());
973 assert!(it.next().is_some());
974 assert_eq!(it.size_hint(), (0, Some(0)));
975 assert!(it.next().is_none());
979 fn test_iterator_mut_double_end() {
980 let mut n = DList::new();
981 assert!(n.mut_iter().next_back().is_none());
985 let mut it = n.mut_iter();
986 assert_eq!(it.size_hint(), (3, Some(3)));
987 assert_eq!(*it.next().unwrap(), 6);
988 assert_eq!(it.size_hint(), (2, Some(2)));
989 assert_eq!(*it.next_back().unwrap(), 4);
990 assert_eq!(it.size_hint(), (1, Some(1)));
991 assert_eq!(*it.next_back().unwrap(), 5);
992 assert!(it.next_back().is_none());
993 assert!(it.next().is_none());
997 fn test_insert_prev() {
998 let mut m = list_from(&[0i,2,4,6,8]);
1001 let mut it = m.mut_iter();
1007 it.insert_next(*elt + 1);
1008 match it.peek_next() {
1009 Some(x) => assert_eq!(*x, *elt + 2),
1010 None => assert_eq!(8, *elt),
1019 assert_eq!(m.len(), 3 + len * 2);
1020 assert_eq!(m.move_iter().collect::<Vec<int>>(), vec![-2,0,1,2,3,4,5,6,7,8,9,0,1]);
1025 let mut m = list_from([0i, 1, 3, 5, 6, 7, 2]);
1026 let n = list_from([-1i, 0, 0, 7, 7, 9]);
1027 let len = m.len() + n.len();
1028 m.merge(n, |a, b| a <= b);
1029 assert_eq!(m.len(), len);
1031 let res = m.move_iter().collect::<Vec<int>>();
1032 assert_eq!(res, vec![-1, 0, 0, 0, 1, 3, 5, 6, 7, 2, 7, 7, 9]);
1036 fn test_insert_ordered() {
1037 let mut n = DList::new();
1038 n.insert_ordered(1i);
1039 assert_eq!(n.len(), 1);
1040 assert_eq!(n.pop_front(), Some(1));
1042 let mut m = DList::new();
1045 m.insert_ordered(3);
1047 assert_eq!(vec![2,3,4], m.move_iter().collect::<Vec<int>>());
1051 fn test_mut_rev_iter() {
1052 let mut m = generate_test();
1053 for (i, elt) in m.mut_iter().rev().enumerate() {
1054 assert_eq!((6-i) as int, *elt);
1056 let mut n = DList::new();
1057 assert!(n.mut_iter().rev().next().is_none());
1059 let mut it = n.mut_iter().rev();
1060 assert!(it.next().is_some());
1061 assert!(it.next().is_none());
1066 let n = list_from([1i,2,3]);
1069 assert_eq!(&[&1,&2,&3], n.iter().collect::<Vec<&int>>().as_slice());
1075 let mut n: DList<u8> = list_from([]);
1076 let mut m = list_from([]);
1083 let n = list_from([2i,3,4]);
1084 let m = list_from([1i,2,3]);
1090 let n: DList<int> = list_from([]);
1091 let m = list_from([1i,2,3]);
1100 let nan = 0.0f64/0.0;
1101 let n = list_from([nan]);
1102 let m = list_from([nan]);
1108 let n = list_from([nan]);
1109 let one = list_from([1.0f64]);
1110 assert!(!(n < one));
1111 assert!(!(n > one));
1112 assert!(!(n <= one));
1113 assert!(!(n >= one));
1115 let u = list_from([1.0f64,2.0,nan]);
1116 let v = list_from([1.0f64,2.0,3.0]);
1122 let s = list_from([1.0f64,2.0,4.0,2.0]);
1123 let t = list_from([1.0f64,2.0,3.0,2.0]);
1126 assert!(!(s <= one));
1132 for _ in range(0u, 25) {
1141 let list: DList<int> = range(0i, 10).collect();
1142 assert!(list.to_string().as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1144 let list: DList<&str> = vec!["just", "one", "test", "more"].iter()
1147 assert!(list.to_string().as_slice() == "[just, one, test, more]");
1151 fn fuzz_test(sz: int) {
1152 let mut m: DList<int> = DList::new();
1154 for i in range(0, sz) {
1156 let r: u8 = rand::random();
1180 for (a, &b) in m.move_iter().zip(v.iter()) {
1184 assert_eq!(i, v.len());
1188 fn bench_collect_into(b: &mut test::Bencher) {
1189 let v = &[0i, ..64];
1191 let _: DList<int> = v.iter().map(|x| *x).collect();
1196 fn bench_push_front(b: &mut test::Bencher) {
1197 let mut m: DList<int> = DList::new();
1204 fn bench_push_back(b: &mut test::Bencher) {
1205 let mut m: DList<int> = DList::new();
1212 fn bench_push_back_pop_back(b: &mut test::Bencher) {
1213 let mut m: DList<int> = DList::new();
1221 fn bench_push_front_pop_front(b: &mut test::Bencher) {
1222 let mut m: DList<int> = DList::new();
1230 fn bench_rotate_forward(b: &mut test::Bencher) {
1231 let mut m: DList<int> = DList::new();
1240 fn bench_rotate_backward(b: &mut test::Bencher) {
1241 let mut m: DList<int> = DList::new();
1245 m.rotate_backward();
1250 fn bench_iter(b: &mut test::Bencher) {
1251 let v = &[0i, ..128];
1252 let m: DList<int> = v.iter().map(|&x|x).collect();
1254 assert!(m.iter().count() == 128);
1258 fn bench_iter_mut(b: &mut test::Bencher) {
1259 let v = &[0i, ..128];
1260 let mut m: DList<int> = v.iter().map(|&x|x).collect();
1262 assert!(m.mut_iter().count() == 128);
1266 fn bench_iter_rev(b: &mut test::Bencher) {
1267 let v = &[0i, ..128];
1268 let m: DList<int> = v.iter().map(|&x|x).collect();
1270 assert!(m.iter().rev().count() == 128);
1274 fn bench_iter_mut_rev(b: &mut test::Bencher) {
1275 let v = &[0i, ..128];
1276 let mut m: DList<int> = v.iter().map(|&x|x).collect();
1278 assert!(m.mut_iter().rev().count() == 128);