[rustc.git] / compiler / rustc_index / src / bit_set / tests.rs

use super::*;

extern crate test;
use std::hint::black_box;
use test::Bencher;

#[test]
fn test_new_filled() {
    for i in 0..128 {
        let idx_buf = BitSet::new_filled(i);
        let elems: Vec<usize> = idx_buf.iter().collect();
        let expected: Vec<usize> = (0..i).collect();
        assert_eq!(elems, expected);
    }
}

#[test]
fn bitset_iter_works() {
    let mut bitset: BitSet<usize> = BitSet::new_empty(100);
    bitset.insert(1);
    bitset.insert(10);
    bitset.insert(19);
    bitset.insert(62);
    bitset.insert(63);
    bitset.insert(64);
    bitset.insert(65);
    bitset.insert(66);
    bitset.insert(99);
    assert_eq!(bitset.iter().collect::<Vec<_>>(), [1, 10, 19, 62, 63, 64, 65, 66, 99]);
}

#[test]
fn bitset_iter_works_2() {
    let mut bitset: BitSet<usize> = BitSet::new_empty(320);
    bitset.insert(0);
    bitset.insert(127);
    bitset.insert(191);
    bitset.insert(255);
    bitset.insert(319);
    assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
}

#[test]
fn union_two_sets() {
    let mut set1: BitSet<usize> = BitSet::new_empty(65);
    let mut set2: BitSet<usize> = BitSet::new_empty(65);
    assert!(set1.insert(3));
    assert!(!set1.insert(3));
    assert!(set2.insert(5));
    assert!(set2.insert(64));
    assert!(set1.union(&set2));
    assert!(!set1.union(&set2));
    assert!(set1.contains(3));
    assert!(!set1.contains(4));
    assert!(set1.contains(5));
    assert!(!set1.contains(63));
    assert!(set1.contains(64));
}

#[test]
fn hybrid_bitset() {
    let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
    assert!(sparse038.is_empty());
    assert!(sparse038.insert(0));
    assert!(sparse038.insert(1));
    assert!(sparse038.insert(8));
    assert!(sparse038.insert(3));
    assert!(!sparse038.insert(3));
    assert!(sparse038.remove(1));
    assert!(!sparse038.is_empty());
    assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);

    for i in 0..256 {
        if i == 0 || i == 3 || i == 8 {
            assert!(sparse038.contains(i));
        } else {
            assert!(!sparse038.contains(i));
        }
    }

    let mut sparse01358 = sparse038.clone();
    assert!(sparse01358.insert(1));
    assert!(sparse01358.insert(5));
    assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);

    let mut dense10 = HybridBitSet::new_empty(256);
    for i in 0..10 {
        assert!(dense10.insert(i));
    }
    assert!(!dense10.is_empty());
    assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

    let mut dense256 = HybridBitSet::new_empty(256);
    assert!(dense256.is_empty());
    dense256.insert_all();
    assert!(!dense256.is_empty());
    for i in 0..256 {
        assert!(dense256.contains(i));
    }

    assert!(sparse038.superset(&sparse038)); // sparse + sparse (self)
    assert!(sparse01358.superset(&sparse038)); // sparse + sparse
    assert!(dense10.superset(&sparse038)); // dense + sparse
    assert!(dense10.superset(&dense10)); // dense + dense (self)
    assert!(dense256.superset(&dense10)); // dense + dense

    let mut hybrid = sparse038.clone();
    assert!(!sparse01358.union(&hybrid)); // no change
    assert!(hybrid.union(&sparse01358));
    assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
    assert!(!dense256.union(&dense10));

    // dense / sparse where dense superset sparse
    assert!(!dense10.clone().union(&sparse01358));
    assert!(sparse01358.clone().union(&dense10));
    assert!(dense10.clone().intersect(&sparse01358));
    assert!(!sparse01358.clone().intersect(&dense10));
    assert!(dense10.clone().subtract(&sparse01358));
    assert!(sparse01358.clone().subtract(&dense10));

    // dense / sparse where sparse superset dense
    let dense038 = sparse038.to_dense();
    assert!(!sparse01358.clone().union(&dense038));
    assert!(dense038.clone().union(&sparse01358));
    assert!(sparse01358.clone().intersect(&dense038));
    assert!(!dense038.clone().intersect(&sparse01358));
    assert!(sparse01358.clone().subtract(&dense038));
    assert!(dense038.clone().subtract(&sparse01358));

    let mut dense = dense10.clone();
    assert!(dense.union(&dense256));
    assert!(dense.superset(&dense256) && dense256.superset(&dense));
    assert!(hybrid.union(&dense256));
    assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));

    assert!(!dense10.clone().intersect(&dense256));
    assert!(dense256.clone().intersect(&dense10));
    assert!(dense10.clone().subtract(&dense256));
    assert!(dense256.clone().subtract(&dense10));

    assert_eq!(dense256.iter().count(), 256);
    let mut dense0 = dense256;
    for i in 0..256 {
        assert!(dense0.remove(i));
    }
    assert!(!dense0.remove(0));
    assert!(dense0.is_empty());
}

