Struct DenseBitSetExtended

pub struct DenseBitSetExtended { /* private fields */ }

Provides a dense BitSet implementation (only limited by available memory)

Internally, a Vec<u64> data structure is used to store information.

This structure implements BitSet, Clone, Default, Debug, Hash, PartialEq, Eq and bit operations.

Implementations

impl DenseBitSetExtended

pub fn new() -> Self

Returns a new empty DenseBitsetExtended

Example

let bs = DenseBitSetExtended::new();

pub fn with_capacity(size: usize) -> Self

Returns an empty DenseBitsetExtended with pre-allocated memory of size bits.

This is useful to avoid additional allocations is situations where the bitset’s space requirements are known in advance.

Example

let mut bs = DenseBitSetExtended::with_capacity(128);
bs.set_bit(127, true); // No additional allocation performed

pub fn from_dense_bitset(dbs: DenseBitSet) -> Self

Returns a DenseBitSetExtended extending a given DenseBitSet.

Example

let dbs = DenseBitSet::from_integer(0b111000111);
let dbse = DenseBitSetExtended::from_dense_bitset(dbs);
println!("{}", dbse.to_string())

pub fn all(&self) -> bool

Returns true if and only if all bits are set to true

pub fn any(&self) -> bool

Returns true if at least one bit is set to true

pub fn none(&self) -> bool

Returns true if all the bits are set to false

pub fn get_size(&self) -> usize

Returns the size (in bits) of the bitset

pub fn extract_u64(&self, position: usize, length: usize) -> u64

Returns an integer representation of the bitsting starting at the given position with given length (little endian convention).

Note: this method can extract up to 64 bits into an u64. For larger extractions, use subset instead.

Example

let dbs = DenseBitSet::from_integer(0b111000111);
let dbse = DenseBitSetExtended::from_dense_bitset(dbs);
println!("{}", dbse.extract_u64(2, 4)); // Extracts "0001" (displayed with leading zeros)

Panics

The function panics if length is zero

let panic_me = dbse.extract_u64(3, 0);

pub fn subset(&self, position: usize, length: usize) -> Self

Returns a DenseBitSetExtended of given length whose bits are extracted from the given position.

Example

let dbs = DenseBitSet::from_integer(0b111000111);
let dbse = DenseBitSetExtended::from_dense_bitset(dbs);
println!("{}", dbse.subset(2, 4).to_string());

pub fn insert(&mut self, other: &Self, position: usize, length: usize)

Inserts the first length bits of other at the given position in the current structure.

Example

let mut bs = DenseBitSetExtended::new();
let bs2 =
   DenseBitSetExtended::from_dense_bitset(DenseBitSet::from_integer(0b1011011101111));
bs.insert(&bs2, 60, 13);

pub fn insert_u64(&mut self, value: u64, position: usize, length: usize)

Inserts a length-bit integer as a bitset at the given position.

Example

let mut bs = DenseBitSetExtended::new();
bs.insert_u64(0b1011011101111, 50, 64);

pub fn reverse(&self) -> Self

Returns a bit-reversed bitset.

Example

let val = 66612301234;
let dbs = DenseBitSet::from_integer(val);
let ext_dbs = DenseBitSetExtended::from_dense_bitset(dbs);
println!("{}", dbs.to_string());
println!("{}", ext_dbs.reverse().to_string());

pub fn rotl(self, shift: usize) -> Self

Returns a left rotation of the bitset by shift bits.

Note: The bitset is extended by shift bits by this operation.

pub fn rotr(self, shift: usize) -> Self

Returns a right rotation of the bitset by shift bits.

pub fn from_string(s: String, radix: u32) -> Self

Constructs a DenseBitSetExtended from a provided String.

Example

let bs2 = DenseBitSetExtended::from_string(String::from("f8d5215a52b57ea0aeb294af576a0aeb"), 16);

Panics

This function expects a radix between 2 and 32 included, and will otherwise panic. This function will also panic if incorrect characters are provided.

pub fn first_set(&self) -> usize

Returns the position of the first set bit (little endian convention)

Example

let dbs = DenseBitSetExtended::from_dense_bitset( DenseBitSet::from_integer(256) ) << 12;
println!("{}", dbs.first_set());

Trait Implementations

impl BitAnd for DenseBitSetExtended

type Output = DenseBitSetExtended

The resulting type after applying the & operator.

fn bitand(self, rhs: Self) -> Self

Performs the & operation.

impl BitAndAssign for DenseBitSetExtended

fn bitand_assign(&mut self, rhs: Self)

Performs the &= operation.

impl BitOr for DenseBitSetExtended

type Output = DenseBitSetExtended

The resulting type after applying the | operator.

fn bitor(self, rhs: Self) -> Self

Performs the | operation.

impl BitOrAssign for DenseBitSetExtended

fn bitor_assign(&mut self, rhs: Self)

Performs the |= operation.

impl BitSet for DenseBitSetExtended

This is an extended implementation of the BitSet trait. It dynamically resizes the bitset as necessary to accomodate growing or shrinking operations (e.g. left shifts) and is only limited by available memory. In practice however, we (arbitrarily) limited allocation to 64000 bits.

Note: The BitSet trait must be in scope in order to use methods from this trait.

Note: The Copy trait cannot be implemented for DenseBitSetExtended (for the same reasons avec Vec).

fn set_bit(&mut self, position: usize, value: bool)

Sets the bit at index position to value.

fn get_bit(&self, position: usize) -> bool

Get the bit at index position.

fn get_weight(&self) -> u32

Returns the bitset’s Hamming weight (in other words, the number of bits set to true).

fn reset(&mut self)

This resets the bitset to its empty state.

fn to_string(self) -> String

Returns a representation of the bitset as a String.

impl BitXor for DenseBitSetExtended

type Output = DenseBitSetExtended

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Self) -> Self

Performs the ^ operation.

impl BitXorAssign for DenseBitSetExtended

fn bitxor_assign(&mut self, rhs: Self)

Performs the ^= operation.

impl Clone for DenseBitSetExtended

fn clone(&self) -> DenseBitSetExtended

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DenseBitSetExtended

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for DenseBitSetExtended

fn default() -> DenseBitSetExtended

Returns the “default value” for a type.

impl Hash for DenseBitSetExtended

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Not for DenseBitSetExtended

type Output = DenseBitSetExtended

The resulting type after applying the ! operator.

fn not(self) -> Self

Performs the unary ! operation.

impl PartialEq for DenseBitSetExtended

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Shl<usize> for DenseBitSetExtended

type Output = DenseBitSetExtended

The resulting type after applying the << operator.

fn shl(self, rhs: usize) -> Self

Performs the << operation.

impl ShlAssign<usize> for DenseBitSetExtended

fn shl_assign(&mut self, rhs: usize)

Performs the <<= operation.

impl Shr<usize> for DenseBitSetExtended

type Output = DenseBitSetExtended

The resulting type after applying the >> operator.

fn shr(self, rhs: usize) -> Self

Performs the >> operation.

impl ShrAssign<usize> for DenseBitSetExtended

fn shr_assign(&mut self, rhs: usize)

Performs the >>= operation.

impl Eq for DenseBitSetExtended