nya-core 0.2.0

//! Sparse Set

use smallvec::SmallVec;

/// An entry in the [SparseSet]
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Entry<T> {
    sparse_index: usize,

    /// Value contained in the entry
    pub value: T,
}

impl<T> Entry<T> {
    /// Get the sparse index associated with the entry
    pub fn index(&self) -> usize {
        self.sparse_index
    }
}

/// See [module-level documentation](self)
pub struct SparseSet<T> {
    new_index: usize,
    sparse: SmallVec<[usize; 32]>,
    dense: Vec<Entry<T>>,
}

impl<T> SparseSet<T> {
    /// Initialize a new empty sparse set
    #[must_use]
    pub fn new() -> Self {
        Self {
            new_index: 0,
            sparse: SmallVec::new(),
            dense: Vec::new(),
        }
    }

    /// Create a sparse set with dense capacity `n`
    #[must_use]
    pub fn with_capacity(n: usize) -> Self {
        Self {
            new_index: 0,
            sparse: SmallVec::new(),
            dense: Vec::with_capacity(n),
        }
    }

    /// Insert an item into the sparse set
    pub fn insert(&mut self, value: T) -> usize {
        let dense_index = self.dense.len();
        let sparse_index = self.new_index;
        self.new_index += 1;

        self.dense.push(Entry {
            sparse_index,
            value,
        });
        self.sparse.push(dense_index);

        return sparse_index;
    }

    /// Remove an element from the sparse set
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if index >= self.sparse.len() {
            return None;
        }

        let dense_index = self.sparse.get(index).copied()?;
        if self.dense.get(dense_index).is_none() {
            return None;
        }

        self.sparse[index] = self.dense.len();

        Some(self.dense.swap_remove(dense_index).value)
    }

    /// Get a reference to element at `index`
    #[must_use]
    pub fn get(&self, index: usize) -> Option<&T> {
        if index >= self.sparse.len() {
            return None;
        }

        let dense_index = self.sparse.get(index).copied()?;
        self.dense.get(dense_index).map(|entry| &entry.value)
    }

    /// Get a mutable reference to element at `index`
    #[must_use]
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index >= self.sparse.len() {
            return None;
        }

        let dense_index = self.sparse.get(index).copied()?;
        self.dense
            .get_mut(dense_index)
            .map(|entry| &mut entry.value)
    }

    /// Create an immutable iterator for the sparse set
    #[must_use]
    pub fn iter<'a>(&'a self) -> iter::Iter<'a, T> {
        iter::Iter::new(self)
    }

    /// Create a mutable iterator for the sparse set
    #[must_use]
    pub fn iter_mut<'a>(&'a mut self) -> iter::IterMut<'a, T> {
        iter::IterMut::new(self)
    }
}

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

impl<'a, T> IntoIterator for &'a SparseSet<T> {
    type Item = &'a Entry<T>;
    type IntoIter = iter::Iter<'a, T>;

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

impl<'a, T> IntoIterator for &'a mut SparseSet<T> {
    type Item = &'a mut Entry<T>;
    type IntoIter = iter::IterMut<'a, T>;

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

impl<T> IntoIterator for SparseSet<T> {
    type Item = Entry<T>;
    type IntoIter = iter::IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        iter::IntoIter::new(self)
    }
}

#[cfg(feature = "serde")]
impl<T: serde::Serialize> serde::Serialize for SparseSet<T> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        let v = self.dense.iter().map(|e| &e.value).collect::<Vec<_>>();
        v.serialize(serializer)
    }
}

#[cfg(feature = "serde")]
impl<'de, T: serde::Deserialize<'de>> serde::Deserialize<'de> for SparseSet<T> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let de: Vec<T> = Vec::deserialize(deserializer)?;
        let mut s = SparseSet::new();
        for e in de {
            s.insert(e);
        }
        Ok(s)
    }
}

/// Iterators
pub mod iter {
    use std::mem;

    use super::{Entry, SparseSet};

    /// Immutable iterator to a [SparseSet]
    pub struct Iter<'a, T> {
        sparse: &'a SparseSet<T>,
        index: usize,
    }

    impl<'a, T> Iter<'a, T> {
        pub(crate) fn new(sparse: &'a SparseSet<T>) -> Self {
            Self { sparse, index: 0 }
        }
    }

    impl<'a, T> Iterator for Iter<'a, T> {
        type Item = &'a Entry<T>;

        fn next(&mut self) -> Option<Self::Item> {
            let index = self.index;
            self.index += 1;
            self.sparse.dense.get(index)
        }
    }

    /// Mutable iterator to a [SparseSet]
    pub struct IterMut<'a, T> {
        sparse: &'a mut SparseSet<T>,
        index: usize,
    }

    impl<'a, T> IterMut<'a, T> {
        pub(crate) fn new(sparse: &'a mut SparseSet<T>) -> Self {
            Self { sparse, index: 0 }
        }
    }

    impl<'a, T> Iterator for IterMut<'a, T> {
        type Item = &'a mut Entry<T>;

        fn next(&mut self) -> Option<Self::Item> {
            let index = self.index;
            self.index += 1;
            self.sparse
                .dense
                .get_mut(index)
                .map(|v| unsafe { &mut *(v as *mut Entry<T>) })
        }
    }

    /// [SparseSet] iterator that owns the structure
    pub struct IntoIter<T> {
        sparse: SparseSet<T>,
        index: usize,
    }

    impl<T> IntoIter<T> {
        pub(crate) fn new(sparse: SparseSet<T>) -> Self {
            Self { sparse, index: 0 }
        }
    }

    impl<T> Iterator for IntoIter<T> {
        type Item = Entry<T>;

        fn next(&mut self) -> Option<Self::Item> {
            let index = self.index;
            if index == self.sparse.dense.len() {
                None
            } else {
                self.index += 1;
                let mut entry = unsafe { mem::zeroed() };
                mem::swap(&mut self.sparse.dense[index], &mut entry);
                Some(entry)
            }
        }
    }
}

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

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

        set.insert(1);
        let index = set.insert(2);
        assert_eq!(set.remove(index), Some(2));
        assert_eq!(set.insert(3), 2);
    }

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

        set.insert("static string");
        set.insert("another static string");
        let i = set.insert("abcdefghi");
        set.remove(i);
        assert_eq!(set.insert("hello"), 3);
        set.insert("feijfoej");

        for entry in set.iter() {
            println!("entry #{}: {}", entry.index(), entry.value);
        }
        println!("{:?}, {:#?}", set.sparse, set.dense);
    }
}