#[test]
fn grow() {
    let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
    for index in 0..65 {
        assert!(set.insert(index));
        assert!(!set.insert(index));
    }
    set.ensure(128);

    // Check if the bits set before growing are still set
    for index in 0..65 {
        assert!(set.contains(index));
    }

    // Check if the new bits are all un-set
    for index in 65..128 {
        assert!(!set.contains(index));
    }

    // Check that we can set all new bits without running out of bounds
    for index in 65..128 {
        assert!(set.insert(index));
        assert!(!set.insert(index));
    }
}

#[test]
fn matrix_intersection() {
    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);

    // (*) Elements reachable from both 2 and 65.

    matrix.insert(2, 3);
    matrix.insert(2, 6);
    matrix.insert(2, 10); // (*)
    matrix.insert(2, 64); // (*)
    matrix.insert(2, 65);
    matrix.insert(2, 130);
    matrix.insert(2, 160); // (*)

    matrix.insert(64, 133);

    matrix.insert(65, 2);
    matrix.insert(65, 8);
    matrix.insert(65, 10); // (*)
    matrix.insert(65, 64); // (*)
    matrix.insert(65, 68);
    matrix.insert(65, 133);
    matrix.insert(65, 160); // (*)

    let intersection = matrix.intersect_rows(2, 64);
    assert!(intersection.is_empty());

    let intersection = matrix.intersect_rows(2, 65);
    assert_eq!(intersection, &[10, 64, 160]);
}

#[test]
fn matrix_iter() {
    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
    matrix.insert(3, 22);
    matrix.insert(3, 75);
    matrix.insert(2, 99);
    matrix.insert(4, 0);
    matrix.union_rows(3, 5);
    matrix.insert_all_into_row(6);

    let expected = [99];
    let mut iter = expected.iter();
    for i in matrix.iter(2) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    let expected = [22, 75];
    let mut iter = expected.iter();
    assert_eq!(matrix.count(3), expected.len());
    for i in matrix.iter(3) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    let expected = [0];
    let mut iter = expected.iter();
    assert_eq!(matrix.count(4), expected.len());
    for i in matrix.iter(4) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    let expected = [22, 75];
    let mut iter = expected.iter();
    assert_eq!(matrix.count(5), expected.len());
    for i in matrix.iter(5) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    assert_eq!(matrix.count(6), 100);
    let mut count = 0;
    for (idx, i) in matrix.iter(6).enumerate() {
        assert_eq!(idx, i);
        count += 1;
    }
    assert_eq!(count, 100);

    if let Some(i) = matrix.iter(7).next() {
        panic!("expected no elements in row, but contains element {:?}", i);
    }
}

