compacts-bits 0.2.1

succinct bit vector
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use ops::*;

macro_rules! impl_op {
    ( $op:ident, $fn_name:ident, $fn:ident ) => {
        impl $op<super::Vec64> for super::Vec64 {
            type Output = super::Vec64;
            fn $fn_name(self, that: super::Vec64) -> Self::Output {
                let mut this = self;
                this.$fn(&that);
                this
            }
        }
        impl<'r> $op<&'r super::Vec64> for super::Vec64 {
            type Output = super::Vec64;
            fn $fn_name(self, that: &super::Vec64) -> Self::Output {
                let mut this = self;
                this.$fn(that);
                this
            }
        }
        impl<'r1, 'r2> $op<&'r2 super::Vec64> for &'r1 super::Vec64 {
            type Output = super::Vec64;
            fn $fn_name(self, that: &super::Vec64) -> Self::Output {
                let mut this = self.clone();
                this.$fn(that);
                this
            }
        }
    }
}

impl_op!(Intersection, intersection, intersection_with);
impl_op!(Union, union, union_with);
impl_op!(Difference, difference, difference_with);
impl_op!(
    SymmetricDifference,
    symmetric_difference,
    symmetric_difference_with
);

impl<'r> IntersectionWith<&'r super::Vec64> for super::Vec64 {
    fn intersection_with(&mut self, that: &'r super::Vec64) {

        let keys_to_remove = {
            let mut keys = Vec::with_capacity(self.vec32s.len());
            for (key, vec) in &mut self.vec32s {
                if that.vec32s.contains_key(key) {
                    vec.intersection_with(&that.vec32s[key]);
                    if vec.count_ones() != 0 {
                        vec.optimize();
                    } else {
                        keys.push(*key);
                    }
                } else {
                    keys.push(*key);
                }
            }
            keys
        };

        for key in keys_to_remove {
            let removed = self.vec32s.remove(&key);
            debug_assert!(removed.is_some());
        }
    }
}

#[cfg_attr(feature = "cargo-clippy", allow(map_entry))]
impl<'r> UnionWith<&'r super::Vec64> for super::Vec64 {
    fn union_with(&mut self, that: &'r super::Vec64) {
        for (&key, vec) in &that.vec32s {
            if !self.vec32s.contains_key(&key) {
                self.vec32s.insert(key, vec.clone());
                continue;
            }
            let mut lb = self.vec32s[&key].clone();
            lb.union_with(vec);
            self.vec32s.insert(key, lb);
        }
    }
}

impl<'r> DifferenceWith<&'r super::Vec64> for super::Vec64 {
    fn difference_with(&mut self, that: &'r super::Vec64) {
        for (&key, vec) in &mut self.vec32s {
            if !that.vec32s.contains_key(&key) {
                continue;
            }
            let lb = vec.clone();
            let rb = &that.vec32s[&key];
            *vec = lb.difference(rb);
        }
    }
}

#[cfg_attr(feature = "cargo-clippy", allow(map_entry))]
impl<'r> SymmetricDifferenceWith<&'r super::Vec64> for super::Vec64 {
    fn symmetric_difference_with(&mut self, that: &'r super::Vec64) {
        for (&key, vec) in &that.vec32s {
            if !self.vec32s.contains_key(&key) {
                self.vec32s.insert(key, vec.clone());
                continue;
            }
            let mut b = self.vec32s[&key].clone();
            b.symmetric_difference_with(vec);
            self.vec32s.insert(key, b);
        }
    }
}