src/liballoc/tests/linked_list.rs

   1 use std::collections::LinkedList;
   2
   3 #[test]
   4 fn test_basic() {
   5     let mut m = LinkedList::<Box<_>>::new();
   6     assert_eq!(m.pop_front(), None);
   7     assert_eq!(m.pop_back(), None);
   8     assert_eq!(m.pop_front(), None);
   9     m.push_front(box 1);
  10     assert_eq!(m.pop_front(), Some(box 1));
  11     m.push_back(box 2);
  12     m.push_back(box 3);
  13     assert_eq!(m.len(), 2);
  14     assert_eq!(m.pop_front(), Some(box 2));
  15     assert_eq!(m.pop_front(), Some(box 3));
  16     assert_eq!(m.len(), 0);
  17     assert_eq!(m.pop_front(), None);
  18     m.push_back(box 1);
  19     m.push_back(box 3);
  20     m.push_back(box 5);
  21     m.push_back(box 7);
  22     assert_eq!(m.pop_front(), Some(box 1));
  23
  24     let mut n = LinkedList::new();
  25     n.push_front(2);
  26     n.push_front(3);
  27     {
  28         assert_eq!(n.front().unwrap(), &3);
  29         let x = n.front_mut().unwrap();
  30         assert_eq!(*x, 3);
  31         *x = 0;
  32     }
  33     {
  34         assert_eq!(n.back().unwrap(), &2);
  35         let y = n.back_mut().unwrap();
  36         assert_eq!(*y, 2);
  37         *y = 1;
  38     }
  39     assert_eq!(n.pop_front(), Some(0));
  40     assert_eq!(n.pop_front(), Some(1));
  41 }
  42
  43 #[cfg(test)]
  44 fn generate_test() -> LinkedList<i32> {
  45     list_from(&[0, 1, 2, 3, 4, 5, 6])
  46 }
  47
  48 #[cfg(test)]
  49 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
  50     v.iter().cloned().collect()
  51 }
  52
  53 #[test]
  54 fn test_split_off() {
  55     // singleton
  56     {
  57         let mut m = LinkedList::new();
  58         m.push_back(1);
  59
  60         let p = m.split_off(0);
  61         assert_eq!(m.len(), 0);
  62         assert_eq!(p.len(), 1);
  63         assert_eq!(p.back(), Some(&1));
  64         assert_eq!(p.front(), Some(&1));
  65     }
  66
  67     // not singleton, forwards
  68     {
  69         let u = vec![1, 2, 3, 4, 5];
  70         let mut m = list_from(&u);
  71         let mut n = m.split_off(2);
  72         assert_eq!(m.len(), 2);
  73         assert_eq!(n.len(), 3);
  74         for elt in 1..3 {
  75             assert_eq!(m.pop_front(), Some(elt));
  76         }
  77         for elt in 3..6 {
  78             assert_eq!(n.pop_front(), Some(elt));
  79         }
  80     }
  81     // not singleton, backwards
  82     {
  83         let u = vec![1, 2, 3, 4, 5];
  84         let mut m = list_from(&u);
  85         let mut n = m.split_off(4);
  86         assert_eq!(m.len(), 4);
  87         assert_eq!(n.len(), 1);
  88         for elt in 1..5 {
  89             assert_eq!(m.pop_front(), Some(elt));
  90         }
  91         for elt in 5..6 {
  92             assert_eq!(n.pop_front(), Some(elt));
  93         }
  94     }
  95
  96     // no-op on the last index
  97     {
  98         let mut m = LinkedList::new();
  99         m.push_back(1);
 100
 101         let p = m.split_off(1);
 102         assert_eq!(m.len(), 1);
 103         assert_eq!(p.len(), 0);
 104         assert_eq!(m.back(), Some(&1));
 105         assert_eq!(m.front(), Some(&1));
 106     }
 107
 108 }
 109
 110 #[test]
 111 fn test_iterator() {
 112     let m = generate_test();
 113     for (i, elt) in m.iter().enumerate() {
 114         assert_eq!(i as i32, *elt);
 115     }
 116     let mut n = LinkedList::new();
 117     assert_eq!(n.iter().next(), None);
 118     n.push_front(4);
 119     let mut it = n.iter();
 120     assert_eq!(it.size_hint(), (1, Some(1)));
 121     assert_eq!(it.next().unwrap(), &4);
 122     assert_eq!(it.size_hint(), (0, Some(0)));
 123     assert_eq!(it.next(), None);
 124 }
 125
 126 #[test]
 127 fn test_iterator_clone() {
 128     let mut n = LinkedList::new();
 129     n.push_back(2);
 130     n.push_back(3);
 131     n.push_back(4);
 132     let mut it = n.iter();
 133     it.next();
 134     let mut jt = it.clone();
 135     assert_eq!(it.next(), jt.next());
 136     assert_eq!(it.next_back(), jt.next_back());
 137     assert_eq!(it.next(), jt.next());
 138 }
 139
 140 #[test]
 141 fn test_iterator_double_end() {
 142     let mut n = LinkedList::new();
 143     assert_eq!(n.iter().next(), None);
 144     n.push_front(4);
 145     n.push_front(5);
 146     n.push_front(6);
 147     let mut it = n.iter();
 148     assert_eq!(it.size_hint(), (3, Some(3)));
 149     assert_eq!(it.next().unwrap(), &6);
 150     assert_eq!(it.size_hint(), (2, Some(2)));
 151     assert_eq!(it.next_back().unwrap(), &4);
 152     assert_eq!(it.size_hint(), (1, Some(1)));
 153     assert_eq!(it.next_back().unwrap(), &5);
 154     assert_eq!(it.next_back(), None);
 155     assert_eq!(it.next(), None);
 156 }
 157
 158 #[test]
 159 fn test_rev_iter() {
 160     let m = generate_test();
 161     for (i, elt) in m.iter().rev().enumerate() {
 162         assert_eq!((6 - i) as i32, *elt);
 163     }
 164     let mut n = LinkedList::new();
 165     assert_eq!(n.iter().rev().next(), None);
 166     n.push_front(4);
 167     let mut it = n.iter().rev();
 168     assert_eq!(it.size_hint(), (1, Some(1)));
 169     assert_eq!(it.next().unwrap(), &4);
 170     assert_eq!(it.size_hint(), (0, Some(0)));
 171     assert_eq!(it.next(), None);
 172 }
 173
 174 #[test]
 175 fn test_mut_iter() {
 176     let mut m = generate_test();
 177     let mut len = m.len();
 178     for (i, elt) in m.iter_mut().enumerate() {
 179         assert_eq!(i as i32, *elt);
 180         len -= 1;
 181     }
 182     assert_eq!(len, 0);
 183     let mut n = LinkedList::new();
 184     assert!(n.iter_mut().next().is_none());
 185     n.push_front(4);
 186     n.push_back(5);
 187     let mut it = n.iter_mut();
 188     assert_eq!(it.size_hint(), (2, Some(2)));
 189     assert!(it.next().is_some());
 190     assert!(it.next().is_some());
 191     assert_eq!(it.size_hint(), (0, Some(0)));
 192     assert!(it.next().is_none());
 193 }
 194
 195 #[test]
 196 fn test_iterator_mut_double_end() {
 197     let mut n = LinkedList::new();
 198     assert!(n.iter_mut().next_back().is_none());
 199     n.push_front(4);
 200     n.push_front(5);
 201     n.push_front(6);
 202     let mut it = n.iter_mut();
 203     assert_eq!(it.size_hint(), (3, Some(3)));
 204     assert_eq!(*it.next().unwrap(), 6);
 205     assert_eq!(it.size_hint(), (2, Some(2)));
 206     assert_eq!(*it.next_back().unwrap(), 4);
 207     assert_eq!(it.size_hint(), (1, Some(1)));
 208     assert_eq!(*it.next_back().unwrap(), 5);
 209     assert!(it.next_back().is_none());
 210     assert!(it.next().is_none());
 211 }
 212
 213 #[test]
 214 fn test_mut_rev_iter() {
 215     let mut m = generate_test();
 216     for (i, elt) in m.iter_mut().rev().enumerate() {
 217         assert_eq!((6 - i) as i32, *elt);
 218     }
 219     let mut n = LinkedList::new();
 220     assert!(n.iter_mut().rev().next().is_none());
 221     n.push_front(4);
 222     let mut it = n.iter_mut().rev();
 223     assert!(it.next().is_some());
 224     assert!(it.next().is_none());
 225 }
 226
 227 #[test]
 228 fn test_eq() {
 229     let mut n = list_from(&[]);
 230     let mut m = list_from(&[]);
 231     assert!(n == m);
 232     n.push_front(1);
 233     assert!(n != m);
 234     m.push_back(1);
 235     assert!(n == m);
 236
 237     let n = list_from(&[2, 3, 4]);
 238     let m = list_from(&[1, 2, 3]);
 239     assert!(n != m);
 240 }
 241
 242 #[test]
 243 fn test_hash() {
 244     let mut x = LinkedList::new();
 245     let mut y = LinkedList::new();
 246
 247     assert!(::hash(&x) == ::hash(&y));
 248
 249     x.push_back(1);
 250     x.push_back(2);
 251     x.push_back(3);
 252
 253     y.push_front(3);
 254     y.push_front(2);
 255     y.push_front(1);
 256
 257     assert!(::hash(&x) == ::hash(&y));
 258 }
 259
 260 #[test]
 261 fn test_ord() {
 262     let n = list_from(&[]);
 263     let m = list_from(&[1, 2, 3]);
 264     assert!(n < m);
 265     assert!(m > n);
 266     assert!(n <= n);
 267     assert!(n >= n);
 268 }
 269
 270 #[test]
 271 fn test_ord_nan() {
 272     let nan = 0.0f64 / 0.0;
 273     let n = list_from(&[nan]);
 274     let m = list_from(&[nan]);
 275     assert!(!(n < m));
 276     assert!(!(n > m));
 277     assert!(!(n <= m));
 278     assert!(!(n >= m));
 279
 280     let n = list_from(&[nan]);
 281     let one = list_from(&[1.0f64]);
 282     assert!(!(n < one));
 283     assert!(!(n > one));
 284     assert!(!(n <= one));
 285     assert!(!(n >= one));
 286
 287     let u = list_from(&[1.0f64, 2.0, nan]);
 288     let v = list_from(&[1.0f64, 2.0, 3.0]);
 289     assert!(!(u < v));
 290     assert!(!(u > v));
 291     assert!(!(u <= v));
 292     assert!(!(u >= v));
 293
 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]);
 296     assert!(!(s < t));
 297     assert!(s > one);
 298     assert!(!(s <= one));
 299     assert!(s >= one);
 300 }
 301
 302 #[test]
 303 fn test_show() {
 304     let list: LinkedList<_> = (0..10).collect();
 305     assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 306
 307     let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
 308     assert_eq!(format!("{:?}", list),
 309                "[\"just\", \"one\", \"test\", \"more\"]");
 310 }
 311
 312 #[test]
 313 fn test_extend_ref() {
 314     let mut a = LinkedList::new();
 315     a.push_back(1);
 316
 317     a.extend(&[2, 3, 4]);
 318
 319     assert_eq!(a.len(), 4);
 320     assert_eq!(a, list_from(&[1, 2, 3, 4]));
 321
 322     let mut b = LinkedList::new();
 323     b.push_back(5);
 324     b.push_back(6);
 325     a.extend(&b);
 326
 327     assert_eq!(a.len(), 6);
 328     assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
 329 }
 330
 331 #[test]
 332 fn test_extend() {
 333     let mut a = LinkedList::new();
 334     a.push_back(1);
 335     a.extend(vec![2, 3, 4]); // uses iterator
 336
 337     assert_eq!(a.len(), 4);
 338     assert!(a.iter().eq(&[1, 2, 3, 4]));
 339
 340     let b: LinkedList<_> = vec![5, 6, 7].into_iter().collect();
 341     a.extend(b); // specializes to `append`
 342
 343     assert_eq!(a.len(), 7);
 344     assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
 345 }
 346
 347 #[test]
 348 fn test_contains() {
 349     let mut l = LinkedList::new();
 350     l.extend(&[2, 3, 4]);
 351
 352     assert!(l.contains(&3));
 353     assert!(!l.contains(&1));
 354
 355     l.clear();
 356
 357     assert!(!l.contains(&3));
 358 }
 359
 360 #[test]
 361 fn drain_filter_empty() {
 362     let mut list: LinkedList<i32> = LinkedList::new();
 363
 364     {
 365         let mut iter = list.drain_filter(|_| true);
 366         assert_eq!(iter.size_hint(), (0, Some(0)));
 367         assert_eq!(iter.next(), None);
 368         assert_eq!(iter.size_hint(), (0, Some(0)));
 369         assert_eq!(iter.next(), None);
 370         assert_eq!(iter.size_hint(), (0, Some(0)));
 371     }
 372
 373     assert_eq!(list.len(), 0);
 374     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 375 }
 376
 377 #[test]
 378 fn drain_filter_zst() {
 379     let mut list: LinkedList<_> = vec![(), (), (), (), ()].into_iter().collect();
 380     let initial_len = list.len();
 381     let mut count = 0;
 382
 383     {
 384         let mut iter = list.drain_filter(|_| true);
 385         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 386         while let Some(_) = iter.next() {
 387             count += 1;
 388             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 389         }
 390         assert_eq!(iter.size_hint(), (0, Some(0)));
 391         assert_eq!(iter.next(), None);
 392         assert_eq!(iter.size_hint(), (0, Some(0)));
 393     }
 394
 395     assert_eq!(count, initial_len);
 396     assert_eq!(list.len(), 0);
 397     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 398 }
 399
 400 #[test]
 401 fn drain_filter_false() {
 402     let mut list: LinkedList<_> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
 403
 404     let initial_len = list.len();
 405     let mut count = 0;
 406
 407     {
 408         let mut iter = list.drain_filter(|_| false);
 409         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 410         for _ in iter.by_ref() {
 411             count += 1;
 412         }
 413         assert_eq!(iter.size_hint(), (0, Some(0)));
 414         assert_eq!(iter.next(), None);
 415         assert_eq!(iter.size_hint(), (0, Some(0)));
 416     }
 417
 418     assert_eq!(count, 0);
 419     assert_eq!(list.len(), initial_len);
 420     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 421 }
 422
 423 #[test]
 424 fn drain_filter_true() {
 425     let mut list: LinkedList<_> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
 426
 427     let initial_len = list.len();
 428     let mut count = 0;
 429
 430     {
 431         let mut iter = list.drain_filter(|_| true);
 432         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 433         while let Some(_) = iter.next() {
 434             count += 1;
 435             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 436         }
 437         assert_eq!(iter.size_hint(), (0, Some(0)));
 438         assert_eq!(iter.next(), None);
 439         assert_eq!(iter.size_hint(), (0, Some(0)));
 440     }
 441
 442     assert_eq!(count, initial_len);
 443     assert_eq!(list.len(), 0);
 444     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 445 }
 446
 447 #[test]
 448 fn drain_filter_complex() {
 449
 450     {   //                [+xxx++++++xxxxx++++x+x++]
 451         let mut list = vec![
 452             1,
 453             2, 4, 6,
 454             7, 9, 11, 13, 15, 17,
 455             18, 20, 22, 24, 26,
 456             27, 29, 31, 33,
 457             34,
 458             35,
 459             36,
 460             37, 39
 461         ].into_iter().collect::<LinkedList<_>>();
 462
 463         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 464         assert_eq!(removed.len(), 10);
 465         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 466
 467         assert_eq!(list.len(), 14);
 468         assert_eq!(
 469             list.into_iter().collect::<Vec<_>>(),
 470             vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
 471         );
 472     }
 473
 474     {   // [xxx++++++xxxxx++++x+x++]
 475         let mut list = vec![
 476             2, 4, 6,
 477             7, 9, 11, 13, 15, 17,
 478             18, 20, 22, 24, 26,
 479             27, 29, 31, 33,
 480             34,
 481             35,
 482             36,
 483             37, 39
 484         ].into_iter().collect::<LinkedList<_>>();
 485
 486         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 487         assert_eq!(removed.len(), 10);
 488         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 489
 490         assert_eq!(list.len(), 13);
 491         assert_eq!(
 492             list.into_iter().collect::<Vec<_>>(),
 493             vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
 494         );
 495     }
 496
 497     {   // [xxx++++++xxxxx++++x+x]
 498         let mut list = vec![
 499             2, 4, 6,
 500             7, 9, 11, 13, 15, 17,
 501             18, 20, 22, 24, 26,
 502             27, 29, 31, 33,
 503             34,
 504             35,
 505             36
 506         ].into_iter().collect::<LinkedList<_>>();
 507
 508         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 509         assert_eq!(removed.len(), 10);
 510         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 511
 512         assert_eq!(list.len(), 11);
 513         assert_eq!(
 514             list.into_iter().collect::<Vec<_>>(),
 515             vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]
 516         );
 517     }
 518
 519     {   // [xxxxxxxxxx+++++++++++]
 520         let mut list = vec![
 521             2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
 522             1, 3, 5, 7, 9, 11, 13, 15, 17, 19
 523         ].into_iter().collect::<LinkedList<_>>();
 524
 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]);
 528
 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]);
 531     }
 532
 533     {   // [+++++++++++xxxxxxxxxx]
 534         let mut list = vec![
 535             1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
 536             2, 4, 6, 8, 10, 12, 14, 16, 18, 20
 537         ].into_iter().collect::<LinkedList<_>>();
 538
 539         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 540         assert_eq!(removed.len(), 10);
 541         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 542
 543         assert_eq!(list.len(), 10);
 544         assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 545     }
 546 }