Created
May 22, 2019 17:08
-
-
Save sketchpunk/48968a1ddb0fd079b162250d1e840985 to your computer and use it in GitHub Desktop.
Simple Bitset in Rust
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const BITBLOCK_SIZE : usize = 16; | |
const BITBLOCK_SIZEF : f32 = 16.0; | |
type BitBlock = u16; | |
fn calc_block_size( n: f32 ) -> usize { ( n / BITBLOCK_SIZEF ).ceil() as usize } | |
fn calc_block( n: f32 ) -> usize { ( n / BITBLOCK_SIZEF ).floor() as usize } | |
#[derive(Debug)] | |
struct BitSet{ | |
data: Vec< BitBlock >, | |
} | |
impl BitSet{ | |
////////////////////////////////////////////////////////////////// | |
// Constructors | |
////////////////////////////////////////////////////////////////// | |
pub fn new() -> Self{ BitSet::with_size( BITBLOCK_SIZE ) } | |
pub fn with_size( size: usize ) -> Self { | |
let b_size = calc_block_size( size as f32 ); | |
let mut bs = BitSet{ data: Vec::with_capacity( b_size ) }; | |
for i in 0..b_size{ bs.data.push( 0 ); } | |
bs | |
} | |
////////////////////////////////////////////////////////////////// | |
// Methods | |
////////////////////////////////////////////////////////////////// | |
pub fn on( &mut self, bit: usize ) -> &mut Self{ | |
let b_idx = calc_block( bit as f32 ); | |
if b_idx >= self.data.len() { self.expand( b_idx ); } | |
self.data[ b_idx ] |= 1 << (bit % BITBLOCK_SIZE); | |
self | |
} | |
pub fn off( &mut self, bit: usize )-> &mut Self{ | |
let b_idx = calc_block( bit as f32 ); | |
if b_idx >= self.data.len() { self.expand( b_idx ); } | |
self.data[ b_idx ] &= !(1 << (bit % BITBLOCK_SIZE)); //Flip it to make a Masks 1011 | |
self | |
} | |
pub fn clear( &mut self ) -> &mut Self { | |
for i in 0..self.data.len(){ self.data[i] = 0; } | |
self | |
} | |
pub fn is_mask( &self, b: &BitSet ) -> bool { | |
let imax = b.data.len(); | |
if self.data.len() < imax { return false; } // If the bitset has less data then a mask, automatic false | |
for i in 0..imax{ if self.data[i] & b.data[i] != b.data[i] { return false; } } | |
true | |
} | |
////////////////////////////////////////////////////////////////// | |
// Private Helper Functions | |
////////////////////////////////////////////////////////////////// | |
fn expand( &mut self, idx: usize ){ | |
let cap = self.data.capacity(); | |
let resize = idx - (cap - 1); | |
self.data.reserve_exact( resize ); | |
for i in 0..resize{ self.data.push( 0 ); } | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment