Struct flatk::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.

Fields

selection: Select<T, I>

source: S

Methods

impl<S, I> Sparse<S, RangeTo<usize>, I> where
    S: Set,
    I: AsRef<[usize]>, 

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: AsRef<[usize]>, 

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, T, I> Sparse<S, T, I>

pub fn extend_pruned<S2, T2, I2, B>(
    &mut self,
    other: Sparse<S2, T2, I2>,
    combine: impl FnMut(&mut B::Owned, B),
    keep: impl FnMut(usize, &B::Owned) -> bool
) where
    S2: IntoIterator<Item = B>,
    I2: AsRef<[usize]>,
    B: IntoOwned,
    Self: Push<(usize, B::Owned)>, 

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

Example

use flatk::*;
let v = vec![1,2,3,4,5,6];
let sparse = Sparse::from_dim(vec![0,2,2,2,0,3], 4, v.as_slice());
let mut compressed = Sparse::from_dim(Vec::new(), 4, Vec::new());
compressed.extend_pruned(sparse, |a, b| *a += *b, |_, _| true);
let mut iter = compressed.iter(); // Returns (position, source, target) pairs
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());

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: AsRef<[usize]>, 

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: AsRef<[usize]>, 

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: AsRef<[usize]>, 

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: AsRef<[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 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]> + Truncate + Set,
    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::Item

type Iter = S::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::Item

type Iter = S::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 copy 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::CloneType, T, I>

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

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

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

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.

impl<'a, S, T, I> GetIndex<'a, Sparse<S, T, I>> for usize where
    I: AsRef<[usize]>,
    S: Get<'a, usize>, 

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

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

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

type FlatType = S::FlatType

fn into_flat(self) -> Self::FlatType

Convert the sparse set into its raw storage representation.

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

type Owned = Sparse<S::Owned, T::Owned, I::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::OwnedData, T, I>

fn into_owned_data(self) -> Self::OwnedData

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

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)

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

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::Output, T, I::Output>

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

impl<S, T, I, N: Unsigned> IsolateIndex<Sparse<S, T, I>> for StaticRange<N> where
    Range<usize>: IsolateIndex<Sparse<S, T, I>>, 

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

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

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

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

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>

type Elem = (usize, S::Elem)

Owned element of the set.

type Atom = S::Atom

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

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());

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>

type Storage = S::Storage

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);

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::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>

type StorageView = S::StorageView

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());

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

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<S, T, I> ValueType for Sparse<S, T, I>

impl<'a, S, T, I> View<'a> for Sparse<S, T, I> where
    S: View<'a>,
    T: View<'a>,
    I: AsRef<[usize]>, 

type Type = Sparse<S::Type, T::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::Type, T::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: Viewed, T: Viewed, I: Viewed> Viewed for Sparse<S, T, I>