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

vortex_mask/
bitops.rs
