Struct BitVector 

pub struct BitVector { /* private fields */ }

A cache-oblivious succinct bit vector.

Implementations

impl BitVector

pub fn new(bits: &[u64], len: usize) -> Self

Create a new BitVector from a sequence of bits.

use sbits::BitVector;

let bits = vec![0b1011u64]; // bits 0, 1, 3 are set
let bv = BitVector::new(&bits, 64);
assert!(bv.get(0));
assert!(!bv.get(2));
assert_eq!(bv.rank1(4), 3); // three 1-bits in [0, 4)
assert_eq!(bv.select1(2), Some(3)); // third 1-bit is at position 3

pub fn from_ones(positions: impl Iterator<Item = usize>, len: usize) -> Self

Create a BitVector from an iterator of set-bit positions.

use sbits::BitVector;

let bv = BitVector::from_ones([0, 1, 3, 7].into_iter(), 16);
assert_eq!(bv.rank1(4), 3);
assert_eq!(bv.select1(3), Some(7));

pub fn from_parts( storage: Vec<u64>, select1_index: Vec<u32>, select0_index: Vec<u32>, len: usize, ) -> Result<Self>

Reconstruct a BitVector from its internal parts.

This is primarily intended for serialization round-trips.

pub fn to_bytes(&self) -> Vec<u8>

Serialize this bitvector to a stable binary encoding (little-endian).

Format (versioned):

• magic: 8 bytes (SBITBV01)
• len: u64
• storage_len: u64, then storage_len u64 words
• select1_len: u64, then select1_len u32 words
• select0_len: u64, then select0_len u32 words

pub fn from_bytes(bytes: &[u8]) -> Result<Self>

Deserialize a BitVector from to_bytes() output.

pub fn len(&self) -> usize

Return the total number of bits in the vector.

pub fn is_empty(&self) -> bool

Return true if the bit-vector has length 0.

pub fn heap_bytes(&self) -> usize

Heap memory usage in bytes.

pub fn get(&self, i: usize) -> bool

Return true if the bit at index i is set.

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

Return the number of set bits in the range [0, i).

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

Return the number of unset bits in the range [0, i).

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

Return the position of the $k$-th set bit (0-indexed).

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

Return the position of the $k$-th unset bit (0-indexed).

pub fn ones(&self) -> OnesIter<'_>

Return an iterator over the positions of all set bits.

pub fn zeros(&self) -> ZerosIter<'_>

Return an iterator over the positions of all unset bits (up to len).

Trait Implementations

impl Clone for BitVector

fn clone(&self) -> BitVector

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.