src/liballoc/tests/btree/set.rs

   1 use std::collections::BTreeSet;
   2 use std::iter::FromIterator;
   3
   4 use super::DeterministicRng;
   5
   6 #[test]
   7 fn test_clone_eq() {
   8     let mut m = BTreeSet::new();
   9
  10     m.insert(1);
  11     m.insert(2);
  12
  13     assert_eq!(m.clone(), m);
  14 }
  15
  16 #[test]
  17 fn test_hash() {
  18     use crate::hash;
  19
  20     let mut x = BTreeSet::new();
  21     let mut y = BTreeSet::new();
  22
  23     x.insert(1);
  24     x.insert(2);
  25     x.insert(3);
  26
  27     y.insert(3);
  28     y.insert(2);
  29     y.insert(1);
  30
  31     assert_eq!(hash(&x), hash(&y));
  32 }
  33
  34 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
  35 where
  36     F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,
  37 {
  38     let mut set_a = BTreeSet::new();
  39     let mut set_b = BTreeSet::new();
  40
  41     for x in a {
  42         assert!(set_a.insert(*x))
  43     }
  44     for y in b {
  45         assert!(set_b.insert(*y))
  46     }
  47
  48     let mut i = 0;
  49     f(&set_a, &set_b, &mut |&x| {
  50         if i < expected.len() {
  51             assert_eq!(x, expected[i]);
  52         }
  53         i += 1;
  54         true
  55     });
  56     assert_eq!(i, expected.len());
  57 }
  58
  59 #[test]
  60 fn test_intersection() {
  61     fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
  62         check(a, b, expected, |x, y, f| x.intersection(y).all(f))
  63     }
  64
  65     check_intersection(&[], &[], &[]);
  66     check_intersection(&[1, 2, 3], &[], &[]);
  67     check_intersection(&[], &[1, 2, 3], &[]);
  68     check_intersection(&[2], &[1, 2, 3], &[2]);
  69     check_intersection(&[1, 2, 3], &[2], &[2]);
  70     check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]);
  71
  72     if cfg!(miri) {
  73         // Miri is too slow
  74         return;
  75     }
  76
  77     let large = (0..100).collect::<Vec<_>>();
  78     check_intersection(&[], &large, &[]);
  79     check_intersection(&large, &[], &[]);
  80     check_intersection(&[-1], &large, &[]);
  81     check_intersection(&large, &[-1], &[]);
  82     check_intersection(&[0], &large, &[0]);
  83     check_intersection(&large, &[0], &[0]);
  84     check_intersection(&[99], &large, &[99]);
  85     check_intersection(&large, &[99], &[99]);
  86     check_intersection(&[100], &large, &[]);
  87     check_intersection(&large, &[100], &[]);
  88     check_intersection(&[11, 5000, 1, 3, 77, 8924], &large, &[1, 3, 11, 77]);
  89 }
  90
  91 #[test]
  92 fn test_intersection_size_hint() {
  93     let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
  94     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
  95     let mut iter = x.intersection(&y);
  96     assert_eq!(iter.size_hint(), (1, Some(1)));
  97     assert_eq!(iter.next(), Some(&3));
  98     assert_eq!(iter.size_hint(), (0, Some(0)));
  99     assert_eq!(iter.next(), None);
 100
 101     iter = y.intersection(&y);
 102     assert_eq!(iter.size_hint(), (0, Some(3)));
 103     assert_eq!(iter.next(), Some(&1));
 104     assert_eq!(iter.size_hint(), (0, Some(2)));
 105 }
 106
 107 #[test]
 108 fn test_difference() {
 109     fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
 110         check(a, b, expected, |x, y, f| x.difference(y).all(f))
 111     }
 112
 113     check_difference(&[], &[], &[]);
 114     check_difference(&[1, 12], &[], &[1, 12]);
 115     check_difference(&[], &[1, 2, 3, 9], &[]);
 116     check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
 117     check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
 118     check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
 119     check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
 120     check_difference(
 121         &[-5, 11, 22, 33, 40, 42],
 122         &[-12, -5, 14, 23, 34, 38, 39, 50],
 123         &[11, 22, 33, 40, 42],
 124     );
 125
 126     if cfg!(miri) {
 127         // Miri is too slow
 128         return;
 129     }
 130
 131     let large = (0..100).collect::<Vec<_>>();
 132     check_difference(&[], &large, &[]);
 133     check_difference(&[-1], &large, &[-1]);
 134     check_difference(&[0], &large, &[]);
 135     check_difference(&[99], &large, &[]);
 136     check_difference(&[100], &large, &[100]);
 137     check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]);
 138     check_difference(&large, &[], &large);
 139     check_difference(&large, &[-1], &large);
 140     check_difference(&large, &[100], &large);
 141 }
 142
 143 #[test]
 144 fn test_difference_size_hint() {
 145     let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
 146     let s23456: BTreeSet<i32> = (2..=6).collect();
 147     let mut iter = s246.difference(&s23456);
 148     assert_eq!(iter.size_hint(), (0, Some(3)));
 149     assert_eq!(iter.next(), None);
 150
 151     let s12345: BTreeSet<i32> = (1..=5).collect();
 152     iter = s246.difference(&s12345);
 153     assert_eq!(iter.size_hint(), (0, Some(3)));
 154     assert_eq!(iter.next(), Some(&6));
 155     assert_eq!(iter.size_hint(), (0, Some(0)));
 156     assert_eq!(iter.next(), None);
 157
 158     let s34567: BTreeSet<i32> = (3..=7).collect();
 159     iter = s246.difference(&s34567);
 160     assert_eq!(iter.size_hint(), (0, Some(3)));
 161     assert_eq!(iter.next(), Some(&2));
 162     assert_eq!(iter.size_hint(), (0, Some(2)));
 163     assert_eq!(iter.next(), None);
 164
 165     let s1: BTreeSet<i32> = (-9..=1).collect();
 166     iter = s246.difference(&s1);
 167     assert_eq!(iter.size_hint(), (3, Some(3)));
 168
 169     let s2: BTreeSet<i32> = (-9..=2).collect();
 170     iter = s246.difference(&s2);
 171     assert_eq!(iter.size_hint(), (2, Some(2)));
 172     assert_eq!(iter.next(), Some(&4));
 173     assert_eq!(iter.size_hint(), (1, Some(1)));
 174
 175     let s23: BTreeSet<i32> = (2..=3).collect();
 176     iter = s246.difference(&s23);
 177     assert_eq!(iter.size_hint(), (1, Some(3)));
 178     assert_eq!(iter.next(), Some(&4));
 179     assert_eq!(iter.size_hint(), (1, Some(1)));
 180
 181     let s4: BTreeSet<i32> = (4..=4).collect();
 182     iter = s246.difference(&s4);
 183     assert_eq!(iter.size_hint(), (2, Some(3)));
 184     assert_eq!(iter.next(), Some(&2));
 185     assert_eq!(iter.size_hint(), (1, Some(2)));
 186     assert_eq!(iter.next(), Some(&6));
 187     assert_eq!(iter.size_hint(), (0, Some(0)));
 188     assert_eq!(iter.next(), None);
 189
 190     let s56: BTreeSet<i32> = (5..=6).collect();
 191     iter = s246.difference(&s56);
 192     assert_eq!(iter.size_hint(), (1, Some(3)));
 193     assert_eq!(iter.next(), Some(&2));
 194     assert_eq!(iter.size_hint(), (0, Some(2)));
 195
 196     let s6: BTreeSet<i32> = (6..=19).collect();
 197     iter = s246.difference(&s6);
 198     assert_eq!(iter.size_hint(), (2, Some(2)));
 199     assert_eq!(iter.next(), Some(&2));
 200     assert_eq!(iter.size_hint(), (1, Some(1)));
 201
 202     let s7: BTreeSet<i32> = (7..=19).collect();
 203     iter = s246.difference(&s7);
 204     assert_eq!(iter.size_hint(), (3, Some(3)));
 205 }
 206
 207 #[test]
 208 fn test_symmetric_difference() {
 209     fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
 210         check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
 211     }
 212
 213     check_symmetric_difference(&[], &[], &[]);
 214     check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
 215     check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
 216     check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]);
 217 }
 218
 219 #[test]
 220 fn test_symmetric_difference_size_hint() {
 221     let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
 222     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
 223     let mut iter = x.symmetric_difference(&y);
 224     assert_eq!(iter.size_hint(), (0, Some(5)));
 225     assert_eq!(iter.next(), Some(&1));
 226     assert_eq!(iter.size_hint(), (0, Some(4)));
 227     assert_eq!(iter.next(), Some(&3));
 228     assert_eq!(iter.size_hint(), (0, Some(1)));
 229 }
 230
 231 #[test]
 232 fn test_union() {
 233     fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
 234         check(a, b, expected, |x, y, f| x.union(y).all(f))
 235     }
 236
 237     check_union(&[], &[], &[]);
 238     check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
 239     check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
 240     check_union(
 241         &[1, 3, 5, 9, 11, 16, 19, 24],
 242         &[-2, 1, 5, 9, 13, 19],
 243         &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24],
 244     );
 245 }
 246
 247 #[test]
 248 fn test_union_size_hint() {
 249     let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
 250     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
 251     let mut iter = x.union(&y);
 252     assert_eq!(iter.size_hint(), (3, Some(5)));
 253     assert_eq!(iter.next(), Some(&1));
 254     assert_eq!(iter.size_hint(), (2, Some(4)));
 255     assert_eq!(iter.next(), Some(&2));
 256     assert_eq!(iter.size_hint(), (1, Some(2)));
 257 }
 258
 259 #[test]
 260 // Only tests the simple function definition with respect to intersection
 261 fn test_is_disjoint() {
 262     let one = [1].iter().collect::<BTreeSet<_>>();
 263     let two = [2].iter().collect::<BTreeSet<_>>();
 264     assert!(one.is_disjoint(&two));
 265 }
 266
 267 #[test]
 268 // Also implicitly tests the trivial function definition of is_superset
 269 fn test_is_subset() {
 270     fn is_subset(a: &[i32], b: &[i32]) -> bool {
 271         let set_a = a.iter().collect::<BTreeSet<_>>();
 272         let set_b = b.iter().collect::<BTreeSet<_>>();
 273         set_a.is_subset(&set_b)
 274     }
 275
 276     assert_eq!(is_subset(&[], &[]), true);
 277     assert_eq!(is_subset(&[], &[1, 2]), true);
 278     assert_eq!(is_subset(&[0], &[1, 2]), false);
 279     assert_eq!(is_subset(&[1], &[1, 2]), true);
 280     assert_eq!(is_subset(&[2], &[1, 2]), true);
 281     assert_eq!(is_subset(&[3], &[1, 2]), false);
 282     assert_eq!(is_subset(&[1, 2], &[1]), false);
 283     assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
 284     assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
 285     assert_eq!(
 286         is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
 287         true
 288     );
 289     assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false);
 290
 291     if cfg!(miri) {
 292         // Miri is too slow
 293         return;
 294     }
 295
 296     let large = (0..100).collect::<Vec<_>>();
 297     assert_eq!(is_subset(&[], &large), true);
 298     assert_eq!(is_subset(&large, &[]), false);
 299     assert_eq!(is_subset(&[-1], &large), false);
 300     assert_eq!(is_subset(&[0], &large), true);
 301     assert_eq!(is_subset(&[1, 2], &large), true);
 302     assert_eq!(is_subset(&[99, 100], &large), false);
 303 }
 304
 305 #[test]
 306 fn test_clear() {
 307     let mut x = BTreeSet::new();
 308     x.insert(1);
 309
 310     x.clear();
 311     assert!(x.is_empty());
 312 }
 313
 314 #[test]
 315 fn test_zip() {
 316     let mut x = BTreeSet::new();
 317     x.insert(5);
 318     x.insert(12);
 319     x.insert(11);
 320
 321     let mut y = BTreeSet::new();
 322     y.insert("foo");
 323     y.insert("bar");
 324
 325     let x = x;
 326     let y = y;
 327     let mut z = x.iter().zip(&y);
 328
 329     assert_eq!(z.next().unwrap(), (&5, &("bar")));
 330     assert_eq!(z.next().unwrap(), (&11, &("foo")));
 331     assert!(z.next().is_none());
 332 }
 333
 334 #[test]
 335 fn test_from_iter() {
 336     let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
 337
 338     let set: BTreeSet<_> = xs.iter().cloned().collect();
 339
 340     for x in &xs {
 341         assert!(set.contains(x));
 342     }
 343 }
 344
 345 #[test]
 346 fn test_show() {
 347     let mut set = BTreeSet::new();
 348     let empty = BTreeSet::<i32>::new();
 349
 350     set.insert(1);
 351     set.insert(2);
 352
 353     let set_str = format!("{:?}", set);
 354
 355     assert_eq!(set_str, "{1, 2}");
 356     assert_eq!(format!("{:?}", empty), "{}");
 357 }
 358
 359 #[test]
 360 fn test_extend_ref() {
 361     let mut a = BTreeSet::new();
 362     a.insert(1);
 363
 364     a.extend(&[2, 3, 4]);
 365
 366     assert_eq!(a.len(), 4);
 367     assert!(a.contains(&1));
 368     assert!(a.contains(&2));
 369     assert!(a.contains(&3));
 370     assert!(a.contains(&4));
 371
 372     let mut b = BTreeSet::new();
 373     b.insert(5);
 374     b.insert(6);
 375
 376     a.extend(&b);
 377
 378     assert_eq!(a.len(), 6);
 379     assert!(a.contains(&1));
 380     assert!(a.contains(&2));
 381     assert!(a.contains(&3));
 382     assert!(a.contains(&4));
 383     assert!(a.contains(&5));
 384     assert!(a.contains(&6));
 385 }
 386
 387 #[test]
 388 fn test_recovery() {
 389     use std::cmp::Ordering;
 390
 391     #[derive(Debug)]
 392     struct Foo(&'static str, i32);
 393
 394     impl PartialEq for Foo {
 395         fn eq(&self, other: &Self) -> bool {
 396             self.0 == other.0
 397         }
 398     }
 399
 400     impl Eq for Foo {}
 401
 402     impl PartialOrd for Foo {
 403         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 404             self.0.partial_cmp(&other.0)
 405         }
 406     }
 407
 408     impl Ord for Foo {
 409         fn cmp(&self, other: &Self) -> Ordering {
 410             self.0.cmp(&other.0)
 411         }
 412     }
 413
 414     let mut s = BTreeSet::new();
 415     assert_eq!(s.replace(Foo("a", 1)), None);
 416     assert_eq!(s.len(), 1);
 417     assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
 418     assert_eq!(s.len(), 1);
 419
 420     {
 421         let mut it = s.iter();
 422         assert_eq!(it.next(), Some(&Foo("a", 2)));
 423         assert_eq!(it.next(), None);
 424     }
 425
 426     assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
 427     assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
 428     assert_eq!(s.len(), 0);
 429
 430     assert_eq!(s.get(&Foo("a", 1)), None);
 431     assert_eq!(s.take(&Foo("a", 1)), None);
 432
 433     assert_eq!(s.iter().next(), None);
 434 }
 435
 436 #[test]
 437 #[allow(dead_code)]
 438 fn test_variance() {
 439     use std::collections::btree_set::{IntoIter, Iter, Range};
 440
 441     fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
 442         v
 443     }
 444     fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
 445         v
 446     }
 447     fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
 448         v
 449     }
 450     fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
 451         v
 452     }
 453 }
 454
 455 #[test]
 456 fn test_append() {
 457     let mut a = BTreeSet::new();
 458     a.insert(1);
 459     a.insert(2);
 460     a.insert(3);
 461
 462     let mut b = BTreeSet::new();
 463     b.insert(3);
 464     b.insert(4);
 465     b.insert(5);
 466
 467     a.append(&mut b);
 468
 469     assert_eq!(a.len(), 5);
 470     assert_eq!(b.len(), 0);
 471
 472     assert_eq!(a.contains(&1), true);
 473     assert_eq!(a.contains(&2), true);
 474     assert_eq!(a.contains(&3), true);
 475     assert_eq!(a.contains(&4), true);
 476     assert_eq!(a.contains(&5), true);
 477 }
 478
 479 #[test]
 480 fn test_first_last() {
 481     let mut a = BTreeSet::new();
 482     assert_eq!(a.first(), None);
 483     assert_eq!(a.last(), None);
 484     a.insert(1);
 485     assert_eq!(a.first(), Some(&1));
 486     assert_eq!(a.last(), Some(&1));
 487     a.insert(2);
 488     assert_eq!(a.first(), Some(&1));
 489     assert_eq!(a.last(), Some(&2));
 490     a.insert(3);
 491     assert_eq!(a.first(), Some(&1));
 492     assert_eq!(a.last(), Some(&3));
 493
 494     assert_eq!(a.len(), 3);
 495     assert_eq!(a.pop_first(), Some(1));
 496     assert_eq!(a.len(), 2);
 497     assert_eq!(a.pop_last(), Some(3));
 498     assert_eq!(a.len(), 1);
 499     assert_eq!(a.pop_first(), Some(2));
 500     assert_eq!(a.len(), 0);
 501     assert_eq!(a.pop_last(), None);
 502     assert_eq!(a.len(), 0);
 503     assert_eq!(a.pop_first(), None);
 504     assert_eq!(a.len(), 0);
 505 }
 506
 507 fn rand_data(len: usize) -> Vec<u32> {
 508     let mut rng = DeterministicRng::new();
 509     Vec::from_iter((0..len).map(|_| rng.next()))
 510 }
 511
 512 #[test]
 513 fn test_split_off_empty_right() {
 514     let mut data = rand_data(173);
 515
 516     let mut set = BTreeSet::from_iter(data.clone());
 517     let right = set.split_off(&(data.iter().max().unwrap() + 1));
 518
 519     data.sort();
 520     assert!(set.into_iter().eq(data));
 521     assert!(right.into_iter().eq(None));
 522 }
 523
 524 #[test]
 525 fn test_split_off_empty_left() {
 526     let mut data = rand_data(314);
 527
 528     let mut set = BTreeSet::from_iter(data.clone());
 529     let right = set.split_off(data.iter().min().unwrap());
 530
 531     data.sort();
 532     assert!(set.into_iter().eq(None));
 533     assert!(right.into_iter().eq(data));
 534 }
 535
 536 #[test]
 537 fn test_split_off_large_random_sorted() {
 538     #[cfg(not(miri))] // Miri is too slow
 539     let mut data = rand_data(1529);
 540     #[cfg(miri)]
 541     let mut data = rand_data(529);
 542     // special case with maximum height.
 543     data.sort();
 544
 545     let mut set = BTreeSet::from_iter(data.clone());
 546     let key = data[data.len() / 2];
 547     let right = set.split_off(&key);
 548
 549     assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
 550     assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
 551 }