Struct Sequence 

pub struct Sequence<S = DefaultSelectStrategy, S0 = DefaultSelectStrategy, BV = Box<[u64]>> { /* private fields */ }

Elias-Fano representation of a non-decreasing sequence of integers.

By default bitm::CombinedSampling is used used as both a select and select0 strategy for internal bit vector (see bitm::RankSelect101111). However, either of these two strategies can be changed to bitm::BinaryRankSearch to save a bit of space (maximum about 0.39% per strategy) at the cost of slower:

• (for select) getting an item at the given index,
• (for select0) finding the index of an item with a value (exactly or at least) equal to the given.

The structure was invented by Peter Elias and, independently, Robert Fano:

• Peter Elias “Efficient storage and retrieval by content and address of static files”, J. ACM 21 (2) (1974) 246–260. doi:10.1145/321812.321820.
• Robert Mario Fano “On the number of bits required to implement an associative memory”, Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, Mass., nd (1971) 27.

Our implementation draws ideas from:

• Sebastiano Vigna “Quasi-succinct indices”, 2013, In Proceedings of the sixth ACM international conference on Web search and data mining (WSDM ’13), Association for Computing Machinery, New York, NY, USA, 83–92. https://doi.org/10.1145/2433396.2433409
• Daisuke Okanohara, Kunihiko Sadakane, “Practical entropy-compressed rank/select dictionary”, Proceedings of the Meeting on Algorithm Engineering & Expermiments, January 2007, pages 60–70, https://dl.acm.org/doi/10.5555/2791188.2791194 (Section 6 “SDarrays”)

Implementations

impl<S, S0, BV> Sequence<S, S0, BV>

pub fn len(&self) -> usize

Returns number of stored values.

pub fn is_empty(&self) -> bool

Returns whether the sequence is empty.

pub fn bits_per_lo(&self) -> u8

impl<S, S0, BV: Deref<Target = [u64]>> Sequence<S, S0, BV>

pub fn iter(&self) -> Iterator<'_, S, S0, BV>

Returns iterator over self values.

pub fn diffs(&self) -> DiffIterator<'_, S, S0, BV>

Returns an iterator that gives the value of the first item followed by the differences between the values of subsequent items.

pub fn begin(&self) -> Cursor<'_, S, S0, BV>

Returns cursor that points to the first item of self.

pub fn end(&self) -> Cursor<'_, S, S0, BV>

Returns cursor that points past the end.

pub fn write_bytes(&self) -> usize

Returns number of bytes which write will write.

pub fn write(&self, output: &mut dyn Write) -> Result<()>

Writes self to the output.

impl Sequence

pub fn with_items_from_slice<I: Into<u64> + Clone>(items: &[I]) -> Self

Constructs Sequence filled with elements from the items slice, which must be in non-decreasing order.

pub fn read(input: &mut dyn Read) -> Result<Self>

Reads self from the input.

impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]> + FromIterator<u64>> Sequence<S, S0, BV>

pub fn read_s(input: &mut dyn Read) -> Result<Self>

Reads self from the input.

Custom select strategies do not have to be the same as the ones used by the written sequence.

impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: BitVec + DerefMut<Target = [u64]>> Sequence<S, S0, BV>

pub fn with_items_from_slice_s<I: Into<u64> + Clone>(items: &[I]) -> Self

Constructs Sequence with custom select strategy and filled with elements from the items slice, which must be in non-decreasing order.

impl<S: SelectForRank101111, S0, BV: Deref<Target = [u64]>> Sequence<S, S0, BV>

pub unsafe fn get_unchecked(&self, index: usize) -> u64

Returns value at given index. The result is undefined if index is out of bounds.

pub fn get(&self, index: usize) -> Option<u64>

Returns value at given index or None if index is out of bounds.

pub fn get_or_panic(&self, index: usize) -> u64

Returns value at given index or panics if index is out of bounds.

