/rust/registry/src/index.crates.io-1949cf8c6b5b557f/roaring-0.11.3/src/treemap/ops.rs

Source
use alloc::collections::btree_map::Entry;
use core::mem;
use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Sub, SubAssign};

use crate::RoaringTreemap;

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

impl RoaringTreemap {
    /// Computes the len of the union with the specified other treemap without creating a new
    /// treemap.
    ///
    /// This is faster and more space efficient when you're only interested in the cardinality of
    /// the union.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    ///
    /// let rb1: RoaringTreemap = (1..4).collect();
    /// let rb2: RoaringTreemap = (3..5).collect();
    ///
    ///
    /// assert_eq!(rb1.union_len(&rb2), (rb1 | rb2).len());
    /// ```
    pub fn union_len(&self, other: &RoaringTreemap) -> u64 {
        self.len().wrapping_add(other.len()).wrapping_sub(self.intersection_len(other))
    }

    /// Computes the len of the intersection with the specified other treemap without creating a
    /// new treemap.
    ///
    /// This is faster and more space efficient when you're only interested in the cardinality of
    /// the intersection.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    ///
    /// let rb1: RoaringTreemap = (1..4).collect();
    /// let rb2: RoaringTreemap = (3..5).collect();
    ///
    ///
    /// assert_eq!(rb1.intersection_len(&rb2), (rb1 & rb2).len());
    /// ```
    pub fn intersection_len(&self, other: &RoaringTreemap) -> u64 {
        self.pairs(other)
            .map(|pair| match pair {
                (Some(..), None) => 0,
                (None, Some(..)) => 0,
                (Some(lhs), Some(rhs)) => lhs.intersection_len(rhs),
                (None, None) => 0,
            })
            .sum()
    }

    /// Computes the len of the difference with the specified other treemap without creating a new
    /// treemap.
    ///
    /// This is faster and more space efficient when you're only interested in the cardinality of
    /// the difference.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    ///
    /// let rb1: RoaringTreemap = (1..4).collect();
    /// let rb2: RoaringTreemap = (3..5).collect();
    ///
    ///
    /// assert_eq!(rb1.difference_len(&rb2), (rb1 - rb2).len());
    /// ```
    pub fn difference_len(&self, other: &RoaringTreemap) -> u64 {
        self.len() - self.intersection_len(other)
    }

    /// Computes the len of the symmetric difference with the specified other treemap without
    /// creating a new bitmap.
    ///
    /// This is faster and more space efficient when you're only interested in the cardinality of
    /// the symmetric difference.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    ///
    /// let rb1: RoaringTreemap = (1..4).collect();
    /// let rb2: RoaringTreemap = (3..5).collect();
    ///
    ///
    /// assert_eq!(rb1.symmetric_difference_len(&rb2), (rb1 ^ rb2).len());
    /// ```
    pub fn symmetric_difference_len(&self, other: &RoaringTreemap) -> u64 {
        let intersection_len = self.intersection_len(other);

        self.len()
            .wrapping_add(other.len())
            .wrapping_sub(intersection_len)
            .wrapping_sub(intersection_len)
    }
}

impl BitOr<RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `union` between two sets.
    fn bitor(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
        BitOrAssign::bitor_assign(&mut self, rhs);
        self
    }
}

impl BitOr<&RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `union` between two sets.
    fn bitor(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
        BitOrAssign::bitor_assign(&mut self, rhs);
        self
    }
}

impl BitOr<RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `union` between two sets.
    fn bitor(self, rhs: RoaringTreemap) -> RoaringTreemap {
        BitOr::bitor(rhs, self)
    }
}

impl BitOr<&RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `union` between two sets.
    fn bitor(self, rhs: &RoaringTreemap) -> RoaringTreemap {
        if self.len() <= rhs.len() {
            BitOr::bitor(rhs.clone(), self)
        } else {
            BitOr::bitor(self.clone(), rhs)
        }
    }
}

impl BitOrAssign<RoaringTreemap> for RoaringTreemap {
    /// An `union` between two sets.
    fn bitor_assign(&mut self, mut rhs: RoaringTreemap) {
        // We make sure that we apply the union operation on the biggest map.
        if self.len() < rhs.len() {
            mem::swap(self, &mut rhs);
        }

        for (key, other_rb) in rhs.map {
            match self.map.entry(key) {
                Entry::Vacant(ent) => {
                    ent.insert(other_rb);
                }
                Entry::Occupied(mut ent) => {
                    BitOrAssign::bitor_assign(ent.get_mut(), other_rb);
                }
            }
        }
    }
}

impl BitOrAssign<&RoaringTreemap> for RoaringTreemap {
    /// An `union` between two sets.
    fn bitor_assign(&mut self, rhs: &RoaringTreemap) {
        for (key, other_rb) in &rhs.map {
            match self.map.entry(*key) {
                Entry::Vacant(ent) => {
                    ent.insert(other_rb.clone());
                }
                Entry::Occupied(mut ent) => {
                    BitOrAssign::bitor_assign(ent.get_mut(), other_rb);
                }
            }
        }
    }
}

impl BitAnd<RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `intersection` between two sets.
    fn bitand(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
        BitAndAssign::bitand_assign(&mut self, rhs);
        self
    }
}

impl BitAnd<&RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `intersection` between two sets.
    fn bitand(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
        BitAndAssign::bitand_assign(&mut self, rhs);
        self
    }
}

impl BitAnd<RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `intersection` between two sets.
    fn bitand(self, rhs: RoaringTreemap) -> RoaringTreemap {
        BitAnd::bitand(rhs, self)
    }
}

impl BitAnd<&RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// An `intersection` between two sets.
    fn bitand(self, rhs: &RoaringTreemap) -> RoaringTreemap {
        if rhs.len() < self.len() {
            BitAnd::bitand(self.clone(), rhs)
        } else {
            BitAnd::bitand(rhs.clone(), self)
        }
    }
}

impl BitAndAssign<RoaringTreemap> for RoaringTreemap {
    /// An `intersection` between two sets.
    fn bitand_assign(&mut self, mut rhs: RoaringTreemap) {
        // We make sure that we apply the intersection operation on the smallest map.
        if rhs.len() < self.len() {
            mem::swap(self, &mut rhs);
        }

        BitAndAssign::bitand_assign(self, &rhs)
    }
}

impl BitAndAssign<&RoaringTreemap> for RoaringTreemap {
    /// An `intersection` between two sets.
    fn bitand_assign(&mut self, rhs: &RoaringTreemap) {
        let mut keys_to_remove: Vec<u32> = Vec::new();
        for (key, self_rb) in &mut self.map {
            match rhs.map.get(key) {
                Some(other_rb) => {
                    BitAndAssign::bitand_assign(self_rb, other_rb);
                    if self_rb.is_empty() {
                        keys_to_remove.push(*key);
                    }
                }
                None => keys_to_remove.push(*key),
            }
        }

        for key in keys_to_remove {
            self.map.remove(&key);
        }
    }
}

impl Sub<RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `difference` between two sets.
    fn sub(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
        SubAssign::sub_assign(&mut self, rhs);
        self
    }
}

impl Sub<&RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `difference` between two sets.
    fn sub(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
        SubAssign::sub_assign(&mut self, rhs);
        self
    }
}

impl Sub<RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `difference` between two sets.
    fn sub(self, rhs: RoaringTreemap) -> RoaringTreemap {
        Sub::sub(self.clone(), rhs)
    }
}

impl Sub<&RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `difference` between two sets.
    fn sub(self, rhs: &RoaringTreemap) -> RoaringTreemap {
        Sub::sub(self.clone(), rhs)
    }
}

impl SubAssign<RoaringTreemap> for RoaringTreemap {
    /// A `difference` between two sets.
    fn sub_assign(&mut self, rhs: RoaringTreemap) {
        SubAssign::sub_assign(self, &rhs)
    }
}

impl SubAssign<&RoaringTreemap> for RoaringTreemap {
    /// A `difference` between two sets.
    fn sub_assign(&mut self, rhs: &RoaringTreemap) {
        for (key, rhs_rb) in &rhs.map {
            match self.map.entry(*key) {
                Entry::Vacant(_entry) => (),
                Entry::Occupied(mut entry) => {
                    SubAssign::sub_assign(entry.get_mut(), rhs_rb);
                    if entry.get().is_empty() {
                        entry.remove_entry();
                    }
                }
            }
        }
    }
}

