xuko-core 0.1.0

//! Sparse set data structure

/// Sparse set data structure
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
pub struct SparseSet<T> {
    sparse: Vec<usize>,
    dense: Vec<T>,
}

impl<T> SparseSet<T> {
    const NULL_INDEX: usize = usize::MAX;

    /// Create a [`SparseSet`]
    pub fn new() -> Self {
        Self {
            sparse: Vec::new(),
            dense: Vec::new(),
        }
    }

    /// Inserts an item into the [`SparseSet`] at `index`
    pub fn insert(&mut self, index: usize, value: T) {
        if self.sparse.len() + index > self.sparse.capacity() {
            self.sparse.reserve(index.max(4));
        }
        self.sparse.insert(index, self.dense.len());
        self.dense.push(value);
    }

    /// Get a reference to an item in the [`SparseSet`]
    pub fn get(&self, index: usize) -> Option<&T> {
        if index == Self::NULL_INDEX {
            None
        } else if let Some(i) = self.sparse.get(index).copied() {
            self.dense.get(i)
        } else {
            None
        }
    }

    /// Get a mutable reference to an item in the [`SparseSet`]
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index == Self::NULL_INDEX {
            None
        } else if let Some(i) = self.sparse.get(index).copied() {
            self.dense.get_mut(i)
        } else {
            None
        }
    }

    /// Removes an element from the [`SparseSet`]
    pub fn remove(&mut self, index: usize) {
        if self.dense.is_empty() {
            return;
        }

        let Some(dense_index) = self.sparse.get(index).copied() else {
            return;
        };

        let back = self.dense.len() - 1;
        self.dense.swap(dense_index, back);
        self.dense.remove(back);
        self.sparse[index] = Self::NULL_INDEX;
        self.sparse[back] = index;
    }
}

impl<T> Default for SparseSet<T> {
    fn default() -> Self {
        Self {
            sparse: Vec::new(),
            dense: Vec::new(),
        }
    }
}

#[cfg(test)]
mod tests {
    use std::time::SystemTime;

    use super::*;

    #[test]
    fn basic() {
        const N: usize = 1000000;
        let time = SystemTime::now();
        let mut set = SparseSet::new();

        // set.insert(43, "".to_owned());

        let mut remove = vec![];
        for i in 0..=N {
            set.insert(i, format!("Hello #{i}"));

            if i % 153 == 0 {
                remove.push(i);
            }
        }

        // println!("{:?}", set.dense);

        for i in &remove {
            set.remove(*i);
        }
        let dur = time.elapsed().unwrap();
        println!("Time took: {}ms:{}ns", dur.as_millis(), dur.as_nanos());
        remove.clear();

        let mut hash = std::collections::HashMap::new();
        let time = SystemTime::now();
        for i in 0..=N {
            hash.insert(i, format!("Hello #{i}"));

            if i % 153 == 0 {
                remove.push(i);
            }
        }

        for i in &remove {
            hash.remove(i);
        }

        let dur = time.elapsed().unwrap();
        println!("Time took: {}ms:{}ns", dur.as_millis(), dur.as_nanos());
    }
}