wachter_storage/
vec_backed_set.rs

1/// Structure that exists only to have an "exists" method
2/// but backed by a vec.
3/// Backing it by a vec offers two distinct benefits:
4/// - We can access elements by index. Really useful for passing around cheap handles.
5/// - We are guaranteed an order AND a memory layout. Useful for passing to shaders.
6#[derive(Eq, PartialEq, Debug)]
7pub struct VecBackedSet<T: Eq> {
8    inner: Vec<T>,
9}
10
11impl<T: Eq> VecBackedSet<T> {
12    pub fn new() -> Self {
13        Self { inner: vec![] }
14    }
15
16    pub fn with_capacity(capacity: usize) -> Self {
17        Self {
18            inner: Vec::with_capacity(capacity),
19        }
20    }
21
22    /// Insert an element, return the index.
23    /// Returns the index of the stored element.
24    pub fn insert(&mut self, elem: T) -> usize {
25        if let Some(idx) = self.idx_of(&elem) {
26            return idx;
27        }
28        let idx = self.inner.len();
29        self.inner.push(elem);
30        idx
31    }
32
33    pub fn get(&self, index: usize) -> Option<&T> {
34        self.inner.get(index)
35    }
36
37    fn idx_of(&self, elem: &T) -> Option<usize> {
38        self.inner
39            .iter()
40            .enumerate()
41            .find(|(_, e)| e == &elem)
42            .map(|(idx, _)| idx)
43    }
44
45    pub fn contains(&self, elem: &T) -> bool {
46        self.idx_of(elem).is_some()
47    }
48
49    pub fn clear(&mut self) {
50        self.inner.clear()
51    }
52
53    pub fn len(&self) -> usize {
54        self.inner.len()
55    }
56}
57
58impl<'a, T: Eq> Into<&'a mut Vec<T>> for &'a mut VecBackedSet<T> {
59    fn into(self) -> &'a mut Vec<T> {
60        &mut self.inner
61    }
62}
63
64impl<'a, T: Eq> Into<&'a Vec<T>> for &'a VecBackedSet<T> {
65    fn into(self) -> &'a Vec<T> {
66        &self.inner
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_insert_and_exists() {
76        let mut set = VecBackedSet::<i32>::new();
77        let two_idx = set.insert(2);
78        let three_idx = set.insert(3);
79        assert!(set.contains(&2));
80        assert_eq!(three_idx, 1);
81        assert_eq!(set.get(two_idx), Some(&2));
82        assert_eq!(set.len(), 2);
83        set.clear();
84        assert_eq!(set.len(), 0);
85        assert_eq!(set.contains(&2), false);
86        assert_eq!(set.get(two_idx), None);
87    }
88
89    #[derive(PartialEq, Eq, Clone, Copy)]
90    struct Point(u8, u8);
91
92    #[test]
93    fn test_insertions_are_idempotent() {
94        let p = Point(1, 2);
95        let mut set = VecBackedSet::<Point>::new();
96        let idx1 = set.insert(p);
97        assert_eq!(set.len(), 1);
98        let idx2 = set.insert(p);
99        assert_eq!(set.len(), 1);
100        assert_eq!(idx1, idx2);
101    }
102
103    #[test]
104    fn test_into_vec() {
105        let mut set = VecBackedSet::<i32>::new();
106        let _ = set.insert(2);
107        let _ = set.insert(3);
108        let as_vec: &Vec<i32> = (&set).into();
109        assert_eq!(as_vec, &vec![2, 3]);
110    }
111}
wachter_storage/vec_backed_set.rs

wachter_storage/
vec_backed_set.rs
