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