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

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