Struct SparseBuilder 

pub struct SparseBuilder { /* private fields */ }

Space-efficient SparseVector construction.

A SparseBuilder allocates the data structures based on universe size (bitvector length) and the number of set bits. The set bits must then be indicated in order using SparseBuilder::set or the Extend trait. Once the builder is full, it can be converted into a SparseVector using the TryFrom trait. The conversion will not fail if the builder is full.

Setting a bit i fails if the builder is full or the index is too small (i < self.next_index()) or too large (i > self.universe()). Extend::extend will panic in such situations.

Examples

use simple_sds_sbwt::ops::BitVec;
use simple_sds_sbwt::sparse_vector::{SparseVector, SparseBuilder};
use std::convert::TryFrom;

let mut builder = SparseBuilder::new(300, 5).unwrap();
assert_eq!(builder.len(), 0);
assert_eq!(builder.capacity(), 5);
assert_eq!(builder.universe(), 300);
assert_eq!(builder.next_index(), 0);
assert!(!builder.is_full());
assert!(!builder.is_multiset());

builder.set(12);
assert_eq!(builder.len(), 1);
assert_eq!(builder.next_index(), 13);

// This will return an error because the index is too small.
let _ = builder.try_set(10);
assert_eq!(builder.len(), 1);
assert_eq!(builder.next_index(), 13);

let v: Vec<usize> = vec![24, 48, 96, 192];
builder.extend(v);
assert_eq!(builder.len(), 5);
assert!(builder.is_full());

let sv = SparseVector::try_from(builder).unwrap();
assert_eq!(sv.len(), 300);
assert_eq!(sv.count_ones(), 5);

Implementations

impl SparseBuilder

pub fn new(universe: usize, ones: usize) -> Result<SparseBuilder, &'static str>

Returns an empty SparseBuilder without multiset semantics.

Returns Err if ones > universe.

Arguments

• universe: Universe size or length of the bitvector.
• ones: Number of bits that will be set in the bitvector.

pub fn multiset(universe: usize, ones: usize) -> SparseBuilder

Returns an empty SparseBuilder with multiset semantics.

Arguments

• universe: Universe size or length of the bitvector.
• ones: Number of bits that will be set in the bitvector.

Examples

use simple_sds_sbwt::ops::BitVec;
use simple_sds_sbwt::sparse_vector::{SparseVector, SparseBuilder};
use std::convert::TryFrom;

let mut builder = SparseBuilder::multiset(120, 3);
assert_eq!(builder.capacity(), 3);
assert_eq!(builder.universe(), 120);
assert!(builder.is_multiset());

builder.set(12);
builder.set(24);
builder.set(24);
assert!(builder.is_full());

let sv = SparseVector::try_from(builder).unwrap();
assert_eq!(sv.len(), 120);
assert_eq!(sv.count_ones(), 3);
assert!(sv.is_multiset());

pub fn is_multiset(&self) -> bool

Returns true if the builder is using multiset semantics.

pub fn len(&self) -> usize

Returns the number of bits that have already been set.

pub fn capacity(&self) -> usize

Returns the number of bits that can be set.

pub fn universe(&self) -> usize

Returns the universe size or the length of the bitvector.

pub fn next_index(&self) -> usize

Returns the smallest index in the bitvector that can still be set.

pub fn is_full(&self) -> bool

Returns true if all bits that can be set have been set.

pub fn is_empty(&self) -> bool

Returns true if no bits have been set.

Keeps Clippy happy.

pub fn set(&mut self, index: usize)

Sets the specified bit in the bitvector.

Panics

Panics if the builder is full, if index < self.next_index(), or if index >= self.universe().

pub unsafe fn set_unchecked(&mut self, index: usize)

Unsafe version of SparseBuilder::set without sanity checks.

Safety

Behavior is undefined if the builder is full, if index < self.next_index(), or if index >= self.universe().

pub fn try_set(&mut self, index: usize) -> Result<(), &'static str>

Tries to set the specified bit in the bitvector.

Returns Err if the builder is full, if index < self.next_index(), or if index >= self.universe().

Trait Implementations

impl Clone for SparseBuilder

fn clone(&self) -> SparseBuilder

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseBuilder

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

Formats the value using the given formatter.

impl Extend<usize> for SparseBuilder

fn extend<T: IntoIterator<Item = usize>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl TryFrom<SparseBuilder> for SparseVector

type Error = &'static str

The type returned in the event of a conversion error.

fn try_from(builder: SparseBuilder) -> Result<Self, Self::Error>

Performs the conversion.