Skip to content

Instantly share code, notes, and snippets.

@sketchpunk
Created May 22, 2019 17:08
Show Gist options
  • Save sketchpunk/48968a1ddb0fd079b162250d1e840985 to your computer and use it in GitHub Desktop.
Save sketchpunk/48968a1ddb0fd079b162250d1e840985 to your computer and use it in GitHub Desktop.
Simple Bitset in Rust
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