impl BitXor<RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `symmetric difference` between two sets.
    fn bitxor(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
        BitXorAssign::bitxor_assign(&mut self, rhs);
        self
    }
}

impl BitXor<&RoaringTreemap> for RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `symmetric difference` between two sets.
    fn bitxor(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
        BitXorAssign::bitxor_assign(&mut self, rhs);
        self
    }
}

impl BitXor<RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `symmetric difference` between two sets.
    fn bitxor(self, rhs: RoaringTreemap) -> RoaringTreemap {
        BitXor::bitxor(rhs, self)
    }
}

impl BitXor<&RoaringTreemap> for &RoaringTreemap {
    type Output = RoaringTreemap;

    /// A `symmetric difference` between two sets.
    fn bitxor(self, rhs: &RoaringTreemap) -> RoaringTreemap {
        if self.len() < rhs.len() {
            BitXor::bitxor(self, rhs.clone())
        } else {
            BitXor::bitxor(self.clone(), rhs)
        }
    }
}

impl BitXorAssign<RoaringTreemap> for RoaringTreemap {
    /// A `symmetric difference` between two sets.
    fn bitxor_assign(&mut self, rhs: RoaringTreemap) {
        for (key, other_rb) in rhs.map {
            match self.map.entry(key) {
                Entry::Vacant(entry) => {
                    entry.insert(other_rb);
                }
                Entry::Occupied(mut entry) => {
                    BitXorAssign::bitxor_assign(entry.get_mut(), other_rb);
                    if entry.get().is_empty() {
                        entry.remove_entry();
                    }
                }
            }
        }
    }
}

impl BitXorAssign<&RoaringTreemap> for RoaringTreemap {
    /// A `symmetric difference` between two sets.
    fn bitxor_assign(&mut self, rhs: &RoaringTreemap) {
        for (key, other_rb) in &rhs.map {
            match self.map.entry(*key) {
                Entry::Vacant(entry) => {
                    entry.insert(other_rb.clone());
                }
                Entry::Occupied(mut entry) => {
                    BitXorAssign::bitxor_assign(entry.get_mut(), other_rb);
                    if entry.get().is_empty() {
                        entry.remove_entry();
                    }
                }
            }
        }
    }
}

#[cfg(test)]
mod test {
    use crate::{MultiOps, RoaringTreemap};
    use proptest::prelude::*;

    // fast count tests
    proptest! {
        #[test]
        fn union_len_eq_len_of_materialized_union(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary()
        ) {
            prop_assert_eq!(a.union_len(&b), (a | b).len());
        }

        #[test]
        fn intersection_len_eq_len_of_materialized_intersection(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary()
        ) {
            prop_assert_eq!(a.intersection_len(&b), (a & b).len());
        }

        #[test]
        fn difference_len_eq_len_of_materialized_difference(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary()
        ) {
            prop_assert_eq!(a.difference_len(&b), (a - b).len());
        }

        #[test]
        fn symmetric_difference_len_eq_len_of_materialized_symmetric_difference(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary()
        ) {
            prop_assert_eq!(a.symmetric_difference_len(&b), (a ^ b).len());
        }

        #[test]
        fn all_union_give_the_same_result(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary(),
            c in RoaringTreemap::arbitrary()
        ) {
            let mut ref_assign = a.clone();
            ref_assign |= &b;
            ref_assign |= &c;

            let mut own_assign = a.clone();
            own_assign |= b.clone();
            own_assign |= c.clone();

            let ref_inline = &a | &b | &c;
            let own_inline = a.clone() | b.clone() | c.clone();

            let ref_multiop = [&a, &b, &c].union();
            let own_multiop = [a, b.clone(), c.clone()].union();

            for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
                prop_assert_eq!(&ref_assign, roar);
            }
        }

