Struct sucds::darray::DArray

pub struct DArray { /* private fields */ }

Constant-time select data structure over integer sets with the dense array technique by Okanohara and Sadakane.

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

Examples

use sucds::DArray;

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

assert_eq!(da.select(0), 0);
assert_eq!(da.select(1), 3);

let mut bytes = vec![];
let size = da.serialize_into(&mut bytes).unwrap();
let other = DArray::deserialize_from(&bytes[..]).unwrap();
assert_eq!(da, other);
assert_eq!(size, bytes.len());
assert_eq!(size, da.size_in_bytes());

References

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

Implementations

impl DArray

pub fn from_bits<'a, I>(bits: I) -> Self where
    I: IntoIterator<Item = &'a bool>, 

Creates a new DArray from input bitset bits.

Arguments

• bits: List of bits.

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

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

Arguments

• writer: std::io::Write variable.

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

Deserializes the data structure from the reader.

Arguments

• reader: std::io::Read variable.

pub fn size_in_bytes(&self) -> usize

Returns the number of bytes to serialize the data structure.

pub fn select(&self, k: usize) -> usize

Searches the k-th iteger.

Arguments

• k: Select query.

Complexity

• Constant

Examples

use sucds::DArray;

let da = DArray::from_bits(&[true, false, false, true]);
assert_eq!(da.select(0), 0);
assert_eq!(da.select(1), 3);

pub const fn len(&self) -> usize

Gets the number of integers.

pub const fn is_empty(&self) -> bool

Checks if the set is empty.

Trait Implementations

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 PartialEq<DArray> 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: &DArray) -> bool

This method tests for !=.

impl Eq for DArray

impl StructuralEq for DArray

impl StructuralPartialEq for DArray