Struct BitVector 

pub struct BitVector { /* private fields */ }

A bitmap with rank and select, in both directions.

The monotone forward link of section 3.4 asks all four questions of one vector: rank0 and select1 answer forward, and select0 answers backward. That is the whole reason the monotone form replaces both a forward link and a backward adjacency rather than only the forward one.

Implementations

impl BitVector

pub fn new(words: Vec<u64>, len: usize) -> Result<Self>

Builds a vector over len bits held in words, least significant bit of word zero first.

Errors

If words is not exactly the number of words len bits take, or if a bit is set in the tail past len. The second one matters: a set tail bit is counted by rank and found by select, so accepting it would mean a vector that answers questions about bits nobody wrote.

pub fn len(&self) -> usize

Bits in the vector.

pub fn is_empty(&self) -> bool

Whether the vector has no bits at all.

pub fn ones(&self) -> u64

Bits set.

pub fn zeros(&self) -> u64

Bits clear, within the length.

pub fn rank1(&self, at: usize) -> u64

Bits set strictly below at.

pub fn rank0(&self, at: usize) -> u64

Bits clear strictly below at.

pub fn select1(&self, nth: u64) -> Option<usize>

Where the nth set bit is, counting from zero, or None if there are not that many.

pub fn select0(&self, nth: u64) -> Option<usize>

Where the nth clear bit is, counting from zero, or None if there are not that many.

pub fn bytes(&self) -> usize

Bytes this costs on disk, which is the bitmap and the rank index and not the samples.

pub fn bytes_for(len: usize) -> usize

Bytes BitVector::write produces for a vector of len bits, whatever its bits are.

For a payload that puts something after a vector and has to find where it starts.

pub fn write(&self, out: &mut Vec<u8>)

Appends the bitmap and its rank index.

pub fn read(bytes: &[u8], len: usize) -> Result<Self>

Reads a vector of len bits from exactly the bytes BitVector::write produced.

The rank index is read rather than rebuilt, and then it is not checked against the bitmap. Checking would be the pass that reading it was meant to avoid. A torn index is a wrong answer from a structure section 3.1 says can be deleted without changing any answer, so the protection that matters is the section checksum above this layer, not a recount here.

Errors

If the bytes are not the length len implies, or if the tail past len is not zero.

Panics

It does not. chunks_exact hands out eight bytes and the conversion to an eight byte array is the one the compiler cannot see through.

Trait Implementations

impl Clone for BitVector

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for BitVector

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

Formats the value using the given formatter.