compiler/rustc_index/src/bit_set/tests.rs

   1 use super::*;
   2
   3 extern crate test;
   4 use std::hint::black_box;
   5 use test::Bencher;
   6
   7 #[test]
   8 fn test_new_filled() {
   9     for i in 0..128 {
  10         let idx_buf = BitSet::new_filled(i);
  11         let elems: Vec<usize> = idx_buf.iter().collect();
  12         let expected: Vec<usize> = (0..i).collect();
  13         assert_eq!(elems, expected);
  14     }
  15 }
  16
  17 #[test]
  18 fn bitset_iter_works() {
  19     let mut bitset: BitSet<usize> = BitSet::new_empty(100);
  20     bitset.insert(1);
  21     bitset.insert(10);
  22     bitset.insert(19);
  23     bitset.insert(62);
  24     bitset.insert(63);
  25     bitset.insert(64);
  26     bitset.insert(65);
  27     bitset.insert(66);
  28     bitset.insert(99);
  29     assert_eq!(bitset.iter().collect::<Vec<_>>(), [1, 10, 19, 62, 63, 64, 65, 66, 99]);
  30 }
  31
  32 #[test]
  33 fn bitset_iter_works_2() {
  34     let mut bitset: BitSet<usize> = BitSet::new_empty(320);
  35     bitset.insert(0);
  36     bitset.insert(127);
  37     bitset.insert(191);
  38     bitset.insert(255);
  39     bitset.insert(319);
  40     assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
  41 }
  42
  43 #[test]
  44 fn bitset_clone_from() {
  45     let mut a: BitSet<usize> = BitSet::new_empty(10);
  46     a.insert(4);
  47     a.insert(7);
  48     a.insert(9);
  49
  50     let mut b = BitSet::new_empty(2);
  51     b.clone_from(&a);
  52     assert_eq!(b.domain_size(), 10);
  53     assert_eq!(b.iter().collect::<Vec<_>>(), [4, 7, 9]);
  54
  55     b.clone_from(&BitSet::new_empty(40));
  56     assert_eq!(b.domain_size(), 40);
  57     assert_eq!(b.iter().collect::<Vec<_>>(), []);
  58 }
  59
  60 #[test]
  61 fn union_two_sets() {
  62     let mut set1: BitSet<usize> = BitSet::new_empty(65);
  63     let mut set2: BitSet<usize> = BitSet::new_empty(65);
  64     assert!(set1.insert(3));
  65     assert!(!set1.insert(3));
  66     assert!(set2.insert(5));
  67     assert!(set2.insert(64));
  68     assert!(set1.union(&set2));
  69     assert!(!set1.union(&set2));
  70     assert!(set1.contains(3));
  71     assert!(!set1.contains(4));
  72     assert!(set1.contains(5));
  73     assert!(!set1.contains(63));
  74     assert!(set1.contains(64));
  75 }
  76
  77 #[test]
  78 fn hybrid_bitset() {
  79     let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
  80     assert!(sparse038.is_empty());
  81     assert!(sparse038.insert(0));
  82     assert!(sparse038.insert(1));
  83     assert!(sparse038.insert(8));
  84     assert!(sparse038.insert(3));
  85     assert!(!sparse038.insert(3));
  86     assert!(sparse038.remove(1));
  87     assert!(!sparse038.is_empty());
  88     assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
  89
  90     for i in 0..256 {
  91         if i == 0 || i == 3 || i == 8 {
  92             assert!(sparse038.contains(i));
  93         } else {
  94             assert!(!sparse038.contains(i));
  95         }
  96     }
  97
  98     let mut sparse01358 = sparse038.clone();
  99     assert!(sparse01358.insert(1));
 100     assert!(sparse01358.insert(5));
 101     assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
 102
 103     let mut dense10 = HybridBitSet::new_empty(256);
 104     for i in 0..10 {
 105         assert!(dense10.insert(i));
 106     }
 107     assert!(!dense10.is_empty());
 108     assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
 109
 110     let mut dense256 = HybridBitSet::new_empty(256);
 111     assert!(dense256.is_empty());
 112     dense256.insert_all();
 113     assert!(!dense256.is_empty());
 114     for i in 0..256 {
 115         assert!(dense256.contains(i));
 116     }
 117
 118     assert!(sparse038.superset(&sparse038)); // sparse + sparse (self)
 119     assert!(sparse01358.superset(&sparse038)); // sparse + sparse
 120     assert!(dense10.superset(&sparse038)); // dense + sparse
 121     assert!(dense10.superset(&dense10)); // dense + dense (self)
 122     assert!(dense256.superset(&dense10)); // dense + dense
 123
 124     let mut hybrid = sparse038.clone();
 125     assert!(!sparse01358.union(&hybrid)); // no change
 126     assert!(hybrid.union(&sparse01358));
 127     assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
 128     assert!(!dense256.union(&dense10));
 129
 130     // dense / sparse where dense superset sparse
 131     assert!(!dense10.clone().union(&sparse01358));
 132     assert!(sparse01358.clone().union(&dense10));
 133     assert!(dense10.clone().intersect(&sparse01358));
 134     assert!(!sparse01358.clone().intersect(&dense10));
 135     assert!(dense10.clone().subtract(&sparse01358));
 136     assert!(sparse01358.clone().subtract(&dense10));
 137
 138     // dense / sparse where sparse superset dense
 139     let dense038 = sparse038.to_dense();
 140     assert!(!sparse01358.clone().union(&dense038));
 141     assert!(dense038.clone().union(&sparse01358));
 142     assert!(sparse01358.clone().intersect(&dense038));
 143     assert!(!dense038.clone().intersect(&sparse01358));
 144     assert!(sparse01358.clone().subtract(&dense038));
 145     assert!(dense038.clone().subtract(&sparse01358));
 146
 147     let mut dense = dense10.clone();
 148     assert!(dense.union(&dense256));
 149     assert!(dense.superset(&dense256) && dense256.superset(&dense));
 150     assert!(hybrid.union(&dense256));
 151     assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
 152
 153     assert!(!dense10.clone().intersect(&dense256));
 154     assert!(dense256.clone().intersect(&dense10));
 155     assert!(dense10.clone().subtract(&dense256));
 156     assert!(dense256.clone().subtract(&dense10));
 157
 158     assert_eq!(dense256.iter().count(), 256);
 159     let mut dense0 = dense256;
 160     for i in 0..256 {
 161         assert!(dense0.remove(i));
 162     }
 163     assert!(!dense0.remove(0));
 164     assert!(dense0.is_empty());
 165 }
 166
 167 #[test]
 168 fn chunked_bitset() {
 169     let mut b0 = ChunkedBitSet::<usize>::new_empty(0);
 170     let b0b = b0.clone();
 171     assert_eq!(b0, ChunkedBitSet { domain_size: 0, chunks: Box::new([]), marker: PhantomData });
 172
 173     // There are no valid insert/remove/contains operations on a 0-domain
 174     // bitset, but we can test `union`.
 175     b0.assert_valid();
 176     assert!(!b0.union(&b0b));
 177     assert_eq!(b0.chunks(), vec![]);
 178     assert_eq!(b0.count(), 0);
 179     b0.assert_valid();
 180
 181     //-----------------------------------------------------------------------
 182
 183     let mut b1 = ChunkedBitSet::<usize>::new_empty(1);
 184     assert_eq!(
 185         b1,
 186         ChunkedBitSet { domain_size: 1, chunks: Box::new([Zeros(1)]), marker: PhantomData }
 187     );
 188
 189     b1.assert_valid();
 190     assert!(!b1.contains(0));
 191     assert_eq!(b1.count(), 0);
 192     assert!(b1.insert(0));
 193     assert!(b1.contains(0));
 194     assert_eq!(b1.count(), 1);
 195     assert_eq!(b1.chunks(), [Ones(1)]);
 196     assert!(!b1.insert(0));
 197     assert!(b1.remove(0));
 198     assert!(!b1.contains(0));
 199     assert_eq!(b1.count(), 0);
 200     assert_eq!(b1.chunks(), [Zeros(1)]);
 201     b1.assert_valid();
 202
 203     //-----------------------------------------------------------------------
 204
 205     let mut b100 = ChunkedBitSet::<usize>::new_filled(100);
 206     assert_eq!(
 207         b100,
 208         ChunkedBitSet { domain_size: 100, chunks: Box::new([Ones(100)]), marker: PhantomData }
 209     );
 210
 211     b100.assert_valid();
 212     for i in 0..100 {
 213         assert!(b100.contains(i));
 214     }
 215     assert_eq!(b100.count(), 100);
 216     assert!(b100.remove(3));
 217     assert!(b100.insert(3));
 218     assert_eq!(b100.chunks(), vec![Ones(100)]);
 219     assert!(
 220         b100.remove(20) && b100.remove(30) && b100.remove(40) && b100.remove(99) && b100.insert(30)
 221     );
 222     assert_eq!(b100.count(), 97);
 223     assert!(!b100.contains(20) && b100.contains(30) && !b100.contains(99) && b100.contains(50));
 224     assert_eq!(
 225         b100.chunks(),
 226         vec![Mixed(
 227             100,
 228             97,
 229             #[rustfmt::skip]
 230             Rc::new([
 231                 0b11111111_11111111_11111110_11111111_11111111_11101111_11111111_11111111,
 232                 0b00000000_00000000_00000000_00000111_11111111_11111111_11111111_11111111,
 233                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 234                 0, 0, 0, 0, 0,
 235             ])
 236         )],
 237     );
 238     b100.assert_valid();
 239     let mut num_removed = 0;
 240     for i in 0..100 {
 241         if b100.remove(i) {
 242             num_removed += 1;
 243         }
 244     }
 245     assert_eq!(num_removed, 97);
 246     assert_eq!(b100.chunks(), vec![Zeros(100)]);
 247     b100.assert_valid();
 248
 249     //-----------------------------------------------------------------------
 250
 251     let mut b2548 = ChunkedBitSet::<usize>::new_empty(2548);
 252     assert_eq!(
 253         b2548,
 254         ChunkedBitSet {
 255             domain_size: 2548,
 256             chunks: Box::new([Zeros(2048), Zeros(500)]),
 257             marker: PhantomData,
 258         }
 259     );
 260
 261     b2548.assert_valid();
 262     b2548.insert(14);
 263     b2548.remove(14);
 264     assert_eq!(b2548.chunks(), vec![Zeros(2048), Zeros(500)]);
 265     b2548.insert_all();
 266     for i in 0..2548 {
 267         assert!(b2548.contains(i));
 268     }
 269     assert_eq!(b2548.count(), 2548);
 270     assert_eq!(b2548.chunks(), vec![Ones(2048), Ones(500)]);
 271     b2548.assert_valid();
 272
 273     //-----------------------------------------------------------------------
 274
 275     let mut b4096 = ChunkedBitSet::<usize>::new_empty(4096);
 276     assert_eq!(
 277         b4096,
 278         ChunkedBitSet {
 279             domain_size: 4096,
 280             chunks: Box::new([Zeros(2048), Zeros(2048)]),
 281             marker: PhantomData,
 282         }
 283     );
 284
 285     b4096.assert_valid();
 286     for i in 0..4096 {
 287         assert!(!b4096.contains(i));
 288     }
 289     assert!(b4096.insert(0) && b4096.insert(4095) && !b4096.insert(4095));
 290     assert!(
 291         b4096.contains(0) && !b4096.contains(2047) && !b4096.contains(2048) && b4096.contains(4095)
 292     );
 293     assert_eq!(
 294         b4096.chunks(),
 295         #[rustfmt::skip]
 296         vec![
 297             Mixed(2048, 1, Rc::new([
 298                 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 299                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 300             ])),
 301             Mixed(2048, 1, Rc::new([
 302                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 303                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x8000_0000_0000_0000
 304             ])),
 305         ],
 306     );
 307     assert_eq!(b4096.count(), 2);
 308     b4096.assert_valid();
 309
 310     //-----------------------------------------------------------------------
 311
 312     let mut b10000 = ChunkedBitSet::<usize>::new_empty(10000);
 313     assert_eq!(
 314         b10000,
 315         ChunkedBitSet {
 316             domain_size: 10000,
 317             chunks: Box::new([Zeros(2048), Zeros(2048), Zeros(2048), Zeros(2048), Zeros(1808),]),
 318             marker: PhantomData,
 319         }
 320     );
 321
 322     b10000.assert_valid();
 323     assert!(b10000.insert(3000) && b10000.insert(5000));
 324     assert_eq!(
 325         b10000.chunks(),
 326         #[rustfmt::skip]
 327         vec![
 328             Zeros(2048),
 329             Mixed(2048, 1, Rc::new([
 330                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100_0000_0000_0000, 0,
 331                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 332             ])),
 333             Mixed(2048, 1, Rc::new([
 334                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100, 0,
 335                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 336             ])),
 337             Zeros(2048),
 338             Zeros(1808),
 339         ],
 340     );
 341     let mut b10000b = ChunkedBitSet::<usize>::new_empty(10000);
 342     b10000b.clone_from(&b10000);
 343     assert_eq!(b10000, b10000b);
 344     for i in 6000..7000 {
 345         b10000b.insert(i);
 346     }
 347     assert_eq!(b10000b.count(), 1002);
 348     b10000b.assert_valid();
 349     b10000b.clone_from(&b10000);
 350     assert_eq!(b10000b.count(), 2);
 351     for i in 2000..8000 {
 352         b10000b.insert(i);
 353     }
 354     b10000.union(&b10000b);
 355     assert_eq!(b10000.count(), 6000);
 356     b10000.union(&b10000b);
 357     assert_eq!(b10000.count(), 6000);
 358     b10000.assert_valid();
 359     b10000b.assert_valid();
 360 }
 361
 362 fn with_elements_chunked(elements: &[usize], domain_size: usize) -> ChunkedBitSet<usize> {
 363     let mut s = ChunkedBitSet::new_empty(domain_size);
 364     for &e in elements {
 365         assert!(s.insert(e));
 366     }
 367     s
 368 }
 369
 370 fn with_elements_standard(elements: &[usize], domain_size: usize) -> BitSet<usize> {
 371     let mut s = BitSet::new_empty(domain_size);
 372     for &e in elements {
 373         assert!(s.insert(e));
 374     }
 375     s
 376 }
 377
 378 #[test]
 379 fn chunked_bitset_into_bitset_operations() {
 380     let a = vec![1, 5, 7, 11, 15, 2000, 3000];
 381     let b = vec![3, 4, 11, 3000, 4000];
 382     let aub = vec![1, 3, 4, 5, 7, 11, 15, 2000, 3000, 4000];
 383     let aib = vec![11, 3000];
 384
 385     let b = with_elements_chunked(&b, 9876);
 386
 387     let mut union = with_elements_standard(&a, 9876);
 388     assert!(union.union(&b));
 389     assert!(!union.union(&b));
 390     assert!(union.iter().eq(aub.iter().copied()));
 391
 392     let mut intersection = with_elements_standard(&a, 9876);
 393     assert!(intersection.intersect(&b));
 394     assert!(!intersection.intersect(&b));
 395     assert!(intersection.iter().eq(aib.iter().copied()));
 396 }
 397
 398 #[test]
 399 fn chunked_bitset_iter() {
 400     fn check_iter(bit: &ChunkedBitSet<usize>, vec: &Vec<usize>) {
 401         // Test collecting via both `.next()` and `.fold()` calls, to make sure both are correct
 402         let mut collect_next = Vec::new();
 403         let mut bit_iter = bit.iter();
 404         while let Some(item) = bit_iter.next() {
 405             collect_next.push(item);
 406         }
 407         assert_eq!(vec, &collect_next);
 408
 409         let collect_fold = bit.iter().fold(Vec::new(), |mut v, item| {
 410             v.push(item);
 411             v
 412         });
 413         assert_eq!(vec, &collect_fold);
 414     }
 415
 416     // Empty
 417     let vec: Vec<usize> = Vec::new();
 418     let bit = with_elements_chunked(&vec, 9000);
 419     check_iter(&bit, &vec);
 420
 421     // Filled
 422     let n = 10000;
 423     let vec: Vec<usize> = (0..n).collect();
 424     let bit = with_elements_chunked(&vec, n);
 425     check_iter(&bit, &vec);
 426
 427     // Filled with trailing zeros
 428     let n = 10000;
 429     let vec: Vec<usize> = (0..n).collect();
 430     let bit = with_elements_chunked(&vec, 2 * n);
 431     check_iter(&bit, &vec);
 432
 433     // Mixed
 434     let n = 12345;
 435     let vec: Vec<usize> = vec![0, 1, 2, 2010, 2047, 2099, 6000, 6002, 6004];
 436     let bit = with_elements_chunked(&vec, n);
 437     check_iter(&bit, &vec);
 438 }
 439
 440 #[test]
 441 fn grow() {
 442     let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
 443     for index in 0..65 {
 444         assert!(set.insert(index));
 445         assert!(!set.insert(index));
 446     }
 447     set.ensure(128);
 448
 449     // Check if the bits set before growing are still set
 450     for index in 0..65 {
 451         assert!(set.contains(index));
 452     }
 453
 454     // Check if the new bits are all un-set
 455     for index in 65..128 {
 456         assert!(!set.contains(index));
 457     }
 458
 459     // Check that we can set all new bits without running out of bounds
 460     for index in 65..128 {
 461         assert!(set.insert(index));
 462         assert!(!set.insert(index));
 463     }
 464 }
 465
 466 #[test]
 467 fn matrix_intersection() {
 468     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
 469
 470     // (*) Elements reachable from both 2 and 65.
 471
 472     matrix.insert(2, 3);
 473     matrix.insert(2, 6);
 474     matrix.insert(2, 10); // (*)
 475     matrix.insert(2, 64); // (*)
 476     matrix.insert(2, 65);
 477     matrix.insert(2, 130);
 478     matrix.insert(2, 160); // (*)
 479
 480     matrix.insert(64, 133);
 481
 482     matrix.insert(65, 2);
 483     matrix.insert(65, 8);
 484     matrix.insert(65, 10); // (*)
 485     matrix.insert(65, 64); // (*)
 486     matrix.insert(65, 68);
 487     matrix.insert(65, 133);
 488     matrix.insert(65, 160); // (*)
 489
 490     let intersection = matrix.intersect_rows(2, 64);
 491     assert!(intersection.is_empty());
 492
 493     let intersection = matrix.intersect_rows(2, 65);
 494     assert_eq!(intersection, &[10, 64, 160]);
 495 }
 496
 497 #[test]
 498 fn matrix_iter() {
 499     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
 500     matrix.insert(3, 22);
 501     matrix.insert(3, 75);
 502     matrix.insert(2, 99);
 503     matrix.insert(4, 0);
 504     matrix.union_rows(3, 5);
 505     matrix.insert_all_into_row(6);
 506
 507     let expected = [99];
 508     let mut iter = expected.iter();
 509     for i in matrix.iter(2) {
 510         let j = *iter.next().unwrap();
 511         assert_eq!(i, j);
 512     }
 513     assert!(iter.next().is_none());
 514
 515     let expected = [22, 75];
 516     let mut iter = expected.iter();
 517     assert_eq!(matrix.count(3), expected.len());
 518     for i in matrix.iter(3) {
 519         let j = *iter.next().unwrap();
 520         assert_eq!(i, j);
 521     }
 522     assert!(iter.next().is_none());
 523
 524     let expected = [0];
 525     let mut iter = expected.iter();
 526     assert_eq!(matrix.count(4), expected.len());
 527     for i in matrix.iter(4) {
 528         let j = *iter.next().unwrap();
 529         assert_eq!(i, j);
 530     }
 531     assert!(iter.next().is_none());
 532
 533     let expected = [22, 75];
 534     let mut iter = expected.iter();
 535     assert_eq!(matrix.count(5), expected.len());
 536     for i in matrix.iter(5) {
 537         let j = *iter.next().unwrap();
 538         assert_eq!(i, j);
 539     }
 540     assert!(iter.next().is_none());
 541
 542     assert_eq!(matrix.count(6), 100);
 543     let mut count = 0;
 544     for (idx, i) in matrix.iter(6).enumerate() {
 545         assert_eq!(idx, i);
 546         count += 1;
 547     }
 548     assert_eq!(count, 100);
 549
 550     if let Some(i) = matrix.iter(7).next() {
 551         panic!("expected no elements in row, but contains element {:?}", i);
 552     }
 553 }
 554
 555 #[test]
 556 fn sparse_matrix_iter() {
 557     let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
 558     matrix.insert(3, 22);
 559     matrix.insert(3, 75);
 560     matrix.insert(2, 99);
 561     matrix.insert(4, 0);
 562     matrix.union_rows(3, 5);
 563
 564     let expected = [99];
 565     let mut iter = expected.iter();
 566     for i in matrix.iter(2) {
 567         let j = *iter.next().unwrap();
 568         assert_eq!(i, j);
 569     }
 570     assert!(iter.next().is_none());
 571
 572     let expected = [22, 75];
 573     let mut iter = expected.iter();
 574     for i in matrix.iter(3) {
 575         let j = *iter.next().unwrap();
 576         assert_eq!(i, j);
 577     }
 578     assert!(iter.next().is_none());
 579
 580     let expected = [0];
 581     let mut iter = expected.iter();
 582     for i in matrix.iter(4) {
 583         let j = *iter.next().unwrap();
 584         assert_eq!(i, j);
 585     }
 586     assert!(iter.next().is_none());
 587
 588     let expected = [22, 75];
 589     let mut iter = expected.iter();
 590     for i in matrix.iter(5) {
 591         let j = *iter.next().unwrap();
 592         assert_eq!(i, j);
 593     }
 594     assert!(iter.next().is_none());
 595 }
 596
 597 #[test]
 598 fn sparse_matrix_operations() {
 599     let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
 600     matrix.insert(3, 22);
 601     matrix.insert(3, 75);
 602     matrix.insert(2, 99);
 603     matrix.insert(4, 0);
 604
 605     let mut disjoint: HybridBitSet<usize> = HybridBitSet::new_empty(100);
 606     disjoint.insert(33);
 607
 608     let mut superset = HybridBitSet::new_empty(100);
 609     superset.insert(22);
 610     superset.insert(75);
 611     superset.insert(33);
 612
 613     let mut subset = HybridBitSet::new_empty(100);
 614     subset.insert(22);
 615
 616     // SparseBitMatrix::remove
 617     {
 618         let mut matrix = matrix.clone();
 619         matrix.remove(3, 22);
 620         assert!(!matrix.row(3).unwrap().contains(22));
 621         matrix.remove(0, 0);
 622         assert!(matrix.row(0).is_none());
 623     }
 624
 625     // SparseBitMatrix::clear
 626     {
 627         let mut matrix = matrix.clone();
 628         matrix.clear(3);
 629         assert!(!matrix.row(3).unwrap().contains(75));
 630         matrix.clear(0);
 631         assert!(matrix.row(0).is_none());
 632     }
 633
 634     // SparseBitMatrix::intersect_row
 635     {
 636         let mut matrix = matrix.clone();
 637         assert!(!matrix.intersect_row(3, &superset));
 638         assert!(matrix.intersect_row(3, &subset));
 639         matrix.intersect_row(0, &disjoint);
 640         assert!(matrix.row(0).is_none());
 641     }
 642
 643     // SparseBitMatrix::subtract_row
 644     {
 645         let mut matrix = matrix.clone();
 646         assert!(!matrix.subtract_row(3, &disjoint));
 647         assert!(matrix.subtract_row(3, &subset));
 648         assert!(matrix.subtract_row(3, &superset));
 649         matrix.intersect_row(0, &disjoint);
 650         assert!(matrix.row(0).is_none());
 651     }
 652
 653     // SparseBitMatrix::union_row
 654     {
 655         let mut matrix = matrix.clone();
 656         assert!(!matrix.union_row(3, &subset));
 657         assert!(matrix.union_row(3, &disjoint));
 658         matrix.union_row(0, &disjoint);
 659         assert!(matrix.row(0).is_some());
 660     }
 661 }
 662
 663 #[test]
 664 fn dense_insert_range() {
 665     #[track_caller]
 666     fn check<R>(domain: usize, range: R)
 667     where
 668         R: RangeBounds<usize> + Clone + IntoIterator<Item = usize> + std::fmt::Debug,
 669     {
 670         let mut set = BitSet::new_empty(domain);
 671         set.insert_range(range.clone());
 672         for i in set.iter() {
 673             assert!(range.contains(&i));
 674         }
 675         for i in range.clone() {
 676             assert!(set.contains(i), "{} in {:?}, inserted {:?}", i, set, range);
 677         }
 678     }
 679     check(300, 10..10);
 680     check(300, WORD_BITS..WORD_BITS * 2);
 681     check(300, WORD_BITS - 1..WORD_BITS * 2);
 682     check(300, WORD_BITS - 1..WORD_BITS);
 683     check(300, 10..100);
 684     check(300, 10..30);
 685     check(300, 0..5);
 686     check(300, 0..250);
 687     check(300, 200..250);
 688
 689     check(300, 10..=10);
 690     check(300, WORD_BITS..=WORD_BITS * 2);
 691     check(300, WORD_BITS - 1..=WORD_BITS * 2);
 692     check(300, WORD_BITS - 1..=WORD_BITS);
 693     check(300, 10..=100);
 694     check(300, 10..=30);
 695     check(300, 0..=5);
 696     check(300, 0..=250);
 697     check(300, 200..=250);
 698
 699     for i in 0..WORD_BITS * 2 {
 700         for j in i..WORD_BITS * 2 {
 701             check(WORD_BITS * 2, i..j);
 702             check(WORD_BITS * 2, i..=j);
 703             check(300, i..j);
 704             check(300, i..=j);
 705         }
 706     }
 707 }
 708
 709 #[test]
 710 fn dense_last_set_before() {
 711     fn easy(set: &BitSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
 712         let mut last_leq = None;
 713         for e in set.iter() {
 714             if needle.contains(&e) {
 715                 last_leq = Some(e);
 716             }
 717         }
 718         last_leq
 719     }
 720
 721     #[track_caller]
 722     fn cmp(set: &BitSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
 723         assert_eq!(
 724             set.last_set_in(needle.clone()),
 725             easy(set, needle.clone()),
 726             "{:?} in {:?}",
 727             needle,
 728             set
 729         );
 730     }
 731     let mut set = BitSet::new_empty(300);
 732     cmp(&set, 50..=50);
 733     set.insert(WORD_BITS);
 734     cmp(&set, WORD_BITS..=WORD_BITS);
 735     set.insert(WORD_BITS - 1);
 736     cmp(&set, 0..=WORD_BITS - 1);
 737     cmp(&set, 0..=5);
 738     cmp(&set, 10..100);
 739     set.insert(100);
 740     cmp(&set, 100..110);
 741     cmp(&set, 99..100);
 742     cmp(&set, 99..=100);
 743
 744     for i in 0..=WORD_BITS * 2 {
 745         for j in i..=WORD_BITS * 2 {
 746             for k in 0..WORD_BITS * 2 {
 747                 let mut set = BitSet::new_empty(300);
 748                 cmp(&set, i..j);
 749                 cmp(&set, i..=j);
 750                 set.insert(k);
 751                 cmp(&set, i..j);
 752                 cmp(&set, i..=j);
 753             }
 754         }
 755     }
 756 }
 757
 758 /// Merge dense hybrid set into empty sparse hybrid set.
 759 #[bench]
 760 fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
 761     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 762     for i in 0..10 {
 763         assert!(pre_dense.insert(i));
 764     }
 765     let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 766     b.iter(|| {
 767         let dense = pre_dense.clone();
 768         let mut sparse = pre_sparse.clone();
 769         sparse.union(&dense);
 770     })
 771 }
 772
 773 /// Merge dense hybrid set into full hybrid set with same indices.
 774 #[bench]
 775 fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
 776     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 777     for i in 0..10 {
 778         assert!(pre_dense.insert(i));
 779     }
 780     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 781     for i in 0..SPARSE_MAX {
 782         assert!(pre_sparse.insert(i));
 783     }
 784     b.iter(|| {
 785         let dense = pre_dense.clone();
 786         let mut sparse = pre_sparse.clone();
 787         sparse.union(&dense);
 788     })
 789 }
 790
 791 /// Merge dense hybrid set into full hybrid set with indices over the whole domain.
 792 #[bench]
 793 fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
 794     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
 795     for i in 0..10 {
 796         assert!(pre_dense.insert(i));
 797     }
 798     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
 799     for i in 0..SPARSE_MAX {
 800         assert!(pre_sparse.insert(i * 64));
 801     }
 802     b.iter(|| {
 803         let dense = pre_dense.clone();
 804         let mut sparse = pre_sparse.clone();
 805         sparse.union(&dense);
 806     })
 807 }
 808
 809 /// Merge dense hybrid set into empty hybrid set where the domain is very small.
 810 #[bench]
 811 fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
 812     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 813     for i in 0..SPARSE_MAX {
 814         assert!(pre_dense.insert(i));
 815     }
 816     let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 817     b.iter(|| {
 818         let dense = pre_dense.clone();
 819         let mut sparse = pre_sparse.clone();
 820         sparse.union(&dense);
 821     })
 822 }
 823
 824 /// Merge dense hybrid set into full hybrid set where the domain is very small.
 825 #[bench]
 826 fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
 827     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 828     for i in 0..SPARSE_MAX {
 829         assert!(pre_dense.insert(i));
 830     }
 831     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 832     for i in 0..SPARSE_MAX {
 833         assert!(pre_sparse.insert(i));
 834     }
 835     b.iter(|| {
 836         let dense = pre_dense.clone();
 837         let mut sparse = pre_sparse.clone();
 838         sparse.union(&dense);
 839     })
 840 }
 841
 842 #[bench]
 843 fn bench_insert(b: &mut Bencher) {
 844     let mut bs = BitSet::new_filled(99999usize);
 845     b.iter(|| {
 846         black_box(bs.insert(black_box(100u32)));
 847     });
 848 }
 849
 850 #[bench]
 851 fn bench_remove(b: &mut Bencher) {
 852     let mut bs = BitSet::new_filled(99999usize);
 853     b.iter(|| {
 854         black_box(bs.remove(black_box(100u32)));
 855     });
 856 }
 857
 858 #[bench]
 859 fn bench_iter(b: &mut Bencher) {
 860     let bs = BitSet::new_filled(99999usize);
 861     b.iter(|| {
 862         bs.iter().map(|b: usize| black_box(b)).for_each(drop);
 863     });
 864 }
 865
 866 #[bench]
 867 fn bench_intersect(b: &mut Bencher) {
 868     let mut ba: BitSet<u32> = BitSet::new_filled(99999usize);
 869     let bb = BitSet::new_filled(99999usize);
 870     b.iter(|| {
 871         ba.intersect(black_box(&bb));
 872     });
 873 }