Struct Sparse 

pub struct Sparse<S, T = RangeTo<usize>, I = Vec<usize>> {
    pub selection: Select<T, I>,
    pub source: S,
}

A Sparse data set S where the sparsity pattern is given by I as select indices into a larger range.

For example we can represent a sparse vector by assigning values to a selection of indices:

use flatk::{Sparse, Get, View};

let values = vec![1.0, 2.0, 3.0, 4.0];
let sparse_vector = Sparse::from_dim(vec![0,5,10,100], 1000, values);
let sparse_vector_view = sparse_vector.view();

assert_eq!(sparse_vector_view.at(0), (0, &1.0));
assert_eq!(sparse_vector_view.at(1), (5, &2.0));
assert_eq!(sparse_vector_view.at(2), (10, &3.0));
assert_eq!(sparse_vector_view.at(3), (100, &4.0));
assert_eq!(sparse_vector_view.selection.target, ..1000);

In this scenario, the target set is just the range 0..1000, however in general this can be any data set, which makes Sparse an implementation of a one-to-one mapping or a directed graph with disjoint source and target node sets.

Fields

selection: Select<T, I>

source: S

Implementations

impl<'a, S, T, I> Sparse<S, T, I>

where S: View<'a>, <S as View<'a>>::Type: Set + IntoParallelIterator, <<S as View<'a>>::Type as IntoParallelIterator>::Iter: IndexedParallelIterator, T: Set + Get<'a, usize> + View<'a> + Sync, T::Output: Send, I: AsIndexSlice + Sync,

