Struct bit_vec::BitVec

source ·

pub struct BitVec<B = u32> {
    pub(crate) storage: Vec<B>,
    pub(crate) nbits: usize,
}

Expand description

The bitvector type.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_elem(10, false);

// insert all primes less than 10
bv.set(2, true);
bv.set(3, true);
bv.set(5, true);
bv.set(7, true);
println!("{:?}", bv);
println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());

// flip all values in bitvector, producing non-primes less than 10
bv.negate();
println!("{:?}", bv);
println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());

// reset bitvector to empty
bv.clear();
println!("{:?}", bv);
println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());

Fields§

§storage: Vec

Internal representation of the bit vector

§nbits: usize

The number of valid bits in the internal representation

Implementations§

source §

Organises the bits into bytes, such that the first bit in the BitVec becomes the high-order bit of the first byte. If the size of the BitVec is not a multiple of eight then trailing bits will be filled-in with false.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_elem(3, true);
bv.set(1, false);

assert_eq!(bv.to_bytes(), [0b10100000]);

let mut bv = BitVec::from_elem(9, false);
bv.set(2, true);
bv.set(8, true);

assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);

source

pub fn eq_vec(&self, v: &[bool]) -> bool

Compares a BitVec to a slice of bools. Both the BitVec and slice must have the same length.

§Panics

Panics if the BitVec and slice are of different length.

§Examples

use bit_vec::BitVec;

let bv = BitVec::from_bytes(&[0b10100000]);

assert!(bv.eq_vec(&[true, false, true, false,
                    false, false, false, false]));

source

pub fn truncate(&mut self, len: usize)

Shortens a BitVec, dropping excess elements.

If len is greater than the vector’s current length, this has no effect.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_bytes(&[0b01001011]);
bv.truncate(2);
assert!(bv.eq_vec(&[false, true]));

source

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more bits to be inserted in the given BitVec. The collection may reserve more space to avoid frequent reallocations.

§Panics

Panics if the new capacity overflows usize.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_elem(3, false);
bv.reserve(10);
assert_eq!(bv.len(), 3);
assert!(bv.capacity() >= 13);

source

pub fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more bits to be inserted in the given BitVec. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

§Panics

Panics if the new capacity overflows usize.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_elem(3, false);
bv.reserve(10);
assert_eq!(bv.len(), 3);
assert!(bv.capacity() >= 13);

source

pub fn capacity(&self) -> usize

Returns the capacity in bits for this bit vector. Inserting any element less than this amount will not trigger a resizing.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::new();
bv.reserve(10);
assert!(bv.capacity() >= 10);

source

pub fn grow(&mut self, n: usize, value: bool)

Grows the BitVec in-place, adding n copies of value to the BitVec.

§Panics

Panics if the new len overflows a usize.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_bytes(&[0b01001011]);
bv.grow(2, true);
assert_eq!(bv.len(), 10);
assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]);

source

pub fn pop(&mut self) -> Option<bool>

Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::from_bytes(&[0b01001001]);
assert_eq!(bv.pop(), Some(true));
assert_eq!(bv.pop(), Some(false));
assert_eq!(bv.len(), 6);

source

pub fn push(&mut self, elem: bool)

Pushes a bool onto the end.

§Examples

use bit_vec::BitVec;

let mut bv = BitVec::new();
bv.push(true);
bv.push(false);
assert!(bv.eq_vec(&[true, false]));

source

pub fn len(&self) -> usize

Returns the total number of bits in this vector

source

pub unsafe fn set_len(&mut self, len: usize)

Sets the number of bits that this BitVec considers initialized.

§Safety

Almost certainly can cause bad stuff. Only really intended for BitSet.

source

pub fn is_empty(&self) -> bool

Returns true if there are no bits in this vector

source

pub fn clear(&mut self)

Clears all bits in this vector.

source

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the underlying storage as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the underlying storage that there is space for a few more elements/bits.

source

pub fn insert(&mut self, at: usize, bit: bool)

Inserts a given bit at index at, shifting all bits after by one

§Panics

Panics if at is out of bounds for BitVec’s length (that is, if at > BitVec::len())

§Examples

 use bit_vec::BitVec;

 let mut b = BitVec::new();

 b.push(true);
 b.push(true);
 b.insert(1, false);

 assert!(b.eq_vec(&[true, false, true]));

§Time complexity

Takes O(len) time. All items after the insertion index must be shifted to the right. In the worst case, all elements are shifted when the insertion index is 0.