xuko 0.10.0

//! Sparse set data structure

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

impl<T> SparseSet<T> {
    /// the "tombstone" index
    pub 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`], returning the index
    ///
    /// Returns [`SparseSet::NULL_INDEX`] when full
    pub fn insert(&mut self, value: T) -> usize {
        let index = self.sparse.len();
        if index == Self::NULL_INDEX {
            return Self::NULL_INDEX;
        }
        self.sparse.insert(index, self.dense.len());
        self.dense.push(value);
        index
    }

    /// 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) -> Option<T> {
        if index == Self::NULL_INDEX {
            return None;
        }

        if self.dense.is_empty() {
            return None;
        }

        let dense_index = self.sparse.get(index).copied()?;

        let back = self.dense.len() - 1;
        self.dense.swap(dense_index, back);

        let value = self.dense.remove(back);
        self.sparse[index] = Self::NULL_INDEX;
        self.sparse[back] = index;
        Some(value)
    }

    /// Returns the length of the dense part of this [`SparseSet`]
    pub fn len(&self) -> usize {
        self.dense.len()
    }

    /// Returns the length of the dense part of this [`SparseSet`]
    pub fn capacity(&self) -> usize {
        self.dense.capacity()
    }

    /// Returns whether the dense part of the [`SparseSet`] is empty
    pub fn is_empty(&self) -> bool {
        self.dense.is_empty()
    }

    /// Return a reference to the dense part of the [`SparseSet`]
    pub fn dense(&self) -> &[T] {
        &self.dense
    }

    /// Return an iterator over the [`SparseSet`]
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.dense.iter()
    }

    /// Return a mutable iterator over the [`SparseSet`]
    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.dense.iter_mut()
    }
}

impl<T> IntoIterator for SparseSet<T> {
    type Item = T;
    type IntoIter = std::vec::IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        self.dense.into_iter()
    }
}

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

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

    #[test]
    fn insert_remove_get() {
        let mut set = SparseSet::new();

        set.insert(1);
        let i = set.insert(2);
        let j = set.insert(3);
        set.remove(i);

        println!("{}", set.get(j).unwrap());
    }
}