pub unsafe fn diff_unchecked(&self, index: usize) -> u64

Returns difference between the value at given index and the previous value. If index is 0, returns value at index 0,just like Self::get_unchecked. The result is undefined if index is out of bounds.

pub fn diff(&self, index: usize) -> Option<u64>

Returns difference between the value at given index and the previous value. If index is 0, returns value at index 0, just like Self::get. Returns None if index is out of bounds.

pub fn diff_or_panic(&self, index: usize) -> u64

Returns difference between the value at given index and the previous value. If index is 0, returns value at index 0, just like Self::get_or_panic. Panics if index is out of bounds.

pub unsafe fn cursor_at_unchecked(&self, index: usize) -> Cursor<'_, S, S0, BV>

Returns valid cursor that points to given index of self. Result is undefined if index is out of bounds.

pub unsafe fn cursor_at(&self, index: usize) -> Option<Cursor<'_, S, S0, BV>>

Returns valid cursor that points to given index of self, or None if index is out of bounds.

impl<S, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> Sequence<S, S0, BV>

pub fn geq_cursor(&self, value: u64) -> Cursor<'_, S, S0, BV>

Returns the cursor pointed to the first self item with value greater than or equal to given value.

pub fn geq_index(&self, value: u64) -> usize

Returns the index of the first self item with value greater than or equal to given value.

pub fn cursor_of(&self, value: u64) -> Option<Cursor<'_, S, S0, BV>>

Returns the cursor pointing to the first occurrence of value or None if self does not contain value.

pub fn index_of(&self, value: u64) -> Option<usize>

Returns the index of the first occurrence of value or None if self does not contain value.

Trait Implementations

impl<S, S0, BV> GetSize for Sequence<S, S0, BV>

where RankSelect101111<S, S0, BV>: GetSize,

const USES_DYN_MEM: bool = true

true if and only if the variables of this type can use dynamic (heap) memory.

fn size_bytes_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self. Same as self.size_bytes() - std::mem::size_of_val(self).

fn size_bytes_content_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self content. It usually equals to size_bytes_dyn(). However, sometimes it is smaller by the amount of memory reserved but not yet used (e.g., size_bytes_content_dyn() only takes into account the length of the vector and not its capacity).

fn size_bytes(&self) -> usize

Returns approximate, total (including heap memory) number of bytes occupied by self.

impl<'ef, S, S0, BV: Deref<Target = [u64]>> IntoIterator for &'ef Sequence<S, S0, BV>

type Item = u64

The type of the elements being iterated over.

type IntoIter = Iterator<'ef, S, S0, BV>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<S, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> Rank for Sequence<S, S0, BV>

unsafe fn rank_unchecked(&self, value: usize) -> usize

Returns the number of self items with values less than given value.

fn try_rank(&self, value: usize) -> Option<usize>

Returns the number of self items with values less than given value.

fn rank(&self, index: usize) -> usize

Returns the number of ones in first index bits or panics if index is out of bounds.

fn try_rank0(&self, index: usize) -> Option<usize>

Returns the number of zeros in first index bits or None if index is out of bounds.

fn rank0(&self, index: usize) -> usize

Returns the number of zeros in first index bits or panics if index is out of bounds.

unsafe fn rank0_unchecked(&self, index: usize) -> usize

Returns the number of ones in first index bits. The result is undefined if index is out of bounds.

impl<S: SelectForRank101111, S0, BV: Deref<Target = [u64]>> Select for Sequence<S, S0, BV>

unsafe fn select_unchecked(&self, rank: usize) -> usize

Returns the position of the rank-th one (counting from 0) in self. The result is undefined if there are no such many ones in self.

fn try_select(&self, rank: usize) -> Option<usize>

Returns the position of the rank-th one (counting from 0) in self or None if there are no such many ones in self.

fn select(&self, rank: usize) -> usize

Returns the position of the rank-th one (counting from 0) in self or panics if there are no such many ones in self.