roaring/treemap/
cmp.rs

1use alloc::collections::btree_map;
2use core::iter::Peekable;
3
4use crate::RoaringBitmap;
5use crate::RoaringTreemap;
6
7pub(crate) struct Pairs<'a>(
8    Peekable<btree_map::Iter<'a, u32, RoaringBitmap>>,
9    Peekable<btree_map::Iter<'a, u32, RoaringBitmap>>,
10);
11
12impl RoaringTreemap {
13    pub(crate) fn pairs<'a>(&'a self, other: &'a RoaringTreemap) -> Pairs<'a> {
14        Pairs(self.map.iter().peekable(), other.map.iter().peekable())
15    }
16
17    /// Returns true if the set has no elements in common with other. This is equivalent to
18    /// checking for an empty intersection.
19    ///
20    /// # Examples
21    ///
22    /// ```rust
23    /// use roaring::RoaringTreemap;
24    ///
25    /// let mut rb1 = RoaringTreemap::new();
26    /// let mut rb2 = RoaringTreemap::new();
27    ///
28    /// rb1.insert(1);
29    ///
30    /// assert_eq!(rb1.is_disjoint(&rb2), true);
31    ///
32    /// rb2.insert(1);
33    ///
34    /// assert_eq!(rb1.is_disjoint(&rb2), false);
35    ///
36    /// ```
37    pub fn is_disjoint(&self, other: &Self) -> bool {
38        self.pairs(other)
39            .filter(|&(c1, c2)| c1.is_some() && c2.is_some())
40            .all(|(c1, c2)| c1.unwrap().is_disjoint(c2.unwrap()))
41    }
42
43    /// Returns `true` if this set is a subset of `other`.
44    ///
45    /// # Examples
46    ///
47    /// ```rust
48    /// use roaring::RoaringTreemap;
49    ///
50    /// let mut rb1 = RoaringTreemap::new();
51    /// let mut rb2 = RoaringTreemap::new();
52    ///
53    /// rb1.insert(1);
54    ///
55    /// assert_eq!(rb1.is_subset(&rb2), false);
56    ///
57    /// rb2.insert(1);
58    ///
59    /// assert_eq!(rb1.is_subset(&rb2), true);
60    ///
61    /// rb1.insert(2);
62    ///
63    /// assert_eq!(rb1.is_subset(&rb2), false);
64    /// ```
65    pub fn is_subset(&self, other: &Self) -> bool {
66        for pair in self.pairs(other) {
67            match pair {
68                (None, _) => (),
69                (_, None) => {
70                    return false;
71                }
72                (Some(c1), Some(c2)) => {
73                    if !c1.is_subset(c2) {
74                        return false;
75                    }
76                }
77            }
78        }
79        true
80    }
81
82    /// Returns `true` if this set is a superset of `other`.
83    ///
84    /// # Examples
85    ///
86    /// ```rust
87    /// use roaring::RoaringTreemap;
88    ///
89    /// let mut rb1 = RoaringTreemap::new();
90    /// let mut rb2 = RoaringTreemap::new();
91    ///
92    /// rb1.insert(1);
93    ///
94    /// assert_eq!(rb2.is_superset(&rb1), false);
95    ///
96    /// rb2.insert(1);
97    ///
98    /// assert_eq!(rb2.is_superset(&rb1), true);
99    ///
100    /// rb1.insert(2);
101    ///
102    /// assert_eq!(rb2.is_superset(&rb1), false);
103    /// ```
104    pub fn is_superset(&self, other: &Self) -> bool {
105        other.is_subset(self)
106    }
107}
108
109impl<'a> Iterator for Pairs<'a> {
110    type Item = (Option<&'a RoaringBitmap>, Option<&'a RoaringBitmap>);
111
112    fn next(&mut self) -> Option<Self::Item> {
113        enum Which {
114            Left,
115            Right,
116            Both,
117            None,
118        }
119        let which = match (self.0.peek(), self.1.peek()) {
120            (None, None) => Which::None,
121            (Some(_), None) => Which::Left,
122            (None, Some(_)) => Which::Right,
123            (Some(c1), Some(c2)) => match (c1.0, c2.0) {
124                (key1, key2) if key1 == key2 => Which::Both,
125                (key1, key2) if key1 < key2 => Which::Left,
126                (key1, key2) if key1 > key2 => Which::Right,
127                (_, _) => unreachable!(),
128            },
129        };
130        match which {
131            Which::Left => Some((self.0.next().map(|e| e.1), None)),
132            Which::Right => Some((None, self.1.next().map(|e| e.1))),
133            Which::Both => Some((self.0.next().map(|e| e.1), self.1.next().map(|e| e.1))),
134            Which::None => None,
135        }
136    }
137}
roaring/treemap/cmp.rs

roaring/treemap/
cmp.rs
