Struct sucds::int_vectors::prefix_summed_elias_fano::PrefixSummedEliasFano

pub struct PrefixSummedEliasFano { /* private fields */ }

Compressed integer sequence with prefix-summed Elias-Fano encoding.

This stores a sequence of integers by converting it into an increasing sequence in a prefix-summing manner and representing it through the Elias-Fano encoding.

Memory complexity

$n \lceil \lg \frac{N}{n} \rceil + 2n + o(n)$ bits where

• $n$ is the number of stored integers, and
• $N$ is the sum of integers plus 1.

Examples

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

let seq = PrefixSummedEliasFano::from_slice(&[5, 14, 334, 10])?;

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

assert_eq!(seq.len(), 4);
assert_eq!(seq.sum(), 363);

Credits

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

References

• P. Elias, “Efficient storage and retrieval by content and address of static files,” Journal of the ACM, 1974.
• R. Fano, “On the number of bits required to implement an associative memory,” Memorandum 61. Computer Structures Group, Project MAC, MIT, 1971.
• D. Okanohara, and K. Sadakane, “Practical Entropy-Compressed Rank/Select Dictionary,” In ALENEX, 2007.

Implementations

impl PrefixSummedEliasFano

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

Creates a new sequence from a slice of integers.

Arguments

• vals: Slice of integers to be stored.

Errors

An error is returned if

• vals contains an integer that cannot be cast to usize, or
• vals is empty.

Examples

use sucds::int_vectors::PrefixSummedEliasFano;

let seq = PrefixSummedEliasFano::from_slice(&[5, 14, 334, 10])?;

assert_eq!(seq.len(), 4);
assert_eq!(seq.sum(), 363);

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

Creates an iterator for enumerating integers.

Examples

use sucds::int_vectors::PrefixSummedEliasFano;

let seq = PrefixSummedEliasFano::from_slice(&[5, 14, 334, 10])?;
let mut it = seq.iter();

assert_eq!(it.next(), Some(5));
assert_eq!(it.next(), Some(14));
assert_eq!(it.next(), Some(334));
assert_eq!(it.next(), Some(10));
assert_eq!(it.next(), None);

pub fn len(&self) -> usize

Gets the number of integers.

pub fn is_empty(&self) -> bool

Checks if the sequence is empty.

pub const fn sum(&self) -> usize

Gets the sum of integers.

Trait Implementations

impl Access for PrefixSummedEliasFano

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

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

Complexity

Constant

Examples

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

let seq = PrefixSummedEliasFano::from_slice(&[5, 14, 334])?;
assert_eq!(seq.access(0), Some(5));
assert_eq!(seq.access(1), Some(14));
assert_eq!(seq.access(2), Some(334));
assert_eq!(seq.access(3), None);

impl Build for PrefixSummedEliasFano

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 PrefixSummedEliasFano

fn clone(&self) -> PrefixSummedEliasFano

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for PrefixSummedEliasFano

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

Formats the value using the given formatter.

impl Default for PrefixSummedEliasFano

fn default() -> PrefixSummedEliasFano

Returns the “default value” for a type.

impl NumVals for PrefixSummedEliasFano

fn num_vals(&self) -> usize

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

impl PartialEq for PrefixSummedEliasFano

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

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 PrefixSummedEliasFano

impl StructuralEq for PrefixSummedEliasFano

impl StructuralPartialEq for PrefixSummedEliasFano