Skip to main content

SparseVector

Struct SparseVector 

Source
pub struct SparseVector<T = f64> { /* private fields */ }
Expand description

A sparse vector: a mapping from integer index to arbitrary value, in which only the positions that differ from a default value are stored.

Because only non-default positions are kept, a vector occupies O(k) memory for k stored entries no matter how far apart the indices are, and whether they are large or negative. Indices need not be contiguous, and an index holding no explicit entry simply reports the default value.

Implementations§

Source§

impl<T> SparseVector<T>

Source

pub fn with_default(default: T) -> Self

Creates a vector whose empty positions read back as default.

Source

pub fn default_value(&self) -> &T

The value reported for every position that has no explicit entry.

There is deliberately no &mut counterpart: mutating the default has to prune, which set_default_value does.

Source

pub fn len(&self) -> usize

The number of explicitly stored entries.

Source

pub fn is_empty(&self) -> bool

Whether no entry is stored at all.

Source

pub fn contains_key(&self, index: i64) -> bool

Whether index has an explicitly stored entry.

Source

pub fn clear(&mut self)

Removes every explicit entry, keeping the default value.

Source

pub fn keys(&self) -> Vec<i64>

The indices holding an explicit entry, in ascending order.

Source

pub fn iter(&self) -> Iter<'_, T> ⓘ

Iterates the explicit entries in ascending index order, borrowing them.

Reach for this instead of elements when you do not want to allocate.

Source§

impl SparseVector<f64>

Source

pub fn new() -> Self

Creates a vector whose empty positions read back as 0.0.

This exists only for f64, where the 0 the shared semantics name is a value of the right type; for any other T use with_default.

Source§

impl<T: Clone> SparseVector<T>

Source

pub fn get(&self, index: i64) -> T

The value at index, or the default value when nothing is stored there.

Reading is total: every i64, negative, huge or far outside anything ever written, returns a value rather than failing, so this returns T and not Option<T>.

Source

pub fn elements(&self) -> Vec<Element<T>>

The explicit entries, in ascending index order.

This is the serialization shape described on Element.

Source

pub fn values(&self) -> Vec<T>

The stored values, in ascending index order.

Source§

impl<T: PartialEq> SparseVector<T>

Source

pub fn set(&mut self, index: i64, value: T) -> &mut Self

Inserts or updates value at index, returning &mut self so calls chain.

Writing a value equal to the default removes whatever was there instead of storing it: that is what keeps the structure sparse.

Source

pub fn set_default_value(&mut self, next: T)

Replaces the default value, immediately dropping every entry equal to it.

Pruning is one-way: the previous default is not remembered, so positions dropped here never come back.

Source

pub fn remove(&mut self, index: i64) -> Option<T>

Removes the explicit entry at index and returns it, if there was one.

The position subsequently reads back as the default value. Returned as an Option rather than a bool so the removed value is available; .is_some() recovers the boolean.

Source

pub fn from_elements<I>(elements: I, default: T) -> Self
where I: IntoIterator<Item = Element<T>>,

Builds a vector from a sequence of elements.

Entries equal to the default are dropped, and for a repeated index the last element wins, both because this goes through set.

Trait Implementations§

Source§

impl<T: Clone> Clone for SparseVector<T>

Source§

fn clone(&self) -> Self

An independent copy, default value included.

1.0.0 (const: unstable) · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<T: Debug> Debug for SparseVector<T>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T: Default> Default for SparseVector<T>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<'a, T> IntoIterator for &'a SparseVector<T>

Source§

type Item = Element<&'a T>

The type of the elements being iterated over.
Source§

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<T> Freeze for SparseVector<T>
where BTreeMap<i64, T>: Freeze, T: Freeze,

§

impl<T> RefUnwindSafe for SparseVector<T>

§

impl<T> Send for SparseVector<T>
where BTreeMap<i64, T>: Send, T: Send,

§

impl<T> Sync for SparseVector<T>
where BTreeMap<i64, T>: Sync, T: Sync,

§

impl<T> Unpin for SparseVector<T>
where BTreeMap<i64, T>: Unpin, T: Unpin,

§

impl<T> UnsafeUnpin for SparseVector<T>

§

impl<T> UnwindSafe for SparseVector<T>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.