#[test]
fn sparse_matrix_iter() {
    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
    matrix.insert(3, 22);
    matrix.insert(3, 75);
    matrix.insert(2, 99);
    matrix.insert(4, 0);
    matrix.union_rows(3, 5);

    let expected = [99];
    let mut iter = expected.iter();
    for i in matrix.iter(2) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    let expected = [22, 75];
    let mut iter = expected.iter();
    for i in matrix.iter(3) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    let expected = [0];
    let mut iter = expected.iter();
    for i in matrix.iter(4) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());

    let expected = [22, 75];
    let mut iter = expected.iter();
    for i in matrix.iter(5) {
        let j = *iter.next().unwrap();
        assert_eq!(i, j);
    }
    assert!(iter.next().is_none());
}

#[test]
fn sparse_matrix_operations() {
    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
    matrix.insert(3, 22);
    matrix.insert(3, 75);
    matrix.insert(2, 99);
    matrix.insert(4, 0);

    let mut disjoint: HybridBitSet<usize> = HybridBitSet::new_empty(100);
    disjoint.insert(33);

    let mut superset = HybridBitSet::new_empty(100);
    superset.insert(22);
    superset.insert(75);
    superset.insert(33);

    let mut subset = HybridBitSet::new_empty(100);
    subset.insert(22);

    // SparseBitMatrix::remove
    {
        let mut matrix = matrix.clone();
        matrix.remove(3, 22);
        assert!(!matrix.row(3).unwrap().contains(22));
        matrix.remove(0, 0);
        assert!(matrix.row(0).is_none());
    }

    // SparseBitMatrix::clear
    {
        let mut matrix = matrix.clone();
        matrix.clear(3);
        assert!(!matrix.row(3).unwrap().contains(75));
        matrix.clear(0);
        assert!(matrix.row(0).is_none());
    }

    // SparseBitMatrix::intersect_row
    {
        let mut matrix = matrix.clone();
        assert!(!matrix.intersect_row(3, &superset));
        assert!(matrix.intersect_row(3, &subset));
        matrix.intersect_row(0, &disjoint);
        assert!(matrix.row(0).is_none());
    }

    // SparseBitMatrix::subtract_row
    {
        let mut matrix = matrix.clone();
        assert!(!matrix.subtract_row(3, &disjoint));
        assert!(matrix.subtract_row(3, &subset));
        assert!(matrix.subtract_row(3, &superset));
        matrix.intersect_row(0, &disjoint);
        assert!(matrix.row(0).is_none());
    }

    // SparseBitMatrix::union_row
    {
        let mut matrix = matrix.clone();
        assert!(!matrix.union_row(3, &subset));
        assert!(matrix.union_row(3, &disjoint));
        matrix.union_row(0, &disjoint);
        assert!(matrix.row(0).is_some());
    }
}

#[test]
fn dense_insert_range() {
    #[track_caller]
    fn check<R>(domain: usize, range: R)
    where
        R: RangeBounds<usize> + Clone + IntoIterator<Item = usize> + std::fmt::Debug,
    {
        let mut set = BitSet::new_empty(domain);
        set.insert_range(range.clone());
        for i in set.iter() {
            assert!(range.contains(&i));
        }
        for i in range.clone() {
            assert!(set.contains(i), "{} in {:?}, inserted {:?}", i, set, range);
        }
    }
    check(300, 10..10);
    check(300, WORD_BITS..WORD_BITS * 2);
    check(300, WORD_BITS - 1..WORD_BITS * 2);
    check(300, WORD_BITS - 1..WORD_BITS);
    check(300, 10..100);
    check(300, 10..30);
    check(300, 0..5);
    check(300, 0..250);
    check(300, 200..250);

    check(300, 10..=10);
    check(300, WORD_BITS..=WORD_BITS * 2);
    check(300, WORD_BITS - 1..=WORD_BITS * 2);
    check(300, WORD_BITS - 1..=WORD_BITS);
    check(300, 10..=100);
    check(300, 10..=30);
    check(300, 0..=5);
    check(300, 0..=250);
    check(300, 200..=250);

    for i in 0..WORD_BITS * 2 {
        for j in i..WORD_BITS * 2 {
            check(WORD_BITS * 2, i..j);
            check(WORD_BITS * 2, i..=j);
            check(300, i..j);
            check(300, i..=j);
        }
    }
}

