Struct RLVector 

pub struct RLVector { /* private fields */ }

An immutable run-length encoded bitvector supporting rank, select, and related queries.

This type should be used when the bitvector contains long runs of both set and unset bits. Other bitvector types are more appropriate for dense (no long runs) and sparse (long runs of unset bits) bitvectors. The bitvector is immutable, though it would be easy to implement a mutable version by storing the blocks in a B+-tree rather than a vector. The maximum length of the vector is approximately usize::MAX bits.

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

RLVector 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::rl_vector::{RLVector, RLBuilder};

let mut builder = RLBuilder::new();
builder.try_set(18, 22);
builder.try_set(95, 15);
builder.try_set(110, 10);
builder.try_set(140, 12);
builder.set_len(200);
let rv = RLVector::from(builder);

// BitVec
assert_eq!(rv.len(), 200);
assert!(!rv.is_empty());
assert_eq!(rv.count_ones(), 59);
assert_eq!(rv.count_zeros(), 141);
assert!(rv.get(119));
assert!(!rv.get(120));
for (index, value) in rv.iter().enumerate() {
    assert_eq!(value, rv.get(index));
}

// Rank
assert!(rv.supports_rank());
assert_eq!(rv.rank(100), 27);
assert_eq!(rv.rank(130), 47);
assert_eq!(rv.rank_zero(60), 38);

// Select
assert!(rv.supports_select());
assert_eq!(rv.select(24), Some(97));
let mut iter = rv.select_iter(46);
assert_eq!(iter.next(), Some((46, 119)));
assert_eq!(iter.next(), Some((47, 140)));
let v: Vec<(usize, usize)> = rv.one_iter().take(4).collect();
assert_eq!(v, vec![(0, 18), (1, 19), (2, 20), (3, 21)]);

// SelectZero
assert!(rv.supports_select_zero());
assert_eq!(rv.select_zero(130), Some(189));
let mut iter = rv.select_zero_iter(72);
assert_eq!(iter.next(), Some((72, 94)));
assert_eq!(iter.next(), Some((73, 120)));
let v: Vec<(usize, usize)> = rv.zero_iter().take(4).collect();
assert_eq!(v, vec![(0, 0), (1, 1), (2, 2), (3, 3)]);

// PredSucc
assert!(rv.supports_pred_succ());
assert!(rv.predecessor(17).next().is_none());
assert_eq!(rv.predecessor(18).next(), Some((0, 18)));
assert_eq!(rv.predecessor(40).next(), Some((21, 39)));
assert_eq!(rv.successor(139).next(), Some((47, 140)));
assert_eq!(rv.successor(140).next(), Some((47, 140)));
assert!(rv.successor(152).next().is_none());

Notes

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

Implementations

impl RLVector

pub const CODE_SIZE: usize = 4usize

Number of bits in a code unit.

pub const BLOCK_SIZE: usize = 64usize

Number of code units in a block.

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

Returns a copy of the source bitvector as RLVector.

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

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

pub fn run_iter(&self) -> RunIter<'_>

Returns an iterator over the runs of set bits in the bitvector.

See RunIter for an example.

Trait Implementations

impl<'a> BitVec<'a> for RLVector

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 RLVector

fn clone(&self) -> RLVector

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for RLVector

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<RLBuilder> for RLVector

fn from(builder: RLBuilder) -> 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<RLVector> for SparseVector

fn from(source: RLVector) -> 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 RLVector

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

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 RLVector

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 RLVector

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 RLVector

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 RLVector

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 RLVector

impl StructuralPartialEq for RLVector