Added tree to bits

1 files changed, 68 insertions, 0 deletions

diff --git a/src/bits.rs b/src/bits.rs
new file mode 100644
index 0000000..b479cc9
--- /dev/null
+++ b/src/bits.rs
@@ -0,0 +1,68 @@
+#[derive(Clone)]
+pub struct BitSet {
+    data: Vec<u8>,
+    len: usize,
+}
+
+impl BitSet {
+    pub fn new() -> BitSet {
+        BitSet { data: Vec::new(), len: 0 }
+    }
+
+    pub fn push_front_bit(&mut self, bit: u8) {
+        if bit != 0 && bit != 1 {
+            panic!("bit should be 1 or 0");
+        }
+        *self >>= 1;
+        self.data[0] |= bit << 7;
+    }
+
+    fn shift_right_once(&mut self) {
+        if self.len == self.data.len() * 8 {
+            self.data.push(0);
+        }
+        for i in (1..self.data.len()).rev() {
+            self.data[i] >>= 1;
+            self.data[i] |= (self.data[i - 1] & 1) << 7;
+        }
+        self.data[0] >>= 1;
+        self.len += 1;
+    }
+
+    pub fn concat(&mut self, other: &BitSet) {
+        if self.len % 8 == 0 {
+            self.data.extend(other.data.iter());
+            self.len += other.len;
+            return;
+        }
+
+        let mut other_mut = other.clone();
+        let len_pre_shift = other_mut.len;
+        other_mut >>= self.len % 8;
+        *self.data.last_mut().unwrap() |= other_mut.data[0];
+        self.data.extend(other_mut.data.iter().skip(1));
+        self.len += len_pre_shift;
+    }
+}
+
+use std::ops;
+
+impl ops::ShrAssign<usize> for BitSet {
+    fn shr_assign(&mut self, shift_size: usize) {
+        for _ in 0..shift_size {
+            self.shift_right_once();
+        }
+    }
+}
+
+use std::fmt;
+
+impl fmt::Debug for BitSet {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "len: {:2} data: ", self.len)?;
+        for chunk in &self.data {
+            write!(f, "{:08b} ", chunk)?;
+        }
+        Ok(())
+    }
+}