Struct BitVec

pub struct BitVec<Block: BlockType = usize> { /* private fields */ }

A bit-vector, akin to Vec<bool> but packed.

BitVec stores its bits in an array of Blocks, where Block is given as a type parameter that defaults to usize. You might find that a different Block size is preferable, but only benchmarking will tell.

Several useful methods are exported in traits, rather than inherent to BitVec. In particular, see:

• Bits::get_bit and
• BitsMut::set_bit.

You will likely want to use these traits (or bv::*) when you use BitVec.

Examples

use bv::BitVec;

let mut bv: BitVec = BitVec::new();
assert_eq!(bv.len(), 0);

bv.push(true);
bv.push(false);
bv.push(true);
assert_eq!(bv.len(), 3);

assert_eq!(bv[0], true);
assert_eq!(bv[1], false);
assert_eq!(bv[2], true);

Implementations

impl<Block: BlockType> BitVec<Block>

pub fn new() -> Self

Creates a new, empty bit-vector with a capacity of one block.

Examples

use bv::BitVec;

let mut bv: BitVec = BitVec::new();
assert_eq!(bv.len(), 0);

bv.push(true);
bv.push(false);
bv.push(true);
assert_eq!(bv.len(), 3);

assert_eq!(bv[0], true);
assert_eq!(bv[1], false);
assert_eq!(bv[2], true);

pub fn with_capacity(nbits: u64) -> Self

Creates a new, empty bit-vector with the given bit capacity.

Examples

use bv::BitVec;

let mut bv: BitVec<u16> = BitVec::with_capacity(20);
assert_eq!(bv.capacity(), 32);

pub fn with_block_capacity(nblocks: usize) -> Self

Creates a new, empty bit-vector with the given block capacity.

Examples

use bv::BitVec;

let mut bv: BitVec<u16> = BitVec::with_block_capacity(8);
assert_eq!(bv.capacity(), 128);

pub fn new_fill(value: bool, len: u64) -> Self

Creates a new bit-vector of size len, filled with all 0s or 1s depending on value.

Examples

use bv::*;

let mut bv: BitVec<u64> = BitVec::new_fill(false, 100);

assert_eq!( bv.get(0), false );
assert_eq!( bv.len(), 100 );

pub fn from_bits<B: Bits<Block = Block>>(bits: B) -> Self

Creates a new BitVec from any value implementing the Bits trait with the same block type.

pub fn len(&self) -> u64

The number of bits in the bit-vector.

Examples

use bv::BitVec;

let mut bv: BitVec = BitVec::new();
assert_eq!(bv.len(), 0);
bv.push(false);
assert_eq!(bv.len(), 1);
bv.push(false);
assert_eq!(bv.len(), 2);
bv.push(false);
assert_eq!(bv.len(), 3);

pub fn block_len(&self) -> usize

The number of blocks used by this bit-vector.

Examples

use bv::*;

let mut bv: BitVec<u64> = BitVec::new_fill(false, 100);

assert_eq!( bv.len(), 100 );
assert_eq!( bv.block_len(), 2 );

pub fn capacity(&self) -> u64

The capacity of the bit-vector in bits.

This is the number of bits that can be held without reallocating.

Examples

use bv::*;

let bv: BitVec<u64> = bit_vec![false; 100];

assert_eq!( bv.len(), 100 );
assert_eq!( bv.capacity(), 128 );

Note that this example holds because bit_vec! does not introduces excess capacity.

pub fn block_capacity(&self) -> usize

The capacity of the bit-vector in blocks.

Examples

use bv::*;

let bv: BitVec<u64> = BitVec::with_capacity(250);

assert_eq!( bv.len(), 0 );
assert_eq!( bv.block_len(), 0 );
assert_eq!( bv.capacity(), 256 );
assert_eq!( bv.block_capacity(), 4 );

Note that this example holds because bit_vec! does not introduces excess capacity.

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

Adjust the capacity to hold at least additional additional bits.

May reserve more to avoid frequent reallocations.

Examples

use bv::*;

let mut bv: BitVec<u32> = bit_vec![ false, false, true ];
assert_eq!( bv.capacity(), 32 );
bv.reserve(100);
assert!( bv.capacity() >= 103 );

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

Adjust the capacity to hold at least additional additional blocks.

May reserve more to avoid frequent reallocations.

Examples

use bv::*;

let mut bv: BitVec<u32> = bit_vec![ false, false, true ];
assert_eq!( bv.block_capacity(), 1 );
bv.block_reserve(3);
assert!( bv.block_capacity() >= 4 );

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

Adjust the capacity to hold at least additional additional bits.

Examples

use bv::*;

let mut bv: BitVec<u32> = bit_vec![ false, false, true ];
assert_eq!( bv.capacity(), 32 );
bv.reserve_exact(100);
assert_eq!( bv.capacity(), 128 );

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

