4
\$\begingroup\$

Looking for a general review.

pub struct BitVector {
    bits: Vec<u8>,
    size: usize,
}

impl BitVector {
    pub fn new() -> BitVector {
        BitVector {
            bits: Vec::new(),
            size: 0,
        }
    }

    pub fn push(&mut self, bit: bool) {
        let leftover = self.size % 8;
        if leftover == 0 {
            self.bits.push(0);
        }
        let last_byte = self.bits
            .last_mut()
            .expect("Assertion error");

        *last_byte |= (bit as u8) << leftover;
        self.size += 1;
    }

    pub fn push_all(&mut self, bits: &[bool]) {
        for bit in bits {
            self.push(*bit);
        }
    }

    pub fn append(&mut self, other: &mut BitVector) {
        let leftover = self.size % 8;
        let empty_bits = 8 - leftover;
        let len = self.bits.len();

        self.bits.append(&mut other.bits);
        self.size += other.size;

        if leftover == 0 {
            return;
        }
        for i in len..self.bits.len() {
            self.move_bits(empty_bits, i);
        }
        if (self.size - 1) / 8 != self.bits.len() - 1 {
            self.bits.pop();
        }
    }

    fn check(&self, i: usize) {
        assert!(i < self.size,
                format!("Index out of bounds. 
                Index: {} >= len: {}", i, self.size));
    }
    pub fn get(&self, i: usize) -> bool {
        self.check(i);
        (1 & (self.bits[i / 8] >> (i % 8))) != 0
    }

    pub fn put(&mut self, i: usize, bit: bool) {
        self.check(i);
        let (byte, bit_pos) = (i / 8, i % 8);
        self.bits[byte] &= !(1 << bit_pos);
        self.bits[byte] |= (bit as u8) << bit_pos;
    }

    fn move_bits(&mut self, bits: usize, i: usize) {
        let leftover = 8 - bits;
        let (from, to) = (self.bits[i], self.bits[i - 1]);
        self.bits[i - 1] = to ^ (from << leftover);
        self.bits[i] = from >> bits;
    }

    pub fn iter<'a>(&'a self) -> BitVectorIter<'a> {
        let itr = self.bits
            .iter()
            .flat_map(|byte| (0..8usize)
                .map(move |i| ((byte >> i) & 1) != 0))
            .take(self.size);

        BitVectorIter { iter: Box::new(itr) }
    }
}

pub struct BitVectorIter<'a> {
    iter: Box<std::iter::Iterator<Item = bool> + 'a>,
}
impl<'a> IntoIterator for &'a BitVector {
    type Item = bool;
    type IntoIter = BitVectorIter<'a>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}
impl<'a> Iterator for BitVectorIter<'a> {
    type Item = bool;
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.