vortex_mask/
bitops.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::ops::BitAnd;
5use std::ops::BitOr;
6use std::ops::Not;
7
8use vortex_error::vortex_panic;
9
10use crate::AllOr;
11use crate::Mask;
12
13impl BitAnd for &Mask {
14    type Output = Mask;
15
16    fn bitand(self, rhs: Self) -> Self::Output {
17        if self.len() != rhs.len() {
18            vortex_panic!("Masks must have the same length");
19        }
20
21        match (self.bit_buffer(), rhs.bit_buffer()) {
22            (AllOr::All, _) => rhs.clone(),
23            (_, AllOr::All) => self.clone(),
24            (AllOr::None, _) => Mask::new_false(self.len()),
25            (_, AllOr::None) => Mask::new_false(self.len()),
26            (AllOr::Some(lhs), AllOr::Some(rhs)) => Mask::from_buffer(lhs & rhs),
27        }
28    }
29}
30
31impl BitOr for &Mask {
32    type Output = Mask;
33
34    fn bitor(self, rhs: Self) -> Self::Output {
35        if self.len() != rhs.len() {
36            vortex_panic!("Masks must have the same length");
37        }
38
39        match (self.bit_buffer(), rhs.bit_buffer()) {
40            (AllOr::All, _) => Mask::new_true(self.len()),
41            (_, AllOr::All) => Mask::new_true(self.len()),
42            (AllOr::None, _) => rhs.clone(),
43            (_, AllOr::None) => self.clone(),
44            (AllOr::Some(lhs), AllOr::Some(rhs)) => Mask::from_buffer(lhs | rhs),
45        }
46    }
47}
48
49impl Mask {
50    /// Computes `self & !rhs` (AND NOT), equivalent to set difference.
51    pub fn bitand_not(self, rhs: &Mask) -> Mask {
52        if self.len() != rhs.len() {
53            vortex_panic!("Masks must have the same length");
54        }
55        match (self.bit_buffer(), rhs.bit_buffer()) {
56            (AllOr::None, _) | (_, AllOr::All) => Mask::new_false(self.len()),
57            (_, AllOr::None) => self,
58            (AllOr::All, _) => !rhs,
59            (AllOr::Some(lhs), AllOr::Some(rhs)) => Mask::from_buffer(lhs.bitand_not(rhs)),
60        }
61    }
62}
63
64impl Not for Mask {
65    type Output = Mask;
66
67    fn not(self) -> Self::Output {
68        !(&self)
69    }
70}
71
72impl Not for &Mask {
73    type Output = Mask;
74
75    fn not(self) -> Self::Output {
76        match self.bit_buffer() {
77            AllOr::All => Mask::new_false(self.len()),
78            AllOr::None => Mask::new_true(self.len()),
79            AllOr::Some(buffer) => Mask::from_buffer(!buffer),
80        }
81    }
82}
83
84#[cfg(test)]
85#[allow(clippy::many_single_char_names)]
86mod tests {
87    use vortex_buffer::BitBuffer;
88
89    use super::*;
90
91    #[test]
92    fn test_bitand_all_combinations() {
93        let len = 5;
94
95        // Test AllTrue & AllTrue
96        let all_true = Mask::new_true(len);
97        let result = &all_true & &all_true;
98        assert!(result.all_true());
99        assert_eq!(result.true_count(), len);
100
101        // Test AllTrue & AllFalse
102        let all_false = Mask::new_false(len);
103        let result = &all_true & &all_false;
104        assert!(result.all_false());
105        assert_eq!(result.true_count(), 0);
106
107        // Test AllFalse & AllTrue
108        let result = &all_false & &all_true;
109        assert!(result.all_false());
110        assert_eq!(result.true_count(), 0);
111
112        // Test AllFalse & AllFalse
113        let result = &all_false & &all_false;
114        assert!(result.all_false());
115        assert_eq!(result.true_count(), 0);
116    }
117
118    #[test]
119    fn test_bitand_with_values() {
120        let mask1 = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
121        let mask2 = Mask::from_buffer(BitBuffer::from_iter([true, true, false, false, true]));
122
123        let result = &mask1 & &mask2;
124        assert_eq!(result.len(), 5);
125        assert_eq!(result.true_count(), 2);
126        assert!(result.value(0)); // true & true = true
127        assert!(!result.value(1)); // false & true = false
128        assert!(!result.value(2)); // true & false = false
129        assert!(!result.value(3)); // false & false = false
130        assert!(result.value(4)); // true & true = true
131    }
132
133    #[test]
134    fn test_bitand_all_true_with_values() {
135        let all_true = Mask::new_true(5);
136        let values = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
137
138        // AllTrue & Values should return Values
139        let result = &all_true & &values;
140        assert_eq!(result.true_count(), 3);
141        assert_eq!(result.len(), 5);
142        assert!(result.value(0));
143        assert!(!result.value(1));
144        assert!(result.value(2));
145        assert!(!result.value(3));
146        assert!(result.value(4));
147    }
148
149    #[test]
150    fn test_bitand_all_false_with_values() {
151        let all_false = Mask::new_false(5);
152        let values = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
153
154        // AllFalse & Values should return AllFalse
155        let result = &all_false & &values;
156        assert!(result.all_false());
157        assert_eq!(result.true_count(), 0);
158    }
159
160    #[test]
161    fn test_bitand_values_with_all_true() {
162        let values = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
163        let all_true = Mask::new_true(5);
164
165        // Values & AllTrue should return Values
166        let result = &values & &all_true;
167        assert_eq!(result.true_count(), 3);
168        assert_eq!(result.len(), 5);
169        assert!(result.value(0));
170        assert!(!result.value(1));
171        assert!(result.value(2));
172        assert!(!result.value(3));
173        assert!(result.value(4));
174    }
175
176    #[test]
177    fn test_bitand_values_with_all_false() {
178        let values = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
179        let all_false = Mask::new_false(5);
180
181        // Values & AllFalse should return AllFalse
182        let result = &values & &all_false;
183        assert!(result.all_false());
184        assert_eq!(result.true_count(), 0);
185    }
186
187    #[test]
188    fn test_bitand_empty_masks() {
189        let empty1 = Mask::new_true(0);
190        let empty2 = Mask::new_false(0);
191
192        let result = &empty1 & &empty2;
193        assert_eq!(result.len(), 0);
194        assert!(result.is_empty());
195    }
196
197    #[test]
198    #[should_panic(expected = "Masks must have the same length")]
199    fn test_bitand_different_lengths() {
200        let mask1 = Mask::new_true(5);
201        let mask2 = Mask::new_true(3);
202        let _unused = &mask1 & &mask2;
203    }
204
205    #[test]
206    fn test_not_all_true() {
207        let all_true = Mask::new_true(5);
208        let result = !&all_true;
209        assert!(result.all_false());
210        assert_eq!(result.true_count(), 0);
211        assert_eq!(result.len(), 5);
212    }
213
214    #[test]
215    fn test_not_all_false() {
216        let all_false = Mask::new_false(5);
217        let result = !&all_false;
218        assert!(result.all_true());
219        assert_eq!(result.true_count(), 5);
220        assert_eq!(result.len(), 5);
221    }
222
223    #[test]
224    fn test_not_values() {
225        let values = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
226        let result = !&values;
227
228        assert_eq!(result.len(), 5);
229        assert_eq!(result.true_count(), 2);
230        assert!(!result.value(0)); // !true = false
231        assert!(result.value(1)); // !false = true
232        assert!(!result.value(2)); // !true = false
233        assert!(result.value(3)); // !false = true
234        assert!(!result.value(4)); // !true = false
235    }
236
237    #[test]
238    fn test_not_empty() {
239        let empty_true = Mask::new_true(0);
240        let result = !&empty_true;
241        assert_eq!(result.len(), 0);
242        assert!(result.is_empty());
243
244        let empty_false = Mask::new_false(0);
245        let result = !&empty_false;
246        assert_eq!(result.len(), 0);
247        assert!(result.is_empty());
248    }
249
250    #[test]
251    fn test_double_not() {
252        let original = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
253        let double_not = !&(!&original);
254
255        // Double negation should return the original
256        assert_eq!(double_not.true_count(), original.true_count());
257        for i in 0..5 {
258            assert_eq!(double_not.value(i), original.value(i));
259        }
260    }
261
262    #[test]
263    fn test_demorgan_law() {
264        // Test De Morgan's law: !(A & B) = !A | !B
265        let a = Mask::from_buffer(BitBuffer::from_iter([true, true, false, false]));
266        let b = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false]));
267
268        let and_result = &a & &b;
269        let not_and = !&and_result;
270
271        let not_a = !&a;
272        let not_b = !&b;
273        let or_result = &not_a | &not_b;
274
275        assert_eq!(not_and.len(), 4);
276        assert!(!not_and.value(0)); // !(true & true) = false
277        assert!(not_and.value(1)); // !(true & false) = true
278        assert!(not_and.value(2)); // !(false & true) = true
279        assert!(not_and.value(3)); // !(false & false) = true
280
281        assert_eq!(or_result.len(), 4);
282        assert_eq!(or_result, not_and)
283    }
284
285    #[test]
286    fn test_bitand_associativity() {
287        // Test (A & B) & C = A & (B & C)
288        let a = Mask::from_buffer(BitBuffer::from_iter([true, true, false, true]));
289        let b = Mask::from_buffer(BitBuffer::from_iter([true, false, true, true]));
290        let c = Mask::from_buffer(BitBuffer::from_iter([false, true, true, true]));
291
292        let left_assoc = &(&a & &b) & &c;
293        let right_assoc = &a & &(&b & &c);
294
295        assert_eq!(left_assoc.true_count(), right_assoc.true_count());
296        for i in 0..4 {
297            assert_eq!(left_assoc.value(i), right_assoc.value(i));
298        }
299    }
300
301    #[test]
302    fn test_bitand_commutativity() {
303        // Test A & B = B & A
304        let a = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false]));
305        let b = Mask::from_buffer(BitBuffer::from_iter([false, true, false, true]));
306
307        let a_and_b = &a & &b;
308        let b_and_a = &b & &a;
309
310        assert_eq!(a_and_b.true_count(), b_and_a.true_count());
311        for i in 0..4 {
312            assert_eq!(a_and_b.value(i), b_and_a.value(i));
313        }
314    }
315
316    #[test]
317    fn test_bitand_identity() {
318        // Test A & AllTrue = A
319        let mask = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false]));
320        let all_true = Mask::new_true(4);
321
322        let result = &mask & &all_true;
323        assert_eq!(result.true_count(), mask.true_count());
324        for i in 0..4 {
325            assert_eq!(result.value(i), mask.value(i));
326        }
327    }
328
329    #[test]
330    fn test_bitand_annihilator() {
331        // Test A & AllFalse = AllFalse
332        let mask = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false]));
333        let all_false = Mask::new_false(4);
334
335        let result = &mask & &all_false;
336        assert!(result.all_false());
337        assert_eq!(result.true_count(), 0);
338    }
339
340    #[test]
341    fn test_bitand_idempotence() {
342        // Test A & A = A
343        let mask = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
344        let result = &mask & &mask;
345
346        assert_eq!(result.true_count(), mask.true_count());
347        for i in 0..5 {
348            assert_eq!(result.value(i), mask.value(i));
349        }
350    }
351
352    #[test]
353    fn test_complex_expression() {
354        // Test a more complex expression: (!(!A) | B) & !C
355        let a = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false]));
356        let b = Mask::from_buffer(BitBuffer::from_iter([true, true, false, false]));
357        let c = Mask::from_buffer(BitBuffer::from_iter([false, true, false, true]));
358
359        let not_not_a = !(&(!&a));
360        let not_not_a_or_b = &not_not_a | &b;
361        let not_c = !&c;
362        let result = &not_not_a_or_b & &not_c;
363
364        // Verify the result manually
365        assert!(result.value(0)); // (!(!true) | true) & !false = (true | true) & true = true
366        assert!(!result.value(1)); // (!(!false) | true) & !true = (false | true) & false = false
367        assert!(result.value(2)); // (!(!true) | false) & !false = (true | false) & true = true
368        assert!(!result.value(3)); // (!(!false) | false) & !true = (false | false) & false = false
369    }
370
371    #[test]
372    fn test_bitand_not() {
373        let a = Mask::from_buffer(BitBuffer::from_iter([true, true, false, false]));
374        let b = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false]));
375        let result = a.clone().bitand_not(&b);
376        assert!(!result.value(0)); // true & !true  = false
377        assert!(result.value(1)); // true & !false = true
378        assert!(!result.value(2)); // false & !true  = false
379        assert!(!result.value(3)); // false & !false = false
380
381        // bitand_not(All) = None
382        assert!(a.clone().bitand_not(&Mask::new_true(4)).all_false());
383
384        // bitand_not(None) = self
385        let none = Mask::new_false(4);
386        assert_eq!(a.clone().bitand_not(&none).true_count(), a.true_count());
387
388        // None.bitand_not(_) = None
389        assert!(none.bitand_not(&a).all_false());
390
391        // All.bitand_not(x) = !x
392        let not_b = !&b;
393        let all_bitand_not_b = Mask::new_true(4).bitand_not(&b);
394        for i in 0..4 {
395            assert_eq!(all_bitand_not_b.value(i), not_b.value(i));
396        }
397    }
398
399    #[test]
400    fn test_bitor() {
401        // Test basic OR operations
402        let mask1 = Mask::from_buffer(BitBuffer::from_iter([true, false, true, false, true]));
403        let mask2 = Mask::from_buffer(BitBuffer::from_iter([true, true, false, false, true]));
404
405        let result = &mask1 | &mask2;
406        assert_eq!(result.len(), 5);
407        assert_eq!(result.true_count(), 4);
408        assert!(result.value(0)); // true | true = true
409        assert!(result.value(1)); // false | true = true
410        assert!(result.value(2)); // true | false = true
411        assert!(!result.value(3)); // false | false = false
412        assert!(result.value(4)); // true | true = true
413
414        // Test with AllTrue
415        let all_true = Mask::new_true(5);
416        let result = &mask1 | &all_true;
417        assert!(result.all_true());
418
419        // Test with AllFalse
420        let all_false = Mask::new_false(5);
421        let result = &mask1 | &all_false;
422        assert_eq!(result.true_count(), mask1.true_count());
423    }
424}
vortex_mask/bitops.rs

vortex_mask/
bitops.rs
