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

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