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