Struct BitVector 

pub struct BitVector { /* private fields */ }

An immutable bit array supporting, rank, select, and related queries.

This structure contains RawVector, which is in turn contains Vec. Because most queries require separate support structures, the bit array itself is immutable. Conversions between BitVector and RawVector are possible using the From trait. The maximum length of the vector is approximately usize::MAX bits.

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

BitVector implements the following simple_sds traits:

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

See rank_support and select_support for algorithmic details on rank/select queries. Predecessor and successor queries depend on both support structures.

The support structures are serialized as Option and hence may be missing. When BitVector is used as a part of another structure, the user should enable the required support structures after loading. This makes interoperation with other libraries easier, as the other library only has to serialize the bitvector itself. Enabling support structures is fast if they were present in the serialized data.

Examples

use simple_sds_sbwt::bit_vector::BitVector;
use simple_sds_sbwt::ops::{BitVec, Rank, Select, SelectZero, PredSucc};
use simple_sds_sbwt::raw_vector::{RawVector, AccessRaw};

let mut data = RawVector::with_len(137, false);
data.set_bit(1, true); data.set_bit(33, true); data.set_bit(95, true); data.set_bit(123, true);
let mut bv = BitVector::from(data);

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

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

// Select
bv.enable_select();
assert!(bv.supports_select());
assert_eq!(bv.select(1), Some(33));
let mut iter = bv.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)> = bv.one_iter().collect();
assert_eq!(v, vec![(0, 1), (1, 33), (2, 95), (3, 123)]);

// SelectZero
bv.enable_select_zero();
assert!(bv.supports_select_zero());
assert_eq!(bv.select_zero(2), Some(3));
let v: Vec<(usize, usize)> = bv.zero_iter().take(4).collect();
assert_eq!(v, vec![(0, 0), (1, 2), (2, 3), (3, 4)]);

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

Notes

• BitVector never panics from I/O errors.

Implementations

impl BitVector

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

Returns a copy of the source bitvector as BitVector.

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 std::iter::FromIterator;

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

Trait Implementations

impl AsRef<RawVector> for BitVector

fn as_ref(&self) -> &RawVector

Converts this type into a shared reference of the (usually inferred) input type.

impl<'a> BitVec<'a> for BitVector

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 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.

fn count_zeros(&self) -> usize

Returns the number of zeros in the bit array.

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.

impl From<BitVector> for RLVector

fn from(source: BitVector) -> Self

Converts to this type from the input type.

impl From<BitVector> for RawVector

fn from(source: BitVector) -> Self

Converts to this type from the input type.

impl From<BitVector> for SparseVector

fn from(source: BitVector) -> Self

Converts to this type from the input type.

impl From<RLVector> for BitVector

fn from(source: RLVector) -> Self

Converts to this type from the input type.

impl From<RawVector> for BitVector

fn from(data: RawVector) -> 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 FromIterator<bool> for BitVector

fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self

Creates a value from an iterator.

impl PartialEq for BitVector

fn eq(&self, other: &BitVector) -> 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 BitVector

type OneIter = OneIter<'a, Identity>

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 BitVector

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 BitVector

type OneIter = OneIter<'a, Identity>

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 BitVector

type ZeroIter = OneIter<'a, Complement>

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 BitVector

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 Eq for BitVector

impl StructuralPartialEq for BitVector