src/libcollectionstest/linked_list.rs

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