Struct SparseVector 

pub struct SparseVector { /* private fields */ }

An immutable Elias-Fano encoded bitvector supporting, rank, select, and related queries.

This structure should be used for sparse bitvectors, where frequency of set bits is low. For dense bitvectors or when SelectZero is needed, BitVector is usually a better choice. Because most queries require support structures for one of the components, the bitvector itself is immutable. The maximum length of the vector is approximately usize::MAX bits.

Conversions between various BitVec types are possible using the From trait.

SparseVector supports partial multiset semantics. A multiset bitvector is one that contains duplicate values in the integer array interpretation. Queries that operate on present values work correctly with a multiset, while Rank::rank_zero and SelectZero do not. Multiset vectors can be built with SparseBuilder::multiset and SparseVector::try_from_iter.

SparseVector implements the following simple_sds traits:

• Basic functionality: BitVec
• Queries and operations: Rank, Select, SelectZero, PredSucc
• Serialization: Serialize

Examples

use simple_sds_sbwt::ops::{BitVec, Rank, Select, SelectZero, PredSucc};
use simple_sds_sbwt::sparse_vector::{SparseVector, SparseBuilder};
use std::convert::TryFrom;

let mut builder = SparseBuilder::new(137, 4).unwrap();
builder.set(1); builder.set(33); builder.set(95); builder.set(123);
let sv = SparseVector::try_from(builder).unwrap();

// BitVec
assert_eq!(sv.len(), 137);
assert!(!sv.is_empty());
assert_eq!(sv.count_ones(), 4);
assert_eq!(sv.count_zeros(), 133);
assert!(sv.get(33));
assert!(!sv.get(34));
for (index, value) in sv.iter().enumerate() {
    assert_eq!(value, sv.get(index));
}

// Rank
assert!(sv.supports_rank());
assert_eq!(sv.rank(33), 1);
assert_eq!(sv.rank(34), 2);
assert_eq!(sv.rank_zero(65), 63);

// Select
assert!(sv.supports_select());
assert_eq!(sv.select(1), Some(33));
let mut iter = sv.select_iter(2);
assert_eq!(iter.next(), Some((2, 95)));
assert_eq!(iter.next(), Some((3, 123)));
assert!(iter.next().is_none());
let v: Vec<(usize, usize)> = sv.one_iter().collect();
assert_eq!(v, vec![(0, 1), (1, 33), (2, 95), (3, 123)]);

// SelectZero
assert!(sv.supports_select_zero());
assert_eq!(sv.select_zero(35), Some(37));
let mut iter = sv.select_zero_iter(92);
assert_eq!(iter.next(), Some((92, 94)));
assert_eq!(iter.next(), Some((93, 96)));

// PredSucc
assert!(sv.supports_pred_succ());
assert!(sv.predecessor(0).next().is_none());
assert_eq!(sv.predecessor(1).next(), Some((0, 1)));
assert_eq!(sv.predecessor(2).next(), Some((0, 1)));
assert_eq!(sv.successor(122).next(), Some((3, 123)));
assert_eq!(sv.successor(123).next(), Some((3, 123)));
assert!(sv.successor(124).next().is_none());

Notes

• SparseVector never panics from I/O errors.
• All SparseVector queries are always enabled without additional support structures.

Implementations

impl SparseVector

pub fn copy_bit_vec<'a, T: BitVec<'a> + Select<'a>>(source: &'a T) -> Self

Returns a copy of the source bitvector as SparseVector.

The copy is created by iterating over the set bits using Select::one_iter. From implementations from other bitvector types should generally use this function.

Examples

use simple_sds_sbwt::bit_vector::BitVector;
use simple_sds_sbwt::ops::BitVec;
use simple_sds_sbwt::sparse_vector::SparseVector;
use std::iter::FromIterator;

let source: Vec<bool> = vec![true, false, true, true, false, true, true, false];
let bv = BitVector::from_iter(source);
let sv = SparseVector::copy_bit_vec(&bv);
assert_eq!(sv.len(), bv.len());
assert_eq!(sv.count_ones(), bv.count_ones());
assert!(!sv.is_multiset());

pub fn try_from_iter<T: Iterator<Item = usize> + DoubleEndedIterator + ExactSizeIterator>( iter: T, ) -> Result<SparseVector, &'static str>

Builds a vector from the values in the iterator using multiset semantics.

Returns an error message if the values are not sorted. Universe size is set to be barely large enough for the values.

Examples

use simple_sds_sbwt::sparse_vector::SparseVector;
use simple_sds_sbwt::ops::{BitVec, Select};

