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

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