flatk/
sparse.rs

1#[cfg(feature = "rayon")]
2mod par_iter;
3
4use super::*;
5use std::convert::{AsMut, AsRef};
6
7/// A `Sparse` data set `S` where the sparsity pattern is given by `I` as select
8/// indices into a larger range.
9///
10/// For example we can represent a sparse vector by assigning values to a selection of indices:
11///
12/// ```rust
13/// use flatk::{Sparse, Get, View};
14///
15/// let values = vec![1.0, 2.0, 3.0, 4.0];
16/// let sparse_vector = Sparse::from_dim(vec![0,5,10,100], 1000, values);
17/// let sparse_vector_view = sparse_vector.view();
18///
19/// assert_eq!(sparse_vector_view.at(0), (0, &1.0));
20/// assert_eq!(sparse_vector_view.at(1), (5, &2.0));
21/// assert_eq!(sparse_vector_view.at(2), (10, &3.0));
22/// assert_eq!(sparse_vector_view.at(3), (100, &4.0));
23/// assert_eq!(sparse_vector_view.selection.target, ..1000);
24/// ```
25///
26/// In this scenario, the target set is just the range `0..1000`, however in general this can be any
27/// data set, which makes `Sparse` an implementation of a one-to-one mapping or a directed graph
28/// with disjoint source and target node sets.
29#[derive(Copy, Clone, Debug, PartialEq)]
30pub struct Sparse<S, T = std::ops::RangeTo<usize>, I = Vec<usize>> {
31    pub selection: Select<T, I>,
32    pub source: S,
33}
34
35/// A borrowed view of a sparse collection.
36pub type SparseView<'a, S, T> = Sparse<S, T, &'a [usize]>;
37
38impl<S, I> Sparse<S, std::ops::RangeTo<usize>, I>
39where
40    S: Set,
41    I: AsIndexSlice,
42{
43    /// Create a sparse collection from the given set of `indices`, a
44    /// `dim`ension and a set of `values`.
45    ///
46    /// The corresponding sparse collection will represent a collection
47    /// of size `dim` which stores only the given `values` at the specified
48    /// `indices`. Note that `dim` may be smaller than `values.len()`, in
49    /// which case a position in the sparse data structure may contain multiple
50    /// values.
51    ///
52    /// # Example
53    ///
54    /// ```
55    /// use flatk::*;
56    /// let v = vec![1,2,3,4,5,6];
57    /// let sparse = Sparse::from_dim(vec![0,2,0,2,0,3], 4, v.as_slice());
58    ///
59    /// // The iterator traverses only non-vacant elements.
60    /// let mut iter = sparse.iter(); // Returns (position, source, target) triplets
61    /// assert_eq!(Some((0, &1, 0)), iter.next());
62    /// assert_eq!(Some((2, &2, 2)), iter.next());
63    /// assert_eq!(Some((0, &3, 0)), iter.next());
64    /// assert_eq!(Some((2, &4, 2)), iter.next());
65    /// assert_eq!(Some((0, &5, 0)), iter.next());
66    /// assert_eq!(Some((3, &6, 3)), iter.next());
67    /// assert_eq!(None, iter.next());
68    /// ```
69    #[inline]
70    pub fn from_dim(indices: I, dim: usize, values: S) -> Self {
71        Sparse::new(Select::new(indices, ..dim), values)
72    }
73}
74
75impl<S, T, I> Sparse<S, T, I>
76where
77    S: Set,
78    T: Set,
79    I: AsIndexSlice,
80{
81    /// The most general constructor for a sparse collection taking a selection
82    /// of values and their corresponding data.
83    ///
84    /// # Panics
85    /// This function will panic if `selection` and `source` have different sizes.
86    #[inline]
87    pub fn new(selection: Select<T, I>, source: S) -> Self {
88        Self::validate(Sparse { selection, source })
89    }
90
91    /// Panics if the number of indices doesn't equal to the number of elements in the source data set.
92    #[inline]
93    fn validate(self) -> Self {
94        assert_eq!(self.source.len(), self.selection.len());
95        self
96    }
97}
98
99impl<S: Set, T, I> Sparse<S, T, I> {
100    /// Extend the current sparse collection with a pruned and compressed version of the given
101    /// sparse collection, `other`.
102    ///
103    /// Each element is in the original sparse collection is guaranteed to be
104    /// passed to exactly one of `keep` or `combine`.
105    ///
106    /// The `keep` function will get the combined value of all consecutively
107    /// overlapping elements, and the source index of the first element in the
108    /// consecutive group.
109    ///
110    /// The `map` function allows the caller to map between original `other`
111    /// sparse collection and the newly populated collection `self`. The first
112    /// parameter passed into `map` is the index in the output sparse array where
113    /// each element is being considered for insertion. The second parameter is
114    /// the position of each element in the output sparse structure. Note that `map`
115    /// is not called on pruned elements.
116    ///
117    /// # Example
118    ///
119    /// ```
120    /// use flatk::*;
121    /// let v = vec![1,2,3,4,5,6];
122    ///
123    /// // Create a sparse vector with overlapping elements:
124    /// // [0] -> 1            [0] -> 5
125    /// // [1] ->              [1] ->
126    /// // [2] -> 2 + 3 + 4    [2] ->
127    /// // [3] ->              [3] -> 6
128    /// let sparse = Sparse::from_dim(vec![0,2,2,2,0,3], 4, v.as_slice());
129    ///
130    /// // Create an empty sparse vector.
131    /// let mut compressed = Sparse::from_dim(Vec::new(), 4, Vec::new());
132    ///
133    /// // Transfer the elements from `sparse` into `compressed` while resolving the consecutive overlaps:
134    /// compressed.extend_pruned(sparse, |_pos, a, b| *a += *b, |_pos, _val| true, |_src_idx, _dst_idx, | {});
135    /// let mut iter = compressed.iter(); // Returns (position, source, target) triplets.
136    /// assert_eq!(Some((0, &1, 0)), iter.next());
137    /// assert_eq!(Some((2, &9, 2)), iter.next());
138    /// assert_eq!(Some((0, &5, 0)), iter.next());
139    /// assert_eq!(Some((3, &6, 3)), iter.next());
140    /// assert_eq!(None, iter.next());
141    /// // Note: 1 and 5 are not merged because they are not consecutive.
142    /// ```
143    pub fn extend_pruned<S2, T2, I2, B>(
144        &mut self,
145        other: Sparse<S2, T2, I2>,
146        mut combine: impl FnMut(usize, &mut B::Owned, B),
147        mut keep: impl FnMut(usize, &B::Owned) -> bool,
148        mut map: impl FnMut(usize, usize),
149    ) where
150        S2: IntoIterator<Item = B>,
151        I2: AsIndexSlice,
152        B: IntoOwned,
153        Self: Push<(usize, B::Owned)>,
154    {
155        let mut it = other
156            .selection
157            .index_iter()
158            .cloned()
159            .zip(other.source.into_iter())
160            .enumerate();
161        if let Some((mut prev_src_idx, (mut prev_idx, prev))) = it.next() {
162            let mut elem = prev.into_owned();
163
164            for (src_idx, (idx, cur)) in it {
165                if prev_idx != idx {
166                    if keep(prev_idx, &elem) {
167                        map(prev_src_idx, self.len());
168                        self.push((prev_idx, elem));
169                    }
170                    elem = cur.into_owned();
171                    prev_idx = idx;
172                    prev_src_idx = src_idx;
173                } else {
174                    map(src_idx, self.len());
175                    combine(idx, &mut elem, cur);
176                }
177            }
178            if keep(prev_idx, &elem) {
179                map(prev_src_idx, self.len()); // Map the last element.
180                self.push((prev_idx, elem)); // Push the last element.
181            }
182        }
183    }
184}
185
186/*
187impl<S, T, I> Sparse<S, T, I>
188where
189    S: Set + Default + Push<<S as Set>::Elem>,
190    <S as Set>::Elem: Default,
191{
192    /// Convert this sparse collection into its dense representation.
193    pub fn dense(&self) -> S {
194        // TODO: This can be optimized with a trait that allows pre-allocating memory.
195        let mut dense = S::default();
196        for (i, v) in self.iter() {
197            while dense.len() < i {
198                dense.push(Default::default());
199            }
200            dense.push(v);
201        }
202
203        dense
204    }
205}
206*/
207
208impl<S, T> Extend<(usize, <S as Set>::Elem)> for Sparse<S, T>
209where
210    S: Set + Extend<<S as Set>::Elem>,
211{
212    #[inline]
213    fn extend<It: IntoIterator<Item = (usize, <S as Set>::Elem)>>(&mut self, iter: It) {
214        let Sparse {
215            source,
216            selection: Select { indices, .. },
217        } = self;
218        let iter = iter.into_iter();
219        indices.reserve(iter.size_hint().0);
220        source.extend(iter.map(|(idx, elem)| {
221            indices.push(idx);
222            elem
223        }));
224    }
225}
226
227impl<S, T, I, A> Push<(usize, A)> for Sparse<S, T, I>
228where
229    S: Set<Elem = A> + Push<A>,
230    I: Push<usize>,
231{
232    #[inline]
233    fn push(&mut self, (index, elem): (usize, A)) {
234        self.source.push(elem);
235        self.selection.indices.push(index);
236    }
237}
238
239impl<'a, S, T, I> Sparse<S, T, I> {
240    /// Get a reference to the underlying source data.
241    #[inline]
242    pub fn source(&self) -> &S {
243        &self.source
244    }
245    /// Get a mutable reference to the underlying source data.
246    #[inline]
247    pub fn source_mut(&mut self) -> &mut S {
248        &mut self.source
249    }
250    /// Get a reference to the underlying selection.
251    #[inline]
252    pub fn selection(&self) -> &Select<T, I> {
253        &self.selection
254    }
255
256    #[inline]
257    pub fn selection_mut(&mut self) -> &mut Select<T, I> {
258        &mut self.selection
259    }
260
261    /// Get a reference to the underlying indices.
262    #[inline]
263    pub fn indices(&self) -> &I {
264        &self.selection.indices
265    }
266
267    #[inline]
268    pub fn indices_mut(&mut self) -> &mut I {
269        &mut self.selection.indices
270    }
271}
272
273// Note to self:
274// To enable a collection to be chunked, we need to implement:
275// Set, View, SplitAt
276// For mutability we also need ViewMut,
277// For UniChunked we need:
278// Set, Vew, ReinterpretSet (this needs to be refined)
279
280// Required for `Chunked` and `UniChunked` subsets.
281impl<S: Set, T, I> Set for Sparse<S, T, I> {
282    type Elem = (usize, S::Elem);
283    type Atom = S::Atom;
284    /// Get the length of this sparse collection.
285    ///
286    /// # Example
287    ///
288    /// ```rust
289    /// use flatk::*;
290    /// let v = vec![1,2,3,4,5];
291    /// let sparse = Sparse::from_dim(vec![0,2,2,1,1], 3, v.as_slice());
292    /// assert_eq!(5, sparse.len());
293    /// ```
294    #[inline]
295    fn len(&self) -> usize {
296        self.source.len()
297    }
298}
299
300// Required for `Chunked` and `UniChunked` subsets.
301impl<'a, S, T, I> View<'a> for Sparse<S, T, I>
302where
303    S: View<'a>,
304    T: View<'a>,
305    I: AsIndexSlice,
306{
307    type Type = Sparse<S::Type, T::Type, &'a [usize]>;
308    #[inline]
309    fn view(&'a self) -> Self::Type {
310        Sparse {
311            selection: self.selection.view(),
312            source: self.source.view(),
313        }
314    }
315}
316
317impl<'a, S, T, I> ViewMut<'a> for Sparse<S, T, I>
318where
319    S: Set + ViewMut<'a>,
320    T: Set + View<'a>,
321    I: AsMut<[usize]>,
322{
323    type Type = Sparse<S::Type, T::Type, &'a mut [usize]>;
324    #[inline]
325    fn view_mut(&'a mut self) -> Self::Type {
326        let Sparse {
327            selection: Select {
328                indices,
329                ref target,
330            },
331            source,
332        } = self;
333        Sparse {
334            selection: Select {
335                indices: indices.as_mut(),
336                target: target.view(),
337            },
338            source: source.view_mut(),
339        }
340    }
341}
342
343// This impl enables `Chunked` `Subset`s
344impl<S, T, I> SplitAt for Sparse<S, T, I>
345where
346    S: Set + SplitAt,
347    T: Set + Clone,
348    I: SplitAt,
349{
350    #[inline]
351    fn split_at(self, mid: usize) -> (Self, Self) {
352        let Sparse { selection, source } = self;
353        let (selection_l, selection_r) = selection.split_at(mid);
354        let (source_l, source_r) = source.split_at(mid);
355        (
356            Sparse {
357                selection: selection_l,
358                source: source_l,
359            },
360            Sparse {
361                selection: selection_r,
362                source: source_r,
363            },
364        )
365    }
366}
367
368impl<S: RemovePrefix, T, I: RemovePrefix> RemovePrefix for Sparse<S, T, I> {
369    #[inline]
370    fn remove_prefix(&mut self, n: usize) {
371        self.selection.remove_prefix(n);
372        self.source.remove_prefix(n);
373    }
374}
375
376/*
377 * Indexing operators for convenience. Users familiar with indexing by `usize`
378 * may find these implementations convenient.
379 */
380
381impl<'a, S, T, I> GetIndex<'a, Sparse<S, T, I>> for usize
382where
383    I: AsIndexSlice,
384    S: Get<'a, usize>,
385{
386    type Output = (usize, <S as Get<'a, usize>>::Output);
387
388    #[inline]
389    fn get(self, sparse: &Sparse<S, T, I>) -> Option<Self::Output> {
390        let Sparse { selection, source } = sparse;
391        let selected = selection.indices.as_ref();
392        source.get(self).map(|item| (selected[self], item))
393    }
394}
395
396impl<'a, S, T, I> GetIndex<'a, Sparse<S, T, I>> for &usize
397where
398    I: AsIndexSlice,
399    S: Get<'a, usize>,
400{
401    type Output = (usize, <S as Get<'a, usize>>::Output);
402
403    #[inline]
404    fn get(self, sparse: &Sparse<S, T, I>) -> Option<Self::Output> {
405        GetIndex::get(*self, sparse)
406    }
407}
408
409impl<S, T, I> IsolateIndex<Sparse<S, T, I>> for usize
410where
411    I: Isolate<usize>,
412    <I as Isolate<usize>>::Output: std::borrow::Borrow<usize>,
413    S: Isolate<usize>,
414    T: Isolate<usize>,
415{
416    type Output = (
417        <I as Isolate<usize>>::Output,
418        <S as Isolate<usize>>::Output,
419        <T as Isolate<usize>>::Output,
420    );
421
422    #[inline]
423    unsafe fn isolate_unchecked(self, sparse: Sparse<S, T, I>) -> Self::Output {
424        let Sparse { selection, source } = sparse;
425        let item = source.isolate_unchecked(self);
426        let (idx, target) = selection.isolate_unchecked(self);
427        (idx, item, target)
428    }
429
430    #[inline]
431    fn try_isolate(self, sparse: Sparse<S, T, I>) -> Option<Self::Output> {
432        let Sparse { selection, source } = sparse;
433        let item = source.try_isolate(self)?;
434        // SAFETY: selection must be the same size as source.
435        let (idx, target) = unsafe { selection.isolate_unchecked(self) };
436        Some((idx, item, target))
437    }
438}
439
440impl<S, T, I> IsolateIndex<Sparse<S, T, I>> for std::ops::Range<usize>
441where
442    S: Isolate<std::ops::Range<usize>>,
443    I: Isolate<std::ops::Range<usize>>,
444{
445    type Output = Sparse<S::Output, T, I::Output>;
446
447    #[inline]
448    unsafe fn isolate_unchecked(self, sparse: Sparse<S, T, I>) -> Self::Output {
449        let Sparse { selection, source } = sparse;
450        let source = source.isolate_unchecked(self.clone());
451        Sparse {
452            selection: selection.isolate_unchecked(self),
453            source,
454        }
455    }
456
457    #[inline]
458    fn try_isolate(self, sparse: Sparse<S, T, I>) -> Option<Self::Output> {
459        let Sparse { selection, source } = sparse;
460        let source = source.try_isolate(self.clone())?;
461        // SAFETY: selection must be the same size as source.
462        Some(Sparse {
463            selection: unsafe { selection.isolate_unchecked(self) },
464            source,
465        })
466    }
467}
468
469//impl_isolate_index_for_static_range!(impl<S, T, I> for Sparse<S, T, I>);
470
471/*
472 * Iteration
473 */
474
475impl<'a, S, T> IntoIterator for SparseView<'a, S, T>
476where
477    S: SplitFirst + SplitAt + Dummy + Set,
478{
479    type Item = (usize, S::First);
480    type IntoIter = SparseIter<std::iter::Cloned<std::slice::Iter<'a, usize>>, S>;
481
482    #[inline]
483    fn into_iter(self) -> Self::IntoIter {
484        SparseIter {
485            indices: self.selection.indices.iter().cloned(),
486            source: self.source,
487        }
488    }
489}
490
491pub struct SparseIter<I, S> {
492    indices: I,
493    source: S,
494}
495
496impl<I, S> Iterator for SparseIter<I, S>
497where
498    S: SplitFirst + SplitAt + Dummy + Set,
499    I: ExactSizeIterator<Item = usize>,
500{
501    type Item = (usize, S::First);
502
503    #[inline]
504    fn next(&mut self) -> Option<Self::Item> {
505        // SAFETY: A sparse dummy is a valid sparse set.
506        let source_slice = std::mem::replace(&mut self.source, unsafe { Dummy::dummy() });
507        source_slice.split_first().map(|(first, rest)| {
508            self.source = rest;
509            // We know that sparse has at least one element, no need to check again.
510            let first_idx = self.indices.next().unwrap();
511            // SAFETY: We know there is at least one element in beginning.
512            (first_idx, first)
513        })
514    }
515    #[inline]
516    fn nth(&mut self, n: usize) -> Option<Self::Item> {
517        // SAFETY: A sparse dummy is a valid sparse set.
518        let source_slice = std::mem::replace(&mut self.source, unsafe { Dummy::dummy() });
519        self.indices.nth(n).map(|nth_idx| {
520            let (_, rest) = source_slice.split_at(n);
521            // SAFETY: source_slice is known to have at least n elements since indices does.
522            let (nth, rest) = unsafe { rest.split_first_unchecked() };
523            self.source = rest;
524            (nth_idx, nth)
525        })
526    }
527}
528
529impl<I, S> ExactSizeIterator for SparseIter<I, S> where Self: Iterator {}
530
531impl<I, S> DoubleEndedIterator for SparseIter<I, S>
532where
533    S: SplitFirst + SplitAt + Dummy + Set,
534    I: ExactSizeIterator + DoubleEndedIterator<Item = usize>,
535{
536    #[inline]
537    fn next_back(&mut self) -> Option<Self::Item> {
538        let source_slice = std::mem::replace(&mut self.source, unsafe { Dummy::dummy() });
539        let len = source_slice.len();
540        if len < 1 {
541            return None;
542        }
543
544        let (prefix, end) = source_slice.split_at(len - 1);
545
546        self.source = prefix;
547        // We know that sparse has at least one element, no need to check again.
548        let last_idx = self.indices.next_back().unwrap();
549        // SAFETY: We know there is at least one element in end.
550        Some((last_idx, unsafe { end.split_first_unchecked().0 }))
551    }
552    #[inline]
553    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
554        // SAFETY: A sparse dummy is a valid sparse set.
555        let source_slice = std::mem::replace(&mut self.source, unsafe { Dummy::dummy() });
556        self.indices.nth_back(n).map(|nth_idx| {
557            let (beginning, end) = source_slice.split_at(n);
558            // SAFETY: source_slice is known to have at least n elements since indices does.
559            let (nth, _) = unsafe { end.split_first_unchecked() };
560            self.source = beginning;
561            (nth_idx, nth)
562        })
563    }
564}
565
566impl<'a, S, T, I> Sparse<S, T, I>
567where
568    S: View<'a>,
569    <S as View<'a>>::Type: Set + IntoIterator,
570    T: Set + Get<'a, usize> + View<'a>,
571    I: AsIndexSlice,
572{
573    #[inline]
574    pub fn iter(
575        &'a self,
576    ) -> impl Iterator<
577        Item = (
578            usize,
579            <<S as View<'a>>::Type as IntoIterator>::Item,
580            <T as Get<'a, usize>>::Output,
581        ),
582    > {
583        self.selection
584            .iter()
585            .zip(self.source.view().into_iter())
586            .map(|((i, t), s)| (i, s, t))
587    }
588}
589
590impl<'a, S, T, I> Sparse<S, T, I>
591where
592    S: View<'a>,
593    <S as View<'a>>::Type: Set + IntoIterator,
594{
595    #[inline]
596    pub fn source_iter(&'a self) -> <<S as View<'a>>::Type as IntoIterator>::IntoIter {
597        self.source.view().into_iter()
598    }
599}
600
601impl<'a, S, T, I> Sparse<S, T, I>
602where
603    I: AsIndexSlice,
604{
605    #[inline]
606    pub fn index_iter(&'a self) -> std::iter::Cloned<std::slice::Iter<'a, usize>> {
607        self.selection.index_iter().cloned()
608    }
609}
610
611impl<'a, S, T, I> Sparse<S, T, I>
612where
613    S: View<'a>,
614    <S as View<'a>>::Type: Set + IntoIterator,
615    I: AsIndexSlice,
616{
617    #[inline]
618    pub fn indexed_source_iter(
619        &'a self,
620    ) -> std::iter::Zip<
621        std::iter::Cloned<std::slice::Iter<'a, usize>>,
622        <<S as View<'a>>::Type as IntoIterator>::IntoIter,
623    > {
624        self.selection
625            .index_iter()
626            .cloned()
627            .zip(self.source.view().into_iter())
628    }
629}
630
631/// A mutable iterator over the source elements in `S`
632impl<'a, S, T, I> Sparse<S, T, I>
633where
634    S: ViewMut<'a>,
635    <S as ViewMut<'a>>::Type: Set + IntoIterator,
636{
637    #[inline]
638    pub fn source_iter_mut(&'a mut self) -> <<S as ViewMut<'a>>::Type as IntoIterator>::IntoIter {
639        self.source.view_mut().into_iter()
640    }
641}
642
643/// A mutable iterator can only iterate over the source elements in `S` and not
644/// the target elements in `T` since we would need scheduling to modify
645/// potentially overlapping mutable references.
646impl<'a, S, T, I> Sparse<S, T, I>
647where
648    S: ViewMut<'a>,
649    <S as ViewMut<'a>>::Type: Set + IntoIterator,
650    I: AsIndexSlice,
651{
652    #[inline]
653    pub fn indexed_source_iter_mut(
654        &'a mut self,
655    ) -> impl Iterator<Item = (usize, <<S as ViewMut<'a>>::Type as IntoIterator>::Item)> {
656        self.selection
657            .index_iter()
658            .cloned()
659            .zip(self.source.view_mut().into_iter())
660    }
661}
662
663/// A mutable iterator can only iterate over the source elements in `S` and not
664/// the target elements in `T` since we would need scheduling to modify
665/// potentially overlapping mutable references.
666impl<'a, S, T, I> Sparse<S, T, I>
667where
668    S: ViewMut<'a>,
669    <S as ViewMut<'a>>::Type: Set + IntoIterator,
670    I: AsMut<[usize]>,
671{
672    #[inline]
673    pub fn iter_mut(
674        &'a mut self,
675    ) -> std::iter::Zip<
676        std::slice::IterMut<'a, usize>,
677        <<S as ViewMut<'a>>::Type as IntoIterator>::IntoIter,
678    > {
679        self.selection
680            .index_iter_mut()
681            .zip(self.source.view_mut().into_iter())
682    }
683}
684
685/// Mutably iterate over the selected indices.
686impl<'a, S, T, I> Sparse<S, T, I>
687where
688    S: View<'a>,
689    <S as View<'a>>::Type: Set + IntoIterator,
690    I: AsMut<[usize]>,
691{
692    #[inline]
693    pub fn index_iter_mut(
694        &'a mut self,
695    ) -> impl Iterator<Item = (&'a mut usize, <<S as View<'a>>::Type as IntoIterator>::Item)> {
696        self.selection
697            .index_iter_mut()
698            .zip(self.source.view().into_iter())
699    }
700}
701
702impl<'a, S, T, I> ViewIterator<'a> for Sparse<S, T, I>
703where
704    S: View<'a>,
705    <S as View<'a>>::Type: Set + IntoIterator,
706{
707    type Item = <<S as View<'a>>::Type as IntoIterator>::Item;
708    type Iter = <<S as View<'a>>::Type as IntoIterator>::IntoIter;
709
710    #[inline]
711    fn view_iter(&'a self) -> Self::Iter {
712        self.source_iter()
713    }
714}
715
716impl<'a, S, T, I> ViewMutIterator<'a> for Sparse<S, T, I>
717where
718    S: ViewMut<'a>,
719    <S as ViewMut<'a>>::Type: Set + IntoIterator,
720{
721    type Item = <<S as ViewMut<'a>>::Type as IntoIterator>::Item;
722    type Iter = <<S as ViewMut<'a>>::Type as IntoIterator>::IntoIter;
723
724    #[inline]
725    fn view_mut_iter(&'a mut self) -> Self::Iter {
726        self.source_iter_mut()
727    }
728}
729
730impl_atom_iterators_recursive!(impl<S, T, I> for Sparse<S, T, I> { source });
731
732impl<S: Dummy, T: Dummy, I: Dummy> Dummy for Sparse<S, T, I> {
733    #[inline]
734    unsafe fn dummy() -> Self {
735        Sparse {
736            selection: Dummy::dummy(),
737            source: Dummy::dummy(),
738        }
739    }
740}
741
742impl<S: Truncate, T, I: Truncate> Truncate for Sparse<S, T, I> {
743    #[inline]
744    fn truncate(&mut self, new_len: usize) {
745        self.selection.truncate(new_len);
746        self.source.truncate(new_len);
747    }
748}
749
750impl<S: Clear, T, I: Clear> Clear for Sparse<S, T, I> {
751    #[inline]
752    fn clear(&mut self) {
753        self.source.clear();
754        self.selection.clear();
755    }
756}
757
758impl<S, O, T, I> Sparse<Chunked<S, O>, T, I>
759where
760    S: Set + Truncate,
761    O: AsRef<[usize]> + GetOffset + Truncate,
762    I: Truncate,
763{
764    /// Remove any empty elements (indexed chunks) at the end of the collection and any unindexed
765    /// data past the last offset.
766    /// Return the number of elements removed.
767    ///
768    /// # Example
769    ///
770    /// ```
771    /// use flatk::*;
772    /// 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]));
773    /// assert_eq!(3, s.len());
774    ///
775    /// // Transferring the last two elements past the indexed stack.
776    /// // This creates an empty chunk at the end.
777    /// s.source_mut().transfer_forward(2, 2);
778    /// assert_eq!(6, s.storage().len());
779    /// assert_eq!(3, s.len());
780    ///
781    /// s.trim(); // remove unindexed elements.
782    /// assert_eq!(4, s.storage().len());
783    /// ```
784    #[inline]
785    pub fn trim(&mut self) -> usize {
786        let num_removed = self.source.trim();
787        self.selection.truncate(self.source.len());
788        num_removed
789    }
790}
791
792/*
793 * Conversions
794 */
795
796/// Pass through the conversion for structure type `Subset`.
797impl<S: StorageInto<U>, T, I, U> StorageInto<U> for Sparse<S, T, I> {
798    type Output = Sparse<S::Output, T, I>;
799    #[inline]
800    fn storage_into(self) -> Self::Output {
801        Sparse {
802            source: self.source.storage_into(),
803            selection: self.selection,
804        }
805    }
806}
807
808impl<S: MapStorage<Out>, T, I, Out> MapStorage<Out> for Sparse<S, T, I> {
809    type Input = S::Input;
810    type Output = Sparse<S::Output, T, I>;
811    #[inline]
812    fn map_storage<F: FnOnce(Self::Input) -> Out>(self, f: F) -> Self::Output {
813        Sparse {
814            source: self.source.map_storage(f),
815            selection: self.selection,
816        }
817    }
818}
819
820impl<S: IntoStorage, T, I> IntoStorage for Sparse<S, T, I> {
821    type StorageType = S::StorageType;
822    /// Convert the sparse set into its raw storage representation.
823    #[inline]
824    fn into_storage(self) -> Self::StorageType {
825        self.source.into_storage()
826    }
827}
828
829impl<T: Clone, S: CloneWithStorage<U>, I: Clone, U> CloneWithStorage<U> for Sparse<S, T, I> {
830    type CloneType = Sparse<S::CloneType, T, I>;
831    #[inline]
832    fn clone_with_storage(&self, storage: U) -> Self::CloneType {
833        Sparse {
834            selection: self.selection.clone(),
835            source: self.source.clone_with_storage(storage),
836        }
837    }
838}
839
840/*
841 * Storage Access
842 */
843
844impl<'a, S: StorageView<'a>, T, I> StorageView<'a> for Sparse<S, T, I> {
845    type StorageView = S::StorageView;
846    /// Return a view to the underlying storage type of source data.
847    ///
848    /// # Example
849    ///
850    /// ```rust
851    /// use flatk::*;
852    /// let v = vec![1,2,3,4,5,6,7,8,9,10,11,12];
853    /// let s0 = Chunked3::from_flat(v.clone());
854    /// let s1 = Sparse::from_dim(vec![0, 2, 2, 0], 4, s0.clone());
855    /// assert_eq!(s1.storage_view(), v.as_slice());
856    /// ```
857    #[inline]
858    fn storage_view(&'a self) -> Self::StorageView {
859        self.source.storage_view()
860    }
861}
862
863impl<S: Storage, T, I> Storage for Sparse<S, T, I> {
864    type Storage = S::Storage;
865    /// Return an immutable reference to the underlying storage type of source data.
866    ///
867    /// # Example
868    ///
869    /// ```rust
870    /// use flatk::*;
871    /// let v = vec![1,2,3,4,5,6,7,8,9,10,11,12];
872    /// let s0 = Chunked3::from_flat(v.clone());
873    /// let s1 = Sparse::from_dim(vec![0, 2, 2, 0], 4, s0.clone());
874    /// assert_eq!(s1.storage(), &v);
875    /// ```
876    #[inline]
877    fn storage(&self) -> &Self::Storage {
878        self.source.storage()
879    }
880}
881
882impl<S: StorageMut, T, I> StorageMut for Sparse<S, T, I> {
883    /// Return a mutable reference to the underlying storage type of source data.
884    ///
885    /// # Example
886    ///
887    /// ```rust
888    /// use flatk::*;
889    /// let mut v = vec![1,2,3,4,5,6,7,8,9,10,11,12];
890    /// let mut s0 = Chunked3::from_flat(v.clone());
891    /// let mut s1 = Sparse::from_dim(vec![0, 2, 2, 0], 4, s0.clone());
892    /// assert_eq!(s1.storage_mut(), &mut v);
893    /// ```
894    #[inline]
895    fn storage_mut(&mut self) -> &mut Self::Storage {
896        self.source.storage_mut()
897    }
898}
899
900impl<S: PermuteInPlace, T, I: PermuteInPlace> PermuteInPlace for Sparse<S, T, I> {
901    #[inline]
902    fn permute_in_place(&mut self, permutation: &[usize], seen: &mut [bool]) {
903        let Sparse {
904            selection: Select { indices, .. },
905            source,
906        } = self;
907
908        indices.permute_in_place(permutation, seen);
909        seen.iter_mut().for_each(|x| *x = false);
910        source.permute_in_place(permutation, seen);
911    }
912}
913
914/*
915 * Sparse uniformly chunked types
916 */
917
918impl<S: ChunkSize, T, I> ChunkSize for Sparse<S, T, I> {
919    #[inline]
920    fn chunk_size(&self) -> usize {
921        self.source.chunk_size()
922    }
923}
924
925/*
926 * Convert views to owned types
927 */
928
929impl<S: IntoOwned, T: IntoOwned, I: IntoOwned> IntoOwned for Sparse<S, T, I> {
930    type Owned = Sparse<S::Owned, T::Owned, I::Owned>;
931
932    #[inline]
933    fn into_owned(self) -> Self::Owned {
934        Sparse {
935            selection: self.selection.into_owned(),
936            source: self.source.into_owned(),
937        }
938    }
939}
940
941impl<S, T, I> IntoOwnedData for Sparse<S, T, I>
942where
943    S: IntoOwnedData,
944{
945    type OwnedData = Sparse<S::OwnedData, T, I>;
946    #[inline]
947    fn into_owned_data(self) -> Self::OwnedData {
948        Sparse {
949            selection: self.selection,
950            source: self.source.into_owned_data(),
951        }
952    }
953}
954
955impl<S: Reserve, T, I: Reserve> Reserve for Sparse<S, T, I> {
956    #[inline]
957    fn reserve_with_storage(&mut self, n: usize, storage_n: usize) {
958        self.selection.reserve_with_storage(n, storage_n);
959        self.source.reserve_with_storage(n, storage_n);
960    }
961}
962
963/*
964 * Impls for uniformly chunked sparse types
965 */
966
967impl<S, T, I, M> UniChunkable<M> for Sparse<S, T, I> {
968    type Chunk = Sparse<S, T, I>;
969}
970
971#[cfg(test)]
972mod tests {
973    use super::*;
974
975    #[test]
976    fn extend_pruned() {
977        // Empty test
978        let empty = Sparse::from_dim(Vec::new(), 4, Vec::new());
979        let mut compressed = empty.clone();
980        compressed.extend_pruned(empty.view(), |_, a, b| *a += *b, |_, _| true, |_, _| {});
981        assert!(compressed.is_empty());
982
983        // The basic tests from the example
984        let v = vec![1, 2, 3, 4, 5, 6];
985        let sparse = Sparse::from_dim(vec![0, 2, 2, 2, 0, 3], 4, v.as_slice());
986        let mut compressed = empty.clone();
987        compressed.extend_pruned(sparse.view(), |_, a, b| *a += *b, |__, _| true, |_, _| {});
988        let mut iter = compressed.iter(); // Returns (position, source, target) pairs
989        assert_eq!(Some((0, &1, 0)), iter.next());
990        assert_eq!(Some((2, &9, 2)), iter.next());
991        assert_eq!(Some((0, &5, 0)), iter.next());
992        assert_eq!(Some((3, &6, 3)), iter.next());
993        assert_eq!(None, iter.next());
994    }
995}
flatk/sparse.rs

flatk/
sparse.rs
