Struct sucds::bit_vectors::rank9sel::Rank9Sel

pub struct Rank9Sel { /* private fields */ }

Rank/select data structure over bit vectors with Vigna’s rank9 and hinted selection techniques.

This builds rank/select indices on BitVector taking

• 25% overhead of space for the rank index, and
• 3% overhead of space for the select index (together with the rank’s overhead).

Notes

In the default configuration, it does not build the select index for faster queires. To accelerate the queries, set Self::select1_hints() and Self::select0_hints().

Examples

use sucds::bit_vectors::{Rank9Sel, Access, Rank, Select};

let bv = Rank9Sel::from_bits([true, false, false, true])
    .select1_hints()
    .select0_hints();

assert_eq!(bv.len(), 4);
assert_eq!(bv.access(1), Some(false));

assert_eq!(bv.rank1(1), Some(1));
assert_eq!(bv.rank0(1), Some(0));

assert_eq!(bv.select1(1), Some(3));
assert_eq!(bv.select0(0), Some(1));

Credits

This is a yet another Rust port of succinct::rs_bit_vector.

References

• S. Vigna, “Broadword implementation of rank/select queries,” In WEA, 2008.

Implementations

impl Rank9Sel

pub fn new(bv: BitVector) -> Self

Creates a new vector from input bit vector bv.

pub fn select1_hints(self) -> Self

Builds an index for faster select1.

pub fn select0_hints(self) -> Self

Builds an index for faster select0.

pub fn from_bits<I>(bits: I) -> Selfwhere I: IntoIterator<Item = bool>,

Creates a new vector from input bit stream bits.

Arguments

• bits: Bit stream.

pub const fn bit_vector(&self) -> &BitVector

Returns the reference of the internal bit vector.

pub const fn rs_index(&self) -> &Rank9SelIndex

Returns the reference of the internal rank/select index.

pub const fn len(&self) -> usize

Returns the number of bits stored.

pub const fn is_empty(&self) -> bool

Checks if the vector is empty.

Trait Implementations

impl Access for Rank9Sel

fn access(&self, pos: usize) -> Option<bool>

Returns the pos-th bit, or None if out of bounds.

Examples

use sucds::bit_vectors::{Rank9Sel, Access};

let bv = Rank9Sel::from_bits([true, false, false]);

assert_eq!(bv.access(0), Some(true));
assert_eq!(bv.access(1), Some(false));
assert_eq!(bv.access(2), Some(false));
assert_eq!(bv.access(3), None);

impl Build for Rank9Sel

fn build_from_bits<I>( bits: I, _with_rank: bool, with_select1: bool, with_select0: bool ) -> Result<Self>where I: IntoIterator<Item = bool>, Self: Sized,

Creates a new vector from input bit stream bits.

Arguments

• bits: Bit stream.
• with_rank: Dummy.
• with_select1: Flag to enable Self::select1_hints().
• with_select0: Flag to enable Self::select0_hints().

Errors

Never.

impl Clone for Rank9Sel

fn clone(&self) -> Rank9Sel

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Rank9Sel

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

Formats the value using the given formatter.

impl Default for Rank9Sel

fn default() -> Rank9Sel

Returns the “default value” for a type.

impl NumBits for Rank9Sel

fn num_bits(&self) -> usize

Returns the number of bits stored (just wrapping Self::len()).

fn num_ones(&self) -> usize

Returns the number of bits set.

fn num_zeros(&self) -> usize

Returns the number of bits unset.

impl PartialEq for Rank9Sel

fn eq(&self, other: &Rank9Sel) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Rank for Rank9Sel

fn rank1(&self, pos: usize) -> Option<usize>

Returns the number of ones from the 0-th bit to the pos-1-th bit, or None if self.len() < pos.

Complexity

Constant

Examples

use sucds::bit_vectors::{Rank9Sel, Rank};

let bv = Rank9Sel::from_bits([true, false, false, true]);

assert_eq!(bv.rank1(1), Some(1));
assert_eq!(bv.rank1(2), Some(1));
assert_eq!(bv.rank1(3), Some(1));
assert_eq!(bv.rank1(4), Some(2));
assert_eq!(bv.rank1(5), None);

fn rank0(&self, pos: usize) -> Option<usize>

Returns the number of zeros from the 0-th bit to the pos-1-th bit, or None if self.len() < pos.

Complexity

Constant

Examples

use sucds::bit_vectors::{Rank9Sel, Rank};

let bv = Rank9Sel::from_bits([true, false, false, true]);

assert_eq!(bv.rank0(1), Some(0));
assert_eq!(bv.rank0(2), Some(1));
assert_eq!(bv.rank0(3), Some(2));
assert_eq!(bv.rank0(4), Some(2));
assert_eq!(bv.rank0(5), None);

impl Select for Rank9Sel

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

Searches the position of the k-th bit set, or None if self.num_ones() <= k.

Complexity

Logarithmic

Examples

use sucds::bit_vectors::{Rank9Sel, Select};

let bv = Rank9Sel::from_bits([true, false, false, true]).select1_hints();

assert_eq!(bv.select1(0), Some(0));
assert_eq!(bv.select1(1), Some(3));
assert_eq!(bv.select1(2), None);

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

Searches the position of the k-th bit unset, or None if self.num_zeros() <= k.

Complexity

Logarithmic

Examples

use sucds::bit_vectors::{Rank9Sel, Select};

let bv = Rank9Sel::from_bits([true, false, false, true]).select0_hints();

assert_eq!(bv.select0(0), Some(1));
assert_eq!(bv.select0(1), Some(2));
assert_eq!(bv.select0(2), None);

impl Serializable for Rank9Sel

fn serialize_into<W: Write>(&self, writer: W) -> Result<usize>

Serializes the data structure into the writer, returning the number of serialized bytes.

fn deserialize_from<R: Read>(reader: R) -> Result<Self>

Deserializes the data structure from the reader.

fn size_in_bytes(&self) -> usize

Returns the number of bytes to serialize the data structure.

fn size_of() -> Option<usize>

Returns the size of a primitive type in bytes (if the type is so).

impl Eq for Rank9Sel

impl StructuralEq for Rank9Sel

impl StructuralPartialEq for Rank9Sel