]>
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)); |
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 | ||
5e7ed085 FG |
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 | ||
923072b8 FG |
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 | ||
04454e1e FG |
381 | #[test] |
382 | fn chunked_bitset_iter() { | |
923072b8 FG |
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); | |
04454e1e | 389 | } |
923072b8 FG |
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); | |
04454e1e FG |
397 | } |
398 | ||
399 | // Empty | |
400 | let vec: Vec<usize> = Vec::new(); | |
923072b8 FG |
401 | let bit = with_elements_chunked(&vec, 9000); |
402 | check_iter(&bit, &vec); | |
04454e1e FG |
403 | |
404 | // Filled | |
405 | let n = 10000; | |
406 | let vec: Vec<usize> = (0..n).collect(); | |
923072b8 FG |
407 | let bit = with_elements_chunked(&vec, n); |
408 | check_iter(&bit, &vec); | |
04454e1e FG |
409 | |
410 | // Filled with trailing zeros | |
411 | let n = 10000; | |
412 | let vec: Vec<usize> = (0..n).collect(); | |
923072b8 FG |
413 | let bit = with_elements_chunked(&vec, 2 * n); |
414 | check_iter(&bit, &vec); | |
04454e1e FG |
415 | |
416 | // Mixed | |
417 | let n = 12345; | |
418 | let vec: Vec<usize> = vec![0, 1, 2, 2010, 2047, 2099, 6000, 6002, 6004]; | |
923072b8 FG |
419 | let bit = with_elements_chunked(&vec, n); |
420 | check_iter(&bit, &vec); | |
04454e1e FG |
421 | } |
422 | ||
416331ca XL |
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 | ||
94222f64 XL |
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 | ||
3c0e092e XL |
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 | ||
416331ca XL |
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) { | |
dfeec247 | 777 | let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64); |
416331ca XL |
778 | for i in 0..10 { |
779 | assert!(pre_dense.insert(i)); | |
780 | } | |
dfeec247 | 781 | let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64); |
416331ca | 782 | for i in 0..SPARSE_MAX { |
dfeec247 | 783 | assert!(pre_sparse.insert(i * 64)); |
416331ca XL |
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 | } | |
5869c6ff XL |
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 | } |