Struct PrefixSumVec 

pub struct PrefixSumVec<T, Idx = usize> { /* private fields */ }

A data structure for space-efficient storage of repeating sequences.

Much like Vec, this is a growable array-like type. This data structure is capaable of storing a contiguous sequence of repeating values only once, thus “compressing” the representation of the sequence. Conversely index lookups are O(log n), rather than O(1) as provided by Vec.

Note, however, that this data structure can become less space-efficient than a plain Vec if the data is incompressible.

Examples

let mut prefix_sum_vec = prefix_sum_vec::PrefixSumVec::new();

prefix_sum_vec.try_push_many(12, "strings").expect("could not push");
assert_eq!(prefix_sum_vec.max_index(), Some(&11));

assert_eq!(prefix_sum_vec[0], "strings");
assert_eq!(prefix_sum_vec[11], "strings");

Implementations

impl<T, Idx> PrefixSumVec<T, Idx>

pub fn new() -> Self

Create a new, empty PrefixSumVec.

Does not allocate.

pub fn clear(&mut self)

Clears the data structure, removing all contained values.

This method has no effect on the allocated capacity. Due to the compressed representation, a repeating value in a contiguous sequence is dropped only once.

pub fn max_index(&self) -> Option<&Idx>

Get the current maximum index that can be used for indexing this data structure.

Will return None while this data structure contains no elements. In practice this is the number of elements contained within data structure minus one.

Complexity: O(1)

impl<T, Idx: Ord> PrefixSumVec<T, Idx>

pub fn get(&self, index: &Idx) -> Option<&T>

Find the value by an index.

If the value at this index is not present in the data structure, None is returned.

Complexity: O(log n)

impl<T, Idx: Index> PrefixSumVec<T, Idx>

pub fn try_push_many( &mut self, count: Idx, value: T, ) -> Result<(), TryPushError>

Append count copies of a value to the back of the collection.

This method will not inspect the values currently stored in the data structure in search for further compression opportunities. Instead the provided value will be stored compressed as-if a sequence of count repeating values were provided.

Complexity: O(1) amortized.

impl<T: PartialEq, Idx: Index> PrefixSumVec<T, Idx>

pub fn try_push_more( &mut self, count: Idx, value: T, ) -> Result<(), TryPushError>

Append count copies of a value to the back of the collection, attempting compression.

This method will not inspect the values currently stored in the data structure in search for further compression opportunities. Instead the provided value will be stored compressed as-if a sequence of count repeating values were provided.

Complexity: O(1) amortized.

Trait Implementations

impl<T: Debug, Idx: Debug> Debug for PrefixSumVec<T, Idx>

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

Formats the value using the given formatter.

impl<K, Idx: Ord> Index<&Idx> for PrefixSumVec<K, Idx>

type Output = K

The returned type after indexing.

fn index(&self, index: &Idx) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K, Idx: Ord> Index<Idx> for PrefixSumVec<K, Idx>

type Output = K

The returned type after indexing.

fn index(&self, index: Idx) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, T, Idx> IntoIterator for &'a PrefixSumVec<T, Idx>

type Item = (&'a Idx, &'a T)

The type of the elements being iterated over.

type IntoIter = CompressedIter<'a, T, Idx>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.