let source: Vec<usize> = vec![3, 4, 4, 7, 11, 19];
let sv = SparseVector::try_from_iter(source.iter().cloned()).unwrap();
assert_eq!(sv.len(), 20);
assert_eq!(sv.count_ones(), source.len());
assert!(sv.is_multiset());

for (index, value) in sv.one_iter() {
    assert_eq!(value, source[index]);
}

pub fn is_multiset(&self) -> bool

Returns true if the vector is a multiset (contains duplicate values).

This method is somewhat expensive, as it iterates over the vector.

Trait Implementations

impl<'a> BitVec<'a> for SparseVector

type Iter = Iter<'a>

Iterator type over the bit array.

fn len(&self) -> usize

Returns the length of the bit array or the universe size of the integer array.

fn count_ones(&self) -> usize

Returns the length of the integer array or the number of ones in the bit array.

fn count_zeros(&self) -> usize

Returns the number of zeros in the bit array.

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

Reads a bit from the bit array.

fn iter(&'a self) -> Self::Iter

Returns an iterator over the bit array.

fn is_empty(&self) -> bool

Returns true if the bitvector is empty.

impl Clone for SparseVector

fn clone(&self) -> SparseVector

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseVector

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

Formats the value using the given formatter.

impl From<BitVector> for SparseVector

fn from(source: BitVector) -> Self

Converts to this type from the input type.

impl From<RLVector> for SparseVector

fn from(source: RLVector) -> Self

Converts to this type from the input type.

impl From<SparseVector> for BitVector

fn from(source: SparseVector) -> Self

Converts to this type from the input type.

impl From<SparseVector> for RLVector

fn from(source: SparseVector) -> Self

Converts to this type from the input type.

impl PartialEq for SparseVector

fn eq(&self, other: &SparseVector) -> 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<'a> PredSucc<'a> for SparseVector

type OneIter = OneIter<'a>

Iterator type over (index, value) pairs in the integer array.

fn supports_pred_succ(&self) -> bool

Returns true if predecessor/successor support has been enabled.

fn enable_pred_succ(&mut self)

Enables predecessor/successor support for the vector.

fn predecessor(&'a self, value: usize) -> Self::OneIter

Returns an iterator at the largest v <= value in the integer array.

fn successor(&'a self, value: usize) -> Self::OneIter

Returns an iterator at the smallest v >= value in the integer array.

impl<'a> Rank<'a> for SparseVector

fn supports_rank(&self) -> bool

Returns true if rank support has been enabled.

fn enable_rank(&mut self)

Enables rank support for the vector.

fn rank(&self, index: usize) -> usize

Returns the number of indexes i < index in the bit array such that self.get(i) == true.

fn rank_zero(&self, index: usize) -> usize

Returns the number of indexes i < index in the bit array such that self.get(i) == false.

impl<'a> Select<'a> for SparseVector

type OneIter = OneIter<'a>

Iterator type over (index, value) pairs in the integer array.

fn supports_select(&self) -> bool

Returns true if select support has been enabled.

fn enable_select(&mut self)

Enables select support for the vector.

fn one_iter(&'a self) -> Self::OneIter

Returns an iterator over the integer array.

fn select(&'a self, rank: usize) -> Option<usize>

Returns the specified value in the integer array or None if no such value exists.

fn select_iter(&'a self, rank: usize) -> Self::OneIter

Returns an iterator at the specified rank in the integer array.

impl<'a> SelectZero<'a> for SparseVector

type ZeroIter = ZeroIter<'a>

Iterator type over (index, value) pairs in the complement of the integer array.

fn supports_select_zero(&self) -> bool

Returns true if select support has been enabled for the complement.

fn enable_select_zero(&mut self)

Enables select support for the complement vector.

fn zero_iter(&'a self) -> Self::ZeroIter

Returns an iterator over the integer array of the complement vector.

fn select_zero(&'a self, rank: usize) -> Option<usize>

Returns the specified value in the complement of the integer array or None if no such value exists.

fn select_zero_iter(&'a self, rank: usize) -> Self::ZeroIter

Returns an iterator at the specified rank in the complement of the integer array.

impl Serialize for SparseVector

fn serialize_header<T: Write>(&self, writer: &mut T) -> Result<()>

Serializes the header to the writer.

fn serialize_body<T: Write>(&self, writer: &mut T) -> Result<()>

Serializes the body to the writer.

fn load<T: Read>(reader: &mut T) -> Result<Self>

Loads the struct from the reader.

fn size_in_elements(&self) -> usize

Returns the size of the serialized struct in u64 elements.

fn serialize<T: Write>(&self, writer: &mut T) -> Result<()>

Serializes the struct to the writer.

fn size_in_bytes(&self) -> usize

Returns the size of the serialized struct in bytes.

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.

impl Eq for SparseVector

impl StructuralPartialEq for SparseVector