1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
use proptest::collection::hash_set;
use proptest::prelude::*;
use roaring::RoaringBitmap;
#[test]
fn u32_max() {
let mut bitmap = RoaringBitmap::new();
bitmap.insert(u32::MAX);
assert!(bitmap.contains_range(u32::MAX..=u32::MAX));
assert!(!bitmap.contains_range(u32::MAX - 1..=u32::MAX));
bitmap.insert_range(4_000_000_000..);
assert!(bitmap.contains_range(4_000_000_000..));
assert!(bitmap.contains_range(4_000_000_000..u32::MAX));
assert!(bitmap.contains_range(4_000_000_000..=u32::MAX));
assert!(bitmap.contains_range(4_100_000_000..=u32::MAX));
}
proptest! {
#[test]
fn proptest_range(
start in ..=262_143_u32,
len in ..=262_143_u32,
extra in hash_set(..=462_143_u32, ..=100),
){
let end = start + len;
let range = start..end;
let inverse_empty_range = (start+len)..start;
let mut bitmap = RoaringBitmap::new();
bitmap.insert_range(range.clone());
assert!(bitmap.contains_range(range.clone()));
assert!(bitmap.contains_range(inverse_empty_range.clone()));
assert_eq!(bitmap.range_cardinality(range.clone()) as usize, range.len());
for &val in &extra {
bitmap.insert(val);
assert!(bitmap.contains_range(range.clone()));
assert!(bitmap.contains_range(inverse_empty_range.clone()));
assert_eq!(bitmap.range_cardinality(range.clone()) as usize, range.len());
}
for (i, &val) in extra.iter().filter(|x| range.contains(x)).enumerate() {
bitmap.remove(val);
assert!(!bitmap.contains_range(range.clone()));
assert!(bitmap.contains_range(inverse_empty_range.clone()));
assert_eq!(bitmap.range_cardinality(range.clone()) as usize, range.len() - i - 1);
}
}
#[test]
fn proptest_range_boundaries(
// Ensure we can always subtract one from start
start in 1..=262_143_u32,
len in 0..=262_143_u32,
) {
let mut bitmap = RoaringBitmap::new();
let end = start + len;
let half = start + len / 2;
bitmap.insert_range(start..end);
assert!(bitmap.contains_range(start..end));
assert!(bitmap.contains_range(start+1..end));
assert!(bitmap.contains_range(start..end - 1));
assert!(bitmap.contains_range(start+1..end - 1));
assert!(!bitmap.contains_range(start - 1..end));
assert!(!bitmap.contains_range(start - 1..end - 1));
assert!(!bitmap.contains_range(start..end + 1));
assert!(!bitmap.contains_range(start + 1..end + 1));
assert!(!bitmap.contains_range(start - 1..end + 1));
assert!(!bitmap.contains_range(start - 1..half));
assert!(!bitmap.contains_range(half..end + 1));
}
}
|
