Struct sucds::bit_vectors::darray::DArray

pub struct DArray { /* private fields */ }

Constant-time select data structure over integer sets with the dense array technique.

Memory complexity

$u + o(u)$ bits for a bit vector with $u$ bits.

Notes

In the default configuration, this data structure supports only Self::select1(). If rank queries are needed, Self::enable_rank() and Self::enable_select0() must be set up.

Examples

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

let da = DArray::from_bits([true, false, false, true])
    .enable_rank()
    .enable_select0();

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

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

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

Credits

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

References

• D. Okanohara, and K. Sadakane, “Practical Entropy-Compressed Rank/Select Dictionary,” In ALENEX, 2007.

Implementations

impl DArray

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

Creates a new instance from input bit stream bits.

Arguments

• bits: Bit stream.

pub fn enable_rank(self) -> Self

Builds an index to enable rank queries.

pub fn enable_select0(self) -> Self

Builds an index to enable select0.

pub const fn has_rank(&self) -> bool

Checks if Self::enable_rank() is set.

pub const fn has_select0(&self) -> bool

Checks if Self::enable_select0() is set.

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

Returns the reference of the internal bit vector.

pub const fn s1_index(&self) -> &DArrayIndex

Returns the reference of the internal select1 index.

pub const fn s0_index(&self) -> Option<&DArrayIndex>

Returns the reference of the internal select0 index.

pub const fn r9_index(&self) -> Option<&Rank9SelIndex>

Returns the reference of the internal rank 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 DArray

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

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

Examples

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

let da = DArray::from_bits([true, false, false]);

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

impl Build for DArray

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: Flag to enable Self::enable_rank().
• with_select1: Dummy.
• with_select0: Flag to enable Self::enable_select0().

Errors

Never.

impl Clone for DArray

fn clone(&self) -> DArray

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for DArray

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

Formats the value using the given formatter.

impl Default for DArray

fn default() -> DArray

Returns the “default value” for a type.

impl NumBits for DArray

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 DArray

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

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

Panics

It panics if the index is not built by Self::enable_rank().

Examples

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

let da = DArray::from_bits([true, false, false, true]).enable_rank();

assert_eq!(da.rank1(1), Some(1));
assert_eq!(da.rank1(2), Some(1));
assert_eq!(da.rank1(3), Some(1));
assert_eq!(da.rank1(4), Some(2));
assert_eq!(da.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

Panics

It panics if the index is not built by Self::enable_rank().

Examples

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

let da = DArray::from_bits([true, false, false, true]).enable_rank();

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

impl Select for DArray

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

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

Complexity

Constant

Examples

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

let da = DArray::from_bits([true, false, false, true]);

assert_eq!(da.select1(0), Some(0));
assert_eq!(da.select1(1), Some(3));
assert_eq!(da.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

Constant

Panics

It panics if the index is not built by Self::enable_select0().

Examples

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

let da = DArray::from_bits([true, false, false, true]).enable_select0();

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

impl Serializable for DArray

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 DArray

impl StructuralEq for DArray

impl StructuralPartialEq for DArray