        #[test]
        fn all_intersection_give_the_same_result(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary(),
            c in RoaringTreemap::arbitrary()
        ) {
            let mut ref_assign = a.clone();
            ref_assign &= &b;
            ref_assign &= &c;

            let mut own_assign = a.clone();
            own_assign &= b.clone();
            own_assign &= c.clone();

            let ref_inline = &a & &b & &c;
            let own_inline = a.clone() & b.clone() & c.clone();

            let ref_multiop = [&a, &b, &c].intersection();
            let own_multiop = [a, b.clone(), c.clone()].intersection();

            for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
                prop_assert_eq!(&ref_assign, roar);
            }
        }

        #[test]
        fn all_difference_give_the_same_result(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary(),
            c in RoaringTreemap::arbitrary()
        ) {
            let mut ref_assign = a.clone();
            ref_assign -= &b;
            ref_assign -= &c;

            let mut own_assign = a.clone();
            own_assign -= b.clone();
            own_assign -= c.clone();

            let ref_inline = &a - &b - &c;
            let own_inline = a.clone() - b.clone() - c.clone();

            let ref_multiop = [&a, &b, &c].difference();
            let own_multiop = [a, b.clone(), c.clone()].difference();

            for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
                prop_assert_eq!(&ref_assign, roar);
            }
        }

        #[test]
        fn all_symmetric_difference_give_the_same_result(
            a in RoaringTreemap::arbitrary(),
            b in RoaringTreemap::arbitrary(),
            c in RoaringTreemap::arbitrary()
        ) {
            let mut ref_assign = a.clone();
            ref_assign ^= &b;
            ref_assign ^= &c;

            let mut own_assign = a.clone();
            own_assign ^= b.clone();
            own_assign ^= c.clone();

            let ref_inline = &a ^ &b ^ &c;
            let own_inline = a.clone() ^ b.clone() ^ c.clone();

            let ref_multiop = [&a, &b, &c].symmetric_difference();
            let own_multiop = [a, b.clone(), c.clone()].symmetric_difference();

            for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
                prop_assert_eq!(&ref_assign, roar);
            }
        }
    }
}

Coverage Report

Created: 2026-03-31 07:09

