yui_core/misc/
bitseq.rs

1use core::fmt;
2use std::fmt::{Display, Debug};
3use auto_impl_ops::auto_ops;
4use std::ops::{Add, AddAssign, Index};
5use std::str::FromStr;
6
7#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default, derive_more::Display, derive_more::Debug)]
8#[cfg_attr(feature = "serde", derive(serde_repr::Serialize_repr, serde_repr::Deserialize_repr))]
9#[repr(u8)]
10pub enum Bit { 
11    #[default]
12    #[display("0")]
13    #[debug("0")]
14    Bit0 = 0, 
15
16    #[display("1")]
17    #[debug("1")]
18    Bit1 = 1
19}
20
21impl Bit { 
22    pub fn is_zero(&self) -> bool { 
23        self == &Bit::Bit0
24    }
25
26    pub fn is_one(&self) -> bool { 
27        self == &Bit::Bit1
28    }
29
30    pub fn as_u64(&self) -> u64 { 
31        if self.is_zero() { 0 } else { 1 }
32    }
33}
34
35impl From<bool> for Bit {
36    fn from(b: bool) -> Self {
37        if b { 
38            Bit::Bit1
39        } else { 
40            Bit::Bit0
41        }
42    }
43}
44
45macro_rules! impl_bit_from_int {
46    ($t:ty) => {
47        impl From<$t> for Bit {
48            fn from(val: $t) -> Self {
49                match val { 
50                    0 => Bit::Bit0,
51                    1 => Bit::Bit1,
52                    _ => panic!()
53                }
54            }
55        }
56    };
57}
58
59impl_bit_from_int!(u8);
60impl_bit_from_int!(u16);
61impl_bit_from_int!(u32);
62impl_bit_from_int!(u64);
63impl_bit_from_int!(usize);
64impl_bit_from_int!(i8);
65impl_bit_from_int!(i16);
66impl_bit_from_int!(i32);
67impl_bit_from_int!(i64);
68impl_bit_from_int!(isize);
69
70#[derive(Clone, Copy, PartialEq, Eq, Hash, Default)]
71#[cfg_attr(feature = "serde", derive(serde_with::SerializeDisplay, serde_with::DeserializeFromStr))]
72pub struct BitSeq { 
73    val: u64,
74    len: usize
75}
76
77impl BitSeq { 
78    pub const MAX_LEN: usize = 64;
79
80    pub fn new(val: u64, len: usize) -> Self { 
81        assert!(len <= Self::MAX_LEN);
82        assert!(val < (1 << len));
83        Self { val, len }
84    }
85
86    pub fn new_rev(val: u64, len: usize) -> Self { 
87        let val = val.reverse_bits() >> (64 - len);
88        Self::new(val, len)
89    }
90
91    pub fn empty() -> Self { 
92        Self::new(0, 0)
93    }
94
95    pub fn zeros(len: usize) -> Self { 
96        Self::new(0, len)
97    }
98
99    pub fn ones(len: usize) -> Self { 
100        let val = (1 << len) - 1;
101        Self::new(val, len)
102    }
103
104    pub fn len(&self) -> usize { 
105        self.len
106    }
107
108    pub fn as_u64(&self) -> u64 { 
109        self.val
110    }
111
112    pub fn is_empty(&self) -> bool { 
113        self.len == 0
114    } 
115
116    pub fn weight(&self) -> usize { 
117        let mut v = self.val as usize;
118        let mut c = 0;
119        while v > 0 { 
120            v = v & (v - 1);
121            c += 1;
122        }
123        c
124    }
125
126    pub fn iter(&self) -> impl Iterator<Item = Bit> {
127        let mut val = self.val;
128        
129        (0..self.len).map(move |_| {
130            let b = val & 1;
131            val >>= 1;
132            Bit::from(b)
133        })
134    }
135
136    pub fn set(&mut self, i: usize, b: Bit) {
137        assert!(i < self.len);
138        if b.is_zero() { 
139            self.val &= !(1 << i);
140        } else { 
141            self.val |= 1 << i;
142        }
143    }
144
145    pub fn set_0(&mut self, i: usize) {
146        self.set(i, Bit::Bit0)
147    }
148
149    pub fn set_1(&mut self, i: usize) {
150        self.set(i, Bit::Bit1)
151    }
152
153    pub fn push(&mut self, b: Bit) {
154        if b.is_one() { 
155            self.val |= 1 << self.len;
156        }
157        self.len += 1;
158    }
159
160    pub fn push_0(&mut self) { 
161        self.push(Bit::Bit0)
162    }
163
164    pub fn push_1(&mut self) { 
165        self.push(Bit::Bit1)
166    }
167
168    pub fn append(&mut self, b: BitSeq) {
169        assert!(self.len + b.len <= Self::MAX_LEN);
170        self.val |= b.val << self.len;
171        self.len += b.len;
172    }
173
174    pub fn remove(&mut self, i: usize) { 
175        assert!(i < self.len);
176        
177        let a = self.val & !((1 << (i + 1)) - 1);
178        let b = self.val & ((1 << i) - 1);
179
180        self.val = a >> 1 | b;
181        self.len -= 1;
182    }
183
184    pub fn insert(&mut self, i: usize, b: Bit) { 
185        assert!(i <= self.len);
186        assert!(self.len < Self::MAX_LEN);
187
188        let mask = (1 << i) - 1;
189        let a = self.val & !mask;
190        let b = b.as_u64() << i;
191        let c = self.val & mask;
192
193        self.val = a << 1 | b | c;
194        self.len += 1;
195    }
196
197    pub fn insert_0(&mut self, i: usize) { 
198        self.insert(i, Bit::Bit0)
199    }
200
201    pub fn insert_1(&mut self, i: usize) { 
202        self.insert(i, Bit::Bit1)
203    }
204
205    pub fn edit<F>(&self, f: F) -> Self
206    where F: FnOnce(&mut BitSeq) {
207        let mut copy = *self;
208        f(&mut copy);
209        copy
210    }
211
212    pub fn sub(&self, l: usize) -> Self { 
213        assert!(l <= self.len);
214        let val = self.val & ((1 << l) - 1);
215        Self::new(val, l)
216    }
217
218    pub fn is_sub(&self, other: &Self) -> bool { 
219        self.len <= other.len && 
220        self.val == (other.val & ((1 << self.len) - 1))
221    }
222
223    pub fn generate(len: usize) -> impl Iterator<Item = BitSeq> {
224        assert!(len <= Self::MAX_LEN);
225        (0..2_u64.pow(len as u32)).map(move |v| Self::new(v, len))
226    }
227}
228
229impl<T> From<T> for BitSeq 
230where Bit: From<T> {
231    fn from(b: T) -> Self {
232        let val = if Bit::from(b).is_zero() { 0 } else { 1 };
233        Self::new(val, 1)
234    }
235}
236
237impl<T, const N: usize> From<[T; N]> for BitSeq 
238where Bit: From<T> {
239    fn from(value: [T; N]) -> Self {
240        Self::from_iter(value)
241    }
242}
243
244impl<T> FromIterator<T> for BitSeq
245where Bit: From<T> {
246    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
247        let mut val = 0;
248        let mut len = 0;
249        for b in iter.into_iter() {
250            if Bit::from(b).is_one() {
251                val |= 1 << len;
252            }
253            len += 1;
254        }
255        Self::new(val, len)
256    }
257}
258
259impl FromStr for BitSeq {
260    type Err = String;
261    fn from_str(s: &str) -> Result<Self, Self::Err> {
262        s.chars().map(|c|
263            match c { 
264                '0' => Ok(Bit::Bit0),
265                '1' => Ok(Bit::Bit1),
266                _   => Err("Invalid bit: {c}".into())
267            }
268        ).collect()
269    }
270}
271
272impl Index<usize> for BitSeq {
273    type Output = Bit;
274
275    fn index(&self, i: usize) -> &Self::Output {
276        assert!(i < self.len);
277        match (self.val >> i) & 1 { 
278            0 => &Bit::Bit0,
279            1 => &Bit::Bit1,
280            _ => panic!()
281        }
282    }
283}
284
285impl Display for BitSeq {
286    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
287        for b in self.iter() { 
288            Display::fmt(&b, f)?;
289        }
290        Ok(())
291    }
292}
293
294impl Debug for BitSeq {
295    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
296        Display::fmt(self, f)
297    }
298}
299
300
301impl PartialOrd for BitSeq {
302    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
303        Some(self.cmp(other))
304    }
305}
306
307// TODO support lex-order (using generic parameter).
308
309impl Ord for BitSeq {
310    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
311        self.len().cmp(&other.len()).then_with( ||
312            self.weight().cmp(&other.weight())
313        ).then_with(|| 
314            self.as_u64().cmp(&other.as_u64())
315        )
316    }
317}
318
319#[auto_ops]
320impl AddAssign<&BitSeq> for BitSeq {
321    fn add_assign(&mut self, rhs: &Self) {
322        self.append(*rhs);
323    }
324}
325
326#[auto_ops]
327impl AddAssign<Bit> for BitSeq {
328    fn add_assign(&mut self, b: Bit) {
329        self.push(b);
330    }
331}
332
333#[cfg(test)]
334mod tests { 
335    use Bit::*;
336    use itertools::Itertools;
337    use super::*;
338
339    #[test]
340    fn new() { 
341        let b = BitSeq::new(0b10110, 5);
342        assert_eq!(b.val, 22);
343        assert_eq!(b.len, 5);
344    }
345
346    #[test]
347    fn new_rev() { 
348        let b = BitSeq::new_rev(0b01101, 5);
349        assert_eq!(b.val, 22);
350        assert_eq!(b.len, 5);
351    }
352
353    #[test]
354    fn from_arr() { 
355        let b = BitSeq::from([1,0,1,1,0]);
356        assert_eq!(b, BitSeq::new(0b01101, 5));
357    }
358
359    #[test]
360    fn from_iter() { 
361        let b = BitSeq::from_iter([1,0,1,1,0]);
362        assert_eq!(b, BitSeq::new(0b01101, 5));
363    }
364
365    #[test]
366    fn weight() { 
367        let b = BitSeq::new(0b10110, 5);
368        assert_eq!(b.weight(), 3);
369
370        let b = BitSeq::new(0b0110101101, 10);
371        assert_eq!(b.weight(), 6);
372    }
373
374    #[test]
375    fn index() { 
376        let b = BitSeq::new(0b01101, 5);
377        assert_eq!(b.len(), 5);
378        assert_eq!(b[0], Bit1);
379        assert_eq!(b[1], Bit0);
380        assert_eq!(b[2], Bit1);
381        assert_eq!(b[3], Bit1);
382        assert_eq!(b[4], Bit0);
383    }
384
385    #[test]
386    fn iter() { 
387        let b = BitSeq::new(0b01101, 5);
388        let v = b.iter().collect_vec();
389        assert_eq!(v, vec![Bit1, Bit0, Bit1, Bit1, Bit0])
390    }
391
392    #[test]
393    fn to_string() { 
394        let b = BitSeq::new(0b01101, 5);
395        let s = b.to_string();
396        assert_eq!(s, "10110");
397    }
398
399    #[test]
400    fn set() { 
401        let mut b = BitSeq::new(0b01101, 5);
402
403        b.set(0, Bit1);
404        assert_eq!(b, BitSeq::new(0b01101, 5));
405
406        b.set(1, Bit0);
407        assert_eq!(b, BitSeq::new(0b01101, 5));
408
409        b.set(2, Bit0);
410        assert_eq!(b, BitSeq::new(0b01001, 5));
411
412        b.set(3, Bit0);
413        assert_eq!(b, BitSeq::new(0b00001, 5));
414
415        b.set(4, Bit1);
416        assert_eq!(b, BitSeq::new(0b10001, 5));
417    }
418
419    #[test]
420    fn remove() { 
421        let mut b = BitSeq::new(0b100101, 6);
422
423        b.remove(0);
424        assert_eq!(b, BitSeq::new(0b10010, 5));
425
426        b.remove(2);
427        assert_eq!(b, BitSeq::new(0b1010, 4));
428
429        b.remove(3);
430        assert_eq!(b, BitSeq::new(0b010, 3));
431
432        b.remove(2);
433        assert_eq!(b, BitSeq::new(0b10, 2));
434        
435        b.remove(1);
436        assert_eq!(b, BitSeq::new(0b0, 1));
437        
438        b.remove(0);
439        assert_eq!(b, BitSeq::new(0b0, 0));
440    }
441
442    #[test]
443    fn insert() { 
444        let mut b = BitSeq::empty();
445
446        b.insert(0, Bit1);
447        assert_eq!(b, BitSeq::new(0b1, 1));
448
449        b.insert(0, Bit0);
450        assert_eq!(b, BitSeq::new(0b10, 2));
451
452        b.insert(2, Bit0);
453        assert_eq!(b, BitSeq::new(0b010, 3));
454
455        b.insert(3, Bit1);
456        assert_eq!(b, BitSeq::new(0b1010, 4));
457    }
458
459    #[test]
460    fn push() { 
461        let mut b = BitSeq::new(0b01101, 5);
462
463        b.push(Bit0);
464        assert_eq!(b, BitSeq::new(0b001101, 6));
465
466        b.push(Bit1);
467        assert_eq!(b, BitSeq::new(0b1001101, 7));
468    }
469
470    #[test]
471    fn push_by_add() { 
472        let mut b = BitSeq::new(0b01101, 5);
473
474        b += Bit::Bit0;
475        assert_eq!(b, BitSeq::new(0b001101, 6));
476
477        b += Bit::Bit1;
478        assert_eq!(b, BitSeq::new(0b1001101, 7));
479    }
480
481    #[test]
482    fn append() { 
483        let mut b0 = BitSeq::new(0b10110, 5);
484        let b1 = BitSeq::new(0b0101, 4);
485
486        b0.append(b1);
487
488        assert_eq!(b0, BitSeq::new(0b010110110, 9));
489    }
490
491    #[test]
492    fn append_by_add() { 
493        let mut b0 = BitSeq::new(0b10110, 5);
494        let b1 = BitSeq::new(0b0101, 4);
495
496        b0 += b1;
497
498        assert_eq!(b0, BitSeq::new(0b010110110, 9));
499    }
500
501    #[test]
502    fn generate() { 
503        let v = BitSeq::generate(3).collect_vec();
504        assert_eq!(v, vec![
505            BitSeq::new(0b000, 3),
506            BitSeq::new(0b001, 3),
507            BitSeq::new(0b010, 3),
508            BitSeq::new(0b011, 3),
509            BitSeq::new(0b100, 3),
510            BitSeq::new(0b101, 3),
511            BitSeq::new(0b110, 3),
512            BitSeq::new(0b111, 3),
513        ]);
514    }
515
516    #[test]
517    fn ord() { 
518        // order priority: len > weight > val
519
520        let b0 = BitSeq::new(0b0,  1);
521        let b1 = BitSeq::new(0b00, 2);
522
523        assert!(b0 < b1);
524        
525        let b0 = BitSeq::new(0b110, 3);
526        let b1 = BitSeq::new(0b100, 3);
527        let b2 = BitSeq::new(0b011, 3);
528
529        assert!(b0 > b1);
530        assert!(b1 < b2);
531        assert!(b0 > b2);
532    }
533
534    #[test]
535    fn sub() { 
536        let b = BitSeq::new(0b10110, 5);
537
538        assert_eq!(b.sub(0), BitSeq::empty());
539        assert_eq!(b.sub(3), BitSeq::new(0b110, 3));
540        assert_eq!(b.sub(5), b);
541    }
542
543    #[test]
544    fn is_sub() { 
545        let b0 = BitSeq::new(0b110,   3);
546        let b1 = BitSeq::new(0b10110, 5);
547        let b2 = BitSeq::new(0b11110, 5);
548
549        assert!(b0.is_sub(&b1));
550        assert!(b0.is_sub(&b2));
551        assert!(!b1.is_sub(&b0));
552        assert!(!b1.is_sub(&b2));
553        assert!(!b2.is_sub(&b0));
554        assert!(!b2.is_sub(&b1));
555    }
556
557    #[test]
558    fn edit() {
559        let b = BitSeq::new(0b10110, 5);
560        let c = b.edit(|b| b.set_1(0));
561        assert_eq!(c, BitSeq::new(0b10111, 5))
562    }
563
564    #[cfg(feature = "serde")]
565    #[test]
566    fn serialize() { 
567        let b = BitSeq::new(0b10110, 5);
568        let ser = serde_json::to_string(&b).unwrap();
569        assert_eq!(ser, "\"01101\"");
570
571        let des = serde_json::from_str(&ser).unwrap();
572        assert_eq!(b, des);
573    }
574}
yui_core/misc/bitseq.rs

yui_core/misc/
bitseq.rs
