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