monotree/
bits.rs

1//! A module for representing `BitVec` in terms of bytes slice.
2use crate::utils::*;
3use crate::*;
4use std::ops::Range;
5
6#[derive(Debug, Clone, PartialEq)]
7/// `BitVec` implementation based on bytes slice.
8pub struct Bits<'a> {
9    pub path: &'a [u8],
10    pub range: Range<BitsLen>,
11}
12
13impl<'a> Bits<'a> {
14    pub fn new(bytes: &'a [u8]) -> Self {
15        Bits {
16            path: bytes,
17            range: 0..(bytes.len() as BitsLen * 8),
18        }
19    }
20
21    /// Construct `Bits` instance by deserializing bytes slice.
22    pub fn from_bytes(bytes: &'a [u8]) -> Self {
23        let u = std::mem::size_of::<BitsLen>();
24        let start: BitsLen = bytes_to_int(&bytes[..u]);
25        let end: BitsLen = bytes_to_int(&bytes[u..2 * u]);
26        Self {
27            path: &bytes[2 * u..],
28            range: start..end,
29        }
30    }
31
32    /// Serialize `Bits` into bytes.
33    pub fn to_bytes(&self) -> Result<Vec<u8>> {
34        let start = (self.range.start / 8) as usize;
35        let end = self.range.end.div_ceil(8) as usize;
36        let mut path = self.path[start..end].to_owned();
37        let r = (self.range.start % 8) as u8;
38        if r != 0 {
39            let mask = 0xffu8 >> r;
40            path[0] &= mask;
41        }
42        let r = (self.range.end % 8) as u8;
43        if r != 0 {
44            let mask = 0xffu8 << (8 - r);
45            let last = path.len() - 1;
46            path[last] &= mask;
47        }
48        Ok([
49            &self.range.start.to_be_bytes(),
50            &self.range.end.to_be_bytes(),
51            &path[..],
52        ]
53        .concat())
54    }
55
56    /// Get the very first bit.
57    pub fn first(&self) -> bool {
58        bit(self.path, self.range.start)
59    }
60
61    pub fn len(&self) -> BitsLen {
62        self.range.end - self.range.start
63    }
64
65    pub fn is_empty(&self) -> bool {
66        self.len() == 0 || self.path.len() == 0
67    }
68
69    /// Get the first `n` bits.
70    pub fn take(&self, n: BitsLen) -> Self {
71        let x = self.range.start + n;
72        let q = nbytes_across(self.range.start, x);
73        let range = self.range.start..x;
74        Self {
75            path: &self.path[..q as usize],
76            range,
77        }
78    }
79
80    /// Skip the first `n` bits.
81    pub fn drop(&self, n: BitsLen) -> Self {
82        let x = self.range.start + n;
83        let q = x / 8;
84        let range = x % 8..self.range.end - 8 * (x / 8);
85        Self {
86            path: &self.path[q as usize..],
87            range,
88        }
89    }
90
91    /// Get length of the longest common prefix bits for the given two `Bits`.
92    pub fn len_common_bits(a: &Self, b: &Self) -> BitsLen {
93        len_lcp(a.path, &a.range, b.path, &b.range)
94    }
95}
monotree/bits.rs

monotree/
bits.rs
