Struct sucds::int_vectors::dacs_byte::DacsByte

pub struct DacsByte { /* private fields */ }

Compressed integer sequence using Directly Addressable Codes (DACs) in a simple bytewise scheme.

DACs are a compact representation of an integer sequence consisting of many small values. DacsByte is a simple variant and uses Vec<u8> for each level to obtain faster operations than DacsOpt.

Memory complexity

$\textrm{DAC}(A) + o(\textrm{DAC}(A)/b) + O(\lg u)$ bits where

• $u$ is the maximum value plus 1,
• $b$ is the length in bits assigned for each level with DACs (here $b = 8$), and
• $\textrm{DAC}(A)$ is the length in bits of the encoded sequence from an original sequence $A$ with DACs.

Examples

use sucds::int_vectors::{DacsByte, Access};

let seq = DacsByte::from_slice(&[5, 0, 100000, 334])?;

assert_eq!(seq.access(0), Some(5));
assert_eq!(seq.access(1), Some(0));
assert_eq!(seq.access(2), Some(100000));
assert_eq!(seq.access(3), Some(334));

assert_eq!(seq.len(), 4);
assert_eq!(seq.num_levels(), 3);

References

• N. R. Brisaboa, S. Ladra, and G. Navarro, “DACs: Bringing direct access to variable-length codes.” Information Processing & Management, 49(1), 392-404, 2013.

Implementations

impl DacsByte

pub fn from_slice<T>(vals: &[T]) -> Result<Self>where T: ToPrimitive,

Builds DACs by assigning 8 bits to represent each level.

Arguments

• vals: Slice of integers to be stored.

Errors

An error is returned if vals contains an integer that cannot be cast to usize.

pub const fn iter(&self) -> Iter<'_>

Creates an iterator for enumerating integers.

Examples

use sucds::int_vectors::DacsByte;

let seq = DacsByte::from_slice(&[5, 0, 100000, 334])?;
let mut it = seq.iter();

assert_eq!(it.next(), Some(5));
assert_eq!(it.next(), Some(0));
assert_eq!(it.next(), Some(100000));
assert_eq!(it.next(), Some(334));
assert_eq!(it.next(), None);

pub fn len(&self) -> usize

Gets the number of integers.

pub fn is_empty(&self) -> bool

Checks if the vector is empty.

pub fn num_levels(&self) -> usize

Gets the number of levels.

pub fn widths(&self) -> Vec<usize>

Gets the number of bits for each level.

Trait Implementations

impl Access for DacsByte

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

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

Complexity

$O( \ell_{pos} )$ where $\ell_{pos}$ is the number of levels corresponding to the pos-th integer.

Examples

use sucds::int_vectors::{DacsByte, Access};

let seq = DacsByte::from_slice(&[5, 999, 334])?;

assert_eq!(seq.access(0), Some(5));
assert_eq!(seq.access(1), Some(999));
assert_eq!(seq.access(2), Some(334));
assert_eq!(seq.access(3), None);

impl Build for DacsByte

fn build_from_slice<T>(vals: &[T]) -> Result<Self>where T: ToPrimitive, Self: Sized,

Creates a new vector from a slice of integers vals.

This just calls Self::from_slice(). See the documentation.

impl Clone for DacsByte

fn clone(&self) -> DacsByte

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for DacsByte

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

Formats the value using the given formatter.

impl Default for DacsByte

fn default() -> Self

Returns the “default value” for a type.

impl NumVals for DacsByte

fn num_vals(&self) -> usize

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

impl PartialEq for DacsByte

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

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 DacsByte

impl StructuralEq for DacsByte

impl StructuralPartialEq for DacsByte