xuko_core/
sparse_set.rs

1//! Sparse set data structure
2
3/// Sparse set data structure
4#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
5pub struct SparseSet<T> {
6    sparse: Vec<usize>,
7    dense: Vec<T>,
8}
9
10impl<T> SparseSet<T> {
11    const NULL_INDEX: usize = usize::MAX;
12
13    /// Create a [`SparseSet`]
14    pub fn new() -> Self {
15        Self {
16            sparse: Vec::new(),
17            dense: Vec::new(),
18        }
19    }
20
21    /// Inserts an item into the [`SparseSet`] at `index`
22    pub fn insert(&mut self, index: usize, value: T) {
23        if self.sparse.len() + index > self.sparse.capacity() {
24            self.sparse.reserve(index.max(4));
25        }
26        self.sparse.insert(index, self.dense.len());
27        self.dense.push(value);
28    }
29
30    /// Get a reference to an item in the [`SparseSet`]
31    pub fn get(&self, index: usize) -> Option<&T> {
32        if index == Self::NULL_INDEX {
33            None
34        } else if let Some(i) = self.sparse.get(index).copied() {
35            self.dense.get(i)
36        } else {
37            None
38        }
39    }
40
41    /// Get a mutable reference to an item in the [`SparseSet`]
42    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
43        if index == Self::NULL_INDEX {
44            None
45        } else if let Some(i) = self.sparse.get(index).copied() {
46            self.dense.get_mut(i)
47        } else {
48            None
49        }
50    }
51
52    /// Removes an element from the [`SparseSet`]
53    pub fn remove(&mut self, index: usize) {
54        if self.dense.is_empty() {
55            return;
56        }
57
58        let Some(dense_index) = self.sparse.get(index).copied() else {
59            return;
60        };
61
62        let back = self.dense.len() - 1;
63        self.dense.swap(dense_index, back);
64        self.dense.remove(back);
65        self.sparse[index] = Self::NULL_INDEX;
66        self.sparse[back] = index;
67    }
68}
69
70impl<T> Default for SparseSet<T> {
71    fn default() -> Self {
72        Self {
73            sparse: Vec::new(),
74            dense: Vec::new(),
75        }
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use std::time::SystemTime;
82
83    use super::*;
84
85    #[test]
86    fn basic() {
87        const N: usize = 1000000;
88        let time = SystemTime::now();
89        let mut set = SparseSet::new();
90
91        // set.insert(43, "".to_owned());
92
93        let mut remove = vec![];
94        for i in 0..=N {
95            set.insert(i, format!("Hello #{i}"));
96
97            if i % 153 == 0 {
98                remove.push(i);
99            }
100        }
101
102        // println!("{:?}", set.dense);
103
104        for i in &remove {
105            set.remove(*i);
106        }
107        let dur = time.elapsed().unwrap();
108        println!("Time took: {}ms:{}ns", dur.as_millis(), dur.as_nanos());
109        remove.clear();
110
111        let mut hash = std::collections::HashMap::new();
112        let time = SystemTime::now();
113        for i in 0..=N {
114            hash.insert(i, format!("Hello #{i}"));
115
116            if i % 153 == 0 {
117                remove.push(i);
118            }
119        }
120
121        for i in &remove {
122            hash.remove(i);
123        }
124
125        let dur = time.elapsed().unwrap();
126        println!("Time took: {}ms:{}ns", dur.as_millis(), dur.as_nanos());
127    }
128}
xuko_core/sparse_set.rs

xuko_core/
sparse_set.rs
