vortex_mask/
bitops.rs

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

vortex_mask/
bitops.rs
