Struct vers_vecs::bit_vec::BitVec

pub struct BitVec { /* private fields */ }

A simple bit vector that does not support rank and select queries. It stores bits densely in 64 bit limbs. The last limb may be partially filled. Other than that, there is no overhead.

Example

use vers_vecs::{BitVec, RsVec};

let mut bit_vec = BitVec::new();
bit_vec.append_bit(0u64);
bit_vec.append_bit_u32(1u32);
bit_vec.append_word(0b1010_1010_1010_1010u64); // appends exactly 64 bits

assert_eq!(bit_vec.len(), 66);
assert_eq!(bit_vec.get(0), Some(0u64));
assert_eq!(bit_vec.get(1), Some(1u64));

Implementations

impl BitVec

pub fn new() -> Self

Create a new empty bit vector.

pub fn with_capacity(capacity: usize) -> Self

Create a new empty bit vector with the given capacity. The capacity is measured in bits.

pub fn from_zeros(len: usize) -> Self

Create a new bit vector with all zeros and the given length. The length is measured in bits.

pub fn from_ones(len: usize) -> Self

Create a new bit vector with all ones and the given length. The length is measured in bits.

pub fn from_bits(bits: &[u8]) -> Self

Construct a bit vector from a set of bits given as distinct u8 values. The constructor will take the least significant bit from each value and append it to a bit vector. All other bits are ignored.

See also: from_bits_u64

pub fn from_bits_u64(bits: &[u64]) -> Self

Construct a bit vector from a set of bits given as distinct u64 values. The constructor will take the least significant bit from each value and append it to a bit vector. All other bits are ignored.

See also: from_bits

pub fn append(&mut self, bit: bool)

Append a bit to the bit vector. The bit is given as a boolean, where true means 1 and false means 0.

pub fn drop_last(&mut self, n: usize)

Drop the last n bits from the bit vector. If more bits are dropped than the bit vector contains, the bit vector is cleared.

pub fn append_bit(&mut self, bit: u64)

Append a bit from a u64. The least significant bit is appended to the bit vector. All other bits are ignored.

pub fn append_bit_u32(&mut self, bit: u32)

Append a bit from a u32. The least significant bit is appended to the bit vector. All other bits are ignored.

pub fn append_bit_u8(&mut self, bit: u8)

Append a bit from a u8. The least significant bit is appended to the bit vector. All other bits are ignored.

pub fn append_word(&mut self, word: u64)

Append a word to the bit vector. The bits are appended in little endian order (i.e. the first bit of the word is appended first).

pub fn append_bits(&mut self, bits: u64, len: usize)

Append multiple bits to the bit vector. The bits are appended in little-endian order (i.e. the least significant bit is appended first). The number of bits to append is given by len. The bits are taken from the least significant bits of bits. All other bits are ignored.

Panics

Panics if len is larger than 64.

pub fn len(&self) -> usize

Return the length of the bit vector. The length is measured in bits.

pub fn is_empty(&self) -> bool

Return whether the bit vector is empty (contains no bits).

pub fn flip_bit(&mut self, pos: usize)

Flip the bit at the given position.

Panics

If the position is larger than the length of the vector, the function panics.

pub fn flip_bit_unchecked(&mut self, pos: usize)

Flip the bit at the given position.

Panics

If the position is larger than the length of the vector, the function will either modify unused memory or panic. This will not corrupt memory.

pub fn get(&self, pos: usize) -> Option<u64>

Return the bit at the given position. The bit takes the least significant bit of the returned u64 word. If the position is larger than the length of the vector, None is returned.

pub fn get_unchecked(&self, pos: usize) -> u64

Return the bit at the given position. The bit takes the least significant bit of the returned u64 word.

Panics

If the position is larger than the length of the vector, the function will either return unpredictable data, or panic. Use get to properly handle this case with an Option.

pub fn set(&mut self, pos: usize, value: u64) -> Result<(), &str>

Set the bit at the given position. The bit is given as a u64 value of which only the least significant bit is used.

Errors

If the position is out of range, the function will return Err with an error message, otherwise it will return an empty Ok.

pub fn set_unchecked(&mut self, pos: usize, value: u64)

Set the bit at the given position. The bit is given as a u64 value of which only the least significant bit is used.

Panics

If the position is larger than the length of the vector, the function will either do nothing, or panic. Use set to properly handle this case with a Result.

pub fn is_bit_set(&self, pos: usize) -> Option<bool>

Return whether the bit at the given position is set. If the position is larger than the length of the vector, None is returned.

pub fn is_bit_set_unchecked(&self, pos: usize) -> bool

Return whether the bit at the given position is set.

Panics

