library/alloc/tests/btree/set.rs

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