dfir_rs/util/
sparse_vec.rs

Help
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.get(item) {
34            for index in indices {
35                self.items[*index] = None;
36            }
37        }
38    }
39
40    /// Iterate through all items in the vector in order. Deleted items will not appear in the iteration.
41    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> + FusedIterator + Clone {
42        self.items.iter().filter_map(|x| x.as_ref())
43    }
44}
45
46#[cfg(test)]
47mod test {
48    use super::*;
49
50    fn collect<T: Eq + Hash + Clone>(sv: &SparseVec<T>) -> Vec<T> {
51        sv.iter().cloned().collect()
52    }
53
54    #[test]
55    fn basic() {
56        let mut x = SparseVec::default();
57
58        x.push(0);
59        x.push(1);
60        x.push(2);
61
62        x.delete(&1);
63
64        assert_eq!(collect(&x), vec![0, 2]);
65    }
66
67    #[test]
68    fn can_implement_default_on_types_that_dont_implement_default() {
69        struct NoDefault;
70
71        let x = SparseVec::<NoDefault>::default();
72
73        assert_eq!(x.items.len(), 0);
74        assert_eq!(x.item_locs.len(), 0);
75    }
76}
dfir_rs/util/sparse_vec.rs

dfir_rs/util/
sparse_vec.rs
