1use crate::{complement::Complement, ops::*};
2
3macro_rules! impl_for_primitive {
4 ($ty:ty : $size:literal) => {
5
6 impl BitEmpty for $ty {
7 fn empty() -> $ty {
8 <$ty>::MIN
9 }
10 }
11
12 impl BitTest for $ty {
13 #[inline]
14 fn test(&self, idx: usize) -> bool {
15 if idx < $size {
16 0 != *self & ((1 as $ty) << idx)
17 } else {
18 false
19 }
20 }
21 }
22
23 impl BitTestAll for $ty {
24 #[inline]
25 fn test_all(&self) -> bool {
26 $size == usize::MAX && *self == <$ty>::MAX
27 }
28 }
29
30 impl BitTestNone for $ty {
31 #[inline]
32 fn test_none(&self) -> bool {
33 *self == 0
34 }
35 }
36
37 impl BitSetLimit for $ty {
38 const MAX_SET_INDEX: usize = $size - 1;
39 }
40
41 impl BitSet for $ty {
42 #[inline]
43 unsafe fn set_unchecked(&mut self, idx: usize) {
44 debug_assert!(idx < $size);
45 *self |= (1 as $ty << idx);
46 }
47 }
48
49 impl BitUnsetLimit for $ty {
50 const MAX_UNSET_INDEX: usize = usize::MAX;
51 }
52
53 impl BitUnset for $ty {
54 #[inline]
55 unsafe fn unset_unchecked(&mut self, idx: usize) {
56 if idx < $size {
57 *self &= !(1 as $ty << idx);
58 }
59 }
60 }
61
62 impl BitSearch for $ty {
63 fn find_first_set(&self, lower_bound: usize) -> Option<usize> {
64 if lower_bound > Self::MAX_SET_INDEX {
65 return None;
66 }
67
68 let masked = *self & (<$ty>::MAX).wrapping_shl((lower_bound as u32));
69 match masked.trailing_zeros() {
70 $size => None,
71 idx => Some(idx as usize),
72 }
73 }
74 }
75
76 impl BitComplement for $ty {
77 type Output = Complement<$ty>;
78
79 fn complement(self) -> Complement<Self> {
80 Complement(self)
81 }
82 }
83
84 impl BitUnion for $ty {
85 type Output = Self;
86
87 fn union(self, rhs: Self) -> Self {
88 self | rhs
89 }
90 }
91
92 impl BitUnion<Complement<$ty>> for $ty {
93 type Output = Complement<Self>;
94
95 fn union(self, rhs: Complement<Self>) -> Complement<Self> {
96 Complement(rhs.0 & (!self))
97 }
98 }
99
100 impl BitIntersection for $ty {
101 type Output = Self;
102
103 fn intersection(self, rhs: Self) -> Self {
104 self & rhs
105 }
106 }
107
108 impl BitIntersection<Complement<$ty>> for $ty {
109 type Output = Self;
110
111 fn intersection(self, rhs: Complement<Self>) -> Self {
112 self & (!rhs.0)
113 }
114 }
115
116 impl BitDifference for $ty {
117 type Output = Self;
118
119 fn difference(self, rhs: Self) -> Self {
120 self & (!rhs)
121 }
122 }
123
124 impl BitDifference<Complement<$ty>> for $ty {
125 type Output = Self;
126
127 fn difference(self, rhs: Complement<Self>) -> Self {
128 self & rhs.0
129 }
130 }
131
132 impl BitSubset for $ty {
133 fn is_subset_of(&self, rhs: &Self) -> bool {
134 *self & !*rhs == 0
135 }
136 }
137
138 impl BitSubset<Complement<$ty>> for $ty {
139 fn is_subset_of(&self, rhs: &Complement<Self>) -> bool {
140 *self & rhs.0 == 0
141 }
142 }
143
144 impl BitDisjoint for $ty {
145 fn is_disjoint(&self, rhs: &Self) -> bool {
146 *self & *rhs == 0
147 }
148 }
149
150 impl BitDisjoint<Complement<$ty>> for $ty {
151 fn is_disjoint(&self, rhs: &Complement<Self>) -> bool {
152 *self & !rhs.0 == 0
153 }
154 }
155
156
157 impl<const N: usize> BitEmpty for [$ty; N] {
158 fn empty() -> [$ty; N] {
159 [<$ty>::MIN; N]
160 }
161 }
162
163 impl<const N: usize> BitTest for [$ty; N] {
164 #[inline]
165 fn test(&self, idx: usize) -> bool {
166 if idx < $size * N {
167 let i = idx / $size;
168 let j = idx % $size;
169 0 != self[i] & ((1 as $ty) << j)
170 } else {
171 false
172 }
173 }
174 }
175
176 impl<const N: usize> BitTestAll for [$ty; N] {
177 #[inline]
178 fn test_all(&self) -> bool {
179 false
180 }
181 }
182
183 impl<const N: usize> BitTestNone for [$ty; N] {
184 #[inline]
185 fn test_none(&self) -> bool {
186 self.iter().all(|e| *e == 0)
187 }
188 }
189
190 impl<const N: usize> BitSetLimit for [$ty; N] {
191 const MAX_SET_INDEX: usize = ($size * N) - 1;
192 }
193
194 impl<const N: usize> BitSet for [$ty; N] {
195 #[inline]
196 unsafe fn set_unchecked(&mut self, idx: usize) {
197 debug_assert!(idx < $size * N);
198 let i = idx / $size;
199 let j = idx % $size;
200 self[i] |= (1 as $ty << j);
201 }
202 }
203
204 impl<const N: usize> BitUnsetLimit for [$ty; N] {
205 const MAX_UNSET_INDEX: usize = usize::MAX;
206 }
207
208 impl<const N: usize> BitUnset for [$ty; N] {
209 #[inline]
210 unsafe fn unset_unchecked(&mut self, idx: usize) {
211 if idx < $size * N {
212 let i = idx / $size;
213 let j = idx % $size;
214
215 self[i] &= !(1 as $ty << j);
216 }
217 }
218 }
219
220 impl<const N: usize> BitSearch for [$ty; N] {
221 fn find_first_set(&self, lower_bound: usize) -> Option<usize> {
222 if lower_bound > Self::MAX_SET_INDEX {
223 return None;
224 }
225
226 let mut i = lower_bound / $size;
227 let j = lower_bound % $size;
228
229 let mut masked = self[i] & (<$ty>::MAX).wrapping_shl((j as u32));
230
231 loop {
232 match masked.trailing_zeros() {
233 $size => {
234 i += 1;
235 if i >= N {
236 return None;
237 }
238 masked = self[i];
239 },
240 idx => return Some(i * $size + idx as usize)
241 }
242 }
243 }
244 }
245
246 impl<const N: usize> BitComplement for [$ty; N] {
247 type Output = Complement<Self>;
248
249 fn complement(self) -> Complement<Self> {
250 Complement(self)
251 }
252 }
253
254 impl<const N: usize> BitUnion for [$ty; N] {
255 type Output = Self;
256
257 fn union(self, rhs: Self) -> Self {
258 crate::map2_arrays(self, rhs, |l, r| l | r)
259 }
260 }
261
262 impl<const N: usize> BitUnion<Complement<[$ty; N]>> for [$ty; N] {
263 type Output = Complement<Self>;
264
265 fn union(self, rhs: Complement<Self>) -> Complement<Self> {
266 Complement(crate::map2_arrays(self, rhs.0, |l, r| r & !l))
267 }
268 }
269
270 impl<const N: usize> BitIntersection for [$ty; N] {
271 type Output = Self;
272
273 fn intersection(self, rhs: Self) -> Self {
274 crate::map2_arrays(self, rhs, |l, r| l & r)
275 }
276 }
277
278 impl<const N: usize> BitIntersection<Complement<[$ty; N]>> for [$ty; N] {
279 type Output = Self;
280
281 fn intersection(self, rhs: Complement<Self>) -> Self {
282 crate::map2_arrays(self, rhs.0, |l, r| l & !r)
283 }
284 }
285
286 impl<const N: usize> BitDifference for [$ty; N] {
287 type Output = Self;
288
289 fn difference(self, rhs: Self) -> Self {
290 crate::map2_arrays(self, rhs, |l, r| l & !r)
291 }
292 }
293
294 impl<const N: usize> BitDifference<Complement<[$ty; N]>> for [$ty; N] {
295 type Output = Self;
296
297 fn difference(self, rhs: Complement<Self>) -> Self {
298 crate::map2_arrays(self, rhs.0, |l, r| l & r)
299 }
300 }
301
302 impl<const N: usize> BitSubset for [$ty; N] {
303 fn is_subset_of(&self, rhs: &Self) -> bool {
304 self.iter().zip(rhs).all(|(lhs, rhs)| *lhs & !*rhs == 0)
305 }
306 }
307
308 impl<const N: usize> BitSubset<Complement<[$ty; N]>> for [$ty; N] {
309 fn is_subset_of(&self, rhs: &Complement<Self>) -> bool {
310 self.iter().zip(&rhs.0).all(|(lhs, rhs)| *lhs & *rhs == 0)
311 }
312 }
313
314 impl<const N: usize> BitDisjoint for [$ty; N] {
315 fn is_disjoint(&self, rhs: &Self) -> bool {
316 self.iter().zip(rhs).all(|(lhs, rhs)| *lhs & *rhs == 0)
317 }
318 }
319
320 impl<const N: usize> BitDisjoint<Complement<[$ty; N]>> for [$ty; N] {
321 fn is_disjoint(&self, rhs: &Complement<Self>) -> bool {
322 self.iter().zip(&rhs.0).all(|(lhs, rhs)| *lhs & !*rhs == 0)
323 }
324 }
325 };
326
327 ($ty:ty : $size:literal, $($tail:tt)+) => {
328 impl_for_primitive!($ty : $size);
329 impl_for_primitive!($($tail)+);
330 }
331}
332
333impl_for_primitive!(u8 : 8, u16 : 16, u32 : 32, u64 : 64, u128 : 128);
334
335impl BitEmpty for bool {
336 fn empty() -> bool {
337 false
338 }
339}
340
341impl BitTest for bool {
342 #[inline]
343 fn test(&self, idx: usize) -> bool {
344 if idx == 0 {
345 *self
346 } else {
347 false
348 }
349 }
350}
351
352impl BitTestAll for bool {
353 #[inline]
354 fn test_all(&self) -> bool {
355 usize::MAX == 0 && *self
356 }
357}
358
359impl BitTestNone for bool {
360 #[inline]
361 fn test_none(&self) -> bool {
362 !*self
363 }
364}
365
366impl BitSetLimit for bool {
367 const MAX_SET_INDEX: usize = 0;
368}
369
370impl BitSet for bool {
371 #[inline]
372 unsafe fn set_unchecked(&mut self, idx: usize) {
373 debug_assert_eq!(idx, 0);
374 *self = true;
375 }
376}
377
378impl BitUnsetLimit for bool {
379 const MAX_UNSET_INDEX: usize = usize::MAX;
380}
381
382impl BitUnset for bool {
383 #[inline]
384 unsafe fn unset_unchecked(&mut self, idx: usize) {
385 if idx == 0 {
386 *self = false;
387 }
388 }
389}
390
391impl BitSearch for bool {
392 fn find_first_set(&self, lower_bound: usize) -> Option<usize> {
393 if lower_bound > 0 {
394 return None;
395 }
396
397 if *self {
398 Some(0)
399 } else {
400 None
401 }
402 }
403}
404
405impl BitComplement for bool {
406 type Output = Complement<bool>;
407
408 fn complement(self) -> Complement<Self> {
409 Complement(self)
410 }
411}
412
413impl BitUnion for bool {
414 type Output = Self;
415
416 fn union(self, rhs: Self) -> Self {
417 self || rhs
418 }
419}
420
421impl BitUnion<Complement<bool>> for bool {
422 type Output = Complement<Self>;
423
424 fn union(self, rhs: Complement<Self>) -> Complement<Self> {
425 Complement(rhs.0 && (!self))
426 }
427}
428
429impl BitIntersection for bool {
430 type Output = Self;
431
432 fn intersection(self, rhs: Self) -> Self {
433 self && rhs
434 }
435}
436
437impl BitIntersection<Complement<bool>> for bool {
438 type Output = Self;
439
440 fn intersection(self, rhs: Complement<Self>) -> Self {
441 self && (!rhs.0)
442 }
443}
444
445impl BitDifference for bool {
446 type Output = Self;
447
448 fn difference(self, rhs: Self) -> Self {
449 self && (!rhs)
450 }
451}
452
453impl BitDifference<Complement<bool>> for bool {
454 type Output = Self;
455
456 fn difference(self, rhs: Complement<Self>) -> Self {
457 self && rhs.0
458 }
459}
460
461impl BitSubset for bool {
462 fn is_subset_of(&self, rhs: &Self) -> bool {
463 !*self || *rhs
464 }
465}
466
467impl BitSubset<Complement<bool>> for bool {
468 fn is_subset_of(&self, rhs: &Complement<Self>) -> bool {
469 !*self || !rhs.0
470 }
471}
472
473impl BitDisjoint for bool {
474 fn is_disjoint(&self, rhs: &Self) -> bool {
475 !*self || !*rhs
476 }
477}
478
479impl BitDisjoint<Complement<bool>> for bool {
480 fn is_disjoint(&self, rhs: &Complement<Self>) -> bool {
481 !*self || rhs.0
482 }
483}