yui_core/conc/misc/
bitseq.rs

1//! A single [`Bit`], and a packed sequence of bits [`BitSeq`] over a generic word `I`.
2
3use core::fmt;
4use std::fmt::{Display, Debug};
5use std::hash::Hash;
6use std::iter::successors;
7use std::ops::{Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, Index, Not, Shl, Shr, ShrAssign, Sub};
8use std::str::FromStr;
9use auto_impl_ops::auto_ops;
10use crate::util::parse_err::ParseErr;
11
12/// A single binary digit, `0` or `1`.
13#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default, derive_more::Display, derive_more::Debug)]
14#[cfg_attr(feature = "serde", derive(serde_repr::Serialize_repr, serde_repr::Deserialize_repr))]
15#[repr(u8)]
16pub enum Bit {
17    #[default]
18    #[display("0")]
19    #[debug("0")]
20    Bit0 = 0,
21
22    #[display("1")]
23    #[debug("1")]
24    Bit1 = 1
25}
26
27impl Bit {
28    pub fn is_zero(&self) -> bool {
29        self == &Bit::Bit0
30    }
31
32    pub fn is_one(&self) -> bool {
33        self == &Bit::Bit1
34    }
35}
36
37impl From<bool> for Bit {
38    fn from(b: bool) -> Self {
39        if b {
40            Bit::Bit1
41        } else {
42            Bit::Bit0
43        }
44    }
45}
46
47macro_rules! impl_bit_from_int {
48    ($t:ty) => {
49        impl From<$t> for Bit {
50            fn from(val: $t) -> Self {
51                match val {
52                    0 => Bit::Bit0,
53                    1 => Bit::Bit1,
54                    _ => panic!()
55                }
56            }
57        }
58    };
59}
60
61impl_bit_from_int!(u8);
62impl_bit_from_int!(u16);
63impl_bit_from_int!(u32);
64impl_bit_from_int!(u64);
65impl_bit_from_int!(u128);
66impl_bit_from_int!(usize);
67impl_bit_from_int!(i8);
68impl_bit_from_int!(i16);
69impl_bit_from_int!(i32);
70impl_bit_from_int!(i64);
71impl_bit_from_int!(isize);
72
73/// The unsigned word backing a [`BitSeq`]. Implemented for `u8` … `u128`.
74pub trait BitRepr:
75    Copy + Eq + Ord + Hash + Default + Debug + Send + Sync + 'static
76    + BitAnd<Output = Self> + BitAndAssign
77    + BitOr<Output = Self> + BitOrAssign
78    + Not<Output = Self>
79    + Shl<usize, Output = Self> + Shr<usize, Output = Self> + ShrAssign<usize>
80    + Add<Output = Self> + Sub<Output = Self>
81{
82    const BITS: usize;
83    const ZERO: Self;
84    const ONE: Self;
85    const MAX: Self;
86
87    fn count_ones(self) -> u32;
88    fn reverse_bits(self) -> Self;
89    fn to_usize(self) -> Option<usize>;
90}
91
92macro_rules! impl_bit_repr {
93    ($($t:ty),* $(,)?) => {$(
94        impl BitRepr for $t {
95            const BITS: usize = <$t>::BITS as usize;
96            const ZERO: Self = 0;
97            const ONE: Self = 1;
98            const MAX: Self = <$t>::MAX;
99
100            fn count_ones(self) -> u32 {
101                <$t>::count_ones(self)
102            }
103
104            fn reverse_bits(self) -> Self {
105                <$t>::reverse_bits(self)
106            }
107
108            fn to_usize(self) -> Option<usize> {
109                usize::try_from(self).ok()
110            }
111        }
112    )*};
113}
114
115impl_bit_repr!(u8, u16, u32, u64, u128);
116
117/// A sequence of [`Bit`]s of length up to [`MAX_LEN`](BitSeq::MAX_LEN) = `I::BITS`,
118/// packed into a single word `I`. The bit at index `i` is stored at
119/// position `i` of `val`, i.e. the least-significant bit of `val` is `self[0]`.
120#[derive(Clone, Copy, PartialEq, Eq, Hash, Default)]
121#[cfg_attr(feature = "serde", derive(serde_with::SerializeDisplay, serde_with::DeserializeFromStr))]
122pub struct BitSeq<I: BitRepr> {
123    val: I,
124    len: usize
125}
126
127macro_rules! impl_bitseq_alias {
128    ($($name:ident => $t:ty),* $(,)?) => {$(
129        #[doc = concat!("[`BitSeq`] packed into a `", stringify!($t), "`.")]
130        pub type $name = BitSeq<$t>;
131    )*};
132}
133
134impl_bitseq_alias!(
135    BitSeq8   => u8,
136    BitSeq16  => u16,
137    BitSeq32  => u32,
138    BitSeq64  => u64,
139    BitSeq128 => u128,
140);
141
142impl<I: BitRepr> BitSeq<I> {
143    pub const MAX_LEN: usize = I::BITS;
144
145    pub fn new(val: I, len: usize) -> Self {
146        assert!(len <= Self::MAX_LEN);
147        assert!(len == Self::MAX_LEN || val < (I::ONE << len));
148        Self { val, len }
149    }
150
151    /// Like [`new`](Self::new), but interprets `val` as bit-reversed so that
152    /// the most-significant bit becomes `self[0]`.
153    pub fn new_rev(val: I, len: usize) -> Self {
154        if len == 0 {
155            return Self::empty();
156        }
157        let val = val.reverse_bits() >> (Self::MAX_LEN - len);
158        Self::new(val, len)
159    }
160
161    pub fn empty() -> Self {
162        Self::new(I::ZERO, 0)
163    }
164
165    pub fn zeros(len: usize) -> Self {
166        Self::new(I::ZERO, len)
167    }
168
169    pub fn ones(len: usize) -> Self {
170        let val = if len == 0 { I::ZERO } else { I::MAX >> (Self::MAX_LEN - len) };
171        Self::new(val, len)
172    }
173
174    pub fn len(&self) -> usize {
175        self.len
176    }
177
178    pub fn val(&self) -> I {
179        self.val
180    }
181
182    /// The packed word as an index. Panics rather than truncating, which a plain `as usize`
183    /// would do once the sequence exceeds `usize::BITS`.
184    pub fn as_usize(&self) -> usize {
185        self.val.to_usize().unwrap_or_else(||
186            panic!("BitSeq value {:?} does not fit in usize", self.val)
187        )
188    }
189
190    pub fn is_empty(&self) -> bool {
191        self.len == 0
192    }
193
194    /// The number of bits set to `1` (Hamming weight).
195    pub fn weight(&self) -> usize {
196        self.val.count_ones() as usize
197    }
198
199    pub fn iter(&self) -> impl Iterator<Item = Bit> + use<I> {
200        let mut val = self.val;
201
202        (0..self.len).map(move |_| {
203            let b = val & I::ONE == I::ONE;
204            val >>= 1;
205            Bit::from(b)
206        })
207    }
208
209    pub fn set(&mut self, i: usize, b: Bit) {
210        assert!(i < self.len);
211        if b.is_zero() {
212            self.val &= !(I::ONE << i);
213        } else {
214            self.val |= I::ONE << i;
215        }
216    }
217
218    pub fn set_0(&mut self, i: usize) {
219        self.set(i, Bit::Bit0)
220    }
221
222    pub fn set_1(&mut self, i: usize) {
223        self.set(i, Bit::Bit1)
224    }
225
226    pub fn push(&mut self, b: Bit) {
227        assert!(self.len < Self::MAX_LEN);
228        if b.is_one() {
229            self.val |= I::ONE << self.len;
230        }
231        self.len += 1;
232    }
233
234    pub fn push_0(&mut self) {
235        self.push(Bit::Bit0)
236    }
237
238    pub fn push_1(&mut self) {
239        self.push(Bit::Bit1)
240    }
241
242    pub fn append(&mut self, b: BitSeq<I>) {
243        assert!(self.len + b.len <= Self::MAX_LEN);
244
245        // `self.len` may be `MAX_LEN`, where the shift below is undefined.
246        if b.len == 0 {
247            return
248        }
249
250        self.val |= b.val << self.len;
251        self.len += b.len;
252    }
253
254    pub fn remove(&mut self, i: usize) {
255        assert!(i < self.len);
256
257        // shifted in two steps: `i + 1` may be `MAX_LEN`, where a shift is undefined.
258        let hi = ((self.val >> i) >> 1) << i;
259        let lo = self.val & ((I::ONE << i) - I::ONE);
260
261        self.val = hi | lo;
262        self.len -= 1;
263    }
264
265    pub fn insert(&mut self, i: usize, b: Bit) {
266        assert!(i <= self.len);
267        assert!(self.len < Self::MAX_LEN);
268
269        let mask = (I::ONE << i) - I::ONE;
270        let a = self.val & !mask;
271        let b = if b.is_one() { I::ONE << i } else { I::ZERO };
272        let c = self.val & mask;
273
274        self.val = a << 1 | b | c;
275        self.len += 1;
276    }
277
278    pub fn insert_0(&mut self, i: usize) {
279        self.insert(i, Bit::Bit0)
280    }
281
282    pub fn insert_1(&mut self, i: usize) {
283        self.insert(i, Bit::Bit1)
284    }
285
286    pub fn edit<F>(&self, f: F) -> Self
287    where F: FnOnce(&mut BitSeq<I>) {
288        let mut copy = *self;
289        f(&mut copy);
290        copy
291    }
292
293    pub fn sub(&self, l: usize) -> Self {
294        assert!(l <= self.len);
295        let val = if l == Self::MAX_LEN { self.val } else { self.val & ((I::ONE << l) - I::ONE) };
296        Self::new(val, l)
297    }
298
299    /// `true` if `self` is a prefix of `other`.
300    pub fn is_sub(&self, other: &Self) -> bool {
301        self.len <= other.len &&
302        self.val == other.sub(self.len).val
303    }
304
305    /// Enumerate all `2^len` sequences of the given length, in ascending order of `val`.
306    pub fn generate(len: usize) -> impl Iterator<Item = BitSeq<I>> {
307        assert!(len <= Self::MAX_LEN);
308        assert!(len < usize::BITS as usize, "generate is only sensible for small lengths");
309        successors(Some(I::ZERO), |&v| Some(v + I::ONE))
310            .take(1 << len)
311            .map(move |v| Self::new(v, len))
312    }
313}
314
315impl<I: BitRepr, T> From<T> for BitSeq<I>
316where Bit: From<T> {
317    fn from(b: T) -> Self {
318        let val = if Bit::from(b).is_zero() { I::ZERO } else { I::ONE };
319        Self::new(val, 1)
320    }
321}
322
323impl<I: BitRepr, T, const N: usize> From<[T; N]> for BitSeq<I>
324where Bit: From<T> {
325    fn from(value: [T; N]) -> Self {
326        Self::from_iter(value)
327    }
328}
329
330impl<I: BitRepr, T> FromIterator<T> for BitSeq<I>
331where Bit: From<T> {
332    fn from_iter<Itr: IntoIterator<Item = T>>(iter: Itr) -> Self {
333        let mut val = I::ZERO;
334        let mut len = 0;
335        for b in iter.into_iter() {
336            if Bit::from(b).is_one() {
337                val |= I::ONE << len;
338            }
339            len += 1;
340        }
341        Self::new(val, len)
342    }
343}
344
345impl<I: BitRepr> FromStr for BitSeq<I> {
346    type Err = ParseErr;
347    fn from_str(s: &str) -> Result<Self, Self::Err> {
348        s.chars().map(|c|
349            match c {
350                '0' => Ok(Bit::Bit0),
351                '1' => Ok(Bit::Bit1),
352                _   => Err(ParseErr::new(format!("invalid bit '{c}' in \"{s}\"")))
353            }
354        ).collect()
355    }
356}
357
358impl<I: BitRepr> Index<usize> for BitSeq<I> {
359    type Output = Bit;
360
361    fn index(&self, i: usize) -> &Self::Output {
362        assert!(i < self.len);
363        if (self.val >> i) & I::ONE == I::ONE {
364            &Bit::Bit1
365        } else {
366            &Bit::Bit0
367        }
368    }
369}
370
371impl<I: BitRepr> Display for BitSeq<I> {
372    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
373        for b in self.iter() {
374            Display::fmt(&b, f)?;
375        }
376        Ok(())
377    }
378}
379
380impl<I: BitRepr> Debug for BitSeq<I> {
381    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
382        Display::fmt(self, f)
383    }
384}
385
386impl<I: BitRepr> PartialOrd for BitSeq<I> {
387    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
388        Some(self.cmp(other))
389    }
390}
391
392// TODO support lex-order (using generic parameter).
393
394/// Ordered by `len`, then [`weight`](BitSeq::weight), then raw `val`.
395impl<I: BitRepr> Ord for BitSeq<I> {
396    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
397        self.len().cmp(&other.len()).then_with( ||
398            self.weight().cmp(&other.weight())
399        ).then_with(||
400            self.val.cmp(&other.val)
401        )
402    }
403}
404
405#[auto_ops]
406impl<I: BitRepr> AddAssign<&BitSeq<I>> for BitSeq<I> {
407    fn add_assign(&mut self, rhs: &Self) {
408        self.append(*rhs);
409    }
410}
411
412#[auto_ops]
413impl<I: BitRepr> AddAssign<Bit> for BitSeq<I> {
414    fn add_assign(&mut self, b: Bit) {
415        self.push(b);
416    }
417}
418
419#[cfg(test)]
420mod tests {
421    use Bit::*;
422    use itertools::Itertools;
423    use super::*;
424
425    type B = BitSeq64;
426
427    #[test]
428    fn width_aliases() {
429        assert_eq!(BitSeq64::generate(3).count(), 8);
430
431        assert_eq!(BitSeq8::MAX_LEN, 8);
432        assert_eq!(BitSeq128::MAX_LEN, 128);
433        assert_eq!(BitSeq8::ones(3).val(), 7_u8);
434        assert_eq!(BitSeq128::ones(3).val(), 7_u128);
435    }
436
437    #[test]
438    fn as_usize() {
439        assert_eq!(B::ones(5).as_usize(), 31);
440        assert_eq!(B::zeros(5).as_usize(), 0);
441        assert_eq!(B::empty().as_usize(), 0);
442    }
443
444    #[test]
445    #[should_panic(expected = "does not fit in usize")]
446    fn as_usize_wont_truncate() {
447        // plain `as usize` on the u128 accessor would wrap silently here.
448        BitSeq128::ones(usize::BITS as usize + 1).as_usize();
449    }
450
451    #[test]
452    fn new() {
453        let b = B::new(0b10110, 5);
454        assert_eq!(b.val, 22);
455        assert_eq!(b.len, 5);
456    }
457
458    #[test]
459    fn new_rev() {
460        let b = B::new_rev(0b01101, 5);
461        assert_eq!(b.val, 22);
462        assert_eq!(b.len, 5);
463    }
464
465    #[test]
466    fn from_arr() {
467        let b = B::from([1,0,1,1,0]);
468        assert_eq!(b, B::new(0b01101, 5));
469    }
470
471    #[test]
472    fn from_iter() {
473        let b = B::from_iter([1,0,1,1,0]);
474        assert_eq!(b, B::new(0b01101, 5));
475    }
476
477    #[test]
478    fn weight() {
479        let b = B::new(0b10110, 5);
480        assert_eq!(b.weight(), 3);
481
482        let b = B::new(0b0110101101, 10);
483        assert_eq!(b.weight(), 6);
484    }
485
486    #[test]
487    fn index() {
488        let b = B::new(0b01101, 5);
489        assert_eq!(b.len(), 5);
490        assert_eq!(b[0], Bit1);
491        assert_eq!(b[1], Bit0);
492        assert_eq!(b[2], Bit1);
493        assert_eq!(b[3], Bit1);
494        assert_eq!(b[4], Bit0);
495    }
496
497    #[test]
498    fn iter() {
499        let b = B::new(0b01101, 5);
500        let v = b.iter().collect_vec();
501        assert_eq!(v, vec![Bit1, Bit0, Bit1, Bit1, Bit0])
502    }
503
504    #[test]
505    fn to_string() {
506        let b = B::new(0b01101, 5);
507        let s = b.to_string();
508        assert_eq!(s, "10110");
509    }
510
511    #[test]
512    fn set() {
513        let mut b = B::new(0b01101, 5);
514
515        b.set(0, Bit1);
516        assert_eq!(b, B::new(0b01101, 5));
517
518        b.set(1, Bit0);
519        assert_eq!(b, B::new(0b01101, 5));
520
521        b.set(2, Bit0);
522        assert_eq!(b, B::new(0b01001, 5));
523
524        b.set(3, Bit0);
525        assert_eq!(b, B::new(0b00001, 5));
526
527        b.set(4, Bit1);
528        assert_eq!(b, B::new(0b10001, 5));
529    }
530
531    #[test]
532    fn remove() {
533        let mut b = B::new(0b100101, 6);
534
535        b.remove(0);
536        assert_eq!(b, B::new(0b10010, 5));
537
538        b.remove(2);
539        assert_eq!(b, B::new(0b1010, 4));
540
541        b.remove(3);
542        assert_eq!(b, B::new(0b010, 3));
543
544        b.remove(2);
545        assert_eq!(b, B::new(0b10, 2));
546
547        b.remove(1);
548        assert_eq!(b, B::new(0b0, 1));
549
550        b.remove(0);
551        assert_eq!(b, B::new(0b0, 0));
552    }
553
554    #[test]
555    fn remove_at_max_len() {
556        // dropping the top bit of a full-length sequence.
557        let n = B::MAX_LEN;
558
559        let mut b = B::ones(n);
560        b.remove(n - 1);
561        assert_eq!(b, B::ones(n - 1));
562
563        let mut b = B::zeros(n);
564        b.set_1(n - 1);
565        b.remove(n - 1);
566        assert_eq!(b, B::zeros(n - 1));
567    }
568
569    #[test]
570    fn insert() {
571        let mut b = B::empty();
572
573        b.insert(0, Bit1);
574        assert_eq!(b, B::new(0b1, 1));
575
576        b.insert(0, Bit0);
577        assert_eq!(b, B::new(0b10, 2));
578
579        b.insert(2, Bit0);
580        assert_eq!(b, B::new(0b010, 3));
581
582        b.insert(3, Bit1);
583        assert_eq!(b, B::new(0b1010, 4));
584    }
585
586    #[test]
587    fn push() {
588        let mut b = B::new(0b01101, 5);
589
590        b.push(Bit0);
591        assert_eq!(b, B::new(0b001101, 6));
592
593        b.push(Bit1);
594        assert_eq!(b, B::new(0b1001101, 7));
595    }
596
597    #[test]
598    fn push_by_add() {
599        let mut b = B::new(0b01101, 5);
600
601        b += Bit::Bit0;
602        assert_eq!(b, B::new(0b001101, 6));
603
604        b += Bit::Bit1;
605        assert_eq!(b, B::new(0b1001101, 7));
606    }
607
608    #[test]
609    fn append() {
610        let mut b0 = B::new(0b10110, 5);
611        let b1 = B::new(0b0101, 4);
612
613        b0.append(b1);
614
615        assert_eq!(b0, B::new(0b010110110, 9));
616    }
617
618    #[test]
619    fn append_empty_to_full() {
620        let full = B::ones(B::MAX_LEN);
621
622        let mut b = full;
623        b.append(B::empty());
624
625        assert_eq!(b, full);
626    }
627
628    #[test]
629    fn append_by_add() {
630        let mut b0 = B::new(0b10110, 5);
631        let b1 = B::new(0b0101, 4);
632
633        b0 += b1;
634
635        assert_eq!(b0, B::new(0b010110110, 9));
636    }
637
638    #[test]
639    fn generate() {
640        let v = B::generate(3).collect_vec();
641        assert_eq!(v, vec![
642            B::new(0b000, 3),
643            B::new(0b001, 3),
644            B::new(0b010, 3),
645            B::new(0b011, 3),
646            B::new(0b100, 3),
647            B::new(0b101, 3),
648            B::new(0b110, 3),
649            B::new(0b111, 3),
650        ]);
651    }
652
653    #[test]
654    fn ord() {
655        // order priority: len > weight > val
656
657        let b0 = B::new(0b0,  1);
658        let b1 = B::new(0b00, 2);
659
660        assert!(b0 < b1);
661
662        let b0 = B::new(0b110, 3);
663        let b1 = B::new(0b100, 3);
664        let b2 = B::new(0b011, 3);
665
666        assert!(b0 > b1);
667        assert!(b1 < b2);
668        assert!(b0 > b2);
669    }
670
671    #[test]
672    fn sub() {
673        let b = B::new(0b10110, 5);
674
675        assert_eq!(b.sub(0), B::empty());
676        assert_eq!(b.sub(3), B::new(0b110, 3));
677        assert_eq!(b.sub(5), b);
678    }
679
680    #[test]
681    fn is_sub() {
682        let b0 = B::new(0b110,   3);
683        let b1 = B::new(0b10110, 5);
684        let b2 = B::new(0b11110, 5);
685
686        assert!(b0.is_sub(&b1));
687        assert!(b0.is_sub(&b2));
688        assert!(!b1.is_sub(&b0));
689        assert!(!b1.is_sub(&b2));
690        assert!(!b2.is_sub(&b0));
691        assert!(!b2.is_sub(&b1));
692    }
693
694    #[test]
695    fn edit() {
696        let b = B::new(0b10110, 5);
697        let c = b.edit(|b| b.set_1(0));
698        assert_eq!(c, B::new(0b10111, 5))
699    }
700
701    #[test]
702    fn u128_long() {
703        type B128 = BitSeq<u128>;
704
705        assert_eq!(B128::MAX_LEN, 128);
706
707        let mut b = B128::zeros(100);
708        assert_eq!(b.len(), 100);
709        assert_eq!(b.weight(), 0);
710
711        b.set_1(72);
712        b.set_1(99);
713        assert_eq!(b.weight(), 2);
714        assert_eq!(b[72], Bit1);
715        assert_eq!(b[71], Bit0);
716
717        let ones = B128::ones(128);
718        assert_eq!(ones.len(), 128);
719        assert_eq!(ones.weight(), 128);
720
721        let s = b.to_string();
722        assert_eq!(s.len(), 100);
723        assert_eq!(B128::from_str(&s).unwrap(), b);
724    }
725
726    #[cfg(feature = "serde")]
727    #[test]
728    fn serialize() {
729        let b = B::new(0b10110, 5);
730        let ser = serde_json::to_string(&b).unwrap();
731        assert_eq!(ser, "\"01101\"");
732
733        let des = serde_json::from_str(&ser).unwrap();
734        assert_eq!(b, des);
735    }
736}
yui_core/conc/misc/bitseq.rs

yui_core/conc/misc/
bitseq.rs
