hyperloglog_rs/bitor.rs
1use crate::primitive::Primitive;
2use crate::{array_default::ArrayIter, prelude::*};
3use core::ops::{BitOr, BitOrAssign};
4
5#[allow(clippy::suspicious_op_assign_impl)]
6impl<P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<Self> for HyperLogLog<P, BITS> {
7 #[inline(always)]
8 /// Computes union between HLL counters.
9 ///
10 /// ```rust
11 /// # use hyperloglog_rs::prelude::*;
12 /// # use core::ops::BitOrAssign;
13 ///
14 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
15 /// hll.insert(1u8);
16 ///
17 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
18 /// hll2.insert(2u8);
19 ///
20 /// hll.bitor_assign(hll2);
21 ///
22 /// assert!(hll.estimate_cardinality() > 2.0 - 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
23 /// assert!(hll.estimate_cardinality() < 2.0 + 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
24 ///
25 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
26 /// hll.insert(1u8);
27 ///
28 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
29 /// hll2.insert(1u8);
30 ///
31 /// hll.bitor_assign(hll2);
32 ///
33 /// assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
34 /// assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
35 ///
36 /// let mut hll3 = HyperLogLog::<Precision16, 6>::default();
37 /// hll3.insert(3u8);
38 /// hll3.insert(4u8);
39 ///
40 /// let mut hll4 = HyperLogLog::<Precision16, 6>::default();
41 /// hll4.insert(5u8);
42 /// hll4.insert(6u8);
43 ///
44 /// hll3.bitor_assign(hll4);
45 ///
46 /// assert!(hll3.estimate_cardinality() > 4.0 - 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
47 /// assert!(hll3.estimate_cardinality() < 4.0 + 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
48 /// ```
49 fn bitor_assign(&mut self, rhs: Self) {
50 self.bitor_assign(&rhs)
51 }
52}
53
54#[allow(clippy::suspicious_op_assign_impl)]
55impl<P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<&Self> for HyperLogLog<P, BITS> {
56 #[inline(always)]
57 /// Computes union between HLL counters.
58 ///
59 /// ```rust
60 /// # use hyperloglog_rs::prelude::*;
61 /// # use core::ops::BitOrAssign;
62 ///
63 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
64 /// hll.insert(1u8);
65 ///
66 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
67 /// hll2.insert(2u8);
68 ///
69 /// hll.bitor_assign(&hll2);
70 ///
71 /// assert!(hll.estimate_cardinality() > 2.0 - 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
72 /// assert!(hll.estimate_cardinality() < 2.0 + 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
73 ///
74 /// let mut hll = HyperLogLog::<Precision8, 6>::default();
75 /// hll.insert(1u8);
76 ///
77 /// let mut hll2 = HyperLogLog::<Precision8, 6>::default();
78 /// hll2.insert(1u8);
79 ///
80 /// hll.bitor_assign(&hll2);
81 ///
82 /// assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
83 /// assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
84 ///
85 /// let mut hll3 = HyperLogLog::<Precision16, 6>::default();
86 /// hll3.insert(3u8);
87 /// hll3.insert(4u8);
88 ///
89 /// let mut hll4 = HyperLogLog::<Precision16, 6>::default();
90 /// hll4.insert(5u8);
91 /// hll4.insert(6u8);
92 ///
93 /// hll3.bitor_assign(&hll4);
94 ///
95 /// assert!(hll3.estimate_cardinality() > 4.0 - 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
96 /// assert!(hll3.estimate_cardinality() < 4.0 + 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
97 /// ```
98 fn bitor_assign(&mut self, rhs: &Self) {
99 self.number_of_zero_registers = P::NumberOfZeros::ZERO;
100 for (left_word, mut right_word) in self
101 .words
102 .iter_elements_mut()
103 .zip(rhs.words.into_iter_elements())
104 {
105 let mut left_word_copy = *left_word;
106
107 for i in 0..Self::NUMBER_OF_REGISTERS_IN_WORD {
108 let mut left_register = left_word_copy & Self::LOWER_REGISTER_MASK;
109 let right_register = right_word & Self::LOWER_REGISTER_MASK;
110 left_register = (left_register).max(right_register);
111 *left_word &= !(Self::LOWER_REGISTER_MASK << (i * BITS));
112 *left_word |= left_register << (i * BITS);
113 self.number_of_zero_registers +=
114 P::NumberOfZeros::reverse((left_register == 0) as usize);
115 left_word_copy >>= BITS;
116 right_word >>= BITS;
117 }
118 }
119 self.number_of_zero_registers -=
120 P::NumberOfZeros::reverse(Self::get_number_of_padding_registers());
121 }
122}
123
124impl<P: Precision + WordType<BITS>, const BITS: usize> BitOr<Self> for HyperLogLog<P, BITS> {
125 type Output = Self;
126
127 #[inline(always)]
128 /// Computes the union between two HyperLogLog counters of the same precision and number of bits per register.
129 ///
130 /// # Example
131 ///
132 /// ```rust
133 /// # use hyperloglog_rs::prelude::*;
134 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
135 /// hll1.insert(&1);
136 /// hll1.insert(&2);
137 ///
138 /// let mut hll2 = HyperLogLog::<Precision14, 5>::default();
139 /// hll2.insert(&2);
140 /// hll2.insert(&3);
141 ///
142 /// let hll_union = hll1 | hll2;
143 ///
144 /// assert!(hll_union.estimate_cardinality() >= 3.0_f32 * 0.9 &&
145 /// hll_union.estimate_cardinality() <= 3.0_f32 * 1.1);
146 /// ```
147 ///
148 /// Merging a set with an empty set should not change the cardinality.
149 ///
150 /// ```rust
151 /// # use hyperloglog_rs::prelude::*;
152 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
153 /// hll1.insert(&1);
154 /// hll1.insert(&2);
155 ///
156 /// let hll_union = hll1.clone() | HyperLogLog::<Precision14, 5>::default();
157 /// assert_eq!(
158 /// hll_union,
159 /// hll1,
160 /// concat!(
161 /// "The cardinality of the union should ",
162 /// "be the same as the cardinality of the first set."
163 /// )
164 /// );
165 /// ```
166 ///
167 /// We can create the HLL counters from array from registers,
168 /// so to be able to check that everything works as expected.
169 ///
170 /// ```rust
171 /// # use hyperloglog_rs::prelude::*;
172 ///
173 /// let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
174 /// let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
175 /// let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
176 ///
177 /// let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
178 /// let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
179 /// let union = hll1 | hll2;
180 ///
181 /// assert_eq!(union.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", union.get_registers(), expected);
182 /// ```
183 ///
184 fn bitor(mut self, rhs: Self) -> Self {
185 self.bitor_assign(rhs);
186 self
187 }
188}
189
190impl<P: Precision + WordType<BITS>, const BITS: usize> BitOr<&Self> for HyperLogLog<P, BITS> {
191 type Output = Self;
192
193 #[inline(always)]
194 /// Computes the union between two HyperLogLog counters of the same precision and number of bits per register.
195 ///
196 /// # Example
197 ///
198 /// ```rust
199 /// # use hyperloglog_rs::prelude::*;
200 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
201 /// hll1.insert(&1);
202 /// hll1.insert(&2);
203 ///
204 /// let mut hll2 = HyperLogLog::<Precision14, 5>::default();
205 /// hll2.insert(&2);
206 /// hll2.insert(&3);
207 ///
208 /// let hll_union = hll1 | hll2;
209 ///
210 /// assert!(hll_union.estimate_cardinality() >= 3.0_f32 * 0.9 &&
211 /// hll_union.estimate_cardinality() <= 3.0_f32 * 1.1);
212 /// ```
213 ///
214 /// Merging a set with an empty set should not change the cardinality.
215 ///
216 /// ```rust
217 /// # use hyperloglog_rs::prelude::*;
218 /// let mut hll1 = HyperLogLog::<Precision14, 5>::default();
219 /// hll1.insert(&1);
220 /// hll1.insert(&2);
221 ///
222 /// let hll_union = hll1.clone() | HyperLogLog::<Precision14, 5>::default();
223 /// assert_eq!(
224 /// hll_union,
225 /// hll1,
226 /// concat!(
227 /// "The cardinality of the union should ",
228 /// "be the same as the cardinality of the first set."
229 /// )
230 /// );
231 /// ```
232 ///
233 /// We can create the HLL counters from array from registers,
234 /// so to be able to check that everything works as expected.
235 ///
236 /// ```rust
237 /// # use hyperloglog_rs::prelude::*;
238 ///
239 /// let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
240 /// let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
241 /// let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
242 ///
243 /// let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
244 /// let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
245 /// let union = hll1 | &hll2;
246 ///
247 /// assert_eq!(union.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", union.get_registers(), expected);
248 /// ```
249 ///
250 fn bitor(mut self, rhs: &Self) -> Self {
251 self.bitor_assign(rhs);
252 self
253 }
254}