xsparseset/
lib.rs

1//! # XSparseSet
2//! Sparse-set is a data-structure that can get data by dispersed ID and cache-friendly
3mod sparse_storage;
4
5use std::{
6    collections::{BTreeMap, HashMap},
7    num::NonZeroUsize,
8};
9
10pub use sparse_storage::{SparseStorage, VecStorage};
11
12/// SparseSet with `Vec` as SparseStorage
13pub type SparseSetVec<E, T> = SparseSet<E, T, VecStorage<E>>;
14/// SparseSet with `HashMap` as SparseStorage
15pub type SparseSetHashMap<E, T> = SparseSet<E, T, HashMap<E, NonZeroUsize>>;
16/// SparseSet with `BTreeMap` as SparseStorage
17pub type SparseSetBTreeMap<E, T> = SparseSet<E, T, BTreeMap<E, NonZeroUsize>>;
18
19/// The core struct
20/// # Type parameters
21/// * `E` is the type of entity id
22/// * `T` is the type of the data stored in `SparseSet`
23/// * `S` is the type of the sparse storage
24#[derive(Debug, Clone)]
25pub struct SparseSet<E, T, S> {
26    sparse: S,
27    dense: Vec<E>,
28    data: Vec<T>,
29}
30
31impl<E, T, S> Default for SparseSet<E, T, S>
32where
33    E: Copy,
34    S: SparseStorage<EntityId = E> + Default,
35{
36    fn default() -> Self {
37        SparseSet {
38            sparse: S::default(),
39            dense: Vec::new(),
40            data: Vec::new(),
41        }
42    }
43}
44
45impl<E, T, S> SparseSet<E, T, S>
46where
47    E: Copy,
48    S: SparseStorage<EntityId = E>,
49{
50    /// Create sparse set with sparse storage
51    pub fn with_storage(sparse_storage: S) -> Self {
52        SparseSet {
53            sparse: sparse_storage,
54            dense: Vec::new(),
55            data: Vec::new(),
56        }
57    }
58
59    /// Clear the sparse set
60    pub fn clear(&mut self) {
61        self.sparse.clear();
62        self.dense.clear();
63        self.data.clear();
64    }
65
66    /// Insert the `dat` with `id` into sparse set
67    /// # return
68    /// It returns Some(T) if sparse set has this id ,
69    /// otherwise returns None
70    pub fn insert(&mut self, id: E, dat: T) -> Option<T> {
71        if let Some(index) = self.sparse.get_index(id) {
72            let index: usize = index.get() - 1;
73            // Safety
74            // The index stored in sparse is always in range
75            let data_ref = unsafe { self.data.get_unchecked_mut(index) };
76            Some(std::mem::replace(data_ref, dat))
77        } else {
78            let new_index = NonZeroUsize::new(self.dense.len() + 1);
79            self.sparse.set_index(id, new_index);
80            self.dense.push(id);
81            self.data.push(dat);
82            None
83        }
84    }
85
86    /// Insert a lot of data
87    /// # Panics
88    /// * `ids.len() != data.len()`
89    pub fn insert_batch(&mut self, ids: &mut Vec<E>, data: &mut Vec<T>) {
90        if ids.len() != data.len() {
91            panic!("ids.len() != dat.len()")
92        }
93        let start_index = self.data.len() + 1;
94        // # Safety
95        // * the index stored in sparse is start from 1
96        let start_index = unsafe { NonZeroUsize::new_unchecked(start_index) };
97        self.sparse.set_indices(&ids, start_index);
98        self.dense.append(ids);
99        self.data.append(data);
100    }
101
102    /// Remove from sparse set
103    /// # return
104    /// It returns Some(T) if sparse set has this id ,
105    /// otherwise returns None
106    pub fn swap_remove_by_id(&mut self, id: E) -> Option<T> {
107        let index = self.get_index(id)?;
108        self.swap_remove_by_index(index)
109    }
110
111    /// Remove from sparse set
112    /// # return
113    /// It returns Some(T) if index is valid,
114    /// otherwise returns None
115    pub fn swap_remove_by_index(&mut self, index: usize) -> Option<T> {
116        let id = self.get_id(index)?;
117
118        self.swap_by_index(index, self.len() - 1);
119
120        self.sparse.set_index(id,None);
121        self.dense.pop();
122        self.data.pop()
123    }
124
125
126    /// swap 2 entities in sparse set by entity id
127    /// # Details
128    /// Do nothing if `id_a` or `id_b` is NOT in sparse set
129    pub fn swap_by_entity_id(&mut self, id_a: E, id_b: E) {
130        let index_a = self.sparse.get_index(id_a);
131        let index_b = self.sparse.get_index(id_b);
132        if index_a.is_none() || index_b.is_none() {
133            return;
134        }
135        let index_a = index_a.unwrap().get() - 1;
136        let index_b = index_b.unwrap().get() - 1;
137
138        // Safety
139        // The index stored in sparse is always in range
140        unsafe {
141            self.swap_by_index_unchecked(index_a, index_b);
142        }
143    }
144
145    /// swap 2 entities in sparse set by index
146    /// # Panics
147    /// Panic if index is out of range
148    pub fn swap_by_index(&mut self, index_a: usize, index_b: usize) {
149        if index_a >= self.len() {
150            panic!("index_a={} is out of range", index_a);
151        }
152        if index_b >= self.len() {
153            panic!("index_b={} is out of range", index_b);
154        }
155
156        unsafe { self.swap_by_index_unchecked(index_a, index_b) }
157    }
158
159    /// swap 2 entities in sparse set by index with out any check
160    /// # Safety
161    /// Safe only `index_a` and `index_b` is less than `self.len()`
162    pub unsafe fn swap_by_index_unchecked(&mut self, index_a: usize, index_b: usize) {
163        if index_a == index_b {
164            return;
165        }
166        let id_a = *self.dense.get_unchecked(index_a);
167        let id_b = *self.dense.get_unchecked(index_b);
168
169        self.sparse.swap(id_a, id_b);
170        self.dense.swap(index_a, index_b);
171        self.data.swap(index_a, index_b);
172    }
173
174    /// Get the count of entities in sparse set
175    pub fn len(&self) -> usize {
176        self.dense.len()
177    }
178
179    /// Check sparse set is empty
180    pub fn is_empty(&self) -> bool {
181        self.dense.is_empty()
182    }
183
184    /// Check if the sparse set has id
185    pub fn contains(&self, id: E) -> bool {
186        self.sparse.get_index(id).is_some()
187    }
188
189    /// Get the reference of data by given `id`
190    /// # Returns
191    /// Return None if sparse set doesn't contain this `id`
192    pub fn get(&self, id: E) -> Option<&T> {
193        let index = self.sparse.get_index(id)?.get() - 1;
194        // Safety
195        // The index stored in sparse is always in range
196        unsafe { Some(self.data.get_unchecked(index)) }
197    }
198
199    /// Get the MUTABLE reference by data by given `id`
200    /// # Returns
201    /// Return None if sparse set doesn't contain this `id`
202    pub fn get_mut(&mut self, id: E) -> Option<&mut T> {
203        let index = self.get_index(id)?;
204        // Safety
205        // The index stored in sparse is always in range
206        unsafe { Some(self.data.get_unchecked_mut(index)) }
207    }
208
209    /// Get the index of the entity was given by `id` in sparse set
210    /// # Returns
211    /// Return None if sparse set doesn't contain this `id`
212    pub fn get_index(&self, id: E) -> Option<usize> {
213        self.sparse.get_index(id).map(|x| x.get() - 1)
214    }
215
216    /// Get the Id from index
217    /// # Return
218    /// Return None if index is not valid
219    pub fn get_id(&self, index: usize) -> Option<E> {
220        self.dense.get(index).copied()
221    }
222
223    /// Get the slice of data
224    pub fn data(&self) -> &[T] {
225        &self.data
226    }
227
228    /// Get the slice of data
229    pub fn data_mut(&mut self) -> &mut [T] {
230        &mut self.data
231    }
232
233    /// Get the slice of ID , or the dense array
234    /// # Details
235    /// There is NO any `fn ids_mut(&self)` in this lib.  
236    /// Because the mapping relations between the sparse and the dense is ensured by this lib.  
237    /// Leaking the mutable slice of dense is unsafe and will cause some unexpected error
238    pub fn ids(&self) -> &[E] {
239        &self.dense
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use std::{collections::BTreeSet, num::NonZeroUsize};
246
247    use rand::{thread_rng, Rng};
248
249    use crate::{sparse_storage::VecStorage, SparseSet};
250
251    type EntityId = NonZeroUsize;
252
253    #[test]
254    fn interface_test() {
255        let mut sparse_set: SparseSet<EntityId, char, VecStorage<EntityId>> = SparseSet::default();
256
257        assert_eq!(sparse_set.len(), 0);
258        assert!(sparse_set.is_empty());
259        assert!(sparse_set.data().is_empty());
260        assert!(sparse_set.ids().is_empty());
261
262        let id = NonZeroUsize::new(124).unwrap();
263
264        assert_eq!(sparse_set.swap_remove_by_id(id), None);
265        assert!(!sparse_set.contains(id));
266        assert_eq!(sparse_set.len(), 0);
267        assert!(sparse_set.is_empty());
268        assert!(sparse_set.data().is_empty());
269        assert!(sparse_set.ids().is_empty());
270
271        // insert
272        assert_eq!(sparse_set.insert(id, 'c'), None);
273
274        assert_eq!(sparse_set.len(), 1);
275        assert!(!sparse_set.is_empty());
276        assert_eq!(sparse_set.get(id).copied(), Some('c'));
277        assert!(sparse_set.contains(id));
278        assert_eq!(sparse_set.data(), &['c']);
279        assert_eq!(sparse_set.ids(), &[id]);
280
281        // insert again to change the value
282        assert_eq!(sparse_set.insert(id, 'b'), Some('c'));
283
284        assert_eq!(sparse_set.len(), 1);
285        assert!(!sparse_set.is_empty());
286        assert_eq!(sparse_set.get(id).copied(), Some('b'));
287        assert!(sparse_set.contains(id));
288        assert_eq!(sparse_set.data(), &['b']);
289        assert_eq!(sparse_set.ids(), &[id]);
290
291        // remove this one
292        assert_eq!(sparse_set.swap_remove_by_id(id), Some('b'));
293
294        assert!(!sparse_set.contains(id));
295        assert_eq!(sparse_set.len(), 0);
296        assert!(sparse_set.is_empty());
297        assert!(sparse_set.data().is_empty());
298        assert!(sparse_set.ids().is_empty());
299
300        // remove twice
301        assert_eq!(sparse_set.swap_remove_by_id(id), None);
302
303        assert!(!sparse_set.contains(id));
304        assert_eq!(sparse_set.len(), 0);
305        assert!(sparse_set.is_empty());
306        assert!(sparse_set.data().is_empty());
307        assert!(sparse_set.ids().is_empty());
308
309        // generate a lot of ids'
310        let mut rng = thread_rng();
311        let count = 100000;
312        // generate unique id
313        let ids = std::iter::from_fn(move || {
314            Some((rng.gen_range(1000..100000), rng.gen_range('a'..='z')))
315        })
316        .map(|(x, c)| (NonZeroUsize::new(x).unwrap(), c))
317        .take(count);
318
319        for (id, c) in ids {
320            sparse_set.insert(id, c);
321            assert!(sparse_set.contains(id));
322            assert_eq!(sparse_set.get(id).copied(), Some(c));
323        }
324    }
325
326    #[test]
327    fn batch_test() {
328        let mut rng = rand::thread_rng();
329        let mut sparse_set: SparseSet<EntityId, char, VecStorage<EntityId>> = SparseSet::default();
330        let mut set = BTreeSet::new();
331
332        let mut ids = Vec::new();
333        let mut data = Vec::new();
334
335        let count = 100_000;
336        for _ in 0..count {
337            'gen_data: loop {
338                let id = rng.gen_range(1..100_000_000);
339                if !set.contains(&id) {
340                    set.insert(id);
341                    let id = EntityId::new(id).unwrap();
342                    let d = rng.gen_range('a'..='z');
343
344                    ids.push(id);
345                    data.push(d);
346                    break 'gen_data;
347                }
348            }
349        }
350
351        let mut ids_in = ids.clone();
352        let mut data_in = data.clone();
353        sparse_set.insert_batch(&mut ids_in, &mut data_in);
354
355        assert_eq!(data.len(), sparse_set.len());
356        assert_eq!(&data, sparse_set.data());
357
358        for (id, data) in ids.iter().zip(data.iter()) {
359            let ch = sparse_set.get(id.clone());
360            assert!(ch.is_some());
361            assert_eq!(data.clone(), ch.copied().unwrap());
362        }
363    }
364}
xsparseset/lib.rs

xsparseset/
lib.rs
