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;
108 assert!(!sparse01358.union(&hybrid)); // no change
109 assert!(hybrid.union(&sparse01358));
110 assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
111 assert!(!dense10.union(&sparse01358));
112 assert!(!dense256.union(&dense10));
113 let mut dense = dense10;
114 assert!(dense.union(&dense256));
115 assert!(dense.superset(&dense256) && dense256.superset(&dense));
116 assert!(hybrid.union(&dense256));
117 assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
118
119 assert_eq!(dense256.iter().count(), 256);
120 let mut dense0 = dense256;
121 for i in 0..256 {
122 assert!(dense0.remove(i));
123 }
124 assert!(!dense0.remove(0));
125 assert!(dense0.is_empty());
126 }
127
128 #[test]
grow()129 fn grow() {
130 let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
131 for index in 0..65 {
132 assert!(set.insert(index));
133 assert!(!set.insert(index));
134 }
135 set.ensure(128);
136
137 // Check if the bits set before growing are still set
138 for index in 0..65 {
139 assert!(set.contains(index));
140 }
141
142 // Check if the new bits are all un-set
143 for index in 65..128 {
144 assert!(!set.contains(index));
145 }
146
147 // Check that we can set all new bits without running out of bounds
148 for index in 65..128 {
149 assert!(set.insert(index));
150 assert!(!set.insert(index));
151 }
152 }
153
154 #[test]
matrix_intersection()155 fn matrix_intersection() {
156 let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
157
158 // (*) Elements reachable from both 2 and 65.
159
160 matrix.insert(2, 3);
161 matrix.insert(2, 6);
162 matrix.insert(2, 10); // (*)
163 matrix.insert(2, 64); // (*)
164 matrix.insert(2, 65);
165 matrix.insert(2, 130);
166 matrix.insert(2, 160); // (*)
167
168 matrix.insert(64, 133);
169
170 matrix.insert(65, 2);
171 matrix.insert(65, 8);
172 matrix.insert(65, 10); // (*)
173 matrix.insert(65, 64); // (*)
174 matrix.insert(65, 68);
175 matrix.insert(65, 133);
176 matrix.insert(65, 160); // (*)
177
178 let intersection = matrix.intersect_rows(2, 64);
179 assert!(intersection.is_empty());
180
181 let intersection = matrix.intersect_rows(2, 65);
182 assert_eq!(intersection, &[10, 64, 160]);
183 }
184
185 #[test]
matrix_iter()186 fn matrix_iter() {
187 let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
188 matrix.insert(3, 22);
189 matrix.insert(3, 75);
190 matrix.insert(2, 99);
191 matrix.insert(4, 0);
192 matrix.union_rows(3, 5);
193 matrix.insert_all_into_row(6);
194
195 let expected = [99];
196 let mut iter = expected.iter();
197 for i in matrix.iter(2) {
198 let j = *iter.next().unwrap();
199 assert_eq!(i, j);
200 }
201 assert!(iter.next().is_none());
202
203 let expected = [22, 75];
204 let mut iter = expected.iter();
205 assert_eq!(matrix.count(3), expected.len());
206 for i in matrix.iter(3) {
207 let j = *iter.next().unwrap();
208 assert_eq!(i, j);
209 }
210 assert!(iter.next().is_none());
211
212 let expected = [0];
213 let mut iter = expected.iter();
214 assert_eq!(matrix.count(4), expected.len());
215 for i in matrix.iter(4) {
216 let j = *iter.next().unwrap();
217 assert_eq!(i, j);
218 }
219 assert!(iter.next().is_none());
220
221 let expected = [22, 75];
222 let mut iter = expected.iter();
223 assert_eq!(matrix.count(5), expected.len());
224 for i in matrix.iter(5) {
225 let j = *iter.next().unwrap();
226 assert_eq!(i, j);
227 }
228 assert!(iter.next().is_none());
229
230 assert_eq!(matrix.count(6), 100);
231 let mut count = 0;
232 for (idx, i) in matrix.iter(6).enumerate() {
233 assert_eq!(idx, i);
234 count += 1;
235 }
236 assert_eq!(count, 100);
237
238 if let Some(i) = matrix.iter(7).next() {
239 panic!("expected no elements in row, but contains element {:?}", i);
240 }
241 }
242
243 #[test]
sparse_matrix_iter()244 fn sparse_matrix_iter() {
245 let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
246 matrix.insert(3, 22);
247 matrix.insert(3, 75);
248 matrix.insert(2, 99);
249 matrix.insert(4, 0);
250 matrix.union_rows(3, 5);
251
252 let expected = [99];
253 let mut iter = expected.iter();
254 for i in matrix.iter(2) {
255 let j = *iter.next().unwrap();
256 assert_eq!(i, j);
257 }
258 assert!(iter.next().is_none());
259
260 let expected = [22, 75];
261 let mut iter = expected.iter();
262 for i in matrix.iter(3) {
263 let j = *iter.next().unwrap();
264 assert_eq!(i, j);
265 }
266 assert!(iter.next().is_none());
267
268 let expected = [0];
269 let mut iter = expected.iter();
270 for i in matrix.iter(4) {
271 let j = *iter.next().unwrap();
272 assert_eq!(i, j);
273 }
274 assert!(iter.next().is_none());
275
276 let expected = [22, 75];
277 let mut iter = expected.iter();
278 for i in matrix.iter(5) {
279 let j = *iter.next().unwrap();
280 assert_eq!(i, j);
281 }
282 assert!(iter.next().is_none());
283 }
284
285 /// Merge dense hybrid set into empty sparse hybrid set.
286 #[bench]
union_hybrid_sparse_empty_to_dense(b: &mut Bencher)287 fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
288 let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
289 for i in 0..10 {
290 assert!(pre_dense.insert(i));
291 }
292 let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
293 b.iter(|| {
294 let dense = pre_dense.clone();
295 let mut sparse = pre_sparse.clone();
296 sparse.union(&dense);
297 })
298 }
299
300 /// Merge dense hybrid set into full hybrid set with same indices.
301 #[bench]
union_hybrid_sparse_full_to_dense(b: &mut Bencher)302 fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
303 let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
304 for i in 0..10 {
305 assert!(pre_dense.insert(i));
306 }
307 let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
308 for i in 0..SPARSE_MAX {
309 assert!(pre_sparse.insert(i));
310 }
311 b.iter(|| {
312 let dense = pre_dense.clone();
313 let mut sparse = pre_sparse.clone();
314 sparse.union(&dense);
315 })
316 }
317
318 /// Merge dense hybrid set into full hybrid set with indices over the whole domain.
319 #[bench]
union_hybrid_sparse_domain_to_dense(b: &mut Bencher)320 fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
321 let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
322 for i in 0..10 {
323 assert!(pre_dense.insert(i));
324 }
325 let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
326 for i in 0..SPARSE_MAX {
327 assert!(pre_sparse.insert(i * 64));
328 }
329 b.iter(|| {
330 let dense = pre_dense.clone();
331 let mut sparse = pre_sparse.clone();
332 sparse.union(&dense);
333 })
334 }
335
336 /// Merge dense hybrid set into empty hybrid set where the domain is very small.
337 #[bench]
union_hybrid_sparse_empty_small_domain(b: &mut Bencher)338 fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
339 let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
340 for i in 0..SPARSE_MAX {
341 assert!(pre_dense.insert(i));
342 }
343 let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
344 b.iter(|| {
345 let dense = pre_dense.clone();
346 let mut sparse = pre_sparse.clone();
347 sparse.union(&dense);
348 })
349 }
350
351 /// Merge dense hybrid set into full hybrid set where the domain is very small.
352 #[bench]
union_hybrid_sparse_full_small_domain(b: &mut Bencher)353 fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
354 let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
355 for i in 0..SPARSE_MAX {
356 assert!(pre_dense.insert(i));
357 }
358 let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
359 for i in 0..SPARSE_MAX {
360 assert!(pre_sparse.insert(i));
361 }
362 b.iter(|| {
363 let dense = pre_dense.clone();
364 let mut sparse = pre_sparse.clone();
365 sparse.union(&dense);
366 })
367 }
368
369 #[bench]
bench_insert(b: &mut Bencher)370 fn bench_insert(b: &mut Bencher) {
371 let mut bs = BitSet::new_filled(99999usize);
372 b.iter(|| {
373 black_box(bs.insert(black_box(100u32)));
374 });
375 }
376
377 #[bench]
bench_remove(b: &mut Bencher)378 fn bench_remove(b: &mut Bencher) {
379 let mut bs = BitSet::new_filled(99999usize);
380 b.iter(|| {
381 black_box(bs.remove(black_box(100u32)));
382 });
383 }
384
385 #[bench]
bench_iter(b: &mut Bencher)386 fn bench_iter(b: &mut Bencher) {
387 let bs = BitSet::new_filled(99999usize);
388 b.iter(|| {
389 bs.iter().map(|b: usize| black_box(b)).for_each(drop);
390 });
391 }
392
393 #[bench]
bench_intersect(b: &mut Bencher)394 fn bench_intersect(b: &mut Bencher) {
395 let mut ba: BitSet<u32> = BitSet::new_filled(99999usize);
396 let bb = BitSet::new_filled(99999usize);
397 b.iter(|| {
398 ba.intersect(black_box(&bb));
399 });
400 }
401