checs 0.5.1

//! A sparse set for storing entities.

use crate::entity;
use crate::iter;

/// A [sparse set](https://www.geeksforgeeks.org/sparse-set/) of entities, which assigns each
/// [`Entity`] a unique index in a densely packed array.
///
/// The time complexity for [`insert`], [`remove`], [`index_of`], and [`contains`] is `O(1)`.
///
/// The set internally maintains two arrays: `sparse` and `dense`.
///
/// - `sparse`:
///   - Contains indices to entities in the `dense` array.
///   - Entities are used as indices.
///   - Is sparse, meaning it may have holes.
///   - Its length is based on the entity with the highest value in the set.
/// - `dense`:
///   - Contains entities.
///   - Is densely packed.
///   - Its length is the number of entities in the set.
///
/// This should true for any entity in the set: `dense[sparse[entity]] == entity`
///
/// [`Entity`]: entity::Entity
/// [`insert`]: Set::insert
/// [`remove`]: Set::remove
/// [`index_of`]: Set::index_of
/// [`contains`]: Set::contains
pub struct Set {
    sparse: Vec<entity::Index>,
    dense: Vec<entity::Entity>,
}

impl Set {
    /// Constructs a new `Set`.
    #[must_use]
    #[inline]
    pub fn new() -> Self {
        Self {
            sparse: Vec::new(),
            dense: Vec::new(),
        }
    }

    /// Returns the number of elements in the set, also referred to as its 'length'.
    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.dense.len()
    }

    /// Returns `true` if the set contains no elements.
    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns `true` if the set contains the `entity`.
    #[must_use]
    #[inline]
    pub fn contains(&self, entity: entity::Entity) -> bool {
        self.index_of(entity).is_some()
    }

    /// Returns the index that was assigned to the `entity`.
    #[must_use]
    #[inline]
    pub fn index_of(&self, entity: entity::Entity) -> Option<usize> {
        self.sparse
            .get(entity.as_usize())
            .filter(|&&i| i != entity::Index::UNINIT)
            .map(|&i| i.as_usize())
    }

    /// Adds the `entity` to the set.
    ///
    /// Returns `true` if the `entity` was inserted into the set, returns `false` if the `entity`
    /// was already contained in the set.
    #[inline]
    pub fn insert(&mut self, entity: entity::Entity) -> bool {
        if self.contains(entity) {
            return false;
        }

        self.dense.push(entity);

        let sparse_index = entity.as_usize();

        // SAFETY: The following will not truncate, because:
        // - `entity::Index` is `u32`, so it is always smaller than (or equal to) the maximum value
        //   for `self.dense.len()`.
        // - There cannot be duplicate entities (see the use of `contains` above), so there is at
        //   most one entry in `self.dense` per entity.
        // - Therefore, `self.dense.len()` is always small enough to fit in `entity::Index`/`u32`.
        let dense_index = entity::Index::from_usize_truncate(self.dense.len() - 1);

        let min_size = sparse_index + 1;
        if self.sparse.len() < min_size {
            self.sparse.resize(min_size, entity::Index::UNINIT);
        }

        self.sparse[sparse_index] = dense_index;

        true
    }

    /// Removes the `entity` from the set.
    ///
    /// Returns `true` if the `entity` was removed from the set, returns `false` if the `entity`
    /// was not contained in the set.
    #[inline]
    pub fn remove(&mut self, entity: entity::Entity) -> bool {
        if let (Some(index), Some(last)) = (self.index_of(entity), self.dense.pop()) {
            if last != entity {
                self.dense[index] = last;

                // See the SAFETY comment in `fn insert` to find out why this will not truncate.
                self.sparse[last.as_usize()] = entity::Index::from_usize_truncate(index);
            }

            self.sparse[entity.as_usize()] = entity::Index::UNINIT;

            true
        } else {
            false
        }
    }

    /// Reserves capacity for at least `additional` more elements to be inserted into the set.
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        self.dense.reserve(additional);

        // `sparse` is resized to fit at least as many elements as `dense`. This is very likely an
        // underestimate, but it is the best that can be done, because the exact size that is
        // required of `sparse` depends on the entities that are (and will be) stored in the `Set`,
        // which is unknowable.
        if self.dense.capacity() > self.sparse.len() {
            self.sparse
                .resize(self.dense.capacity(), entity::Index::UNINIT);
        }
    }

    /// An iterator visiting all entities in the set.
    #[inline]
    pub fn iter(&self) -> iter::Iter<'_, entity::Entity> {
        self.dense.iter().copied()
    }
}

impl<'a> IntoIterator for &'a Set {
    type IntoIter = iter::Iter<'a, entity::Entity>;
    type Item = entity::Entity;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl Default for Set {
    #[inline]
    fn default() -> Set {
        Set::new()
    }
}

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

    #[test]
    fn sparse_set_append_then_remove() {
        let mut set = Set::new();

        set.insert(Entity::from(17));
        assert_eq!(set.dense.len(), 1);
        assert_eq!(set.sparse.len(), 18);

        assert_eq!(set.index_of(Entity::from(17)), Some(0));

        set.insert(Entity::from(99));
        assert_eq!(set.dense.len(), 2);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(17)), Some(0));
        assert_eq!(set.index_of(Entity::from(99)), Some(1));

        set.insert(Entity::from(42));
        assert_eq!(set.dense.len(), 3);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(17)), Some(0));
        assert_eq!(set.index_of(Entity::from(99)), Some(1));
        assert_eq!(set.index_of(Entity::from(42)), Some(2));

        set.remove(Entity::from(99));
        assert_eq!(set.dense.len(), 2);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(17)), Some(0));
        assert_eq!(set.index_of(Entity::from(42)), Some(1));
        assert_eq!(set.index_of(Entity::from(99)), None);

        set.insert(Entity::from(0));
        assert_eq!(set.dense.len(), 3);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(17)), Some(0));
        assert_eq!(set.index_of(Entity::from(42)), Some(1));
        assert_eq!(set.index_of(Entity::from(99)), None);
        assert_eq!(set.index_of(Entity::from(0)), Some(2));

        set.remove(Entity::from(0));
        assert_eq!(set.dense.len(), 2);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(17)), Some(0));
        assert_eq!(set.index_of(Entity::from(42)), Some(1));
        assert_eq!(set.index_of(Entity::from(99)), None);
        assert_eq!(set.index_of(Entity::from(0)), None);

        set.remove(Entity::from(17));
        assert_eq!(set.dense.len(), 1);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(42)), Some(0));
        assert_eq!(set.index_of(Entity::from(17)), None);
        assert_eq!(set.index_of(Entity::from(99)), None);
        assert_eq!(set.index_of(Entity::from(0)), None);

        set.remove(Entity::from(42));
        assert_eq!(set.dense.len(), 0);
        assert_eq!(set.sparse.len(), 100);

        assert_eq!(set.index_of(Entity::from(17)), None);
        assert_eq!(set.index_of(Entity::from(99)), None);
        assert_eq!(set.index_of(Entity::from(42)), None);
        assert_eq!(set.index_of(Entity::from(0)), None);
    }

    #[test]
    fn sparse_set_maximum_range() {
        let mut set = Set::new();

        for i in 0..256 {
            set.insert(Entity::from(i));
        }

        assert_eq!(set.dense.len(), 256);
        assert_eq!(set.sparse.len(), 256);

        assert_eq!(set.index_of(Entity::from(0)), Some(0));
        assert_eq!(set.index_of(Entity::from(255)), Some(255));

        for i in 0..256 {
            set.remove(Entity::from(i));
        }

        assert_eq!(set.dense.len(), 0);
        assert_eq!(set.sparse.len(), 256);

        assert_eq!(set.index_of(Entity::from(0)), None);
        assert_eq!(set.index_of(Entity::from(255)), None);
    }

    #[test]
    fn reserve() {
        let mut set = Set::new();

        set.insert(Entity::from(50));

        assert_eq!(set.dense.len(), 1);
        assert!(set.dense.capacity() > 0);
        assert_eq!(set.sparse.len(), 51);

        let additional = 100;
        set.reserve(additional);

        assert_eq!(set.dense.len(), 1);
        assert!(set.dense.capacity() >= set.dense.len() + additional);
        assert_eq!(set.sparse.len(), set.dense.capacity());

        let mut set = Set::new();

        set.insert(Entity::from(1000));

        assert_eq!(set.dense.len(), 1);
        assert!(set.dense.capacity() > 0);
        let sparse_len = set.sparse.len();
        assert_eq!(sparse_len, 1001);

        let additional = 100;
        set.reserve(additional);

        assert_eq!(set.dense.len(), 1);
        assert!(set.dense.capacity() >= set.dense.len() + additional);
        // `sparse` was not resized because it was big enough already.
        assert_eq!(set.sparse.len(), sparse_len);
    }

    #[test]
    fn contains() {
        let mut set = Set::new();

        let e0 = entity::Entity::from(0);
        let e1 = entity::Entity::from(1);
        let e2 = entity::Entity::from(2);

        set.insert(e0);
        set.insert(e2);

        assert_eq!(set.contains(e0), true);
        assert_eq!(set.contains(e1), false);
        assert_eq!(set.contains(e2), true);
    }
}