If the position is larger than the length of the vector, the function will either return unpredictable data, or panic. Use is_bit_set to properly handle this case with an Option.

pub fn get_bits(&self, pos: usize, len: usize) -> Option<u64>

Return multiple bits at the given position. The number of bits to return is given by len. At most 64 bits can be returned. If the position at the end of the query is larger than the length of the vector, None is returned (even if the query partially overlaps with the vector). If the length of the query is larger than 64, None is returned.

pub fn get_bits_unchecked(&self, pos: usize, len: usize) -> u64

Return multiple bits at the given position. The number of bits to return is given by len. At most 64 bits can be returned.

This function is always inlined, because it gains a lot from loop optimization and can utilize the processor pre-fetcher better if it is.

Errors

If the length of the query is larger than 64, unpredictable data will be returned. Use get_bits to avoid this.

Panics

If the position or interval is larger than the length of the vector, the function will either return any valid results padded with unpredictable data or panic.

pub fn count_ones(&self) -> u64

Return the number of ones in the bit vector. Since the bit vector doesn’t store additional metadata, this value is calculated. Use RsVec for constant-time rank operations.

pub fn count_zeros(&self) -> u64

Return the number of zeros in the bit vector. Since the bit vector doesn’t store additional metadata, this value is calculated. Use RsVec for constant-time rank operations. This method calls count_ones.

pub fn mask_or<'s, 'b>( &'s self, mask: &'b BitVec, ) -> Result<BitMask<'s, 'b>, String>

Mask this bit vector with another bitvector using bitwise or. The mask is applied lazily whenever an operation on the resulting vector is performed.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn apply_mask_or(&mut self, mask: &BitVec) -> Result<(), String>

Mask this bit vector with another bitvector using bitwise or. The mask is applied immediately, unlike in mask_or.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn mask_and<'s, 'b>( &'s self, mask: &'b BitVec, ) -> Result<BitMask<'s, 'b>, String>

Mask this bit vector with another bitvector using bitwise and. The mask is applied lazily whenever an operation on the resulting vector is performed.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn apply_mask_and(&mut self, mask: &BitVec) -> Result<(), String>

Mask this bit vector with another bitvector using bitwise and. The mask is applied immediately, unlike in mask_and.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn mask_xor<'s, 'b>( &'s self, mask: &'b BitVec, ) -> Result<BitMask<'s, 'b>, String>

Mask this bit vector with another bitvector using bitwise xor. The mask is applied lazily whenever an operation on the resulting vector is performed.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn apply_mask_xor(&mut self, mask: &BitVec) -> Result<(), String>

Mask this bit vector with another bitvector using bitwise xor. The mask is applied immediately, unlike in mask_xor.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn mask_custom<'s, 'b, F>( &'s self, mask: &'b BitVec, mask_op: F, ) -> Result<MaskedBitVec<'s, 'b, F>, String>

where F: Fn(u64, u64) -> u64,

Mask this bit vector with another bitvector using a custom masking operation. The mask is applied lazily whenever an operation on the resulting vector is performed.

The masking operation takes two 64 bit values which contain blocks of 64 bits each. The last block of a bit vector might contain fewer bits, and will be padded with unpredictable data. Implementations may choose to modify those padding bits without repercussions. Implementations shouldn’t use operations like bit shift, because the bit order within the vector is unspecified.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn apply_mask_custom( &mut self, mask: &BitVec, mask_op: fn(_: u64, _: u64) -> u64, ) -> Result<(), String>

Mask this bit vector with another bitvector using a custom masking operation. The mask is applied immediately, unlike in mask_custom.

The masking operation takes two 64 bit values which contain blocks of 64 bits each. The last block of a bit vector might contain fewer bits, and will be padded with unpredictable data. Implementations may choose to modify those padding bits without repercussions. Implementations shouldn’t use operations like bit shift, because the bit order within the vector is unspecified.

Errors

Returns an error if the length of the vector doesn’t match the mask length.

pub fn heap_size(&self) -> usize

Returns the number of bytes on the heap for this vector. Does not include allocated memory that isn’t used.

impl BitVec

pub fn iter(&self) -> BitVecRefIter<'_>

Returns an iterator over the elements of BitVec.

Trait Implementations

impl Clone for BitVec

fn clone(&self) -> BitVec

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BitVec

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

Formats the value using the given formatter.

impl Default for BitVec

fn default() -> BitVec

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for BitVec

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Hash for BitVec

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<'a> IntoIterator for &'a BitVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = BitVecRefIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a> IntoIterator for &'a mut BitVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = BitVecRefIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl IntoIterator for BitVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = BitVecIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl PartialEq for BitVec

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl Serialize for BitVec

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for BitVec

impl StructuralPartialEq for BitVec