WIP: Added deserialize, Testing BitSetHEADmaster

1 files changed, 348 insertions, 0 deletions

diff --git a/src/bits.rs b/src/bits.rs
index 0f944ca..2590708 100644
--- a/src/bits.rs
+++ b/src/bits.rs
@@ -29,6 +29,20 @@ impl BitSet {
         self.len += 1;
     }
 
+    fn shift_left_once(&mut self) {
+        if self.data.len() == 0 || self.len == 0 {
+            return;
+        }
+        for i in 0..(self.data.len() - 1) {
+            self.data[i] <<= 1;
+            self.data[i] |= (self.data[i + 1] & (1 << 7)) >> 7;
+        }
+        if let Some(v) = self.data.last_mut() {
+            *v <<= 1;
+        }
+        self.len -= 1;
+    }
+
     pub fn concat(&mut self, other: &BitSet) {
         if self.len % 8 == 0 {
             self.data.extend(other.data.iter());
@@ -43,6 +57,28 @@ impl BitSet {
         self.data.extend(other_mut.data.iter().skip(1));
         self.len += len_pre_shift;
     }
+
+    pub fn start_with(&self, other: &BitSet) -> bool {
+        if other.len == 0 {
+            return true
+        }
+        if other.len > self.len {
+            return false;
+        }
+        for i in 0..(other.data.len() - 1) {
+            if self.data[i] != other.data[i] {
+                return false;
+            }
+        }
+        let mask = if other.len % 8 == 0 {
+            0xff
+        } else {
+            (0xff >> (8 - other.len % 8)) << (8 - other.len % 8)
+        };
+        let x = self.data[other.data.len() - 1] & mask;
+        let y = other.data[other.data.len() - 1] & mask;
+        x == y
+    }
 }
 
 use std::ops;
@@ -55,6 +91,28 @@ impl ops::ShrAssign<usize> for BitSet {
     }
 }
 