#[test]
fn dense_last_set_before() {
    fn easy(set: &BitSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
        let mut last_leq = None;
        for e in set.iter() {
            if needle.contains(&e) {
                last_leq = Some(e);
            }
        }
        last_leq
    }

    #[track_caller]
    fn cmp(set: &BitSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
        assert_eq!(
            set.last_set_in(needle.clone()),
            easy(set, needle.clone()),
            "{:?} in {:?}",
            needle,
            set
        );
    }
    let mut set = BitSet::new_empty(300);
    cmp(&set, 50..=50);
    set.insert(WORD_BITS);
    cmp(&set, WORD_BITS..=WORD_BITS);
    set.insert(WORD_BITS - 1);
    cmp(&set, 0..=WORD_BITS - 1);
    cmp(&set, 0..=5);
    cmp(&set, 10..100);
    set.insert(100);
    cmp(&set, 100..110);
    cmp(&set, 99..100);
    cmp(&set, 99..=100);

    for i in 0..=WORD_BITS * 2 {
        for j in i..=WORD_BITS * 2 {
            for k in 0..WORD_BITS * 2 {
                let mut set = BitSet::new_empty(300);
                cmp(&set, i..j);
                cmp(&set, i..=j);
                set.insert(k);
                cmp(&set, i..j);
                cmp(&set, i..=j);
            }
        }
    }
}

/// Merge dense hybrid set into empty sparse hybrid set.
#[bench]
fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
    for i in 0..10 {
        assert!(pre_dense.insert(i));
    }
    let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
    b.iter(|| {
        let dense = pre_dense.clone();
        let mut sparse = pre_sparse.clone();
        sparse.union(&dense);
    })
}

/// Merge dense hybrid set into full hybrid set with same indices.
#[bench]
fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
    for i in 0..10 {
        assert!(pre_dense.insert(i));
    }
    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
    for i in 0..SPARSE_MAX {
        assert!(pre_sparse.insert(i));
    }
    b.iter(|| {
        let dense = pre_dense.clone();
        let mut sparse = pre_sparse.clone();
        sparse.union(&dense);
    })
}

/// Merge dense hybrid set into full hybrid set with indices over the whole domain.
#[bench]
fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
    for i in 0..10 {
        assert!(pre_dense.insert(i));
    }
    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
    for i in 0..SPARSE_MAX {
        assert!(pre_sparse.insert(i * 64));
    }
    b.iter(|| {
        let dense = pre_dense.clone();
        let mut sparse = pre_sparse.clone();
        sparse.union(&dense);
    })
}

/// Merge dense hybrid set into empty hybrid set where the domain is very small.
#[bench]
fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
    for i in 0..SPARSE_MAX {
        assert!(pre_dense.insert(i));
    }
    let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
    b.iter(|| {
        let dense = pre_dense.clone();
        let mut sparse = pre_sparse.clone();
        sparse.union(&dense);
    })
}

/// Merge dense hybrid set into full hybrid set where the domain is very small.
#[bench]
fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
    for i in 0..SPARSE_MAX {
        assert!(pre_dense.insert(i));
    }
    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
    for i in 0..SPARSE_MAX {
        assert!(pre_sparse.insert(i));
    }
    b.iter(|| {
        let dense = pre_dense.clone();
        let mut sparse = pre_sparse.clone();
        sparse.union(&dense);
    })
}

#[bench]
fn bench_insert(b: &mut Bencher) {
    let mut bs = BitSet::new_filled(99999usize);
    b.iter(|| {
        black_box(bs.insert(black_box(100u32)));
    });
}

#[bench]
fn bench_remove(b: &mut Bencher) {
    let mut bs = BitSet::new_filled(99999usize);
    b.iter(|| {
        black_box(bs.remove(black_box(100u32)));
    });
}

