1 // Copyright 2012-2015 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 `LinkedList` allows pushing and popping elements at either end and is thus
14 //! efficiently usable as a double-ended queue.
16 // LinkedList is constructed like a singly-linked list over the field `next`.
17 // including the last link being None; each Node owns its `next` field.
19 // Backlinks over LinkedList::prev are raw pointers that form a full chain in
20 // the reverse direction.
22 #![stable(feature = "rust1", since = "1.0.0")]
26 use alloc
::boxed
::Box
;
27 use core
::cmp
::Ordering
;
28 use core
::default::Default
;
30 use core
::hash
::{Hasher, Hash}
;
32 use core
::hash
::Writer
;
33 use core
::iter
::{self, FromIterator, IntoIterator}
;
37 #[deprecated(since = "1.0.0", reason = "renamed to LinkedList")]
38 #[unstable(feature = "collections")]
39 pub use LinkedList
as DList
;
41 /// A doubly-linked list.
42 #[stable(feature = "rust1", since = "1.0.0")]
43 pub struct LinkedList
<T
> {
46 list_tail
: Rawlink
<Node
<T
>>,
49 type Link
<T
> = Option
<Box
<Node
<T
>>>;
55 impl<T
> Copy
for Rawlink
<T
> {}
56 unsafe impl<T
:'
static+Send
> Send
for Rawlink
<T
> {}
57 unsafe impl<T
:Send
+Sync
> Sync
for Rawlink
<T
> {}
61 prev
: Rawlink
<Node
<T
>>,
65 /// An iterator over references to the items of a `LinkedList`.
66 #[stable(feature = "rust1", since = "1.0.0")]
67 pub struct Iter
<'a
, T
:'a
> {
69 tail
: Rawlink
<Node
<T
>>,
73 // FIXME #19839: deriving is too aggressive on the bounds (T doesn't need to be Clone).
74 #[stable(feature = "rust1", since = "1.0.0")]
75 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
76 fn clone(&self) -> Iter
<'a
, T
> {
78 head
: self.head
.clone(),
85 /// An iterator over mutable references to the items of a `LinkedList`.
86 #[stable(feature = "rust1", since = "1.0.0")]
87 pub struct IterMut
<'a
, T
:'a
> {
88 list
: &'a
mut LinkedList
<T
>,
89 head
: Rawlink
<Node
<T
>>,
90 tail
: Rawlink
<Node
<T
>>,
94 /// An iterator over mutable references to the items of a `LinkedList`.
96 #[stable(feature = "rust1", since = "1.0.0")]
97 pub struct IntoIter
<T
> {
101 /// Rawlink is a type like Option<T> but for holding a raw pointer
103 /// Like Option::None for Rawlink
104 fn none() -> Rawlink
<T
> {
105 Rawlink{p: ptr::null_mut()}
108 /// Like Option::Some for Rawlink
109 fn some(n
: &mut T
) -> Rawlink
<T
> {
113 /// Convert the `Rawlink` into an Option value
114 fn resolve_immut
<'a
>(&self) -> Option
<&'a T
> {
116 mem
::transmute(self.p
.as_ref())
120 /// Convert the `Rawlink` into an Option value
121 fn resolve
<'a
>(&mut self) -> Option
<&'a
mut T
> {
122 if self.p
.is_null() {
125 Some(unsafe { mem::transmute(self.p) }
)
129 /// Return the `Rawlink` and replace with `Rawlink::none()`
130 fn take(&mut self) -> Rawlink
<T
> {
131 mem
::replace(self, Rawlink
::none())
135 impl<T
> Clone
for Rawlink
<T
> {
137 fn clone(&self) -> Rawlink
<T
> {
143 fn new(v
: T
) -> Node
<T
> {
144 Node{value: v, next: None, prev: Rawlink::none()}
148 /// Set the .prev field on `next`, then return `Some(next)`
149 fn link_with_prev
<T
>(mut next
: Box
<Node
<T
>>, prev
: Rawlink
<Node
<T
>>)
156 impl<T
> LinkedList
<T
> {
157 /// Add a Node first in the list
159 fn push_front_node(&mut self, mut new_head
: Box
<Node
<T
>>) {
160 match self.list_head
{
162 self.list_tail
= Rawlink
::some(&mut *new_head
);
163 self.list_head
= link_with_prev(new_head
, Rawlink
::none());
165 Some(ref mut head
) => {
166 new_head
.prev
= Rawlink
::none();
167 head
.prev
= Rawlink
::some(&mut *new_head
);
168 mem
::swap(head
, &mut new_head
);
169 head
.next
= Some(new_head
);
175 /// Remove the first Node and return it, or None if the list is empty
177 fn pop_front_node(&mut self) -> Option
<Box
<Node
<T
>>> {
178 self.list_head
.take().map(|mut front_node
| {
180 match front_node
.next
.take() {
181 Some(node
) => self.list_head
= link_with_prev(node
, Rawlink
::none()),
182 None
=> self.list_tail
= Rawlink
::none()
188 /// Add a Node last in the list
190 fn push_back_node(&mut self, mut new_tail
: Box
<Node
<T
>>) {
191 match self.list_tail
.resolve() {
192 None
=> return self.push_front_node(new_tail
),
194 self.list_tail
= Rawlink
::some(&mut *new_tail
);
195 tail
.next
= link_with_prev(new_tail
, Rawlink
::some(tail
));
201 /// Remove the last Node and return it, or None if the list is empty
203 fn pop_back_node(&mut self) -> Option
<Box
<Node
<T
>>> {
204 self.list_tail
.resolve().map_or(None
, |tail
| {
206 self.list_tail
= tail
.prev
;
207 match tail
.prev
.resolve() {
208 None
=> self.list_head
.take(),
209 Some(tail_prev
) => tail_prev
.next
.take()
215 #[stable(feature = "rust1", since = "1.0.0")]
216 impl<T
> Default
for LinkedList
<T
> {
218 #[stable(feature = "rust1", since = "1.0.0")]
219 fn default() -> LinkedList
<T
> { LinkedList::new() }
222 impl<T
> LinkedList
<T
> {
223 /// Creates an empty `LinkedList`.
225 #[stable(feature = "rust1", since = "1.0.0")]
226 pub fn new() -> LinkedList
<T
> {
227 LinkedList{list_head: None, list_tail: Rawlink::none(), length: 0}
230 /// Moves all elements from `other` to the end of the list.
232 /// This reuses all the nodes from `other` and moves them into `self`. After
233 /// this operation, `other` becomes empty.
235 /// This operation should compute in O(1) time and O(1) memory.
240 /// use std::collections::LinkedList;
242 /// let mut a = LinkedList::new();
243 /// let mut b = LinkedList::new();
249 /// a.append(&mut b);
251 /// for e in a.iter() {
252 /// println!("{}", e); // prints 1, then 2, then 3, then 4
254 /// println!("{}", b.len()); // prints 0
256 pub fn append(&mut self, other
: &mut LinkedList
<T
>) {
257 match self.list_tail
.resolve() {
259 self.length
= other
.length
;
260 self.list_head
= other
.list_head
.take();
261 self.list_tail
= other
.list_tail
.take();
264 // Carefully empty `other`.
265 let o_tail
= other
.list_tail
.take();
266 let o_length
= other
.length
;
267 match other
.list_head
.take() {
270 tail
.next
= link_with_prev(node
, self.list_tail
);
271 self.list_tail
= o_tail
;
272 self.length
+= o_length
;
280 /// Provides a forward iterator.
282 #[stable(feature = "rust1", since = "1.0.0")]
283 pub fn iter(&self) -> Iter
<T
> {
284 Iter{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
287 /// Provides a forward iterator with mutable references.
289 #[stable(feature = "rust1", since = "1.0.0")]
290 pub fn iter_mut(&mut self) -> IterMut
<T
> {
291 let head_raw
= match self.list_head
{
292 Some(ref mut h
) => Rawlink
::some(&mut **h
),
293 None
=> Rawlink
::none(),
298 tail
: self.list_tail
,
303 /// Consumes the list into an iterator yielding elements by value.
305 #[stable(feature = "rust1", since = "1.0.0")]
306 pub fn into_iter(self) -> IntoIter
<T
> {
310 /// Returns `true` if the `LinkedList` is empty.
312 /// This operation should compute in O(1) time.
317 /// use std::collections::LinkedList;
319 /// let mut dl = LinkedList::new();
320 /// assert!(dl.is_empty());
322 /// dl.push_front("foo");
323 /// assert!(!dl.is_empty());
326 #[stable(feature = "rust1", since = "1.0.0")]
327 pub fn is_empty(&self) -> bool
{
328 self.list_head
.is_none()
331 /// Returns the length of the `LinkedList`.
333 /// This operation should compute in O(1) time.
338 /// use std::collections::LinkedList;
340 /// let mut dl = LinkedList::new();
342 /// dl.push_front(2);
343 /// assert_eq!(dl.len(), 1);
345 /// dl.push_front(1);
346 /// assert_eq!(dl.len(), 2);
349 /// assert_eq!(dl.len(), 3);
353 #[stable(feature = "rust1", since = "1.0.0")]
354 pub fn len(&self) -> usize {
358 /// Removes all elements from the `LinkedList`.
360 /// This operation should compute in O(n) time.
365 /// use std::collections::LinkedList;
367 /// let mut dl = LinkedList::new();
369 /// dl.push_front(2);
370 /// dl.push_front(1);
371 /// assert_eq!(dl.len(), 2);
372 /// assert_eq!(dl.front(), Some(&1));
375 /// assert_eq!(dl.len(), 0);
376 /// assert_eq!(dl.front(), None);
380 #[stable(feature = "rust1", since = "1.0.0")]
381 pub fn clear(&mut self) {
382 *self = LinkedList
::new()
385 /// Provides a reference to the front element, or `None` if the list is
391 /// use std::collections::LinkedList;
393 /// let mut dl = LinkedList::new();
394 /// assert_eq!(dl.front(), None);
396 /// dl.push_front(1);
397 /// assert_eq!(dl.front(), Some(&1));
401 #[stable(feature = "rust1", since = "1.0.0")]
402 pub fn front(&self) -> Option
<&T
> {
403 self.list_head
.as_ref().map(|head
| &head
.value
)
406 /// Provides a mutable reference to the front element, or `None` if the list
412 /// use std::collections::LinkedList;
414 /// let mut dl = LinkedList::new();
415 /// assert_eq!(dl.front(), None);
417 /// dl.push_front(1);
418 /// assert_eq!(dl.front(), Some(&1));
420 /// match dl.front_mut() {
422 /// Some(x) => *x = 5,
424 /// assert_eq!(dl.front(), Some(&5));
428 #[stable(feature = "rust1", since = "1.0.0")]
429 pub fn front_mut(&mut self) -> Option
<&mut T
> {
430 self.list_head
.as_mut().map(|head
| &mut head
.value
)
433 /// Provides a reference to the back element, or `None` if the list is
439 /// use std::collections::LinkedList;
441 /// let mut dl = LinkedList::new();
442 /// assert_eq!(dl.back(), None);
445 /// assert_eq!(dl.back(), Some(&1));
449 #[stable(feature = "rust1", since = "1.0.0")]
450 pub fn back(&self) -> Option
<&T
> {
451 self.list_tail
.resolve_immut().as_ref().map(|tail
| &tail
.value
)
454 /// Provides a mutable reference to the back element, or `None` if the list
460 /// use std::collections::LinkedList;
462 /// let mut dl = LinkedList::new();
463 /// assert_eq!(dl.back(), None);
466 /// assert_eq!(dl.back(), Some(&1));
468 /// match dl.back_mut() {
470 /// Some(x) => *x = 5,
472 /// assert_eq!(dl.back(), Some(&5));
476 #[stable(feature = "rust1", since = "1.0.0")]
477 pub fn back_mut(&mut self) -> Option
<&mut T
> {
478 self.list_tail
.resolve().map(|tail
| &mut tail
.value
)
481 /// Adds an element first in the list.
483 /// This operation should compute in O(1) time.
488 /// use std::collections::LinkedList;
490 /// let mut dl = LinkedList::new();
492 /// dl.push_front(2);
493 /// assert_eq!(dl.front().unwrap(), &2);
495 /// dl.push_front(1);
496 /// assert_eq!(dl.front().unwrap(), &1);
499 #[stable(feature = "rust1", since = "1.0.0")]
500 pub fn push_front(&mut self, elt
: T
) {
501 self.push_front_node(box Node
::new(elt
))
504 /// Removes the first element and returns it, or `None` if the list is
507 /// This operation should compute in O(1) time.
512 /// use std::collections::LinkedList;
514 /// let mut d = LinkedList::new();
515 /// assert_eq!(d.pop_front(), None);
519 /// assert_eq!(d.pop_front(), Some(3));
520 /// assert_eq!(d.pop_front(), Some(1));
521 /// assert_eq!(d.pop_front(), None);
525 #[stable(feature = "rust1", since = "1.0.0")]
526 pub fn pop_front(&mut self) -> Option
<T
> {
527 self.pop_front_node().map(|box Node{value, ..}
| value
)
530 /// Appends an element to the back of a list
535 /// use std::collections::LinkedList;
537 /// let mut d = LinkedList::new();
540 /// assert_eq!(3, *d.back().unwrap());
542 #[stable(feature = "rust1", since = "1.0.0")]
543 pub fn push_back(&mut self, elt
: T
) {
544 self.push_back_node(box Node
::new(elt
))
547 /// Removes the last element from a list and returns it, or `None` if
553 /// use std::collections::LinkedList;
555 /// let mut d = LinkedList::new();
556 /// assert_eq!(d.pop_back(), None);
559 /// assert_eq!(d.pop_back(), Some(3));
561 #[stable(feature = "rust1", since = "1.0.0")]
562 pub fn pop_back(&mut self) -> Option
<T
> {
563 self.pop_back_node().map(|box Node{value, ..}
| value
)
566 /// Splits the list into two at the given index. Returns everything after the given index,
567 /// including the index.
571 /// Panics if `at > len`.
573 /// This operation should compute in O(n) time.
578 /// use std::collections::LinkedList;
580 /// let mut d = LinkedList::new();
586 /// let mut splitted = d.split_off(2);
588 /// assert_eq!(splitted.pop_front(), Some(1));
589 /// assert_eq!(splitted.pop_front(), None);
591 #[stable(feature = "rust1", since = "1.0.0")]
592 pub fn split_off(&mut self, at
: usize) -> LinkedList
<T
> {
593 let len
= self.len();
594 assert
!(at
<= len
, "Cannot split off at a nonexistent index");
596 return mem
::replace(self, LinkedList
::new());
597 } else if at
== len
{
598 return LinkedList
::new();
601 // Below, we iterate towards the `i-1`th node, either from the start or the end,
602 // depending on which would be faster.
603 let mut split_node
= if at
- 1 <= len
- 1 - (at
- 1) {
604 let mut iter
= self.iter_mut();
605 // instead of skipping using .skip() (which creates a new struct),
606 // we skip manually so we can access the head field without
607 // depending on implementation details of Skip
613 // better off starting from the end
614 let mut iter
= self.iter_mut();
615 for _
in 0..len
- 1 - (at
- 1) {
621 let mut splitted_list
= LinkedList
{
623 list_tail
: self.list_tail
,
627 mem
::swap(&mut split_node
.resolve().unwrap().next
, &mut splitted_list
.list_head
);
628 self.list_tail
= split_node
;
636 #[stable(feature = "rust1", since = "1.0.0")]
637 impl<T
> Drop
for LinkedList
<T
> {
639 // Dissolve the linked_list in backwards direction
640 // Just dropping the list_head can lead to stack exhaustion
641 // when length is >> 1_000_000
642 let mut tail
= self.list_tail
;
644 match tail
.resolve() {
647 prev
.next
.take(); // release Box<Node<T>>
653 self.list_head
= None
;
654 self.list_tail
= Rawlink
::none();
658 #[stable(feature = "rust1", since = "1.0.0")]
659 impl<'a
, A
> Iterator
for Iter
<'a
, A
> {
663 fn next(&mut self) -> Option
<&'a A
> {
667 self.head
.as_ref().map(|head
| {
669 self.head
= &head
.next
;
675 fn size_hint(&self) -> (usize, Option
<usize>) {
676 (self.nelem
, Some(self.nelem
))
680 #[stable(feature = "rust1", since = "1.0.0")]
681 impl<'a
, A
> DoubleEndedIterator
for Iter
<'a
, A
> {
683 fn next_back(&mut self) -> Option
<&'a A
> {
687 self.tail
.resolve_immut().as_ref().map(|prev
| {
689 self.tail
= prev
.prev
;
695 #[stable(feature = "rust1", since = "1.0.0")]
696 impl<'a
, A
> ExactSizeIterator
for Iter
<'a
, A
> {}
698 #[stable(feature = "rust1", since = "1.0.0")]
699 impl<'a
, A
> Iterator
for IterMut
<'a
, A
> {
700 type Item
= &'a
mut A
;
702 fn next(&mut self) -> Option
<&'a
mut A
> {
706 self.head
.resolve().map(|next
| {
708 self.head
= match next
.next
{
709 Some(ref mut node
) => Rawlink
::some(&mut **node
),
710 None
=> Rawlink
::none(),
717 fn size_hint(&self) -> (usize, Option
<usize>) {
718 (self.nelem
, Some(self.nelem
))
722 #[stable(feature = "rust1", since = "1.0.0")]
723 impl<'a
, A
> DoubleEndedIterator
for IterMut
<'a
, A
> {
725 fn next_back(&mut self) -> Option
<&'a
mut A
> {
729 self.tail
.resolve().map(|prev
| {
731 self.tail
= prev
.prev
;
737 #[stable(feature = "rust1", since = "1.0.0")]
738 impl<'a
, A
> ExactSizeIterator
for IterMut
<'a
, A
> {}
740 // private methods for IterMut
741 impl<'a
, A
> IterMut
<'a
, A
> {
742 fn insert_next_node(&mut self, mut ins_node
: Box
<Node
<A
>>) {
743 // Insert before `self.head` so that it is between the
744 // previously yielded element and self.head.
746 // The inserted node will not appear in further iteration.
747 match self.head
.resolve() {
748 None
=> { self.list.push_back_node(ins_node); }
750 let prev_node
= match node
.prev
.resolve() {
751 None
=> return self.list
.push_front_node(ins_node
),
754 let node_own
= prev_node
.next
.take().unwrap();
755 ins_node
.next
= link_with_prev(node_own
, Rawlink
::some(&mut *ins_node
));
756 prev_node
.next
= link_with_prev(ins_node
, Rawlink
::some(prev_node
));
757 self.list
.length
+= 1;
763 impl<'a
, A
> IterMut
<'a
, A
> {
764 /// Inserts `elt` just after the element most recently returned by `.next()`.
765 /// The inserted element does not appear in the iteration.
770 /// use std::collections::LinkedList;
772 /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
775 /// let mut it = list.iter_mut();
776 /// assert_eq!(it.next().unwrap(), &1);
777 /// // insert `2` after `1`
778 /// it.insert_next(2);
781 /// let vec: Vec<_> = list.into_iter().collect();
782 /// assert_eq!(vec, vec![1, 2, 3, 4]);
786 #[unstable(feature = "collections",
787 reason
= "this is probably better handled by a cursor type -- we'll see")]
788 pub fn insert_next(&mut self, elt
: A
) {
789 self.insert_next_node(box Node
::new(elt
))
792 /// Provides a reference to the next element, without changing the iterator.
797 /// use std::collections::LinkedList;
799 /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
801 /// let mut it = list.iter_mut();
802 /// assert_eq!(it.next().unwrap(), &1);
803 /// assert_eq!(it.peek_next().unwrap(), &2);
804 /// // We just peeked at 2, so it was not consumed from the iterator.
805 /// assert_eq!(it.next().unwrap(), &2);
808 #[unstable(feature = "collections",
809 reason
= "this is probably better handled by a cursor type -- we'll see")]
810 pub fn peek_next(&mut self) -> Option
<&mut A
> {
814 self.head
.resolve().map(|head
| &mut head
.value
)
818 #[stable(feature = "rust1", since = "1.0.0")]
819 impl<A
> Iterator
for IntoIter
<A
> {
823 fn next(&mut self) -> Option
<A
> { self.list.pop_front() }
826 fn size_hint(&self) -> (usize, Option
<usize>) {
827 (self.list
.length
, Some(self.list
.length
))
831 #[stable(feature = "rust1", since = "1.0.0")]
832 impl<A
> DoubleEndedIterator
for IntoIter
<A
> {
834 fn next_back(&mut self) -> Option
<A
> { self.list.pop_back() }
837 #[stable(feature = "rust1", since = "1.0.0")]
838 impl<A
> FromIterator
<A
> for LinkedList
<A
> {
839 fn from_iter
<T
: IntoIterator
<Item
=A
>>(iter
: T
) -> LinkedList
<A
> {
840 let mut ret
= DList
::new();
846 #[stable(feature = "rust1", since = "1.0.0")]
847 impl<T
> IntoIterator
for LinkedList
<T
> {
849 type IntoIter
= IntoIter
<T
>;
851 fn into_iter(self) -> IntoIter
<T
> {
856 #[stable(feature = "rust1", since = "1.0.0")]
857 impl<'a
, T
> IntoIterator
for &'a LinkedList
<T
> {
859 type IntoIter
= Iter
<'a
, T
>;
861 fn into_iter(self) -> Iter
<'a
, T
> {
866 impl<'a
, T
> IntoIterator
for &'a
mut LinkedList
<T
> {
867 type Item
= &'a
mut T
;
868 type IntoIter
= IterMut
<'a
, T
>;
870 fn into_iter(mut self) -> IterMut
<'a
, T
> {
875 #[stable(feature = "rust1", since = "1.0.0")]
876 impl<A
> Extend
<A
> for LinkedList
<A
> {
877 fn extend
<T
: IntoIterator
<Item
=A
>>(&mut self, iter
: T
) {
878 for elt
in iter { self.push_back(elt); }
882 #[stable(feature = "rust1", since = "1.0.0")]
883 impl<A
: PartialEq
> PartialEq
for LinkedList
<A
> {
884 fn eq(&self, other
: &LinkedList
<A
>) -> bool
{
885 self.len() == other
.len() &&
886 iter
::order
::eq(self.iter(), other
.iter())
889 fn ne(&self, other
: &LinkedList
<A
>) -> bool
{
890 self.len() != other
.len() ||
891 iter
::order
::ne(self.iter(), other
.iter())
895 #[stable(feature = "rust1", since = "1.0.0")]
896 impl<A
: Eq
> Eq
for LinkedList
<A
> {}
898 #[stable(feature = "rust1", since = "1.0.0")]
899 impl<A
: PartialOrd
> PartialOrd
for LinkedList
<A
> {
900 fn partial_cmp(&self, other
: &LinkedList
<A
>) -> Option
<Ordering
> {
901 iter
::order
::partial_cmp(self.iter(), other
.iter())
905 #[stable(feature = "rust1", since = "1.0.0")]
906 impl<A
: Ord
> Ord
for LinkedList
<A
> {
908 fn cmp(&self, other
: &LinkedList
<A
>) -> Ordering
{
909 iter
::order
::cmp(self.iter(), other
.iter())
913 #[stable(feature = "rust1", since = "1.0.0")]
914 impl<A
: Clone
> Clone
for LinkedList
<A
> {
915 fn clone(&self) -> LinkedList
<A
> {
916 self.iter().cloned().collect()
920 #[stable(feature = "rust1", since = "1.0.0")]
921 impl<A
: fmt
::Debug
> fmt
::Debug
for LinkedList
<A
> {
922 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
923 try
!(write
!(f
, "LinkedList ["));
925 for (i
, e
) in self.iter().enumerate() {
926 if i
!= 0 { try!(write!(f, ", ")); }
927 try
!(write
!(f
, "{:?}", *e
));
934 #[stable(feature = "rust1", since = "1.0.0")]
936 impl<S
: Writer
+ Hasher
, A
: Hash
<S
>> Hash
<S
> for LinkedList
<A
> {
937 fn hash(&self, state
: &mut S
) {
938 self.len().hash(state
);
944 #[stable(feature = "rust1", since = "1.0.0")]
946 impl<A
: Hash
> Hash
for LinkedList
<A
> {
947 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
948 self.len().hash(state
);
959 use std
::hash
::{self, SipHasher}
;
964 use super::{LinkedList, Node}
;
966 pub fn check_links
<T
>(list
: &LinkedList
<T
>) {
968 let mut last_ptr
: Option
<&Node
<T
>> = None
;
969 let mut node_ptr
: &Node
<T
>;
970 match list
.list_head
{
971 None
=> { assert_eq!(0, list.length); return }
972 Some(ref node
) => node_ptr
= &**node
,
975 match (last_ptr
, node_ptr
.prev
.resolve_immut()) {
977 (None
, _
) => panic
!("prev link for list_head"),
978 (Some(p
), Some(pptr
)) => {
979 assert_eq
!(p
as *const Node
<T
>, pptr
as *const Node
<T
>);
981 _
=> panic
!("prev link is none, not good"),
983 match node_ptr
.next
{
985 last_ptr
= Some(node_ptr
);
995 assert_eq
!(len
, list
.length
);
1000 let mut m
= LinkedList
::new();
1001 assert_eq
!(m
.pop_front(), None
);
1002 assert_eq
!(m
.pop_back(), None
);
1003 assert_eq
!(m
.pop_front(), None
);
1004 m
.push_front(box 1);
1005 assert_eq
!(m
.pop_front(), Some(box 1));
1008 assert_eq
!(m
.len(), 2);
1009 assert_eq
!(m
.pop_front(), Some(box 2));
1010 assert_eq
!(m
.pop_front(), Some(box 3));
1011 assert_eq
!(m
.len(), 0);
1012 assert_eq
!(m
.pop_front(), None
);
1017 assert_eq
!(m
.pop_front(), Some(box 1));
1019 let mut n
= LinkedList
::new();
1023 assert_eq
!(n
.front().unwrap(), &3);
1024 let x
= n
.front_mut().unwrap();
1029 assert_eq
!(n
.back().unwrap(), &2);
1030 let y
= n
.back_mut().unwrap();
1034 assert_eq
!(n
.pop_front(), Some(0));
1035 assert_eq
!(n
.pop_front(), Some(1));
1039 fn generate_test() -> LinkedList
<i32> {
1040 list_from(&[0,1,2,3,4,5,6])
1044 fn list_from
<T
: Clone
>(v
: &[T
]) -> LinkedList
<T
> {
1045 v
.iter().cloned().collect()
1052 let mut m
= LinkedList
::<i32>::new();
1053 let mut n
= LinkedList
::new();
1056 assert_eq
!(m
.len(), 0);
1057 assert_eq
!(n
.len(), 0);
1059 // Non-empty to empty
1061 let mut m
= LinkedList
::new();
1062 let mut n
= LinkedList
::new();
1066 assert_eq
!(m
.len(), 1);
1067 assert_eq
!(m
.pop_back(), Some(2));
1068 assert_eq
!(n
.len(), 0);
1071 // Empty to non-empty
1073 let mut m
= LinkedList
::new();
1074 let mut n
= LinkedList
::new();
1078 assert_eq
!(m
.len(), 1);
1079 assert_eq
!(m
.pop_back(), Some(2));
1083 // Non-empty to non-empty
1084 let v
= vec
![1,2,3,4,5];
1085 let u
= vec
![9,8,1,2,3,4,5];
1086 let mut m
= list_from(&v
);
1087 let mut n
= list_from(&u
);
1092 assert_eq
!(sum
.len(), m
.len());
1094 assert_eq
!(m
.pop_front(), Some(elt
))
1096 assert_eq
!(n
.len(), 0);
1097 // let's make sure it's working properly, since we
1098 // did some direct changes to private members
1100 assert_eq
!(n
.len(), 1);
1101 assert_eq
!(n
.pop_front(), Some(3));
1106 fn test_split_off() {
1109 let mut m
= LinkedList
::new();
1112 let p
= m
.split_off(0);
1113 assert_eq
!(m
.len(), 0);
1114 assert_eq
!(p
.len(), 1);
1115 assert_eq
!(p
.back(), Some(&1));
1116 assert_eq
!(p
.front(), Some(&1));
1119 // not singleton, forwards
1121 let u
= vec
![1,2,3,4,5];
1122 let mut m
= list_from(&u
);
1123 let mut n
= m
.split_off(2);
1124 assert_eq
!(m
.len(), 2);
1125 assert_eq
!(n
.len(), 3);
1127 assert_eq
!(m
.pop_front(), Some(elt
));
1130 assert_eq
!(n
.pop_front(), Some(elt
));
1133 // not singleton, backwards
1135 let u
= vec
![1,2,3,4,5];
1136 let mut m
= list_from(&u
);
1137 let mut n
= m
.split_off(4);
1138 assert_eq
!(m
.len(), 4);
1139 assert_eq
!(n
.len(), 1);
1141 assert_eq
!(m
.pop_front(), Some(elt
));
1144 assert_eq
!(n
.pop_front(), Some(elt
));
1148 // no-op on the last index
1150 let mut m
= LinkedList
::new();
1153 let p
= m
.split_off(1);
1154 assert_eq
!(m
.len(), 1);
1155 assert_eq
!(p
.len(), 0);
1156 assert_eq
!(m
.back(), Some(&1));
1157 assert_eq
!(m
.front(), Some(&1));
1163 fn test_iterator() {
1164 let m
= generate_test();
1165 for (i
, elt
) in m
.iter().enumerate() {
1166 assert_eq
!(i
as i32, *elt
);
1168 let mut n
= LinkedList
::new();
1169 assert_eq
!(n
.iter().next(), None
);
1171 let mut it
= n
.iter();
1172 assert_eq
!(it
.size_hint(), (1, Some(1)));
1173 assert_eq
!(it
.next().unwrap(), &4);
1174 assert_eq
!(it
.size_hint(), (0, Some(0)));
1175 assert_eq
!(it
.next(), None
);
1179 fn test_iterator_clone() {
1180 let mut n
= LinkedList
::new();
1184 let mut it
= n
.iter();
1186 let mut jt
= it
.clone();
1187 assert_eq
!(it
.next(), jt
.next());
1188 assert_eq
!(it
.next_back(), jt
.next_back());
1189 assert_eq
!(it
.next(), jt
.next());
1193 fn test_iterator_double_end() {
1194 let mut n
= LinkedList
::new();
1195 assert_eq
!(n
.iter().next(), None
);
1199 let mut it
= n
.iter();
1200 assert_eq
!(it
.size_hint(), (3, Some(3)));
1201 assert_eq
!(it
.next().unwrap(), &6);
1202 assert_eq
!(it
.size_hint(), (2, Some(2)));
1203 assert_eq
!(it
.next_back().unwrap(), &4);
1204 assert_eq
!(it
.size_hint(), (1, Some(1)));
1205 assert_eq
!(it
.next_back().unwrap(), &5);
1206 assert_eq
!(it
.next_back(), None
);
1207 assert_eq
!(it
.next(), None
);
1211 fn test_rev_iter() {
1212 let m
= generate_test();
1213 for (i
, elt
) in m
.iter().rev().enumerate() {
1214 assert_eq
!((6 - i
) as i32, *elt
);
1216 let mut n
= LinkedList
::new();
1217 assert_eq
!(n
.iter().rev().next(), None
);
1219 let mut it
= n
.iter().rev();
1220 assert_eq
!(it
.size_hint(), (1, Some(1)));
1221 assert_eq
!(it
.next().unwrap(), &4);
1222 assert_eq
!(it
.size_hint(), (0, Some(0)));
1223 assert_eq
!(it
.next(), None
);
1227 fn test_mut_iter() {
1228 let mut m
= generate_test();
1229 let mut len
= m
.len();
1230 for (i
, elt
) in m
.iter_mut().enumerate() {
1231 assert_eq
!(i
as i32, *elt
);
1235 let mut n
= LinkedList
::new();
1236 assert
!(n
.iter_mut().next().is_none());
1239 let mut it
= n
.iter_mut();
1240 assert_eq
!(it
.size_hint(), (2, Some(2)));
1241 assert
!(it
.next().is_some());
1242 assert
!(it
.next().is_some());
1243 assert_eq
!(it
.size_hint(), (0, Some(0)));
1244 assert
!(it
.next().is_none());
1248 fn test_iterator_mut_double_end() {
1249 let mut n
= LinkedList
::new();
1250 assert
!(n
.iter_mut().next_back().is_none());
1254 let mut it
= n
.iter_mut();
1255 assert_eq
!(it
.size_hint(), (3, Some(3)));
1256 assert_eq
!(*it
.next().unwrap(), 6);
1257 assert_eq
!(it
.size_hint(), (2, Some(2)));
1258 assert_eq
!(*it
.next_back().unwrap(), 4);
1259 assert_eq
!(it
.size_hint(), (1, Some(1)));
1260 assert_eq
!(*it
.next_back().unwrap(), 5);
1261 assert
!(it
.next_back().is_none());
1262 assert
!(it
.next().is_none());
1266 fn test_insert_prev() {
1267 let mut m
= list_from(&[0,2,4,6,8]);
1270 let mut it
= m
.iter_mut();
1276 it
.insert_next(*elt
+ 1);
1277 match it
.peek_next() {
1278 Some(x
) => assert_eq
!(*x
, *elt
+ 2),
1279 None
=> assert_eq
!(8, *elt
),
1288 assert_eq
!(m
.len(), 3 + len
* 2);
1289 assert_eq
!(m
.into_iter().collect
::<Vec
<_
>>(), vec
![-2,0,1,2,3,4,5,6,7,8,9,0,1]);
1293 fn test_mut_rev_iter() {
1294 let mut m
= generate_test();
1295 for (i
, elt
) in m
.iter_mut().rev().enumerate() {
1296 assert_eq
!((6 - i
) as i32, *elt
);
1298 let mut n
= LinkedList
::new();
1299 assert
!(n
.iter_mut().rev().next().is_none());
1301 let mut it
= n
.iter_mut().rev();
1302 assert
!(it
.next().is_some());
1303 assert
!(it
.next().is_none());
1308 let n
= list_from(&[1,2,3]);
1309 thread
::spawn(move || {
1311 let a
: &[_
] = &[&1,&2,&3];
1312 assert_eq
!(a
, n
.iter().collect
::<Vec
<_
>>());
1313 }).join().ok().unwrap();
1318 let mut n
= list_from(&[]);
1319 let mut m
= list_from(&[]);
1326 let n
= list_from(&[2,3,4]);
1327 let m
= list_from(&[1,2,3]);
1333 let mut x
= LinkedList
::new();
1334 let mut y
= LinkedList
::new();
1336 assert
!(hash
::hash
::<_
, SipHasher
>(&x
) == hash
::hash
::<_
, SipHasher
>(&y
));
1346 assert
!(hash
::hash
::<_
, SipHasher
>(&x
) == hash
::hash
::<_
, SipHasher
>(&y
));
1351 let n
= list_from(&[]);
1352 let m
= list_from(&[1,2,3]);
1361 let nan
= 0.0f64/0.0;
1362 let n
= list_from(&[nan
]);
1363 let m
= list_from(&[nan
]);
1369 let n
= list_from(&[nan
]);
1370 let one
= list_from(&[1.0f64]);
1371 assert
!(!(n
< one
));
1372 assert
!(!(n
> one
));
1373 assert
!(!(n
<= one
));
1374 assert
!(!(n
>= one
));
1376 let u
= list_from(&[1.0f64,2.0,nan
]);
1377 let v
= list_from(&[1.0f64,2.0,3.0]);
1383 let s
= list_from(&[1.0f64,2.0,4.0,2.0]);
1384 let t
= list_from(&[1.0f64,2.0,3.0,2.0]);
1387 assert
!(!(s
<= one
));
1402 let list
: LinkedList
<_
> = (0..10).collect();
1403 assert_eq
!(format
!("{:?}", list
), "LinkedList [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1405 let list
: LinkedList
<_
> = vec
!["just", "one", "test", "more"].iter().cloned().collect();
1406 assert_eq
!(format
!("{:?}", list
), "LinkedList [\"just\", \"one\", \"test\", \"more\"]");
1410 fn fuzz_test(sz
: i32) {
1411 let mut m
: LinkedList
<_
> = LinkedList
::new();
1415 let r
: u8 = rand
::random();
1441 for (a
, &b
) in m
.into_iter().zip(v
.iter()) {
1445 assert_eq
!(i
, v
.len());
1449 fn bench_collect_into(b
: &mut test
::Bencher
) {
1452 let _
: LinkedList
<_
> = v
.iter().cloned().collect();
1457 fn bench_push_front(b
: &mut test
::Bencher
) {
1458 let mut m
: LinkedList
<_
> = LinkedList
::new();
1465 fn bench_push_back(b
: &mut test
::Bencher
) {
1466 let mut m
: LinkedList
<_
> = LinkedList
::new();
1473 fn bench_push_back_pop_back(b
: &mut test
::Bencher
) {
1474 let mut m
: LinkedList
<_
> = LinkedList
::new();
1482 fn bench_push_front_pop_front(b
: &mut test
::Bencher
) {
1483 let mut m
: LinkedList
<_
> = LinkedList
::new();
1491 fn bench_iter(b
: &mut test
::Bencher
) {
1493 let m
: LinkedList
<_
> = v
.iter().cloned().collect();
1495 assert
!(m
.iter().count() == 128);
1499 fn bench_iter_mut(b
: &mut test
::Bencher
) {
1501 let mut m
: LinkedList
<_
> = v
.iter().cloned().collect();
1503 assert
!(m
.iter_mut().count() == 128);
1507 fn bench_iter_rev(b
: &mut test
::Bencher
) {
1509 let m
: LinkedList
<_
> = v
.iter().cloned().collect();
1511 assert
!(m
.iter().rev().count() == 128);
1515 fn bench_iter_mut_rev(b
: &mut test
::Bencher
) {
1517 let mut m
: LinkedList
<_
> = v
.iter().cloned().collect();
1519 assert
!(m
.iter_mut().rev().count() == 128);