+impl ops::ShlAssign<usize> for BitSet {
+    fn shl_assign(&mut self, shift_size: usize) {
+        for _ in 0..shift_size {
+            self.shift_left_once();
+        }
+    }
+}
+
+impl PartialEq for BitSet {
+    fn eq(&self, other: &Self) -> bool {
+        if self.len != other.len {
+            return false;
+        }
+        for (a, b) in self.data.iter().zip(other.data.iter()) {
+            if a != b {
+                return false
+            }
+        }
+        true
+    }
+}
+
 use std::fmt;
 
 impl fmt::Debug for BitSet {
@@ -66,3 +124,293 @@ impl fmt::Debug for BitSet {
         Ok(())
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    fn bitset_from_str(s: &str) -> BitSet {
+        let mut bitset = BitSet::new();
+        for c in s.chars().rev() {
+            match c {
+                '0' => bitset.push_front_bit(0),
+                '1' => bitset.push_front_bit(1),
+                _   => {},
+            }
+        }
+        bitset
+    }
+
+    #[test]
+    fn new() {
+        let b = BitSet::new();
+        assert_eq!(b.len, 0);
+        assert_eq!(b.data.len(), 0);
+    }
+
+    #[test]
+    fn start_with_one_chunk() {
+        let a = bitset_from_str("1001001");
+        let b = bitset_from_str("1001");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_origin_multiple_chunk() {
+        let a = bitset_from_str("10010010000010001101010101111111000000000001011111");
+        let b = bitset_from_str("1001");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_multiple_chunk() {
+        let a = bitset_from_str("10010010000010001101010101111111000000000001011111");
+        let b = bitset_from_str("100100100000100011010101");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_origin_empty() {
+        let a = bitset_from_str("");
+        let b = bitset_from_str("1001");
+        assert!(!a.start_with(&b), "{:?} start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_compared_empty() {
+        let a = bitset_from_str("1001");
+        let b = bitset_from_str("");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_both_empty() {
+        let a = bitset_from_str("");
+        let b = bitset_from_str("");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_zeroes() {
+        let a = bitset_from_str("000000000000000000000000000000000000000000000000000000110");
+        let b = bitset_from_str("000000000000000000000000000000000000000000000000000000");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_ones() {
+        let a = bitset_from_str("11111111111111111111111111111111111111111111111111111010");
+        let b = bitset_from_str("11111111111111111111111111111111111111111111111111111");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_long() {
+        let a = bitset_from_str("0101010101111111111111110100101010101010101011111111111111\
+0000000000000000000000000000000000000000000000000000000000000000111111111111100000011010100\
+1010101001010101001010101001010101001010101010101001010010101010010010101010101010010");
+        let b = bitset_from_str("0101010101111111111111110100101010101010101011111111111111\
+0000000000000000000000000000000000000000000000000000000000000000111111111111100000011010100\
+1010101001010101001010101001010101001010101010101001010010101010010010101010101010");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_chunk_equal() {
+        let a = bitset_from_str("10101010");
+        let b = bitset_from_str("1");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_chunk_one_more() {
+        let a = bitset_from_str("101010100");
+        let b = bitset_from_str("1");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_chunk_one_less() {
+        let a = bitset_from_str("1010101");
+        let b = bitset_from_str("1");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_one_bit() {
+        let a = bitset_from_str("11011101111100001010111100000000");
+        let b = bitset_from_str("1");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+    #[test]
+    fn start_with_two_bit() {
+        let a = bitset_from_str("11011101111100001010111100000000");
+        let b = bitset_from_str("11");
+        assert!(a.start_with(&b), "{:?} doesn't start with {:?}", a, b);
+    }
+
+
+    #[test]
+    fn shift_left_once_one_chunk() {
+        let mut a = bitset_from_str("101");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str("01"));
+    }
+
+    #[test]
+    fn shift_left_once_multiple_chunk() {
+        let mut a = bitset_from_str("1010101010100101010100101100101010011111111111111110");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str("010101010100101010100101100101010011111111111111110"));
+    }
+
+    #[test]
+    fn shift_left_once_long() {
+        let mut a = bitset_from_str("0101010101111111111111110100101010101010101011111111111111\
+0000000000000000000000000000000000000000000000000000000000000000111111111111100000011010100\
+1010101001010101001010101001010101001010101010101001010010101010010010101010101010010");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str("101010101111111111111110100101010101010101011111111111111\
+0000000000000000000000000000000000000000000000000000000000000000111111111111100000011010100\
+1010101001010101001010101001010101001010101010101001010010101010010010101010101010010"));
+    }
+
+    #[test]
+    fn shift_left_once_one_bit() {
+        let mut a = bitset_from_str("0");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str(""));
+    }
+
+    #[test]
+    fn shift_left_once_empty() {
+        let mut a = bitset_from_str("");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str(""));
+    }
+
+    #[test]
+    fn shift_left_chunk_border_equal() {
+        let mut a = bitset_from_str("01010101");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str("1010101"));
+    }
+
+    #[test]
+    fn shift_left_chunk_border_one_more() {
+        let mut a = bitset_from_str("010101010");
+        a.shift_left_once();
+        assert_eq!(a, bitset_from_str("10101010"));
+    }
+
+    #[test]
+    fn shift_right_once_one_chunk() {
+        let mut a = bitset_from_str("101");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("0101"));
+    }
+
+    #[test]
+    fn shift_right_once_multiple_chunk() {
+        let mut a = bitset_from_str("1010101010100101010100101100101010011111111111111110");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("01010101010100101010100101100101010011111111111111110"));
+    }
+
+    #[test]
+    fn shift_right_once_long() {
+        let mut a = bitset_from_str("0101010101111111111111110100101010101010101011111111111111\
+0000000000000000000000000000000000000000000000000000000000000000111111111111100000011010100\
+1010101001010101001010101001010101001010101010101001010010101010010010101010101010010");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("00101010101111111111111110100101010101010101011111111111111\
+0000000000000000000000000000000000000000000000000000000000000000111111111111100000011010100\
+1010101001010101001010101001010101001010101010101001010010101010010010101010101010010"));
+    }
+
+    #[test]
+    fn shift_right_once_one_bit() {
+        let mut a = bitset_from_str("0");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("00"));
+    }
+
+    #[test]
+    fn shift_right_once_empty() {
+        let mut a = bitset_from_str("");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("0"));
+    }
+
+    #[test]
+    fn shift_right_chunk_border_equal() {
+        let mut a = bitset_from_str("01010101");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("001010101"));
+    }
+
+    #[test]
+    fn shift_right_chunk_border_one_more() {
+        let mut a = bitset_from_str("010101010");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("0010101010"));
+    }
+
+    #[test]
+    fn shift_right_chunk_border_one_less() {
+        let mut a = bitset_from_str("0101010");
+        a.shift_right_once();
+        assert_eq!(a, bitset_from_str("00101010"));
+    }
+
+    #[test]
+    fn concat_one_chunk() {
+        let mut a = bitset_from_str("101");
+        a.concat(&bitset_from_str("1011"));
+        assert_eq!(a, bitset_from_str("1011011"));
+    }
+
+    #[test]
+    fn concat_origin_multiple_chunk() {
+        let mut a = bitset_from_str("101010100101010010101111010110");
+        a.concat(&bitset_from_str("1011"));
+        assert_eq!(a, bitset_from_str("1010101001010100101011110101101011"));
+    }
+
+    #[test]
+    fn concat_concatenated_multiple_chunk() {
+        let mut a = bitset_from_str("1011");
+        a.concat(&bitset_from_str("101010100101010010101111010110"));
+        assert_eq!(a, bitset_from_str("1011101010100101010010101111010110"));
+    }
+
+    #[test]
+    fn concat_both_multiple_chunk() {
+        let mut a = bitset_from_str("1010100101010110101010011010101");
+        a.concat(&bitset_from_str("101010100101010010101111010110"));
+        assert_eq!(a,
+            bitset_from_str("1010100101010110101010011010101101010100101010010101111010110"));
+    }
+
+    #[test]
+    fn concat_origin_empty() {
+        let mut a = bitset_from_str("");
+        a.concat(&bitset_from_str("101010100101010010101111010110"));
+        assert_eq!(a, bitset_from_str("101010100101010010101111010110"));
+    }
+
+    #[test]
+    fn concat_concatenated_empty() {
+        let mut a = bitset_from_str("101010100101010010101111010110");
+        a.concat(&bitset_from_str(""));
+        assert_eq!(a, bitset_from_str("101010100101010010101111010110"));
+    }
+
+    #[test]
+    fn concat_both_empty() {
+        let mut a = bitset_from_str("");
+        a.concat(&bitset_from_str(""));
+        assert_eq!(a, bitset_from_str(""));
+    }
+}