pub fn par_iter( &'a self, ) -> impl IndexedParallelIterator<Item = (usize, <<S as View<'a>>::Type as IntoParallelIterator>::Item, <T as Get<'a, usize>>::Output)>

Produce a parallel iterator over elements (borrowed slices) of a Sparse.

impl<'a, S, T, I> Sparse<S, T, I>

where S: ViewMut<'a>, <S as ViewMut<'a>>::Type: Set + IntoParallelIterator, <<S as ViewMut<'a>>::Type as IntoParallelIterator>::Iter: IndexedParallelIterator, I: AsMut<[usize]>,

pub fn par_iter_mut( &'a mut self, ) -> Zip<IterMut<'a, usize>, <<S as ViewMut<'a>>::Type as IntoParallelIterator>::Iter>

Produce a parallel iterator over elements (borrowed slices) of a Sparse.

impl<S, I> Sparse<S, RangeTo<usize>, I>

where S: Set, I: AsIndexSlice,

pub fn from_dim(indices: I, dim: usize, values: S) -> Self

Create a sparse collection from the given set of indices, a dimension and a set of values.

The corresponding sparse collection will represent a collection of size dim which stores only the given values at the specified indices. Note that dim may be smaller than values.len(), in which case a position in the sparse data structure may contain multiple values.

Example

use flatk::*;
let v = vec![1,2,3,4,5,6];
let sparse = Sparse::from_dim(vec![0,2,0,2,0,3], 4, v.as_slice());

// The iterator traverses only non-vacant elements.
let mut iter = sparse.iter(); // Returns (position, source, target) triplets
assert_eq!(Some((0, &1, 0)), iter.next());
assert_eq!(Some((2, &2, 2)), iter.next());
assert_eq!(Some((0, &3, 0)), iter.next());
assert_eq!(Some((2, &4, 2)), iter.next());
assert_eq!(Some((0, &5, 0)), iter.next());
assert_eq!(Some((3, &6, 3)), iter.next());
assert_eq!(None, iter.next());

impl<S, T, I> Sparse<S, T, I>

where S: Set, T: Set, I: AsIndexSlice,

pub fn new(selection: Select<T, I>, source: S) -> Self

The most general constructor for a sparse collection taking a selection of values and their corresponding data.

Panics

This function will panic if selection and source have different sizes.

impl<S: Set, T, I> Sparse<S, T, I>

pub fn extend_pruned<S2, T2, I2, B>( &mut self, other: Sparse<S2, T2, I2>, combine: impl FnMut(usize, &mut B::Owned, B), keep: impl FnMut(usize, &B::Owned) -> bool, map: impl FnMut(usize, usize), )

where S2: IntoIterator<Item = B>, I2: AsIndexSlice, B: IntoOwned, Self: Push<(usize, B::Owned)>,

Extend the current sparse collection with a pruned and compressed version of the given sparse collection, other.

Each element is in the original sparse collection is guaranteed to be passed to exactly one of keep or combine.

The keep function will get the combined value of all consecutively overlapping elements, and the source index of the first element in the consecutive group.

The map function allows the caller to map between original other sparse collection and the newly populated collection self. The first parameter passed into map is the index in the output sparse array where each element is being considered for insertion. The second parameter is the position of each element in the output sparse structure. Note that map is not called on pruned elements.

Example

use flatk::*;
let v = vec![1,2,3,4,5,6];

// Create a sparse vector with overlapping elements:
// [0] -> 1            [0] -> 5
// [1] ->              [1] ->
// [2] -> 2 + 3 + 4    [2] ->
// [3] ->              [3] -> 6
let sparse = Sparse::from_dim(vec![0,2,2,2,0,3], 4, v.as_slice());

// Create an empty sparse vector.
let mut compressed = Sparse::from_dim(Vec::new(), 4, Vec::new());

// Transfer the elements from `sparse` into `compressed` while resolving the consecutive overlaps:
compressed.extend_pruned(sparse, |_pos, a, b| *a += *b, |_pos, _val| true, |_src_idx, _dst_idx, | {});
let mut iter = compressed.iter(); // Returns (position, source, target) triplets.
assert_eq!(Some((0, &1, 0)), iter.next());
assert_eq!(Some((2, &9, 2)), iter.next());
assert_eq!(Some((0, &5, 0)), iter.next());
assert_eq!(Some((3, &6, 3)), iter.next());
assert_eq!(None, iter.next());
// Note: 1 and 5 are not merged because they are not consecutive.

impl<'a, S, T, I> Sparse<S, T, I>

pub fn source(&self) -> &S

Get a reference to the underlying source data.

pub fn source_mut(&mut self) -> &mut S

Get a mutable reference to the underlying source data.

pub fn selection(&self) -> &Select<T, I>

Get a reference to the underlying selection.

pub fn selection_mut(&mut self) -> &mut Select<T, I>

pub fn indices(&self) -> &I

Get a reference to the underlying indices.

pub fn indices_mut(&mut self) -> &mut I

impl<'a, S, T, I> Sparse<S, T, I>

where S: View<'a>, <S as View<'a>>::Type: Set + IntoIterator, T: Set + Get<'a, usize> + View<'a>, I: AsIndexSlice,

pub fn iter( &'a self, ) -> impl Iterator<Item = (usize, <<S as View<'a>>::Type as IntoIterator>::Item, <T as Get<'a, usize>>::Output)>

impl<'a, S, T, I> Sparse<S, T, I>

where S: View<'a>, <S as View<'a>>::Type: Set + IntoIterator,

pub fn source_iter( &'a self, ) -> <<S as View<'a>>::Type as IntoIterator>::IntoIter

impl<'a, S, T, I> Sparse<S, T, I>

where I: AsIndexSlice,

pub fn index_iter(&'a self) -> Cloned<Iter<'a, usize>>

impl<'a, S, T, I> Sparse<S, T, I>

where S: View<'a>, <S as View<'a>>::Type: Set + IntoIterator, I: AsIndexSlice,

pub fn indexed_source_iter( &'a self, ) -> Zip<Cloned<Iter<'a, usize>>, <<S as View<'a>>::Type as IntoIterator>::IntoIter>

impl<'a, S, T, I> Sparse<S, T, I>

where S: ViewMut<'a>, <S as ViewMut<'a>>::Type: Set + IntoIterator,

A mutable iterator over the source elements in S

pub fn source_iter_mut( &'a mut self, ) -> <<S as ViewMut<'a>>::Type as IntoIterator>::IntoIter

impl<'a, S, T, I> Sparse<S, T, I>

where S: ViewMut<'a>, <S as ViewMut<'a>>::Type: Set + IntoIterator, I: AsIndexSlice,

A mutable iterator can only iterate over the source elements in S and not the target elements in T since we would need scheduling to modify potentially overlapping mutable references.

pub fn indexed_source_iter_mut( &'a mut self, ) -> impl Iterator<Item = (usize, <<S as ViewMut<'a>>::Type as IntoIterator>::Item)>

impl<'a, S, T, I> Sparse<S, T, I>

where S: ViewMut<'a>, <S as ViewMut<'a>>::Type: Set + IntoIterator, I: AsMut<[usize]>,

A mutable iterator can only iterate over the source elements in S and not the target elements in T since we would need scheduling to modify potentially overlapping mutable references.

pub fn iter_mut( &'a mut self, ) -> Zip<IterMut<'a, usize>, <<S as ViewMut<'a>>::Type as IntoIterator>::IntoIter>

impl<'a, S, T, I> Sparse<S, T, I>

where S: View<'a>, <S as View<'a>>::Type: Set + IntoIterator, I: AsMut<[usize]>,

Mutably iterate over the selected indices.

pub fn index_iter_mut( &'a mut self, ) -> impl Iterator<Item = (&'a mut usize, <<S as View<'a>>::Type as IntoIterator>::Item)>

impl<S, O, T, I> Sparse<Chunked<S, O>, T, I>

where S: Set + Truncate, O: AsRef<[usize]> + GetOffset + Truncate, I: Truncate,

pub fn trim(&mut self) -> usize

Remove any empty elements (indexed chunks) at the end of the collection and any unindexed data past the last offset. Return the number of elements removed.

Example

use flatk::*;
let mut s = Sparse::from_dim(vec![0,1,2], 3, Chunked::from_sizes(vec![1,3,2], vec![1,2,3,4,5,6]));
assert_eq!(3, s.len());

// Transferring the last two elements past the indexed stack.
// This creates an empty chunk at the end.
s.source_mut().transfer_forward(2, 2);
assert_eq!(6, s.storage().len());
assert_eq!(3, s.len());

s.trim(); // remove unindexed elements.
assert_eq!(4, s.storage().len());

Trait Implementations

impl<'a, S, T, I> AtomIterator<'a> for Sparse<S, T, I>

where S: AtomIterator<'a>,

type Item = <S as AtomIterator<'a>>::Item

type Iter = <S as AtomIterator<'a>>::Iter

fn atom_iter(&'a self) -> Self::Iter

impl<'a, S, T, I> AtomMutIterator<'a> for Sparse<S, T, I>

where S: AtomMutIterator<'a>,

type Item = <S as AtomMutIterator<'a>>::Item

type Iter = <S as AtomMutIterator<'a>>::Iter

fn atom_mut_iter(&'a mut self) -> Self::Iter

impl<S: ChunkSize, T, I> ChunkSize for Sparse<S, T, I>

fn chunk_size(&self) -> usize

impl<S: Clear, T, I: Clear> Clear for Sparse<S, T, I>

fn clear(&mut self)

Remove all elements from the current set without necessarily deallocating the space previously used.

impl<S: Clone, T: Clone, I: Clone> Clone for Sparse<S, T, I>

fn clone(&self) -> Sparse<S, T, I>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Clone, S: CloneWithStorage<U>, I: Clone, U> CloneWithStorage<U> for Sparse<S, T, I>

type CloneType = Sparse<<S as CloneWithStorage<U>>::CloneType, T, I>

fn clone_with_storage(&self, storage: U) -> Self::CloneType

impl<S: Debug, T: Debug, I: Debug> Debug for Sparse<S, T, I>

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

Formats the value using the given formatter.

impl<S: Dummy, T: Dummy, I: Dummy> Dummy for Sparse<S, T, I>

unsafe fn dummy() -> Self

Constructs a potentially invalid instance of a type.

impl<S, T> Extend<(usize, <S as Set>::Elem)> for Sparse<S, T>

where S: Set + Extend<<S as Set>::Elem>,

fn extend<It: IntoIterator<Item = (usize, <S as Set>::Elem)>>( &mut self, iter: It, )

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, S, T, I> GetIndex<'a, Sparse<S, T, I>> for &usize

where I: AsIndexSlice, S: Get<'a, usize>,

type Output = (usize, <S as Get<'a, usize>>::Output)

fn get(self, sparse: &Sparse<S, T, I>) -> Option<Self::Output>

Gets the value in the set at this index.

unsafe fn at_unchecked(self, set: &S) -> Self::Output

where Self: Sized,

Gets the value in the set at this index.

impl<'a, S, T, I> GetIndex<'a, Sparse<S, T, I>> for usize

where I: AsIndexSlice, S: Get<'a, usize>,

type Output = (usize, <S as Get<'a, usize>>::Output)

fn get(self, sparse: &Sparse<S, T, I>) -> Option<Self::Output>

Gets the value in the set at this index.

unsafe fn at_unchecked(self, set: &S) -> Self::Output

where Self: Sized,

Gets the value in the set at this index.

impl<S: IntoOwned, T: IntoOwned, I: IntoOwned> IntoOwned for Sparse<S, T, I>

type Owned = Sparse<<S as IntoOwned>::Owned, <T as IntoOwned>::Owned, <I as IntoOwned>::Owned>

fn into_owned(self) -> Self::Owned

fn clone_into(self, target: &mut Self::Owned)

impl<S, T, I> IntoOwnedData for Sparse<S, T, I>

where S: IntoOwnedData,

type OwnedData = Sparse<<S as IntoOwnedData>::OwnedData, T, I>

fn into_owned_data(self) -> Self::OwnedData

fn clone_into(self, target: &mut Self::OwnedData)

impl<S, T, I> IntoParallelIterator for Sparse<S, T, I>

where S: Send + SplitAt + SplitFirst + Set + Dummy, S::First: Send, I: Send + IndexedParallelIterator + Producer<Item = usize>, I::IntoIter: ExactSizeIterator<Item = usize>,

type Item = (usize, <S as SplitFirst>::First)

The type of item that the parallel iterator will produce.

type Iter = SparseParIter<I, S>

The parallel iterator type that will be created.

fn into_par_iter(self) -> Self::Iter

Converts self into a parallel iterator.

impl<S: IntoStorage, T, I> IntoStorage for Sparse<S, T, I>

fn into_storage(self) -> Self::StorageType

Convert the sparse set into its raw storage representation.

type StorageType = <S as IntoStorage>::StorageType

impl<S, T, I> IsolateIndex<Sparse<S, T, I>> for Range<usize>

where S: Isolate<Range<usize>>, I: Isolate<Range<usize>>,

type Output = Sparse<<S as Isolate<Range<usize>>>::Output, T, <I as Isolate<Range<usize>>>::Output>

unsafe fn isolate_unchecked(self, sparse: Sparse<S, T, I>) -> Self::Output

Attempts to isolate a value in the given set at this index.

fn try_isolate(self, sparse: Sparse<S, T, I>) -> Option<Self::Output>

Attempts to isolate a value in the given set at this index.

impl<S, T, I> IsolateIndex<Sparse<S, T, I>> for usize

where I: Isolate<usize>, <I as Isolate<usize>>::Output: Borrow<usize>, S: Isolate<usize>, T: Isolate<usize>,

type Output = (<I as Isolate<usize>>::Output, <S as Isolate<usize>>::Output, <T as Isolate<usize>>::Output)

unsafe fn isolate_unchecked(self, sparse: Sparse<S, T, I>) -> Self::Output

Attempts to isolate a value in the given set at this index.

fn try_isolate(self, sparse: Sparse<S, T, I>) -> Option<Self::Output>

Attempts to isolate a value in the given set at this index.

impl<S: MapStorage<Out>, T, I, Out> MapStorage<Out> for Sparse<S, T, I>

type Input = <S as MapStorage<Out>>::Input

type Output = Sparse<<S as MapStorage<Out>>::Output, T, I>

fn map_storage<F: FnOnce(Self::Input) -> Out>(self, f: F) -> Self::Output

impl<S: PartialEq, T: PartialEq, I: PartialEq> PartialEq for Sparse<S, T, I>

fn eq(&self, other: &Sparse<S, T, I>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<S: PermuteInPlace, T, I: PermuteInPlace> PermuteInPlace for Sparse<S, T, I>

fn permute_in_place(&mut self, permutation: &[usize], seen: &mut [bool])

impl<S, T, I, A> Push<(usize, A)> for Sparse<S, T, I>

where S: Set<Elem = A> + Push<A>, I: Push<usize>,

fn push(&mut self, (index, elem): (usize, A))

impl<S: RemovePrefix, T, I: RemovePrefix> RemovePrefix for Sparse<S, T, I>

fn remove_prefix(&mut self, n: usize)

Remove n elements from the beginning.

impl<S: Reserve, T, I: Reserve> Reserve for Sparse<S, T, I>

fn reserve_with_storage(&mut self, n: usize, storage_n: usize)

fn reserve(&mut self, n: usize)

impl<S: Set, T, I> Set for Sparse<S, T, I>

fn len(&self) -> usize

Get the length of this sparse collection.

Example

use flatk::*;
let v = vec![1,2,3,4,5];
let sparse = Sparse::from_dim(vec![0,2,2,1,1], 3, v.as_slice());
assert_eq!(5, sparse.len());

type Elem = (usize, <S as Set>::Elem)

Owned element of the set.

type Atom = <S as Set>::Atom

The most basic element contained by this collection. If this collection contains other collections, this type should be different than Elem.

fn is_empty(&self) -> bool

impl<S, T, I> SplitAt for Sparse<S, T, I>

where S: Set + SplitAt, T: Set + Clone, I: SplitAt,

fn split_at(self, mid: usize) -> (Self, Self)

Split self into two sets at the given midpoint. This function is analogous to <[T]>::split_at.

impl<S: Storage, T, I> Storage for Sparse<S, T, I>

fn storage(&self) -> &Self::Storage

Return an immutable reference to the underlying storage type of source data.

Example

use flatk::*;
let v = vec![1,2,3,4,5,6,7,8,9,10,11,12];
let s0 = Chunked3::from_flat(v.clone());
let s1 = Sparse::from_dim(vec![0, 2, 2, 0], 4, s0.clone());
assert_eq!(s1.storage(), &v);

type Storage = <S as Storage>::Storage

impl<S: StorageInto<U>, T, I, U> StorageInto<U> for Sparse<S, T, I>

Pass through the conversion for structure type Subset.

type Output = Sparse<<S as StorageInto<U>>::Output, T, I>

fn storage_into(self) -> Self::Output

impl<S: StorageMut, T, I> StorageMut for Sparse<S, T, I>

fn storage_mut(&mut self) -> &mut Self::Storage

Return a mutable reference to the underlying storage type of source data.

Example

use flatk::*;
let mut v = vec![1,2,3,4,5,6,7,8,9,10,11,12];
let mut s0 = Chunked3::from_flat(v.clone());
let mut s1 = Sparse::from_dim(vec![0, 2, 2, 0], 4, s0.clone());
assert_eq!(s1.storage_mut(), &mut v);

impl<'a, S: StorageView<'a>, T, I> StorageView<'a> for Sparse<S, T, I>

fn storage_view(&'a self) -> Self::StorageView

Return a view to the underlying storage type of source data.

Example

use flatk::*;
let v = vec![1,2,3,4,5,6,7,8,9,10,11,12];
let s0 = Chunked3::from_flat(v.clone());
let s1 = Sparse::from_dim(vec![0, 2, 2, 0], 4, s0.clone());
assert_eq!(s1.storage_view(), v.as_slice());

type StorageView = <S as StorageView<'a>>::StorageView

impl<S: Truncate, T, I: Truncate> Truncate for Sparse<S, T, I>

fn truncate(&mut self, new_len: usize)

impl<S, T, I, M> UniChunkable<M> for Sparse<S, T, I>

type Chunk = Sparse<S, T, I>

impl<'a, S, T, I> View<'a> for Sparse<S, T, I>

where S: View<'a>, T: View<'a>, I: AsIndexSlice,

type Type = Sparse<<S as View<'a>>::Type, <T as View<'a>>::Type, &'a [usize]>

fn view(&'a self) -> Self::Type

impl<'a, S, T, I> ViewIterator<'a> for Sparse<S, T, I>

where S: View<'a>, <S as View<'a>>::Type: Set + IntoIterator,

type Item = <<S as View<'a>>::Type as IntoIterator>::Item

type Iter = <<S as View<'a>>::Type as IntoIterator>::IntoIter

fn view_iter(&'a self) -> Self::Iter

impl<'a, S, T, I> ViewMut<'a> for Sparse<S, T, I>

where S: Set + ViewMut<'a>, T: Set + View<'a>, I: AsMut<[usize]>,

type Type = Sparse<<S as ViewMut<'a>>::Type, <T as View<'a>>::Type, &'a mut [usize]>

fn view_mut(&'a mut self) -> Self::Type

impl<'a, S, T, I> ViewMutIterator<'a> for Sparse<S, T, I>

where S: ViewMut<'a>, <S as ViewMut<'a>>::Type: Set + IntoIterator,

type Item = <<S as ViewMut<'a>>::Type as IntoIterator>::Item

type Iter = <<S as ViewMut<'a>>::Type as IntoIterator>::IntoIter

fn view_mut_iter(&'a mut self) -> Self::Iter

impl<S: Copy, T: Copy, I: Copy> Copy for Sparse<S, T, I>

impl<S, T, I> DynamicRangeIndexType for Sparse<S, T, I>

impl<S, T, I> StructuralPartialEq for Sparse<S, T, I>

impl<S, T, I> ValueType for Sparse<S, T, I>

impl<S: Viewed, T: Viewed, I: Viewed> Viewed for Sparse<S, T, I>