nodedb_types/surrogate_bitmap/
ops.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Set operations on [`SurrogateBitmap`].
4//!
5//! All operations are pure roaring bitmap delegations. Consuming variants
6//! are provided for the hot in-place paths; cloning variants exist for
7//! the few planner paths that must produce a new bitmap without mutating
8//! an existing one.
9
10use super::bitmap::SurrogateBitmap;
11
12impl SurrogateBitmap {
13    /// Return the intersection of `self` and `other` as a new bitmap.
14    pub fn intersect(&self, other: &Self) -> Self {
15        Self(&self.0 & &other.0)
16    }
17
18    /// Return the union of `self` and `other` as a new bitmap.
19    pub fn union(&self, other: &Self) -> Self {
20        Self(&self.0 | &other.0)
21    }
22
23    /// Return the set difference `self \ other` as a new bitmap.
24    pub fn difference(&self, other: &Self) -> Self {
25        Self(&self.0 - &other.0)
26    }
27
28    /// Return `true` if every element of `self` is also in `other`.
29    pub fn is_subset_of(&self, other: &Self) -> bool {
30        self.0.is_subset(&other.0)
31    }
32
33    /// Mutate `self` in place to hold only elements also in `other`.
34    pub fn intersect_in_place(&mut self, other: &Self) {
35        self.0 &= &other.0;
36    }
37
38    /// Mutate `self` in place to hold the union with `other`.
39    pub fn union_in_place(&mut self, other: &Self) {
40        self.0 |= &other.0;
41    }
42}
43
44#[cfg(test)]
45mod tests {
46    use crate::surrogate::Surrogate;
47    use crate::surrogate_bitmap::SurrogateBitmap;
48
49    fn bmp(vals: &[u32]) -> SurrogateBitmap {
50        SurrogateBitmap::from_iter(vals.iter().copied().map(Surrogate))
51    }
52
53    #[test]
54    fn intersect_returns_common_elements() {
55        let a = bmp(&[1, 2, 3, 4]);
56        let b = bmp(&[3, 4, 5, 6]);
57        let c = a.intersect(&b);
58        assert_eq!(c.len(), 2);
59        assert!(c.contains(Surrogate(3)));
60        assert!(c.contains(Surrogate(4)));
61        assert!(!c.contains(Surrogate(1)));
62    }
63
64    #[test]
65    fn union_contains_all_elements() {
66        let a = bmp(&[1, 2]);
67        let b = bmp(&[2, 3]);
68        let c = a.union(&b);
69        assert_eq!(c.len(), 3);
70        for v in [1u32, 2, 3] {
71            assert!(c.contains(Surrogate(v)));
72        }
73    }
74
75    #[test]
76    fn difference_removes_other_elements() {
77        let a = bmp(&[1, 2, 3]);
78        let b = bmp(&[2, 3]);
79        let c = a.difference(&b);
80        assert_eq!(c.len(), 1);
81        assert!(c.contains(Surrogate(1)));
82        assert!(!c.contains(Surrogate(2)));
83    }
84
85    #[test]
86    fn is_subset_of() {
87        let a = bmp(&[1, 2]);
88        let b = bmp(&[1, 2, 3]);
89        assert!(a.is_subset_of(&b));
90        assert!(!b.is_subset_of(&a));
91    }
92
93    #[test]
94    fn intersect_in_place_mutates() {
95        let mut a = bmp(&[1, 2, 3]);
96        let b = bmp(&[2, 3, 4]);
97        a.intersect_in_place(&b);
98        assert_eq!(a.len(), 2);
99        assert!(a.contains(Surrogate(2)));
100        assert!(a.contains(Surrogate(3)));
101    }
102
103    #[test]
104    fn union_in_place_mutates() {
105        let mut a = bmp(&[1, 2]);
106        let b = bmp(&[3, 4]);
107        a.union_in_place(&b);
108        assert_eq!(a.len(), 4);
109    }
110}
nodedb_types/surrogate_bitmap/ops.rs

nodedb_types/surrogate_bitmap/
ops.rs
