[go: up one dir, main page]

roaring 0.10.10

A better compressed bitset - pure Rust implementation
Documentation 
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));
    }
}