Adjusts the capacity to at least additional blocks beyond those used.

Examples

use bv::*;

let mut bv: BitVec<u32> = bit_vec![ false, false, true ];
assert_eq!( bv.block_capacity(), 1 );
bv.block_reserve_exact(3);
assert_eq!( bv.block_capacity(), 4 );

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the vector as much as possible.

Examples

use bv::BitVec;

let mut bv: BitVec<u8> = BitVec::new();

for i in 0 .. 23 {
    bv.push(i % 3 == 0);
}

assert!(bv.capacity() >= 24);

bv.shrink_to_fit();
assert_eq!(bv.capacity(), 24);

pub fn into_boxed_slice(self) -> Box<[Block]>

Converts the vector into Box<[Block]>.

Note that this will not drop any excess capacity.

Examples

use bv::*;

let bv: BitVec<u8> = bit_vec![true, true, false, false, true, false, true, false];
let bs = bv.into_boxed_slice();

assert!( bs.len() >= 1 );
assert_eq!( bs[0], 0b01010011 );

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

Shortens the vector, keeping the first len elements and dropping the rest.

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

Note that this method has no effect on the capacity of the bit-vector.

Examples

use bv::*;

let mut v1: BitVec = bit_vec![ true, true, false, false ];
let     v2: BitVec = bit_vec![ true, true ];

assert_ne!( v1, v2 );

v1.truncate(2);

assert_eq!( v1, v2 );

pub fn resize(&mut self, len: u64, value: bool)

Resizes the bit-vector, filling with value if it has to grow.

Examples

use bv::*;

let     v1: BitVec = bit_vec![ true, true, false, false ];
let mut v2: BitVec = bit_vec![ true, true ];
let mut v3: BitVec = bit_vec![ true, true ];

v2.resize(4, false);
v3.resize(4, true);

assert_eq!( v1, v2 );
assert_ne!( v1, v3 );

pub fn as_slice(&self) -> BitSlice<'_, Block>

Gets a slice to a BitVec.

Examples

use bv::*;

let bv: BitVec = bit_vec![true, false, true];
let slice = bv.as_slice();

assert_eq!( slice.len(), 3 );
assert_eq!( slice[0], true );
assert_eq!( slice[1], false );
assert_eq!( slice[2], true );

pub fn as_mut_slice(&mut self) -> BitSliceMut<'_, Block>

Gets a mutable slice to a BitVec.

Examples

use bv::*;

let mut bv: BitVec = bit_vec![true, false, true];

{
    let mut slice = bv.as_mut_slice();
    slice.set_bit(1, true);
}

assert_eq!( bv[1], true );

pub fn get(&self, position: u64) -> bool

Gets the value of the bit at the given position.

This is an alias for Bits::get_bit.

Panics

If the position is out of bounds.

pub fn set(&mut self, position: u64, value: bool)

Sets the value of the bit at the given position.

This is an alias for BitsMut::set_bit.

Panics

If the position is out of bounds.

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

Adds the given bool to the end of the bit-vector.

Examples

use bv::*;

let mut bv0: BitVec = bit_vec![ ];
let     bv1: BitVec = bit_vec![ true ];
let     bv2: BitVec = bit_vec![ true, false ];
let     bv3: BitVec = bit_vec![ true, false, true ];

assert_ne!( bv0, bv1 );
assert_ne!( bv0, bv2 );
assert_ne!( bv0, bv3 );

bv0.push(true);
assert_eq!( bv0, bv1 );

bv0.push(false);
assert_eq!( bv0, bv2 );

bv0.push(true);
assert_eq!( bv0, bv3 );

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

Removes and returns the last element of the bit-vector, or None if empty.

Examples

use bv::*;

let mut bv: BitVec = bit_vec![ true, false, true ];
assert_eq!( bv.pop(), Some(true) );
assert_eq!( bv.pop(), Some(false) );
assert_eq!( bv.pop(), Some(true) );
assert_eq!( bv.pop(), None );

pub fn clear(&mut self)

Removes all elements from the bit-vector.

Does not change the capacity.

Examples

use bv::*;

let mut bv: BitVec<u32> = bit_vec![ true ];
assert_eq!( bv.len(), 1 );
assert_eq!( bv.capacity(), 32 );
bv.clear();
assert_eq!( bv.len(), 0 );
assert_eq!( bv.capacity(), 32 );

pub fn is_empty(&self) -> bool

Does the bit-vector have no elements?

Examples

use bv::*;

let mut bv: BitVec<u32> = bit_vec![ true ];
assert!( !bv.is_empty() );
bv.clear();
assert!(  bv.is_empty() );

Trait Implementations

impl<'a, Block: BlockType> BitSliceable<Range<u64>> for &'a BitVec<Block>

