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