roaring/bitmap/
cmp.rs

1use core::borrow::Borrow;
2use core::cmp::Ordering;
3use core::iter::Peekable;
4
5use super::container::Container;
6use crate::RoaringBitmap;
7
8impl RoaringBitmap {
9    /// Returns true if the set has no elements in common with other. This is equivalent to
10    /// checking for an empty intersection.
11    ///
12    /// # Examples
13    ///
14    /// ```rust
15    /// use roaring::RoaringBitmap;
16    ///
17    /// let mut rb1 = RoaringBitmap::new();
18    /// let mut rb2 = RoaringBitmap::new();
19    ///
20    /// rb1.insert(1);
21    ///
22    /// assert_eq!(rb1.is_disjoint(&rb2), true);
23    ///
24    /// rb2.insert(1);
25    ///
26    /// assert_eq!(rb1.is_disjoint(&rb2), false);
27    ///
28    /// ```
29    pub fn is_disjoint(&self, other: &Self) -> bool {
30        Pairs::new(&self.containers, &other.containers)
31            .filter_map(|(c1, c2)| c1.zip(c2))
32            .all(|(c1, c2)| c1.is_disjoint(c2))
33    }
34
35    /// Returns `true` if this set is a subset of `other`.
36    ///
37    /// # Examples
38    ///
39    /// ```rust
40    /// use roaring::RoaringBitmap;
41    ///
42    /// let mut rb1 = RoaringBitmap::new();
43    /// let mut rb2 = RoaringBitmap::new();
44    ///
45    /// rb1.insert(1);
46    ///
47    /// assert_eq!(rb1.is_subset(&rb2), false);
48    ///
49    /// rb2.insert(1);
50    ///
51    /// assert_eq!(rb1.is_subset(&rb2), true);
52    ///
53    /// rb1.insert(2);
54    ///
55    /// assert_eq!(rb1.is_subset(&rb2), false);
56    /// ```
57    pub fn is_subset(&self, other: &Self) -> bool {
58        for pair in Pairs::new(&self.containers, &other.containers) {
59            match pair {
60                (None, _) => (),
61                (_, None) => return false,
62                (Some(c1), Some(c2)) => {
63                    if !c1.is_subset(c2) {
64                        return false;
65                    }
66                }
67            }
68        }
69        true
70    }
71
72    /// Returns `true` if this set is a superset of `other`.
73    ///
74    /// # Examples
75    ///
76    /// ```rust
77    /// use roaring::RoaringBitmap;
78    ///
79    /// let mut rb1 = RoaringBitmap::new();
80    /// let mut rb2 = RoaringBitmap::new();
81    ///
82    /// rb1.insert(1);
83    ///
84    /// assert_eq!(rb2.is_superset(&rb1), false);
85    ///
86    /// rb2.insert(1);
87    ///
88    /// assert_eq!(rb2.is_superset(&rb1), true);
89    ///
90    /// rb1.insert(2);
91    ///
92    /// assert_eq!(rb2.is_superset(&rb1), false);
93    /// ```
94    pub fn is_superset(&self, other: &Self) -> bool {
95        other.is_subset(self)
96    }
97}
98
99/// An helping Iterator over pairs of containers.
100///
101/// Returns the smallest container according to its key
102/// or both if the key is the same. It is useful when you need
103/// to iterate over two containers to do operations on them.
104pub(crate) struct Pairs<I, J, L, R>
105where
106    I: Iterator<Item = L>,
107    J: Iterator<Item = R>,
108    L: Borrow<Container>,
109    R: Borrow<Container>,
110{
111    left: Peekable<I>,
112    right: Peekable<J>,
113}
114
115impl<I, J, L, R> Pairs<I, J, L, R>
116where
117    I: Iterator<Item = L>,
118    J: Iterator<Item = R>,
119    L: Borrow<Container>,
120    R: Borrow<Container>,
121{
122    pub fn new<A, B>(left: A, right: B) -> Pairs<I, J, L, R>
123    where
124        A: IntoIterator<Item = L, IntoIter = I>,
125        B: IntoIterator<Item = R, IntoIter = J>,
126    {
127        Pairs { left: left.into_iter().peekable(), right: right.into_iter().peekable() }
128    }
129}
130
131impl<I, J, L, R> Iterator for Pairs<I, J, L, R>
132where
133    I: Iterator<Item = L>,
134    J: Iterator<Item = R>,
135    L: Borrow<Container>,
136    R: Borrow<Container>,
137{
138    type Item = (Option<L>, Option<R>);
139
140    fn next(&mut self) -> Option<Self::Item> {
141        match (self.left.peek(), self.right.peek()) {
142            (None, None) => None,
143            (Some(_), None) => Some((self.left.next(), None)),
144            (None, Some(_)) => Some((None, self.right.next())),
145            (Some(c1), Some(c2)) => match c1.borrow().key.cmp(&c2.borrow().key) {
146                Ordering::Equal => Some((self.left.next(), self.right.next())),
147                Ordering::Less => Some((self.left.next(), None)),
148                Ordering::Greater => Some((None, self.right.next())),
149            },
150        }
151    }
152}
roaring/bitmap/cmp.rs

roaring/bitmap/
cmp.rs