#[bench]
fn bench_iter(b: &mut Bencher) {
    let bs = BitSet::new_filled(99999usize);
    b.iter(|| {
        bs.iter().map(|b: usize| black_box(b)).for_each(drop);
    });
}

#[bench]
fn bench_intersect(b: &mut Bencher) {
    let mut ba: BitSet<u32> = BitSet::new_filled(99999usize);
    let bb = BitSet::new_filled(99999usize);
    b.iter(|| {
        ba.intersect(black_box(&bb));
    });
}
Commit	Line	Data
416331ca XL	1	use super::*;
	2
	3	extern crate test;
5869c6ff	4	use std::hint::black_box;
416331ca XL	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);
dfeec247	29	assert_eq!(bitset.iter().collect::<Vec<_>>(), [1, 10, 19, 62, 63, 64, 65, 66, 99]);
416331ca XL	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
dfeec247 XL	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
416331ca	106
94222f64	107	let mut hybrid = sparse038.clone();
dfeec247	108	assert!(!sparse01358.union(&hybrid)); // no change
416331ca XL	109	assert!(hybrid.union(&sparse01358));
416331ca XL	110	assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
416331ca	111	assert!(!dense256.union(&dense10));
94222f64 XL	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();
416331ca XL	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
94222f64 XL	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
416331ca XL	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 grow() {
	152	let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
	153	for index in 0..65 {
	154	assert!(set.insert(index));
	155	assert!(!set.insert(index));
	156	}
	157	set.ensure(128);
	158
	159	// Check if the bits set before growing are still set
	160	for index in 0..65 {
	161	assert!(set.contains(index));
	162	}
	163
	164	// Check if the new bits are all un-set
	165	for index in 65..128 {
	166	assert!(!set.contains(index));
	167	}
	168
	169	// Check that we can set all new bits without running out of bounds
	170	for index in 65..128 {
	171	assert!(set.insert(index));
	172	assert!(!set.insert(index));
	173	}
	174	}
	175
	176	#[test]
	177	fn matrix_intersection() {
	178	let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
	179
	180	// (*) Elements reachable from both 2 and 65.
	181
	182	matrix.insert(2, 3);
	183	matrix.insert(2, 6);
	184	matrix.insert(2, 10); // (*)
	185	matrix.insert(2, 64); // (*)
	186	matrix.insert(2, 65);
	187	matrix.insert(2, 130);
	188	matrix.insert(2, 160); // (*)
	189
	190	matrix.insert(64, 133);
	191
	192	matrix.insert(65, 2);
	193	matrix.insert(65, 8);
	194	matrix.insert(65, 10); // (*)
	195	matrix.insert(65, 64); // (*)
	196	matrix.insert(65, 68);
	197	matrix.insert(65, 133);
	198	matrix.insert(65, 160); // (*)
	199
	200	let intersection = matrix.intersect_rows(2, 64);
	201	assert!(intersection.is_empty());
	202
	203	let intersection = matrix.intersect_rows(2, 65);
	204	assert_eq!(intersection, &[10, 64, 160]);
205	}
206
207	#[test]
208	fn matrix_iter() {
209	let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
210	matrix.insert(3, 22);
211	matrix.insert(3, 75);
212	matrix.insert(2, 99);
213	matrix.insert(4, 0);
214	matrix.union_rows(3, 5);
215	matrix.insert_all_into_row(6);
216
217	let expected = [99];
218	let mut iter = expected.iter();
219	for i in matrix.iter(2) {
220	let j = *iter.next().unwrap();
221	assert_eq!(i, j);
222	}
223	assert!(iter.next().is_none());
224
225	let expected = [22, 75];
226	let mut iter = expected.iter();
227	assert_eq!(matrix.count(3), expected.len());
228	for i in matrix.iter(3) {
229	let j = *iter.next().unwrap();
230	assert_eq!(i, j);
231	}
232	assert!(iter.next().is_none());
233
234	let expected = [0];
235	let mut iter = expected.iter();
236	assert_eq!(matrix.count(4), expected.len());
237	for i in matrix.iter(4) {
238	let j = *iter.next().unwrap();
239	assert_eq!(i, j);
240	}
241	assert!(iter.next().is_none());
242
243	let expected = [22, 75];
244	let mut iter = expected.iter();
245	assert_eq!(matrix.count(5), expected.len());
246	for i in matrix.iter(5) {
247	let j = *iter.next().unwrap();
248	assert_eq!(i, j);
249	}
250	assert!(iter.next().is_none());
251
252	assert_eq!(matrix.count(6), 100);
253	let mut count = 0;
254	for (idx, i) in matrix.iter(6).enumerate() {
255	assert_eq!(idx, i);
256	count += 1;
257	}
258	assert_eq!(count, 100);
259
260	if let Some(i) = matrix.iter(7).next() {
261	panic!("expected no elements in row, but contains element {:?}", i);
262	}
263	}
264
265	#[test]
266	fn sparse_matrix_iter() {
267	let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
268	matrix.insert(3, 22);
269	matrix.insert(3, 75);
270	matrix.insert(2, 99);
271	matrix.insert(4, 0);
272	matrix.union_rows(3, 5);
273
274	let expected = [99];
275	let mut iter = expected.iter();
276	for i in matrix.iter(2) {
277	let j = *iter.next().unwrap();
278	assert_eq!(i, j);
279	}
280	assert!(iter.next().is_none());
281
282	let expected = [22, 75];
283	let mut iter = expected.iter();
284	for i in matrix.iter(3) {
285	let j = *iter.next().unwrap();
286	assert_eq!(i, j);
287	}
288	assert!(iter.next().is_none());
289
290	let expected = [0];
291	let mut iter = expected.iter();
292	for i in matrix.iter(4) {
293	let j = *iter.next().unwrap();
294	assert_eq!(i, j);
295	}
296	assert!(iter.next().is_none());
297
298	let expected = [22, 75];
299	let mut iter = expected.iter();
300	for i in matrix.iter(5) {
301	let j = *iter.next().unwrap();
302	assert_eq!(i, j);
303	}
304	assert!(iter.next().is_none());
305	}
306
94222f64 XL	307	#[test]
	308	fn sparse_matrix_operations() {
	309	let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
	310	matrix.insert(3, 22);
	311	matrix.insert(3, 75);
	312	matrix.insert(2, 99);
	313	matrix.insert(4, 0);
	314
	315	let mut disjoint: HybridBitSet<usize> = HybridBitSet::new_empty(100);
	316	disjoint.insert(33);
	317
	318	let mut superset = HybridBitSet::new_empty(100);
	319	superset.insert(22);
	320	superset.insert(75);
	321	superset.insert(33);
	322
	323	let mut subset = HybridBitSet::new_empty(100);
	324	subset.insert(22);
	325
	326	// SparseBitMatrix::remove
	327	{
	328	let mut matrix = matrix.clone();
	329	matrix.remove(3, 22);
	330	assert!(!matrix.row(3).unwrap().contains(22));
	331	matrix.remove(0, 0);
	332	assert!(matrix.row(0).is_none());
	333	}
	334
	335	// SparseBitMatrix::clear
	336	{
	337	let mut matrix = matrix.clone();
	338	matrix.clear(3);
	339	assert!(!matrix.row(3).unwrap().contains(75));
	340	matrix.clear(0);
	341	assert!(matrix.row(0).is_none());
	342	}
	343
	344	// SparseBitMatrix::intersect_row
	345	{
	346	let mut matrix = matrix.clone();
	347	assert!(!matrix.intersect_row(3, &superset));
	348	assert!(matrix.intersect_row(3, &subset));
	349	matrix.intersect_row(0, &disjoint);
	350	assert!(matrix.row(0).is_none());
	351	}
	352
	353	// SparseBitMatrix::subtract_row
	354	{
	355	let mut matrix = matrix.clone();
	356	assert!(!matrix.subtract_row(3, &disjoint));
	357	assert!(matrix.subtract_row(3, &subset));
	358	assert!(matrix.subtract_row(3, &superset));
	359	matrix.intersect_row(0, &disjoint);
	360	assert!(matrix.row(0).is_none());
	361	}
	362
	363	// SparseBitMatrix::union_row
	364	{
	365	let mut matrix = matrix.clone();
	366	assert!(!matrix.union_row(3, &subset));
	367	assert!(matrix.union_row(3, &disjoint));
	368	matrix.union_row(0, &disjoint);
	369	assert!(matrix.row(0).is_some());
	370	}
371	}
372
3c0e092e XL	373	#[test]
	374	fn dense_insert_range() {
	375	#[track_caller]
	376	fn check<R>(domain: usize, range: R)
	377	where
	378	R: RangeBounds<usize> + Clone + IntoIterator<Item = usize> + std::fmt::Debug,
	379	{
	380	let mut set = BitSet::new_empty(domain);
	381	set.insert_range(range.clone());
	382	for i in set.iter() {
	383	assert!(range.contains(&i));
	384	}
	385	for i in range.clone() {
	386	assert!(set.contains(i), "{} in {:?}, inserted {:?}", i, set, range);
	387	}
	388	}
	389	check(300, 10..10);
	390	check(300, WORD_BITS..WORD_BITS * 2);
	391	check(300, WORD_BITS - 1..WORD_BITS * 2);
	392	check(300, WORD_BITS - 1..WORD_BITS);
	393	check(300, 10..100);
	394	check(300, 10..30);
	395	check(300, 0..5);
	396	check(300, 0..250);
	397	check(300, 200..250);
	398
	399	check(300, 10..=10);
	400	check(300, WORD_BITS..=WORD_BITS * 2);
	401	check(300, WORD_BITS - 1..=WORD_BITS * 2);
	402	check(300, WORD_BITS - 1..=WORD_BITS);
	403	check(300, 10..=100);
	404	check(300, 10..=30);
	405	check(300, 0..=5);
	406	check(300, 0..=250);
	407	check(300, 200..=250);
	408
	409	for i in 0..WORD_BITS * 2 {
	410	for j in i..WORD_BITS * 2 {
	411	check(WORD_BITS * 2, i..j);
	412	check(WORD_BITS * 2, i..=j);
	413	check(300, i..j);
	414	check(300, i..=j);
	415	}
	416	}
	417	}
	418
	419	#[test]
	420	fn dense_last_set_before() {
	421	fn easy(set: &BitSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
	422	let mut last_leq = None;
	423	for e in set.iter() {
	424	if needle.contains(&e) {
	425	last_leq = Some(e);
	426	}
	427	}
	428	last_leq
	429	}
	430
	431	#[track_caller]
	432	fn cmp(set: &BitSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
	433	assert_eq!(
	434	set.last_set_in(needle.clone()),
	435	easy(set, needle.clone()),
	436	"{:?} in {:?}",
437	needle,
438	set
439	);
440	}
441	let mut set = BitSet::new_empty(300);
442	cmp(&set, 50..=50);
443	set.insert(WORD_BITS);
444	cmp(&set, WORD_BITS..=WORD_BITS);
445	set.insert(WORD_BITS - 1);
446	cmp(&set, 0..=WORD_BITS - 1);
447	cmp(&set, 0..=5);
448	cmp(&set, 10..100);
449	set.insert(100);
450	cmp(&set, 100..110);
451	cmp(&set, 99..100);
452	cmp(&set, 99..=100);
453
454	for i in 0..=WORD_BITS * 2 {
455	for j in i..=WORD_BITS * 2 {
456	for k in 0..WORD_BITS * 2 {
457	let mut set = BitSet::new_empty(300);
458	cmp(&set, i..j);
459	cmp(&set, i..=j);
460	set.insert(k);
461	cmp(&set, i..j);
462	cmp(&set, i..=j);
463	}
464	}
465	}
466	}
467
416331ca XL	468	/// Merge dense hybrid set into empty sparse hybrid set.
	469	#[bench]
	470	fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
	471	let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
	472	for i in 0..10 {
	473	assert!(pre_dense.insert(i));
	474	}
	475	let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
	476	b.iter(\|\| {
	477	let dense = pre_dense.clone();
	478	let mut sparse = pre_sparse.clone();
	479	sparse.union(&dense);
	480	})
	481	}
	482
	483	/// Merge dense hybrid set into full hybrid set with same indices.
	484	#[bench]
	485	fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
	486	let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
	487	for i in 0..10 {
	488	assert!(pre_dense.insert(i));
	489	}
	490	let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
	491	for i in 0..SPARSE_MAX {
	492	assert!(pre_sparse.insert(i));
	493	}
	494	b.iter(\|\| {
	495	let dense = pre_dense.clone();
	496	let mut sparse = pre_sparse.clone();
	497	sparse.union(&dense);
	498	})
	499	}
	500
	501	/// Merge dense hybrid set into full hybrid set with indices over the whole domain.
	502	#[bench]
	503	fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
