1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

//! A vector that supports efficient deletion without reordering all subsequent items.
use std::collections::HashMap;
use std::hash::Hash;
use std::iter::FusedIterator;

/// A vector that supports efficient deletion without reordering all subsequent items.
pub struct SparseVec<T> {
    items: Vec<Option<T>>,
    item_locs: HashMap<T, Vec<usize>>,
}

impl<T> Default for SparseVec<T> {
    fn default() -> Self {
        SparseVec {
            items: Vec::default(),
            item_locs: HashMap::default(),
        }
    }
}

impl<T: Clone + Eq + Hash> SparseVec<T> {
    /// Insert item into the vector, see `https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push`
    pub fn push(&mut self, item: T) {
        self.items.push(Some(item.clone()));
        self.item_locs
            .entry(item)
            .or_insert(Vec::with_capacity(1))
            .push(self.items.len() - 1);
    }

    /// 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.
    pub fn delete(&mut self, item: &T) {
        if let Some(indices) = self.item_locs.get(item) {
            for index in indices {
                self.items[*index] = None;
            }
        }
    }

    /// Iterate through all items in the vector in order. Deleted items will not appear in the iteration.
    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> + FusedIterator + Clone {
        self.items.iter().filter_map(|x| x.as_ref())
    }
}

#[cfg(test)]
mod test {
    use super::*;

    fn collect<T: Eq + Hash + Clone>(sv: &SparseVec<T>) -> Vec<T> {
        sv.iter().cloned().collect()
    }

    #[test]
    fn basic() {
        let mut x = SparseVec::default();

        x.push(0);
        x.push(1);
        x.push(2);

        x.delete(&1);

        assert_eq!(collect(&x), vec![0, 2]);
    }

    #[test]
    fn can_implement_default_on_types_that_dont_implement_default() {
        struct NoDefault;

        let x = SparseVec::<NoDefault>::default();

        assert_eq!(x.items.len(), 0);
        assert_eq!(x.item_locs.len(), 0);
    }
}