Line	Count	Source
1		use alloc::collections::btree_map::Entry;
2		use core::mem;
3		use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Sub, SubAssign};
4
5		use crate::RoaringTreemap;
6
7		#[cfg(not(feature = "std"))]
8		use alloc::vec::Vec;
9
10		impl RoaringTreemap {
11		/// Computes the len of the union with the specified other treemap without creating a new
12		/// treemap.
13		///
14		/// This is faster and more space efficient when you're only interested in the cardinality of
15		/// the union.
16		///
17		/// # Examples
18		///
19		/// ```rust
20		/// use roaring::RoaringTreemap;
21		///
22		/// let rb1: RoaringTreemap = (1..4).collect();
23		/// let rb2: RoaringTreemap = (3..5).collect();
24		///
25		///
26		/// assert_eq!(rb1.union_len(&rb2), (rb1 \| rb2).len());
27		/// ```
28	0	pub fn union_len(&self, other: &RoaringTreemap) -> u64 {
29	0	self.len().wrapping_add(other.len()).wrapping_sub(self.intersection_len(other))
30	0	}
31
32		/// Computes the len of the intersection with the specified other treemap without creating a
33		/// new treemap.
34		///
35		/// This is faster and more space efficient when you're only interested in the cardinality of
36		/// the intersection.
37		///
38		/// # Examples
39		///
40		/// ```rust
41		/// use roaring::RoaringTreemap;
42		///
43		/// let rb1: RoaringTreemap = (1..4).collect();
44		/// let rb2: RoaringTreemap = (3..5).collect();
45		///
46		///
47		/// assert_eq!(rb1.intersection_len(&rb2), (rb1 & rb2).len());
48		/// ```
49	0	pub fn intersection_len(&self, other: &RoaringTreemap) -> u64 {
50	0	self.pairs(other)
51	0	.map(\|pair\| match pair {
52	0	(Some(..), None) => 0,
53	0	(None, Some(..)) => 0,
54	0	(Some(lhs), Some(rhs)) => lhs.intersection_len(rhs),
55	0	(None, None) => 0,
56	0	})
57	0	.sum()
58	0	}
59
60		/// Computes the len of the difference with the specified other treemap without creating a new
61		/// treemap.
62		///
63		/// This is faster and more space efficient when you're only interested in the cardinality of
64		/// the difference.
65		///
66		/// # Examples
67		///
68		/// ```rust
69		/// use roaring::RoaringTreemap;
70		///
71		/// let rb1: RoaringTreemap = (1..4).collect();
72		/// let rb2: RoaringTreemap = (3..5).collect();
73		///
74		///
75		/// assert_eq!(rb1.difference_len(&rb2), (rb1 - rb2).len());
76		/// ```
77	0	pub fn difference_len(&self, other: &RoaringTreemap) -> u64 {
78	0	self.len() - self.intersection_len(other)
79	0	}
80
81		/// Computes the len of the symmetric difference with the specified other treemap without
82		/// creating a new bitmap.
83		///
84		/// This is faster and more space efficient when you're only interested in the cardinality of
85		/// the symmetric difference.
86		///
87		/// # Examples
88		///
89		/// ```rust
90		/// use roaring::RoaringTreemap;
91		///
92		/// let rb1: RoaringTreemap = (1..4).collect();
93		/// let rb2: RoaringTreemap = (3..5).collect();
94		///
95		///
96		/// assert_eq!(rb1.symmetric_difference_len(&rb2), (rb1 ^ rb2).len());
97		/// ```
98	0	pub fn symmetric_difference_len(&self, other: &RoaringTreemap) -> u64 {
99	0	let intersection_len = self.intersection_len(other);
100
101	0	self.len()
102	0	.wrapping_add(other.len())
103	0	.wrapping_sub(intersection_len)
104	0	.wrapping_sub(intersection_len)
105	0	}
106		}
107
108		impl BitOr<RoaringTreemap> for RoaringTreemap {
109		type Output = RoaringTreemap;
110
111		/// An `union` between two sets.
112	0	fn bitor(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
113	0	BitOrAssign::bitor_assign(&mut self, rhs);
114	0	self
115	0	}
116		}
117
118		impl BitOr<&RoaringTreemap> for RoaringTreemap {
119		type Output = RoaringTreemap;
120
121		/// An `union` between two sets.
122	0	fn bitor(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
123	0	BitOrAssign::bitor_assign(&mut self, rhs);
124	0	self
125	0	}
126		}
127
128		impl BitOr<RoaringTreemap> for &RoaringTreemap {
129		type Output = RoaringTreemap;
130
131		/// An `union` between two sets.
132	0	fn bitor(self, rhs: RoaringTreemap) -> RoaringTreemap {
133	0	BitOr::bitor(rhs, self)
134	0	}
135		}
136
137		impl BitOr<&RoaringTreemap> for &RoaringTreemap {
138		type Output = RoaringTreemap;
139
140		/// An `union` between two sets.
141	0	fn bitor(self, rhs: &RoaringTreemap) -> RoaringTreemap {
142	0	if self.len() <= rhs.len() {
143	0	BitOr::bitor(rhs.clone(), self)
144		} else {
145	0	BitOr::bitor(self.clone(), rhs)
146		}
147	0	}
148		}
149
150		impl BitOrAssign<RoaringTreemap> for RoaringTreemap {
151		/// An `union` between two sets.
152	0	fn bitor_assign(&mut self, mut rhs: RoaringTreemap) {
153		// We make sure that we apply the union operation on the biggest map.
154	0	if self.len() < rhs.len() {
155	0	mem::swap(self, &mut rhs);
156	0	}
157
158	0	for (key, other_rb) in rhs.map {
159	0	match self.map.entry(key) {
160	0	Entry::Vacant(ent) => {
161	0	ent.insert(other_rb);
162	0	}
163	0	Entry::Occupied(mut ent) => {
164	0	BitOrAssign::bitor_assign(ent.get_mut(), other_rb);
165	0	}
166		}
167		}
168	0	}
169		}
170
171		impl BitOrAssign<&RoaringTreemap> for RoaringTreemap {
172		/// An `union` between two sets.
173	0	fn bitor_assign(&mut self, rhs: &RoaringTreemap) {
174	0	for (key, other_rb) in &rhs.map {
175	0	match self.map.entry(*key) {
176	0	Entry::Vacant(ent) => {
177	0	ent.insert(other_rb.clone());
178	0	}
179	0	Entry::Occupied(mut ent) => {
180	0	BitOrAssign::bitor_assign(ent.get_mut(), other_rb);
181	0	}
182		}
183		}
184	0	}
185		}
186
187		impl BitAnd<RoaringTreemap> for RoaringTreemap {
188		type Output = RoaringTreemap;
189
190		/// An `intersection` between two sets.
191	0	fn bitand(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
192	0	BitAndAssign::bitand_assign(&mut self, rhs);
193	0	self
194	0	}
195		}
196
197		impl BitAnd<&RoaringTreemap> for RoaringTreemap {
198		type Output = RoaringTreemap;
199
200		/// An `intersection` between two sets.
201	0	fn bitand(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
202	0	BitAndAssign::bitand_assign(&mut self, rhs);
203	0	self
204	0	}
205		}
206
207		impl BitAnd<RoaringTreemap> for &RoaringTreemap {
208		type Output = RoaringTreemap;
209
210		/// An `intersection` between two sets.
211	0	fn bitand(self, rhs: RoaringTreemap) -> RoaringTreemap {
212	0	BitAnd::bitand(rhs, self)
213	0	}
214		}
215
216		impl BitAnd<&RoaringTreemap> for &RoaringTreemap {
217		type Output = RoaringTreemap;
218
219		/// An `intersection` between two sets.
220	0	fn bitand(self, rhs: &RoaringTreemap) -> RoaringTreemap {
221	0	if rhs.len() < self.len() {
222	0	BitAnd::bitand(self.clone(), rhs)
223		} else {
224	0	BitAnd::bitand(rhs.clone(), self)
225		}
226	0	}
227		}
228
229		impl BitAndAssign<RoaringTreemap> for RoaringTreemap {
230		/// An `intersection` between two sets.
231	0	fn bitand_assign(&mut self, mut rhs: RoaringTreemap) {
232		// We make sure that we apply the intersection operation on the smallest map.
233	0	if rhs.len() < self.len() {
234	0	mem::swap(self, &mut rhs);
235	0	}
236
237	0	BitAndAssign::bitand_assign(self, &rhs)
238	0	}
239		}
240
241		impl BitAndAssign<&RoaringTreemap> for RoaringTreemap {
242		/// An `intersection` between two sets.
243	0	fn bitand_assign(&mut self, rhs: &RoaringTreemap) {
244	0	let mut keys_to_remove: Vec<u32> = Vec::new();
245	0	for (key, self_rb) in &mut self.map {
246	0	match rhs.map.get(key) {
247	0	Some(other_rb) => {
248	0	BitAndAssign::bitand_assign(self_rb, other_rb);
249	0	if self_rb.is_empty() {
250	0	keys_to_remove.push(*key);
251	0	}
252		}
253	0	None => keys_to_remove.push(*key),
254		}
255		}
256
257	0	for key in keys_to_remove {
258	0	self.map.remove(&key);
259	0	}
260	0	}
261		}
262
263		impl Sub<RoaringTreemap> for RoaringTreemap {
264		type Output = RoaringTreemap;
265
266		/// A `difference` between two sets.
267	0	fn sub(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
268	0	SubAssign::sub_assign(&mut self, rhs);
269	0	self
270	0	}
271		}
272
273		impl Sub<&RoaringTreemap> for RoaringTreemap {
274		type Output = RoaringTreemap;
275
276		/// A `difference` between two sets.
277	0	fn sub(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
278	0	SubAssign::sub_assign(&mut self, rhs);
279	0	self
280	0	}
281		}
282
283		impl Sub<RoaringTreemap> for &RoaringTreemap {
284		type Output = RoaringTreemap;
285
286		/// A `difference` between two sets.
287	0	fn sub(self, rhs: RoaringTreemap) -> RoaringTreemap {
288	0	Sub::sub(self.clone(), rhs)
289	0	}
290		}
291
292		impl Sub<&RoaringTreemap> for &RoaringTreemap {
293		type Output = RoaringTreemap;
294
295		/// A `difference` between two sets.
296	0	fn sub(self, rhs: &RoaringTreemap) -> RoaringTreemap {
297	0	Sub::sub(self.clone(), rhs)
298	0	}
299		}
300
301		impl SubAssign<RoaringTreemap> for RoaringTreemap {
302		/// A `difference` between two sets.
303	0	fn sub_assign(&mut self, rhs: RoaringTreemap) {
304	0	SubAssign::sub_assign(self, &rhs)
305	0	}
306		}
307
308		impl SubAssign<&RoaringTreemap> for RoaringTreemap {
309		/// A `difference` between two sets.
310	0	fn sub_assign(&mut self, rhs: &RoaringTreemap) {
311	0	for (key, rhs_rb) in &rhs.map {
312	0	match self.map.entry(*key) {
313	0	Entry::Vacant(_entry) => (),
314	0	Entry::Occupied(mut entry) => {
315	0	SubAssign::sub_assign(entry.get_mut(), rhs_rb);
316	0	if entry.get().is_empty() {
317	0	entry.remove_entry();
318	0	}
319		}
320		}
321		}
322	0	}
323		}
324
325		impl BitXor<RoaringTreemap> for RoaringTreemap {
326		type Output = RoaringTreemap;
327
328		/// A `symmetric difference` between two sets.
329	0	fn bitxor(mut self, rhs: RoaringTreemap) -> RoaringTreemap {
330	0	BitXorAssign::bitxor_assign(&mut self, rhs);
331	0	self
332	0	}
333		}
334
335		impl BitXor<&RoaringTreemap> for RoaringTreemap {
336		type Output = RoaringTreemap;
337
338		/// A `symmetric difference` between two sets.
339	0	fn bitxor(mut self, rhs: &RoaringTreemap) -> RoaringTreemap {
340	0	BitXorAssign::bitxor_assign(&mut self, rhs);
341	0	self
342	0	}
343		}
344
345		impl BitXor<RoaringTreemap> for &RoaringTreemap {
346		type Output = RoaringTreemap;
347
348		/// A `symmetric difference` between two sets.
349	0	fn bitxor(self, rhs: RoaringTreemap) -> RoaringTreemap {
350	0	BitXor::bitxor(rhs, self)
351	0	}
352		}
353
354		impl BitXor<&RoaringTreemap> for &RoaringTreemap {
355		type Output = RoaringTreemap;
356
357		/// A `symmetric difference` between two sets.
358	0	fn bitxor(self, rhs: &RoaringTreemap) -> RoaringTreemap {
359	0	if self.len() < rhs.len() {
360	0	BitXor::bitxor(self, rhs.clone())
361		} else {
362	0	BitXor::bitxor(self.clone(), rhs)
363		}
364	0	}
365		}
366
367		impl BitXorAssign<RoaringTreemap> for RoaringTreemap {
368		/// A `symmetric difference` between two sets.
369	0	fn bitxor_assign(&mut self, rhs: RoaringTreemap) {
370	0	for (key, other_rb) in rhs.map {
371	0	match self.map.entry(key) {
372	0	Entry::Vacant(entry) => {
373	0	entry.insert(other_rb);
374	0	}
375	0	Entry::Occupied(mut entry) => {
376	0	BitXorAssign::bitxor_assign(entry.get_mut(), other_rb);
377	0	if entry.get().is_empty() {
378	0	entry.remove_entry();
379	0	}
380		}
381		}
382		}
383	0	}
384		}
385
386		impl BitXorAssign<&RoaringTreemap> for RoaringTreemap {
387		/// A `symmetric difference` between two sets.
388	0	fn bitxor_assign(&mut self, rhs: &RoaringTreemap) {
389	0	for (key, other_rb) in &rhs.map {
390	0	match self.map.entry(*key) {
391	0	Entry::Vacant(entry) => {
392	0	entry.insert(other_rb.clone());
393	0	}
394	0	Entry::Occupied(mut entry) => {
395	0	BitXorAssign::bitxor_assign(entry.get_mut(), other_rb);
396	0	if entry.get().is_empty() {
397	0	entry.remove_entry();
398	0	}
399		}
400		}
401		}
402	0	}
403		}
404
405		#[cfg(test)]
406		mod test {
407		use crate::{MultiOps, RoaringTreemap};
408		use proptest::prelude::*;
409
410		// fast count tests
411		proptest! {
412		#[test]
413		fn union_len_eq_len_of_materialized_union(
414		a in RoaringTreemap::arbitrary(),
415		b in RoaringTreemap::arbitrary()
416		) {
417		prop_assert_eq!(a.union_len(&b), (a \| b).len());
418		}
419
420		#[test]
421		fn intersection_len_eq_len_of_materialized_intersection(
422		a in RoaringTreemap::arbitrary(),
423		b in RoaringTreemap::arbitrary()
424		) {
425		prop_assert_eq!(a.intersection_len(&b), (a & b).len());
426		}
427
428		#[test]
429		fn difference_len_eq_len_of_materialized_difference(
430		a in RoaringTreemap::arbitrary(),
431		b in RoaringTreemap::arbitrary()
432		) {
433		prop_assert_eq!(a.difference_len(&b), (a - b).len());
434		}
435
436		#[test]
437		fn symmetric_difference_len_eq_len_of_materialized_symmetric_difference(
438		a in RoaringTreemap::arbitrary(),
439		b in RoaringTreemap::arbitrary()
440		) {
441		prop_assert_eq!(a.symmetric_difference_len(&b), (a ^ b).len());
442		}
443
444		#[test]
445		fn all_union_give_the_same_result(
446		a in RoaringTreemap::arbitrary(),
447		b in RoaringTreemap::arbitrary(),
448		c in RoaringTreemap::arbitrary()
449		) {
450		let mut ref_assign = a.clone();
451		ref_assign \|= &b;
452		ref_assign \|= &c;
453
454		let mut own_assign = a.clone();
455		own_assign \|= b.clone();
456		own_assign \|= c.clone();
457
458		let ref_inline = &a \| &b \| &c;
459		let own_inline = a.clone() \| b.clone() \| c.clone();
460
461		let ref_multiop = [&a, &b, &c].union();
462		let own_multiop = [a, b.clone(), c.clone()].union();
463
464		for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
465		prop_assert_eq!(&ref_assign, roar);
466		}
467		}
468
469		#[test]
470		fn all_intersection_give_the_same_result(
471		a in RoaringTreemap::arbitrary(),
472		b in RoaringTreemap::arbitrary(),
473		c in RoaringTreemap::arbitrary()
474		) {
475		let mut ref_assign = a.clone();
476		ref_assign &= &b;
477		ref_assign &= &c;
478
479		let mut own_assign = a.clone();
480		own_assign &= b.clone();
481		own_assign &= c.clone();
482
483		let ref_inline = &a & &b & &c;
484		let own_inline = a.clone() & b.clone() & c.clone();
485
486		let ref_multiop = [&a, &b, &c].intersection();
487		let own_multiop = [a, b.clone(), c.clone()].intersection();
488
489		for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
490		prop_assert_eq!(&ref_assign, roar);
491		}
492		}
493
494		#[test]
495		fn all_difference_give_the_same_result(
496		a in RoaringTreemap::arbitrary(),
497		b in RoaringTreemap::arbitrary(),
498		c in RoaringTreemap::arbitrary()
499		) {
500		let mut ref_assign = a.clone();
501		ref_assign -= &b;
502		ref_assign -= &c;
503
504		let mut own_assign = a.clone();
505		own_assign -= b.clone();
506		own_assign -= c.clone();
507
508		let ref_inline = &a - &b - &c;
509		let own_inline = a.clone() - b.clone() - c.clone();
510
511		let ref_multiop = [&a, &b, &c].difference();
512		let own_multiop = [a, b.clone(), c.clone()].difference();
513
514		for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
515		prop_assert_eq!(&ref_assign, roar);
516		}
517		}
518
519		#[test]
520		fn all_symmetric_difference_give_the_same_result(
521		a in RoaringTreemap::arbitrary(),
522		b in RoaringTreemap::arbitrary(),
523		c in RoaringTreemap::arbitrary()
524		) {
525		let mut ref_assign = a.clone();
526		ref_assign ^= &b;
527		ref_assign ^= &c;
528
529		let mut own_assign = a.clone();
530		own_assign ^= b.clone();
531		own_assign ^= c.clone();
532
533		let ref_inline = &a ^ &b ^ &c;
534		let own_inline = a.clone() ^ b.clone() ^ c.clone();
535
536		let ref_multiop = [&a, &b, &c].symmetric_difference();
537		let own_multiop = [a, b.clone(), c.clone()].symmetric_difference();
538
539		for roar in &[own_assign, ref_inline, own_inline, ref_multiop, own_multiop] {
540		prop_assert_eq!(&ref_assign, roar);
541		}
542		}
543		}
544		}