hyperloglog_rs/bitand.rs
1use crate::primitive::Primitive;
2use crate::{array_default::ArrayIter, prelude::*};
3use core::ops::{BitAnd, BitAndAssign};
4
5#[allow(clippy::suspicious_op_assign_impl)]
6impl<P: Precision + WordType<BITS>, const BITS: usize> BitAndAssign<Self> for HyperLogLog<P, BITS> {
7 #[inline(always)]
8 /// Computes intersection between HLL counters.
9 ///
10 /// # Caveats
11 /// Please be advised that HLL are not designed to compute intersections such as the
12 /// one estimated by this operation. The resulting set will most likely be an overestimation of
13 /// the real intersection. Operate with caution.
14 ///
15 /// # Implementation details
16 /// This operation is implemented by computing the minimum register-wise of the
17 /// two HLL counters. This results in an estimation of the intersection because
18 /// we obtain a new HLL counter that at most contain the elements present in both
19 /// HLL counters.
20 ///
21 /// # Example
22 ///
23 /// ```rust
24 /// # use hyperloglog_rs::prelude::*;
25 /// # use core::ops::BitAndAssign;
26 ///
27 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
28 /// hll.insert(1u8);
29 ///
30 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
31 /// hll2.insert(2u8);
32 ///
33 /// hll.bitand_assign(hll2);
34 ///
35 /// assert!(hll.estimate_cardinality() < 0.1, "The cardinality is {}, we were expecting 0.", hll.estimate_cardinality());
36 ///
37 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
38 /// hll.insert(1u8);
39 ///
40 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
41 /// hll2.insert(1u8);
42 ///
43 /// hll.bitand_assign(hll2);
44 ///
45 /// assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
46 /// assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
47 ///
48 /// let mut hll3 = HyperLogLog::<Precision16, 6>::default();
49 /// hll3.insert(3u8);
50 /// hll3.insert(5u8);
51 ///
52 /// let mut hll4 = HyperLogLog::<Precision16, 6>::default();
53 /// hll4.insert(5u8);
54 /// hll4.insert(6u8);
55 ///
56 /// hll3.bitand_assign(hll4);
57 ///
58 /// assert!(hll3.estimate_cardinality() > 1.0 - 0.1, "Expected a value equal to around 1, got {}", hll3.estimate_cardinality());
59 /// assert!(hll3.estimate_cardinality() < 1.0 + 0.1, "Expected a value equal to around 1, got {}", hll3.estimate_cardinality());
60 /// ```
61 fn bitand_assign(&mut self, rhs: Self) {
62 self.bitand_assign(&rhs)
63 }
64}
65
66#[allow(clippy::suspicious_op_assign_impl)]
67impl<P: Precision + WordType<BITS>, const BITS: usize> BitAndAssign<&Self>
68 for HyperLogLog<P, BITS>
69{
70 #[inline(always)]
71 /// Computes intersection between HLL counters.
72 ///
73 /// # Caveats
74 /// Please be advised that HLL are not designed to compute intersections such as the
75 /// one estimated by this operation. The resulting set will most likely be an overestimation of
76 /// the real intersection. Operate with caution.
77 ///
78 /// # Implementation details
79 /// This operation is implemented by computing the minimum register-wise of the
80 /// two HLL counters. This results in an estimation of the intersection because
81 /// we obtain a new HLL counter that at most contain the elements present in both
82 /// HLL counters.
83 ///
84 /// # Example
85 ///
86 /// ```rust
87 /// # use hyperloglog_rs::prelude::*;
88 /// # use core::ops::BitAndAssign;
89 ///
90 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
91 /// hll.insert(1u8);
92 ///
93 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
94 /// hll2.insert(2u8);
95 ///
96 /// hll.bitand_assign(&hll2);
97 ///
98 /// assert!(hll.estimate_cardinality() < 0.1, "The cardinality is {}, we were expecting 0.", hll.estimate_cardinality());
99 ///
100 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
101 /// hll.insert(1u8);
102 ///
103 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
104 /// hll2.insert(1u8);
105 ///
106 /// hll.bitand_assign(&hll2);
107 ///
108 /// assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
109 /// assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
110 ///
111 /// let mut hll3 = HyperLogLog::<Precision16, 6>::default();
112 /// hll3.insert(3u8);
113 /// hll3.insert(5u8);
114 /// hll3.insert(6u8);
115 ///
116 /// let mut hll4 = HyperLogLog::<Precision16, 6>::default();
117 /// hll4.insert(5u8);
118 /// hll4.insert(6u8);
119 ///
120 /// hll3.bitand_assign(&hll4);
121 ///
122 /// assert!(hll3.estimate_cardinality() > 2.0 - 0.1, "Expected a value equal to around 2, got {}", hll3.estimate_cardinality());
123 /// assert!(hll3.estimate_cardinality() < 2.0 + 0.1, "Expected a value equal to around 2, got {}", hll3.estimate_cardinality());
124 /// ```
125 ///
126 /// Another example is that, if we allocate two example vectors which we will
127 /// use to populate both two sets and the two HyperLogLog counter. All elements
128 /// in the intersection of the two sets must also appear in the intersection of
129 /// the two HyperLogLog counters. Usually, the problem is that it may over-estimate
130 /// the cardinality of the intersection.
131 ///
132 /// ```rust
133 /// # use hyperloglog_rs::prelude::*;
134 /// # use core::ops::BitAndAssign;
135 ///
136 /// let first_vec: Vec<u64> = vec![1, 2, 3, 4, 4, 5, 6, 6, 7, 8];
137 /// let second_vec: Vec<u64> = vec![5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12];
138 ///
139 /// let first_set = first_vec.iter().collect::<std::collections::HashSet<_>>();
140 /// let second_set = second_vec.iter().collect::<std::collections::HashSet<_>>();
141 ///
142 /// let mut hll1 = HyperLogLog::<Precision8, 6>::default();
143 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
144 ///
145 /// for element in first_vec.iter() {
146 /// hll1.insert(element);
147 /// }
148 ///
149 /// for element in second_vec.iter() {
150 /// hll2.insert(element);
151 /// }
152 ///
153 /// let mut hll_intersection = hll1.clone();
154 /// hll_intersection &= &hll2;
155 ///
156 /// let intersection = first_set.intersection(&second_set).collect::<std::collections::HashSet<_>>();
157 ///
158 /// assert!(hll_intersection.estimate_cardinality() >= intersection.len() as f32 * 0.9 &&
159 /// hll_intersection.estimate_cardinality() <= intersection.len() as f32 * 1.1);
160 ///
161 /// for element in intersection.iter() {
162 /// assert!(hll_intersection.may_contain(element));
163 /// }
164 ///
165 /// ```
166 ///
167 fn bitand_assign(&mut self, rhs: &Self) {
168 self.number_of_zero_registers = P::NumberOfZeros::ZERO;
169 for (left_word, mut right_word) in self
170 .words
171 .iter_elements_mut()
172 .zip(rhs.words.into_iter_elements())
173 {
174 let mut left_word_copy = *left_word;
175
176 for i in 0..Self::NUMBER_OF_REGISTERS_IN_WORD {
177 let mut left_register = left_word_copy & Self::LOWER_REGISTER_MASK;
178 let right_register = right_word & Self::LOWER_REGISTER_MASK;
179 left_register = (left_register).min(right_register);
180 *left_word &= !(Self::LOWER_REGISTER_MASK << (i * BITS));
181 *left_word |= left_register << (i * BITS);
182 self.number_of_zero_registers +=
183 P::NumberOfZeros::reverse((left_register == 0) as usize);
184 left_word_copy >>= BITS;
185 right_word >>= BITS;
186 }
187 }
188 self.number_of_zero_registers -=
189 P::NumberOfZeros::reverse(Self::get_number_of_padding_registers());
190 }
191}
192
193impl<P: Precision + WordType<BITS>, const BITS: usize> BitAnd<Self> for HyperLogLog<P, BITS> {
194 type Output = Self;
195
196 #[inline(always)]
197 /// Computes the intersection between two HyperLogLog counters of the same precision and number of bits per register.
198 ///
199 /// # Caveats
200 /// Please be advised that HLL are not designed to compute intersections such as the
201 /// one estimated by this operation. The resulting set will most likely be an overestimation of
202 /// the real intersection. Operate with caution.
203 ///
204 /// # Implementation details
205 /// This operation is implemented by computing the minimum register-wise of the
206 /// two HLL counters. This results in an estimation of the intersection because
207 /// we obtain a new HLL counter that at most contain the elements present in both
208 /// HLL counters.
209 ///
210 /// # Example
211 ///
212 /// ```rust
213 /// # use hyperloglog_rs::prelude::*;
214 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
215 /// hll1.insert(&1);
216 /// hll1.insert(&2);
217 ///
218 /// let mut hll2 = HyperLogLog::<Precision14, 5>::default();
219 /// hll2.insert(&2);
220 /// hll2.insert(&3);
221 ///
222 /// let hll_intersection = hll1 & hll2;
223 ///
224 /// assert!(hll_intersection.estimate_cardinality() >= 1.0_f32 * 0.9 &&
225 /// hll_intersection.estimate_cardinality() <= 1.0_f32 * 1.1);
226 /// ```
227 ///
228 /// Executing the intersection between a set and an empty set
229 /// should result in an empty set.
230 ///
231 /// ```rust
232 /// # use hyperloglog_rs::prelude::*;
233 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
234 /// hll1.insert(&1);
235 /// hll1.insert(&2);
236 ///
237 /// let hll_intersection = hll1.clone() & HyperLogLog::<Precision14, 5>::default();
238 /// assert_eq!(
239 /// HyperLogLog::<Precision14, 5>::default(),
240 /// hll_intersection,
241 /// concat!(
242 /// "The cardinality of the intersection should ",
243 /// "be the same as the empty test."
244 /// )
245 /// );
246 /// ```
247 ///
248 /// We can create the HLL counters from array from registers,
249 /// so to be able to check that everything works as expected.
250 ///
251 /// ```rust
252 /// # use hyperloglog_rs::prelude::*;
253 ///
254 /// let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
255 /// let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
256 /// let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
257 ///
258 /// let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
259 /// let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
260 /// let intersection = hll1 | hll2;
261 ///
262 /// assert_eq!(intersection.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", intersection.get_registers(), expected);
263 /// ```
264 ///
265 fn bitand(mut self, rhs: Self) -> Self {
266 self.bitand_assign(rhs);
267 self
268 }
269}
270
271impl<P: Precision + WordType<BITS>, const BITS: usize> BitAnd<&Self> for HyperLogLog<P, BITS> {
272 type Output = Self;
273
274 #[inline(always)]
275 /// Computes the intersection between two HyperLogLog counters of the same precision and number of bits per register.
276 ///
277 /// # Caveats
278 /// Please be advised that HLL are not designed to compute intersections such as the
279 /// one estimated by this operation. The resulting set will most likely be an overestimation of
280 /// the real intersection. Operate with caution.
281 ///
282 /// # Implementation details
283 /// This operation is implemented by computing the minimum register-wise of the
284 /// two HLL counters. This results in an estimation of the intersection because
285 /// we obtain a new HLL counter that at most contain the elements present in both
286 /// HLL counters.
287 ///
288 /// # Example
289 ///
290 /// ```rust
291 /// # use hyperloglog_rs::prelude::*;
292 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
293 /// hll1.insert(&1);
294 /// hll1.insert(&2);
295 ///
296 /// let mut hll2 = HyperLogLog::<Precision14, 5>::default();
297 /// hll2.insert(&2);
298 /// hll2.insert(&3);
299 ///
300 /// let hll_intersection = hll1 | hll2;
301 ///
302 /// assert!(hll_intersection.estimate_cardinality() >= 3.0_f32 * 0.9 &&
303 /// hll_intersection.estimate_cardinality() <= 3.0_f32 * 1.1);
304 /// ```
305 ///
306 /// Merging a set with an empty set should not change the cardinality.
307 ///
308 /// ```rust
309 /// # use hyperloglog_rs::prelude::*;
310 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
311 /// hll1.insert(&1);
312 /// hll1.insert(&2);
313 ///
314 /// let hll_intersection = hll1.clone() | HyperLogLog::<Precision14, 5>::default();
315 /// assert_eq!(
316 /// hll_intersection,
317 /// hll1,
318 /// concat!(
319 /// "The cardinality of the intersection should ",
320 /// "be the same as the cardinality of the first set."
321 /// )
322 /// );
323 /// ```
324 ///
325 /// We can create the HLL counters from array from registers,
326 /// so to be able to check that everything works as expected.
327 ///
328 /// ```rust
329 /// # use hyperloglog_rs::prelude::*;
330 ///
331 /// let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
332 /// let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
333 /// let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
334 ///
335 /// let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
336 /// let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
337 /// let intersection = hll1 | &hll2;
338 ///
339 /// assert_eq!(intersection.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", intersection.get_registers(), expected);
340 /// ```
341 ///
342 fn bitand(mut self, rhs: &Self) -> Self {
343 self.bitand_assign(rhs);
344 self
345 }
346}