dfeec247	504	let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
416331ca XL	505	for i in 0..10 {
	506	assert!(pre_dense.insert(i));
	507	}
dfeec247	508	let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
416331ca	509	for i in 0..SPARSE_MAX {
dfeec247	510	assert!(pre_sparse.insert(i * 64));
416331ca XL	511	}
	512	b.iter(\|\| {
	513	let dense = pre_dense.clone();
	514	let mut sparse = pre_sparse.clone();
	515	sparse.union(&dense);
	516	})
	517	}
	518
	519	/// Merge dense hybrid set into empty hybrid set where the domain is very small.
	520	#[bench]
	521	fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
	522	let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
	523	for i in 0..SPARSE_MAX {
	524	assert!(pre_dense.insert(i));
	525	}
	526	let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
	527	b.iter(\|\| {
	528	let dense = pre_dense.clone();
	529	let mut sparse = pre_sparse.clone();
	530	sparse.union(&dense);
	531	})
	532	}
	533
	534	/// Merge dense hybrid set into full hybrid set where the domain is very small.
	535	#[bench]
	536	fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
	537	let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
	538	for i in 0..SPARSE_MAX {
	539	assert!(pre_dense.insert(i));
	540	}
	541	let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
	542	for i in 0..SPARSE_MAX {
	543	assert!(pre_sparse.insert(i));
	544	}
	545	b.iter(\|\| {
	546	let dense = pre_dense.clone();
	547	let mut sparse = pre_sparse.clone();
	548	sparse.union(&dense);
	549	})
	550	}
5869c6ff XL	551
	552	#[bench]
	553	fn bench_insert(b: &mut Bencher) {
	554	let mut bs = BitSet::new_filled(99999usize);
	555	b.iter(\|\| {
	556	black_box(bs.insert(black_box(100u32)));
	557	});
	558	}
	559
	560	#[bench]
	561	fn bench_remove(b: &mut Bencher) {
	562	let mut bs = BitSet::new_filled(99999usize);
	563	b.iter(\|\| {
	564	black_box(bs.remove(black_box(100u32)));
	565	});
	566	}
	567
	568	#[bench]
	569	fn bench_iter(b: &mut Bencher) {
	570	let bs = BitSet::new_filled(99999usize);
	571	b.iter(\|\| {
	572	bs.iter().map(\|b: usize\| black_box(b)).for_each(drop);
	573	});
	574	}
	575
	576	#[bench]
	577	fn bench_intersect(b: &mut Bencher) {
	578	let mut ba: BitSet<u32> = BitSet::new_filled(99999usize);
	579	let bb = BitSet::new_filled(99999usize);
	580	b.iter(\|\| {
	581	ba.intersect(black_box(&bb));
	582	});
	583	}