type Slice = BitSlice<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: Range<u64>) -> BitSlice<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<Range<u64>> for &'a mut BitVec<Block>

type Slice = BitSliceMut<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: Range<u64>) -> BitSliceMut<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeFrom<u64>> for &'a BitVec<Block>

type Slice = BitSlice<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeFrom<u64>) -> BitSlice<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeFrom<u64>> for &'a mut BitVec<Block>

type Slice = BitSliceMut<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeFrom<u64>) -> BitSliceMut<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeFull> for &'a BitVec<Block>

type Slice = BitSlice<'a, Block>

The type of the slice produced.

fn bit_slice(self, _: RangeFull) -> BitSlice<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeFull> for &'a mut BitVec<Block>

type Slice = BitSliceMut<'a, Block>

The type of the slice produced.

fn bit_slice(self, _: RangeFull) -> BitSliceMut<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeInclusive<u64>> for &'a BitVec<Block>

type Slice = BitSlice<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeInclusive<u64>) -> BitSlice<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeInclusive<u64>> for &'a mut BitVec<Block>

type Slice = BitSliceMut<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeInclusive<u64>) -> BitSliceMut<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeTo<u64>> for &'a BitVec<Block>

type Slice = BitSlice<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeTo<u64>) -> BitSlice<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeTo<u64>> for &'a mut BitVec<Block>

type Slice = BitSliceMut<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeTo<u64>) -> BitSliceMut<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeToInclusive<u64>> for &'a BitVec<Block>

type Slice = BitSlice<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeToInclusive<u64>) -> BitSlice<'a, Block>

Slices or re-slices the given object.

impl<'a, Block: BlockType> BitSliceable<RangeToInclusive<u64>> for &'a mut BitVec<Block>

type Slice = BitSliceMut<'a, Block>

The type of the slice produced.

fn bit_slice(self, range: RangeToInclusive<u64>) -> BitSliceMut<'a, Block>

Slices or re-slices the given object.

impl<Block: BlockType> Bits for BitVec<Block>

type Block = Block

The underlying block type used to store the bits of the vector.

fn bit_len(&self) -> u64

The length of the slice in bits.

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

Gets the bit at position

fn get_block(&self, position: usize) -> Block

Gets the block at position, masked as necessary.

fn get_raw_block(&self, position: usize) -> Block

Gets the block at position, without masking.

fn block_len(&self) -> usize

The length of the slice in blocks.

fn get_bits(&self, start: u64, count: usize) -> Self::Block

Gets count bits starting at bit index start, interpreted as a little-endian integer.

fn to_bit_vec(&self) -> BitVec<Self::Block>

Copies the bits into a new allocated BitVec.

impl<Block: BlockType> BitsMut for BitVec<Block>

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

Sets the bit at position to value.

fn set_block(&mut self, position: usize, value: Block)

Sets the block at position to value.

fn set_bits(&mut self, start: u64, count: usize, value: Self::Block)

Sets count bits starting at bit index start, interpreted as a little-endian integer.

impl<Block: BlockType> BitsPush for BitVec<Block>

fn push_bit(&mut self, value: bool)

Adds the given bit to the end of the bit vector.

fn pop_bit(&mut self) -> Option<bool>

Removes and returns the last bit, if any.

fn align_block(&mut self, value: bool)

Pushes value 0 or more times until the size of the bit vector is block-aligned.

fn push_block(&mut self, value: Block)

Pushes the given block onto the end of the bit vector.

impl<Block: Clone + BlockType> Clone for BitVec<Block>

fn clone(&self) -> BitVec<Block>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Block: BlockType> Debug for BitVec<Block>

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

Formats the value using the given formatter.

impl<Block: BlockType> Default for BitVec<Block>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, Block: BlockType + Deserialize<'de>> Deserialize<'de> for BitVec<Block>

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<Block: BlockType> From<Box<[Block]>> for BitVec<Block>

fn from(bb: Box<[Block]>) -> Self

Converts to this type from the input type.

impl<Block: BlockType> From<Vec<Block>> for BitVec<Block>

fn from(vec: Vec<Block>) -> Self

Converts to this type from the input type.

impl<Block: BlockType + Hash> Hash for BitVec<Block>

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<Block: BlockType> Index<u64> for BitVec<Block>

type Output = bool

The returned type after indexing.

fn index(&self, index: u64) -> &bool

Performs the indexing (container[index]) operation.

impl<Block: BlockType> Ord for BitVec<Block>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<Other: Bits> PartialEq<Other> for BitVec<Other::Block>

fn eq(&self, other: &Other) -> 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<Block: BlockType> PartialOrd for BitVec<Block>

fn partial_cmp(&self, other: &BitVec<Block>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<Block> Serialize for BitVec<Block>

where Block: Serialize + BlockType,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<Block: BlockType> Eq for BitVec<Block>