library/alloc/src/collections/btree/set/tests.rs

   1 use super::super::DeterministicRng;
   2 use super::*;
   3 use crate::vec::Vec;
   4 use std::iter::FromIterator;
   5 use std::panic::{catch_unwind, AssertUnwindSafe};
   6 use std::sync::atomic::{AtomicU32, Ordering};
   7
   8 #[test]
   9 fn test_clone_eq() {
  10     let mut m = BTreeSet::new();
  11
  12     m.insert(1);
  13     m.insert(2);
  14
  15     assert_eq!(m.clone(), m);
  16 }
  17
  18 #[allow(dead_code)]
  19 fn test_const() {
  20     const SET: &'static BTreeSet<()> = &BTreeSet::new();
  21     const LEN: usize = SET.len();
  22     const IS_EMPTY: bool = SET.is_empty();
  23 }
  24
  25 #[test]
  26 fn test_iter_min_max() {
  27     let mut a = BTreeSet::new();
  28     assert_eq!(a.iter().min(), None);
  29     assert_eq!(a.iter().max(), None);
  30     assert_eq!(a.range(..).min(), None);
  31     assert_eq!(a.range(..).max(), None);
  32     assert_eq!(a.difference(&BTreeSet::new()).min(), None);
  33     assert_eq!(a.difference(&BTreeSet::new()).max(), None);
  34     assert_eq!(a.intersection(&a).min(), None);
  35     assert_eq!(a.intersection(&a).max(), None);
  36     assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), None);
  37     assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), None);
  38     assert_eq!(a.union(&a).min(), None);
  39     assert_eq!(a.union(&a).max(), None);
  40     a.insert(1);
  41     a.insert(2);
  42     assert_eq!(a.iter().min(), Some(&1));
  43     assert_eq!(a.iter().max(), Some(&2));
  44     assert_eq!(a.range(..).min(), Some(&1));
  45     assert_eq!(a.range(..).max(), Some(&2));
  46     assert_eq!(a.difference(&BTreeSet::new()).min(), Some(&1));
  47     assert_eq!(a.difference(&BTreeSet::new()).max(), Some(&2));
  48     assert_eq!(a.intersection(&a).min(), Some(&1));
  49     assert_eq!(a.intersection(&a).max(), Some(&2));
  50     assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), Some(&1));
  51     assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), Some(&2));
  52     assert_eq!(a.union(&a).min(), Some(&1));
  53     assert_eq!(a.union(&a).max(), Some(&2));
  54 }
  55
  56 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
  57 where
  58     F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,
  59 {
  60     let mut set_a = BTreeSet::new();
  61     let mut set_b = BTreeSet::new();
  62
  63     for x in a {
  64         assert!(set_a.insert(*x))
  65     }
  66     for y in b {
  67         assert!(set_b.insert(*y))
  68     }
  69
  70     let mut i = 0;
  71     f(&set_a, &set_b, &mut |&x| {
  72         if i < expected.len() {
  73             assert_eq!(x, expected[i]);
  74         }
  75         i += 1;
  76         true
  77     });
  78     assert_eq!(i, expected.len());
  79 }
  80
  81 #[test]
  82 fn test_intersection() {
  83     fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
  84         check(a, b, expected, |x, y, f| x.intersection(y).all(f))
  85     }
  86
  87     check_intersection(&[], &[], &[]);
  88     check_intersection(&[1, 2, 3], &[], &[]);
  89     check_intersection(&[], &[1, 2, 3], &[]);
  90     check_intersection(&[2], &[1, 2, 3], &[2]);
  91     check_intersection(&[1, 2, 3], &[2], &[2]);
  92     check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]);
  93
  94     if cfg!(miri) {
  95         // Miri is too slow
  96         return;
  97     }
  98
  99     let large = (0..100).collect::<Vec<_>>();
 100     check_intersection(&[], &large, &[]);
 101     check_intersection(&large, &[], &[]);
 102     check_intersection(&[-1], &large, &[]);
 103     check_intersection(&large, &[-1], &[]);
 104     check_intersection(&[0], &large, &[0]);
 105     check_intersection(&large, &[0], &[0]);
 106     check_intersection(&[99], &large, &[99]);
 107     check_intersection(&large, &[99], &[99]);
 108     check_intersection(&[100], &large, &[]);
 109     check_intersection(&large, &[100], &[]);
 110     check_intersection(&[11, 5000, 1, 3, 77, 8924], &large, &[1, 3, 11, 77]);
 111 }
 112
 113 #[test]
 114 fn test_intersection_size_hint() {
 115     let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
 116     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
 117     let mut iter = x.intersection(&y);
 118     assert_eq!(iter.size_hint(), (1, Some(1)));
 119     assert_eq!(iter.next(), Some(&3));
 120     assert_eq!(iter.size_hint(), (0, Some(0)));
 121     assert_eq!(iter.next(), None);
 122
 123     iter = y.intersection(&y);
 124     assert_eq!(iter.size_hint(), (0, Some(3)));
 125     assert_eq!(iter.next(), Some(&1));
 126     assert_eq!(iter.size_hint(), (0, Some(2)));
 127 }
 128
 129 #[test]
 130 fn test_difference() {
 131     fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
 132         check(a, b, expected, |x, y, f| x.difference(y).all(f))
 133     }
 134
 135     check_difference(&[], &[], &[]);
 136     check_difference(&[1, 12], &[], &[1, 12]);
 137     check_difference(&[], &[1, 2, 3, 9], &[]);
 138     check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
 139     check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
 140     check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
 141     check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
 142     check_difference(
 143         &[-5, 11, 22, 33, 40, 42],
 144         &[-12, -5, 14, 23, 34, 38, 39, 50],
 145         &[11, 22, 33, 40, 42],
 146     );
 147
 148     if cfg!(miri) {
 149         // Miri is too slow
 150         return;
 151     }
 152
 153     let large = (0..100).collect::<Vec<_>>();
 154     check_difference(&[], &large, &[]);
 155     check_difference(&[-1], &large, &[-1]);
 156     check_difference(&[0], &large, &[]);
 157     check_difference(&[99], &large, &[]);
 158     check_difference(&[100], &large, &[100]);
 159     check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]);
 160     check_difference(&large, &[], &large);
 161     check_difference(&large, &[-1], &large);
 162     check_difference(&large, &[100], &large);
 163 }
 164
 165 #[test]
 166 fn test_difference_size_hint() {
 167     let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
 168     let s23456: BTreeSet<i32> = (2..=6).collect();
 169     let mut iter = s246.difference(&s23456);
 170     assert_eq!(iter.size_hint(), (0, Some(3)));
 171     assert_eq!(iter.next(), None);
 172
 173     let s12345: BTreeSet<i32> = (1..=5).collect();
 174     iter = s246.difference(&s12345);
 175     assert_eq!(iter.size_hint(), (0, Some(3)));
 176     assert_eq!(iter.next(), Some(&6));
 177     assert_eq!(iter.size_hint(), (0, Some(0)));
 178     assert_eq!(iter.next(), None);
 179
 180     let s34567: BTreeSet<i32> = (3..=7).collect();
 181     iter = s246.difference(&s34567);
 182     assert_eq!(iter.size_hint(), (0, Some(3)));
 183     assert_eq!(iter.next(), Some(&2));
 184     assert_eq!(iter.size_hint(), (0, Some(2)));
 185     assert_eq!(iter.next(), None);
 186
 187     let s1: BTreeSet<i32> = (-9..=1).collect();
 188     iter = s246.difference(&s1);
 189     assert_eq!(iter.size_hint(), (3, Some(3)));
 190
 191     let s2: BTreeSet<i32> = (-9..=2).collect();
 192     iter = s246.difference(&s2);
 193     assert_eq!(iter.size_hint(), (2, Some(2)));
 194     assert_eq!(iter.next(), Some(&4));
 195     assert_eq!(iter.size_hint(), (1, Some(1)));
 196
 197     let s23: BTreeSet<i32> = (2..=3).collect();
 198     iter = s246.difference(&s23);
 199     assert_eq!(iter.size_hint(), (1, Some(3)));
 200     assert_eq!(iter.next(), Some(&4));
 201     assert_eq!(iter.size_hint(), (1, Some(1)));
 202
 203     let s4: BTreeSet<i32> = (4..=4).collect();
 204     iter = s246.difference(&s4);
 205     assert_eq!(iter.size_hint(), (2, Some(3)));
 206     assert_eq!(iter.next(), Some(&2));
 207     assert_eq!(iter.size_hint(), (1, Some(2)));
 208     assert_eq!(iter.next(), Some(&6));
 209     assert_eq!(iter.size_hint(), (0, Some(0)));
 210     assert_eq!(iter.next(), None);
 211
 212     let s56: BTreeSet<i32> = (5..=6).collect();
 213     iter = s246.difference(&s56);
 214     assert_eq!(iter.size_hint(), (1, Some(3)));
 215     assert_eq!(iter.next(), Some(&2));
 216     assert_eq!(iter.size_hint(), (0, Some(2)));
 217
 218     let s6: BTreeSet<i32> = (6..=19).collect();
 219     iter = s246.difference(&s6);
 220     assert_eq!(iter.size_hint(), (2, Some(2)));
 221     assert_eq!(iter.next(), Some(&2));
 222     assert_eq!(iter.size_hint(), (1, Some(1)));
 223
 224     let s7: BTreeSet<i32> = (7..=19).collect();
 225     iter = s246.difference(&s7);
 226     assert_eq!(iter.size_hint(), (3, Some(3)));
 227 }
 228
 229 #[test]
 230 fn test_symmetric_difference() {
 231     fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
 232         check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
 233     }
 234
 235     check_symmetric_difference(&[], &[], &[]);
 236     check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
 237     check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
 238     check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]);
 239 }
 240
 241 #[test]
 242 fn test_symmetric_difference_size_hint() {
 243     let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
 244     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
 245     let mut iter = x.symmetric_difference(&y);
 246     assert_eq!(iter.size_hint(), (0, Some(5)));
 247     assert_eq!(iter.next(), Some(&1));
 248     assert_eq!(iter.size_hint(), (0, Some(4)));
 249     assert_eq!(iter.next(), Some(&3));
 250     assert_eq!(iter.size_hint(), (0, Some(1)));
 251 }
 252
 253 #[test]
 254 fn test_union() {
 255     fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
 256         check(a, b, expected, |x, y, f| x.union(y).all(f))
 257     }
 258
 259     check_union(&[], &[], &[]);
 260     check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
 261     check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
 262     check_union(
 263         &[1, 3, 5, 9, 11, 16, 19, 24],
 264         &[-2, 1, 5, 9, 13, 19],
 265         &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24],
 266     );
 267 }
 268
 269 #[test]
 270 fn test_union_size_hint() {
 271     let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
 272     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
 273     let mut iter = x.union(&y);
 274     assert_eq!(iter.size_hint(), (3, Some(5)));
 275     assert_eq!(iter.next(), Some(&1));
 276     assert_eq!(iter.size_hint(), (2, Some(4)));
 277     assert_eq!(iter.next(), Some(&2));
 278     assert_eq!(iter.size_hint(), (1, Some(2)));
 279 }
 280
 281 #[test]
 282 // Only tests the simple function definition with respect to intersection
 283 fn test_is_disjoint() {
 284     let one = [1].iter().collect::<BTreeSet<_>>();
 285     let two = [2].iter().collect::<BTreeSet<_>>();
 286     assert!(one.is_disjoint(&two));
 287 }
 288
 289 #[test]
 290 // Also implicitly tests the trivial function definition of is_superset
 291 fn test_is_subset() {
 292     fn is_subset(a: &[i32], b: &[i32]) -> bool {
 293         let set_a = a.iter().collect::<BTreeSet<_>>();
 294         let set_b = b.iter().collect::<BTreeSet<_>>();
 295         set_a.is_subset(&set_b)
 296     }
 297
 298     assert_eq!(is_subset(&[], &[]), true);
 299     assert_eq!(is_subset(&[], &[1, 2]), true);
 300     assert_eq!(is_subset(&[0], &[1, 2]), false);
 301     assert_eq!(is_subset(&[1], &[1, 2]), true);
 302     assert_eq!(is_subset(&[2], &[1, 2]), true);
 303     assert_eq!(is_subset(&[3], &[1, 2]), false);
 304     assert_eq!(is_subset(&[1, 2], &[1]), false);
 305     assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
 306     assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
 307     assert_eq!(
 308         is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
 309         true
 310     );
 311     assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false);
 312
 313     if cfg!(miri) {
 314         // Miri is too slow
 315         return;
 316     }
 317
 318     let large = (0..100).collect::<Vec<_>>();
 319     assert_eq!(is_subset(&[], &large), true);
 320     assert_eq!(is_subset(&large, &[]), false);
 321     assert_eq!(is_subset(&[-1], &large), false);
 322     assert_eq!(is_subset(&[0], &large), true);
 323     assert_eq!(is_subset(&[1, 2], &large), true);
 324     assert_eq!(is_subset(&[99, 100], &large), false);
 325 }
 326
 327 #[test]
 328 fn test_retain() {
 329     let xs = [1, 2, 3, 4, 5, 6];
 330     let mut set: BTreeSet<i32> = xs.iter().cloned().collect();
 331     set.retain(|&k| k % 2 == 0);
 332     assert_eq!(set.len(), 3);
 333     assert!(set.contains(&2));
 334     assert!(set.contains(&4));
 335     assert!(set.contains(&6));
 336 }
 337
 338 #[test]
 339 fn test_drain_filter() {
 340     let mut x: BTreeSet<_> = [1].iter().copied().collect();
 341     let mut y: BTreeSet<_> = [1].iter().copied().collect();
 342
 343     x.drain_filter(|_| true);
 344     y.drain_filter(|_| false);
 345     assert_eq!(x.len(), 0);
 346     assert_eq!(y.len(), 1);
 347 }
 348
 349 #[test]
 350 fn test_drain_filter_drop_panic_leak() {
 351     static PREDS: AtomicU32 = AtomicU32::new(0);
 352     static DROPS: AtomicU32 = AtomicU32::new(0);
 353
 354     #[derive(PartialEq, Eq, PartialOrd, Ord)]
 355     struct D(i32);
 356     impl Drop for D {
 357         fn drop(&mut self) {
 358             if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
 359                 panic!("panic in `drop`");
 360             }
 361         }
 362     }
 363
 364     let mut set = BTreeSet::new();
 365     set.insert(D(0));
 366     set.insert(D(4));
 367     set.insert(D(8));
 368
 369     catch_unwind(move || {
 370         drop(set.drain_filter(|d| {
 371             PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst);
 372             true
 373         }))
 374     })
 375     .ok();
 376
 377     assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
 378     assert_eq!(DROPS.load(Ordering::SeqCst), 3);
 379 }
 380
 381 #[test]
 382 fn test_drain_filter_pred_panic_leak() {
 383     static PREDS: AtomicU32 = AtomicU32::new(0);
 384     static DROPS: AtomicU32 = AtomicU32::new(0);
 385
 386     #[derive(PartialEq, Eq, PartialOrd, Ord)]
 387     struct D(i32);
 388     impl Drop for D {
 389         fn drop(&mut self) {
 390             DROPS.fetch_add(1, Ordering::SeqCst);
 391         }
 392     }
 393
 394     let mut set = BTreeSet::new();
 395     set.insert(D(0));
 396     set.insert(D(4));
 397     set.insert(D(8));
 398
 399     catch_unwind(AssertUnwindSafe(|| {
 400         drop(set.drain_filter(|d| {
 401             PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst);
 402             match d.0 {
 403                 0 => true,
 404                 _ => panic!(),
 405             }
 406         }))
 407     }))
 408     .ok();
 409
 410     assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
 411     assert_eq!(DROPS.load(Ordering::SeqCst), 1);
 412     assert_eq!(set.len(), 2);
 413     assert_eq!(set.first().unwrap().0, 4);
 414     assert_eq!(set.last().unwrap().0, 8);
 415 }
 416
 417 #[test]
 418 fn test_clear() {
 419     let mut x = BTreeSet::new();
 420     x.insert(1);
 421
 422     x.clear();
 423     assert!(x.is_empty());
 424 }
 425
 426 #[test]
 427 fn test_zip() {
 428     let mut x = BTreeSet::new();
 429     x.insert(5);
 430     x.insert(12);
 431     x.insert(11);
 432
 433     let mut y = BTreeSet::new();
 434     y.insert("foo");
 435     y.insert("bar");
 436
 437     let x = x;
 438     let y = y;
 439     let mut z = x.iter().zip(&y);
 440
 441     assert_eq!(z.next().unwrap(), (&5, &("bar")));
 442     assert_eq!(z.next().unwrap(), (&11, &("foo")));
 443     assert!(z.next().is_none());
 444 }
 445
 446 #[test]
 447 fn test_from_iter() {
 448     let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
 449
 450     let set: BTreeSet<_> = xs.iter().cloned().collect();
 451
 452     for x in &xs {
 453         assert!(set.contains(x));
 454     }
 455 }
 456
 457 #[test]
 458 fn test_show() {
 459     let mut set = BTreeSet::new();
 460     let empty = BTreeSet::<i32>::new();
 461
 462     set.insert(1);
 463     set.insert(2);
 464
 465     let set_str = format!("{:?}", set);
 466
 467     assert_eq!(set_str, "{1, 2}");
 468     assert_eq!(format!("{:?}", empty), "{}");
 469 }
 470
 471 #[test]
 472 fn test_extend_ref() {
 473     let mut a = BTreeSet::new();
 474     a.insert(1);
 475
 476     a.extend(&[2, 3, 4]);
 477
 478     assert_eq!(a.len(), 4);
 479     assert!(a.contains(&1));
 480     assert!(a.contains(&2));
 481     assert!(a.contains(&3));
 482     assert!(a.contains(&4));
 483
 484     let mut b = BTreeSet::new();
 485     b.insert(5);
 486     b.insert(6);
 487
 488     a.extend(&b);
 489
 490     assert_eq!(a.len(), 6);
 491     assert!(a.contains(&1));
 492     assert!(a.contains(&2));
 493     assert!(a.contains(&3));
 494     assert!(a.contains(&4));
 495     assert!(a.contains(&5));
 496     assert!(a.contains(&6));
 497 }
 498
 499 #[test]
 500 fn test_recovery() {
 501     use std::cmp::Ordering;
 502
 503     #[derive(Debug)]
 504     struct Foo(&'static str, i32);
 505
 506     impl PartialEq for Foo {
 507         fn eq(&self, other: &Self) -> bool {
 508             self.0 == other.0
 509         }
 510     }
 511
 512     impl Eq for Foo {}
 513
 514     impl PartialOrd for Foo {
 515         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 516             self.0.partial_cmp(&other.0)
 517         }
 518     }
 519
 520     impl Ord for Foo {
 521         fn cmp(&self, other: &Self) -> Ordering {
 522             self.0.cmp(&other.0)
 523         }
 524     }
 525
 526     let mut s = BTreeSet::new();
 527     assert_eq!(s.replace(Foo("a", 1)), None);
 528     assert_eq!(s.len(), 1);
 529     assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
 530     assert_eq!(s.len(), 1);
 531
 532     {
 533         let mut it = s.iter();
 534         assert_eq!(it.next(), Some(&Foo("a", 2)));
 535         assert_eq!(it.next(), None);
 536     }
 537
 538     assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
 539     assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
 540     assert_eq!(s.len(), 0);
 541
 542     assert_eq!(s.get(&Foo("a", 1)), None);
 543     assert_eq!(s.take(&Foo("a", 1)), None);
 544
 545     assert_eq!(s.iter().next(), None);
 546 }
 547
 548 #[allow(dead_code)]
 549 fn test_variance() {
 550     fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
 551         v
 552     }
 553     fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
 554         v
 555     }
 556     fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
 557         v
 558     }
 559     fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
 560         v
 561     }
 562     // not applied to Difference, Intersection, SymmetricDifference, Union
 563 }
 564
 565 #[allow(dead_code)]
 566 fn test_sync() {
 567     fn set<T: Sync>(v: &BTreeSet<T>) -> impl Sync + '_ {
 568         v
 569     }
 570
 571     fn iter<T: Sync>(v: &BTreeSet<T>) -> impl Sync + '_ {
 572         v.iter()
 573     }
 574
 575     fn into_iter<T: Sync>(v: BTreeSet<T>) -> impl Sync {
 576         v.into_iter()
 577     }
 578
 579     fn range<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
 580         v.range(..)
 581     }
 582
 583     fn drain_filter<T: Sync + Ord>(v: &mut BTreeSet<T>) -> impl Sync + '_ {
 584         v.drain_filter(|_| false)
 585     }
 586
 587     fn difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
 588         v.difference(&v)
 589     }
 590
 591     fn intersection<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
 592         v.intersection(&v)
 593     }
 594
 595     fn symmetric_difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
 596         v.symmetric_difference(&v)
 597     }
 598
 599     fn union<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
 600         v.union(&v)
 601     }
 602 }
 603
 604 #[allow(dead_code)]
 605 fn test_send() {
 606     fn set<T: Send>(v: BTreeSet<T>) -> impl Send {
 607         v
 608     }
 609
 610     fn iter<T: Send + Sync>(v: &BTreeSet<T>) -> impl Send + '_ {
 611         v.iter()
 612     }
 613
 614     fn into_iter<T: Send>(v: BTreeSet<T>) -> impl Send {
 615         v.into_iter()
 616     }
 617
 618     fn range<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
 619         v.range(..)
 620     }
 621
 622     fn drain_filter<T: Send + Ord>(v: &mut BTreeSet<T>) -> impl Send + '_ {
 623         v.drain_filter(|_| false)
 624     }
 625
 626     fn difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
 627         v.difference(&v)
 628     }
 629
 630     fn intersection<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
 631         v.intersection(&v)
 632     }
 633
 634     fn symmetric_difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
 635         v.symmetric_difference(&v)
 636     }
 637
 638     fn union<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
 639         v.union(&v)
 640     }
 641 }
 642
 643 #[test]
 644 fn test_append() {
 645     let mut a = BTreeSet::new();
 646     a.insert(1);
 647     a.insert(2);
 648     a.insert(3);
 649
 650     let mut b = BTreeSet::new();
 651     b.insert(3);
 652     b.insert(4);
 653     b.insert(5);
 654
 655     a.append(&mut b);
 656
 657     assert_eq!(a.len(), 5);
 658     assert_eq!(b.len(), 0);
 659
 660     assert_eq!(a.contains(&1), true);
 661     assert_eq!(a.contains(&2), true);
 662     assert_eq!(a.contains(&3), true);
 663     assert_eq!(a.contains(&4), true);
 664     assert_eq!(a.contains(&5), true);
 665 }
 666
 667 #[test]
 668 fn test_first_last() {
 669     let mut a = BTreeSet::new();
 670     assert_eq!(a.first(), None);
 671     assert_eq!(a.last(), None);
 672     a.insert(1);
 673     assert_eq!(a.first(), Some(&1));
 674     assert_eq!(a.last(), Some(&1));
 675     a.insert(2);
 676     assert_eq!(a.first(), Some(&1));
 677     assert_eq!(a.last(), Some(&2));
 678     for i in 3..=12 {
 679         a.insert(i);
 680     }
 681     assert_eq!(a.first(), Some(&1));
 682     assert_eq!(a.last(), Some(&12));
 683     assert_eq!(a.pop_first(), Some(1));
 684     assert_eq!(a.pop_last(), Some(12));
 685     assert_eq!(a.pop_first(), Some(2));
 686     assert_eq!(a.pop_last(), Some(11));
 687     assert_eq!(a.pop_first(), Some(3));
 688     assert_eq!(a.pop_last(), Some(10));
 689     assert_eq!(a.pop_first(), Some(4));
 690     assert_eq!(a.pop_first(), Some(5));
 691     assert_eq!(a.pop_first(), Some(6));
 692     assert_eq!(a.pop_first(), Some(7));
 693     assert_eq!(a.pop_first(), Some(8));
 694     assert_eq!(a.clone().pop_last(), Some(9));
 695     assert_eq!(a.pop_first(), Some(9));
 696     assert_eq!(a.pop_first(), None);
 697     assert_eq!(a.pop_last(), None);
 698 }
 699
 700 fn rand_data(len: usize) -> Vec<u32> {
 701     assert!(len <= 70029); // from that point on numbers repeat
 702     let mut rng = DeterministicRng::new();
 703     Vec::from_iter((0..len).map(|_| rng.next()))
 704 }
 705
 706 #[test]
 707 fn test_split_off_empty_right() {
 708     let mut data = rand_data(173);
 709
 710     let mut set = BTreeSet::from_iter(data.clone());
 711     let right = set.split_off(&(data.iter().max().unwrap() + 1));
 712
 713     data.sort();
 714     assert!(set.into_iter().eq(data));
 715     assert!(right.into_iter().eq(None));
 716 }
 717
 718 #[test]
 719 fn test_split_off_empty_left() {
 720     let mut data = rand_data(314);
 721
 722     let mut set = BTreeSet::from_iter(data.clone());
 723     let right = set.split_off(data.iter().min().unwrap());
 724
 725     data.sort();
 726     assert!(set.into_iter().eq(None));
 727     assert!(right.into_iter().eq(data));
 728 }
 729
 730 #[test]
 731 fn test_split_off_large_random_sorted() {
 732     // Miri is too slow
 733     let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
 734     // special case with maximum height.
 735     data.sort();
 736
 737     let mut set = BTreeSet::from_iter(data.clone());
 738     let key = data[data.len() / 2];
 739     let right = set.split_off(&key);
 740
 741     assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
 742     assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
 743 }