1 use super::*;
2
3 extern crate test;
4 use std::hint::black_box;
5 use test::Bencher;
6
7 #[test]
test_new_filled()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]
bitset_iter_works()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]
bitset_iter_works_2()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]
union_two_sets()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]
hybrid_bitset()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]
grow()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]
matrix_intersection()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]
matrix_iter()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]
sparse_matrix_iter()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
307 #[test]
sparse_matrix_operations()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
373 #[test]
dense_insert_range()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]
dense_last_set_before()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
468 /// Merge dense hybrid set into empty sparse hybrid set.
469 #[bench]
union_hybrid_sparse_empty_to_dense(b: &mut Bencher)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]
union_hybrid_sparse_full_to_dense(b: &mut Bencher)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]
union_hybrid_sparse_domain_to_dense(b: &mut Bencher)503 fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
504 let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
505 for i in 0..10 {
506 assert!(pre_dense.insert(i));
507 }
508 let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
509 for i in 0..SPARSE_MAX {
510 assert!(pre_sparse.insert(i * 64));
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]
union_hybrid_sparse_empty_small_domain(b: &mut Bencher)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]
union_hybrid_sparse_full_small_domain(b: &mut Bencher)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 }
551
552 #[bench]
bench_insert(b: &mut Bencher)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]
bench_remove(b: &mut Bencher)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]
bench_iter(b: &mut Bencher)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]
bench_intersect(b: &mut Bencher)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 }
584