map.rs

use std::fmt;
use super::hamt::MAP_BYTES;

#[derive(Debug)]
/// Bitmap stores MAP_BYTES bytes and allows for setting and getting on individual bits.
pub struct Bitmap {
    map: [u8; MAP_BYTES as usize]
}

impl Bitmap {
    pub fn new() -> Bitmap {
        Bitmap{map: [0; MAP_BYTES as usize]}
    }
    pub fn set(&mut self, i: u64) {
        let byte = (i / 8) as usize;
        let bit = (i % 8) as usize;
        println!("Setting bit {:?} of byte {:?}", bit, byte);
        self.map[byte] = self.map[byte] | (1 << bit) as u8
    }
    pub fn is_set(&self, i: u64) -> bool {
        let byte = (i / 8) as usize;
        let bit = (i % 8) as usize;
        println!("Getting bit {:?} of byte {:?}", bit, byte);
        let mask = 1 << bit;
        let result = self.map[byte] & mask as u8;
        println!("Mask: {:0b} Result: {:0b}", mask, result);
        !((self.map[byte] & (1 << bit) as u8) == 0)
    }
    /// Counts the number of bits set in map up to and including i.
    /// Note: It is assumed that the ith bit is 0. We've chosen to
    /// include it in case this is used to get the total number of
    /// bits set.
    pub fn pop_count(&self, i: u64) -> u32 {
        let byte = (i / 8) as usize;
        let bit = (i % 8) as u8;
        println!("Index {} is at bit {} of byte {}", i, bit, byte);
        let mut count = 0;
        for i in 0..byte {
            count += self.map[i].count_ones();
            println!("Byte: {} Count: {}", byte, count);
        }

        // Remove any leading ones we wish to ignore
        let mask = self.map[byte] << (7 - bit);

        count += mask.count_ones();
        println!("Found {} 1's for index {}", count, i);
        count
    }
}

impl fmt::Display for Bitmap {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for i in 0..self.map.len() {
            write!(f, "({}): {:0b}", i, self.map[i]);
        }
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn set_and_get() {
        let mut b = Bitmap::new();
        b.set(1);
        println!("Current: {}", b);
        b.set(7);
        println!("Current: {}", b);
        assert_eq!(b.is_set(0), false);
        assert_eq!(b.is_set(1), true);
        assert_eq!(b.is_set(2), false);
        assert_eq!(b.is_set(3), false);
        assert_eq!(b.is_set(4), false);
        assert_eq!(b.is_set(5), false);
        assert_eq!(b.is_set(6), false);
        assert_eq!(b.is_set(7), true);
    }

    #[test]
    fn pop_count() {
        let mut b  = Bitmap::new();
        for i in 0..(MAP_BYTES * 8) {
            b.set(i);
            assert_eq!(b.pop_count(15), (i + 1) as u32);
        }
    }

    #[test]
    #[should_panic]
    fn pop_count_out_of_range() {
        let mut b = Bitmap::new();
        b.pop_count(16);
    }
}