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

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