1 use std::collections::LinkedList;
2 use std::panic::catch_unwind;
6 let mut m = LinkedList::<Box<_>>::new();
7 assert_eq!(m.pop_front(), None);
8 assert_eq!(m.pop_back(), None);
9 assert_eq!(m.pop_front(), None);
11 assert_eq!(m.pop_front(), Some(box 1));
14 assert_eq!(m.len(), 2);
15 assert_eq!(m.pop_front(), Some(box 2));
16 assert_eq!(m.pop_front(), Some(box 3));
17 assert_eq!(m.len(), 0);
18 assert_eq!(m.pop_front(), None);
23 assert_eq!(m.pop_front(), Some(box 1));
25 let mut n = LinkedList::new();
29 assert_eq!(n.front().unwrap(), &3);
30 let x = n.front_mut().unwrap();
35 assert_eq!(n.back().unwrap(), &2);
36 let y = n.back_mut().unwrap();
40 assert_eq!(n.pop_front(), Some(0));
41 assert_eq!(n.pop_front(), Some(1));
44 fn generate_test() -> LinkedList<i32> {
45 list_from(&[0, 1, 2, 3, 4, 5, 6])
48 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
49 v.iter().cloned().collect()
56 let mut m = LinkedList::new();
59 let p = m.split_off(0);
60 assert_eq!(m.len(), 0);
61 assert_eq!(p.len(), 1);
62 assert_eq!(p.back(), Some(&1));
63 assert_eq!(p.front(), Some(&1));
66 // not singleton, forwards
68 let u = vec![1, 2, 3, 4, 5];
69 let mut m = list_from(&u);
70 let mut n = m.split_off(2);
71 assert_eq!(m.len(), 2);
72 assert_eq!(n.len(), 3);
74 assert_eq!(m.pop_front(), Some(elt));
77 assert_eq!(n.pop_front(), Some(elt));
80 // not singleton, backwards
82 let u = vec![1, 2, 3, 4, 5];
83 let mut m = list_from(&u);
84 let mut n = m.split_off(4);
85 assert_eq!(m.len(), 4);
86 assert_eq!(n.len(), 1);
88 assert_eq!(m.pop_front(), Some(elt));
91 assert_eq!(n.pop_front(), Some(elt));
95 // no-op on the last index
97 let mut m = LinkedList::new();
100 let p = m.split_off(1);
101 assert_eq!(m.len(), 1);
102 assert_eq!(p.len(), 0);
103 assert_eq!(m.back(), Some(&1));
104 assert_eq!(m.front(), Some(&1));
110 let m = generate_test();
111 for (i, elt) in m.iter().enumerate() {
112 assert_eq!(i as i32, *elt);
114 let mut n = LinkedList::new();
115 assert_eq!(n.iter().next(), None);
117 let mut it = n.iter();
118 assert_eq!(it.size_hint(), (1, Some(1)));
119 assert_eq!(it.next().unwrap(), &4);
120 assert_eq!(it.size_hint(), (0, Some(0)));
121 assert_eq!(it.next(), None);
125 fn test_iterator_clone() {
126 let mut n = LinkedList::new();
130 let mut it = n.iter();
132 let mut jt = it.clone();
133 assert_eq!(it.next(), jt.next());
134 assert_eq!(it.next_back(), jt.next_back());
135 assert_eq!(it.next(), jt.next());
139 fn test_iterator_double_end() {
140 let mut n = LinkedList::new();
141 assert_eq!(n.iter().next(), None);
145 let mut it = n.iter();
146 assert_eq!(it.size_hint(), (3, Some(3)));
147 assert_eq!(it.next().unwrap(), &6);
148 assert_eq!(it.size_hint(), (2, Some(2)));
149 assert_eq!(it.next_back().unwrap(), &4);
150 assert_eq!(it.size_hint(), (1, Some(1)));
151 assert_eq!(it.next_back().unwrap(), &5);
152 assert_eq!(it.next_back(), None);
153 assert_eq!(it.next(), None);
158 let m = generate_test();
159 for (i, elt) in m.iter().rev().enumerate() {
160 assert_eq!((6 - i) as i32, *elt);
162 let mut n = LinkedList::new();
163 assert_eq!(n.iter().rev().next(), None);
165 let mut it = n.iter().rev();
166 assert_eq!(it.size_hint(), (1, Some(1)));
167 assert_eq!(it.next().unwrap(), &4);
168 assert_eq!(it.size_hint(), (0, Some(0)));
169 assert_eq!(it.next(), None);
174 let mut m = generate_test();
175 let mut len = m.len();
176 for (i, elt) in m.iter_mut().enumerate() {
177 assert_eq!(i as i32, *elt);
181 let mut n = LinkedList::new();
182 assert!(n.iter_mut().next().is_none());
185 let mut it = n.iter_mut();
186 assert_eq!(it.size_hint(), (2, Some(2)));
187 assert!(it.next().is_some());
188 assert!(it.next().is_some());
189 assert_eq!(it.size_hint(), (0, Some(0)));
190 assert!(it.next().is_none());
194 fn test_iterator_mut_double_end() {
195 let mut n = LinkedList::new();
196 assert!(n.iter_mut().next_back().is_none());
200 let mut it = n.iter_mut();
201 assert_eq!(it.size_hint(), (3, Some(3)));
202 assert_eq!(*it.next().unwrap(), 6);
203 assert_eq!(it.size_hint(), (2, Some(2)));
204 assert_eq!(*it.next_back().unwrap(), 4);
205 assert_eq!(it.size_hint(), (1, Some(1)));
206 assert_eq!(*it.next_back().unwrap(), 5);
207 assert!(it.next_back().is_none());
208 assert!(it.next().is_none());
212 fn test_mut_rev_iter() {
213 let mut m = generate_test();
214 for (i, elt) in m.iter_mut().rev().enumerate() {
215 assert_eq!((6 - i) as i32, *elt);
217 let mut n = LinkedList::new();
218 assert!(n.iter_mut().rev().next().is_none());
220 let mut it = n.iter_mut().rev();
221 assert!(it.next().is_some());
222 assert!(it.next().is_none());
227 let mut n = list_from(&[]);
228 let mut m = list_from(&[]);
235 let n = list_from(&[2, 3, 4]);
236 let m = list_from(&[1, 2, 3]);
244 let mut x = LinkedList::new();
245 let mut y = LinkedList::new();
247 assert!(hash(&x) == hash(&y));
257 assert!(hash(&x) == hash(&y));
262 let n = list_from(&[]);
263 let m = list_from(&[1, 2, 3]);
272 let nan = 0.0f64 / 0.0;
273 let n = list_from(&[nan]);
274 let m = list_from(&[nan]);
280 let n = list_from(&[nan]);
281 let one = list_from(&[1.0f64]);
284 assert!(!(n <= one));
285 assert!(!(n >= one));
287 let u = list_from(&[1.0f64, 2.0, nan]);
288 let v = list_from(&[1.0f64, 2.0, 3.0]);
294 let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
295 let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
298 assert!(!(s <= one));
304 let list: LinkedList<_> = (0..10).collect();
305 assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
307 let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
308 assert_eq!(format!("{:?}", list), "[\"just\", \"one\", \"test\", \"more\"]");
312 fn test_extend_ref() {
313 let mut a = LinkedList::new();
316 a.extend(&[2, 3, 4]);
318 assert_eq!(a.len(), 4);
319 assert_eq!(a, list_from(&[1, 2, 3, 4]));
321 let mut b = LinkedList::new();
326 assert_eq!(a.len(), 6);
327 assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
332 let mut a = LinkedList::new();
334 a.extend(vec![2, 3, 4]); // uses iterator
336 assert_eq!(a.len(), 4);
337 assert!(a.iter().eq(&[1, 2, 3, 4]));
339 let b: LinkedList<_> = vec![5, 6, 7].into_iter().collect();
340 a.extend(b); // specializes to `append`
342 assert_eq!(a.len(), 7);
343 assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
348 let mut l = LinkedList::new();
349 l.extend(&[2, 3, 4]);
351 assert!(l.contains(&3));
352 assert!(!l.contains(&1));
356 assert!(!l.contains(&3));
360 fn drain_filter_empty() {
361 let mut list: LinkedList<i32> = LinkedList::new();
364 let mut iter = list.drain_filter(|_| true);
365 assert_eq!(iter.size_hint(), (0, Some(0)));
366 assert_eq!(iter.next(), None);
367 assert_eq!(iter.size_hint(), (0, Some(0)));
368 assert_eq!(iter.next(), None);
369 assert_eq!(iter.size_hint(), (0, Some(0)));
372 assert_eq!(list.len(), 0);
373 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
377 fn drain_filter_zst() {
378 let mut list: LinkedList<_> = vec![(), (), (), (), ()].into_iter().collect();
379 let initial_len = list.len();
383 let mut iter = list.drain_filter(|_| true);
384 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
385 while let Some(_) = iter.next() {
387 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
389 assert_eq!(iter.size_hint(), (0, Some(0)));
390 assert_eq!(iter.next(), None);
391 assert_eq!(iter.size_hint(), (0, Some(0)));
394 assert_eq!(count, initial_len);
395 assert_eq!(list.len(), 0);
396 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
400 fn drain_filter_false() {
401 let mut list: LinkedList<_> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
403 let initial_len = list.len();
407 let mut iter = list.drain_filter(|_| false);
408 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
409 for _ in iter.by_ref() {
412 assert_eq!(iter.size_hint(), (0, Some(0)));
413 assert_eq!(iter.next(), None);
414 assert_eq!(iter.size_hint(), (0, Some(0)));
417 assert_eq!(count, 0);
418 assert_eq!(list.len(), initial_len);
419 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
423 fn drain_filter_true() {
424 let mut list: LinkedList<_> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
426 let initial_len = list.len();
430 let mut iter = list.drain_filter(|_| true);
431 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
432 while let Some(_) = iter.next() {
434 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
436 assert_eq!(iter.size_hint(), (0, Some(0)));
437 assert_eq!(iter.next(), None);
438 assert_eq!(iter.size_hint(), (0, Some(0)));
441 assert_eq!(count, initial_len);
442 assert_eq!(list.len(), 0);
443 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
447 fn drain_filter_complex() {
449 // [+xxx++++++xxxxx++++x+x++]
451 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
455 .collect::<LinkedList<_>>();
457 let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
458 assert_eq!(removed.len(), 10);
459 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
461 assert_eq!(list.len(), 14);
463 list.into_iter().collect::<Vec<_>>(),
464 vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
469 // [xxx++++++xxxxx++++x+x++]
471 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
474 .collect::<LinkedList<_>>();
476 let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
477 assert_eq!(removed.len(), 10);
478 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
480 assert_eq!(list.len(), 13);
482 list.into_iter().collect::<Vec<_>>(),
483 vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
488 // [xxx++++++xxxxx++++x+x]
490 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36]
492 .collect::<LinkedList<_>>();
494 let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
495 assert_eq!(removed.len(), 10);
496 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
498 assert_eq!(list.len(), 11);
500 list.into_iter().collect::<Vec<_>>(),
501 vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]
506 // [xxxxxxxxxx+++++++++++]
507 let mut list = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
509 .collect::<LinkedList<_>>();
511 let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
512 assert_eq!(removed.len(), 10);
513 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
515 assert_eq!(list.len(), 10);
516 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
520 // [+++++++++++xxxxxxxxxx]
521 let mut list = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
523 .collect::<LinkedList<_>>();
525 let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
526 assert_eq!(removed.len(), 10);
527 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
529 assert_eq!(list.len(), 10);
530 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
536 static mut DROPS: i32 = 0;
546 let mut ring = LinkedList::new();
547 ring.push_back(Elem);
548 ring.push_front(Elem);
549 ring.push_back(Elem);
550 ring.push_front(Elem);
553 assert_eq!(unsafe { DROPS }, 4);
557 fn test_drop_with_pop() {
558 static mut DROPS: i32 = 0;
568 let mut ring = LinkedList::new();
569 ring.push_back(Elem);
570 ring.push_front(Elem);
571 ring.push_back(Elem);
572 ring.push_front(Elem);
574 drop(ring.pop_back());
575 drop(ring.pop_front());
576 assert_eq!(unsafe { DROPS }, 2);
579 assert_eq!(unsafe { DROPS }, 4);
583 fn test_drop_clear() {
584 static mut DROPS: i32 = 0;
594 let mut ring = LinkedList::new();
595 ring.push_back(Elem);
596 ring.push_front(Elem);
597 ring.push_back(Elem);
598 ring.push_front(Elem);
600 assert_eq!(unsafe { DROPS }, 4);
603 assert_eq!(unsafe { DROPS }, 4);
607 fn test_drop_panic() {
608 static mut DROPS: i32 = 0;
619 panic!("panic in `drop`");
624 let mut q = LinkedList::new();
625 q.push_back(D(false));
626 q.push_back(D(false));
627 q.push_back(D(false));
628 q.push_back(D(false));
629 q.push_back(D(false));
630 q.push_front(D(false));
631 q.push_front(D(false));
632 q.push_front(D(true));
634 catch_unwind(move || drop(q)).ok();
636 assert_eq!(unsafe { DROPS }, 8);