dfir_rs/util/
sparse_vec.rs

1//! A vector that supports efficient deletion without reordering all subsequent items.
2use std::collections::HashMap;
3use std::hash::Hash;
4use std::iter::FusedIterator;
5
6/// A vector that supports efficient deletion without reordering all subsequent items.
7pub struct SparseVec<T> {
8    items: Vec<Option<T>>,
9    item_locs: HashMap<T, Vec<usize>>,
10}
11
12impl<T> Default for SparseVec<T> {
13    fn default() -> Self {
14        SparseVec {
15            items: Vec::default(),
16            item_locs: HashMap::default(),
17        }
18    }
19}
20
21impl<T: Clone + Eq + Hash> SparseVec<T> {
22    /// Insert item into the vector, see `https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push`
23    pub fn push(&mut self, item: T) {
24        self.items.push(Some(item.clone()));
25        self.item_locs
26            .entry(item)
27            .or_insert(Vec::with_capacity(1))
28            .push(self.items.len() - 1);
29    }
30
31    /// Delete all items of a specific value from this vector. This takes time proportional to the amount of items with that value in the vector, not the total size of the vector.
32    pub fn delete(&mut self, item: &T) {
33        if let Some(indices) = self.item_locs.remove(item) {
34            for index in indices {
35                self.items[index] = None;
36            }
37        }
38    }
39
40    /// Iterate through all items `&T` in the vector in order. Deleted items will not appear in the iteration.
41    pub fn iter(&self) -> SparseVecIter<'_, T> {
42        SparseVecIter { vec: self, idx: 0 }
43    }
44}
45
46/// An iterator for [`SparseVec`].
47#[derive(Clone)]
48pub struct SparseVecIter<'a, T> {
49    vec: &'a SparseVec<T>,
50    idx: usize,
51}
52
53impl<'a, T> Iterator for SparseVecIter<'a, T> {
54    type Item = &'a T;
55
56    fn next(&mut self) -> Option<Self::Item> {
57        while self.idx < self.vec.items.len() {
58            let item = &self.vec.items[self.idx];
59            self.idx += 1;
60            if let Some(item) = item {
61                return Some(item);
62            }
63        }
64        None
65    }
66}
67
68impl<'a, T> FusedIterator for SparseVecIter<'a, T> {}
69
70#[cfg(test)]
71mod test {
72    use super::*;
73
74    fn collect<T: Eq + Hash + Clone>(sv: &SparseVec<T>) -> Vec<T> {
75        sv.iter().cloned().collect()
76    }
77
78    #[test]
79    fn basic() {
80        let mut x = SparseVec::default();
81
82        x.push(0);
83        x.push(1);
84        x.push(2);
85
86        x.delete(&1);
87
88        assert_eq!(collect(&x), vec![0, 2]);
89    }
90
91    #[test]
92    fn can_implement_default_on_types_that_dont_implement_default() {
93        struct NoDefault;
94
95        let x = SparseVec::<NoDefault>::default();
96
97        assert_eq!(x.items.len(), 0);
98        assert_eq!(x.item_locs.len(), 0);
99    }
100}
dfir_rs/util/sparse_vec.rs

dfir_rs/util/
sparse_vec.rs
