checs 0.5.1

//! Entities and their allocation.

use std::collections::BTreeSet;
use std::error;
use std::fmt;

/// The underlying integer type that represents an entity.
///
/// > 4 billion entities ought to be enough for anybody.
/// >
/// > -- <cite>Someone, somewhere presumably</cite>
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) struct Index(u32);

impl Index {
    pub const MAX: Index = Index(u32::MAX - 1);
    pub const UNINIT: Index = Index(u32::MAX);

    #[inline]
    pub fn as_usize(self) -> usize {
        self.0 as usize
    }

    #[inline]
    pub fn from_usize_truncate(value: usize) -> Index {
        #![allow(clippy::cast_possible_truncation)]

        debug_assert!(u32::try_from(value).is_ok());
        Index(value as u32)
    }
}

/// A thing that can be associated with components.
///
/// An entity can be associated with components by inserting them in a [`ComponentVec`].
///
/// [`ComponentVec`]: crate::ComponentVec
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Entity(Index);

impl Entity {
    #[inline]
    pub(crate) fn as_usize(self) -> usize {
        self.0.as_usize()
    }

    /// Creates a new entity, without using an [`Allocator`].
    ///
    /// This is used for crate internal unit tests only.
    #[allow(dead_code)]
    #[inline]
    pub(crate) fn from(value: u32) -> Entity {
        Entity(Index(value))
    }
}

/// An allocator that can create new entities and free old entities.
///
/// This is not necessarily meant to be used directly. Instead, a [`World`] can be used to manage
/// entities and components, which maintains its own `Allocator`.
///
/// [`World`]: crate::World
///
/// # Examples
///
/// ```
/// use checs::entity::{Allocator, Error};
///
/// let mut entities = Allocator::new();
///
/// let entity = entities.alloc();
///
/// assert_eq!(entities.free(entity), Ok(()));
/// assert_eq!(entities.free(entity), Err(Error::DoubleFree));
/// ```
///
/// Constructing an `Entity` without using an `Allocator` is currently not supported:
///
/// ```compile_fail
/// let impossible = checs::Entity(99);
///
/// assert_eq!(entities.free(impossible), Err(Error::Unallocated));
/// ```
pub struct Allocator {
    count: Index,
    freed: BTreeSet<Entity>,
}

impl Allocator {
    /// Constructs a new `Allocator`.
    #[must_use]
    #[inline]
    pub fn new() -> Self {
        Self {
            count: Index(0),
            freed: BTreeSet::new(),
        }
    }

    /// Creates a new entity.
    ///
    /// # Panics
    ///
    /// Panics if the maximum number of entities has been reached. The current maximum is at
    /// [`u32::MAX - 1`](u32::MAX).
    #[must_use]
    #[inline]
    pub fn alloc(&mut self) -> Entity {
        if let Some(entity) = self.freed.pop_first() {
            entity
        } else {
            assert!(self.count < Index::MAX, "out of entities");

            let entity = self.count;
            self.count = Index(self.count.0 + 1);
            Entity(entity)
        }
    }

    /// Frees an entity.
    ///
    /// # Errors
    ///
    /// Returns an [`Error::Unallocated`] if the `entity` has never been allocated.
    /// Returns an [`Error::DoubleFree`] if the `entity` has already been freed.
    ///
    /// # Note
    ///
    /// This methods does not and can not remove any components from the `entity`. To do this use a
    /// higher-level collection like [`World`] and its [`remove`] method, which both frees an
    /// entity and removes all of its components.
    ///
    /// [`remove`]: crate::World::remove
    /// [`World`]: crate::World
    #[inline]
    pub fn free(&mut self, entity: Entity) -> Result<(), Error> {
        if entity.0 >= self.count {
            Err(Error::Unallocated)
        } else if self.freed.insert(entity) {
            Ok(())
        } else {
            Err(Error::DoubleFree)
        }
    }
}

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

/// The error type which is returned from the methods of an [`Allocator`].
#[derive(Debug, PartialEq)]
pub enum Error {
    /// An unallocated entity was freed.
    Unallocated,
    /// An entity was freed multiple times.
    DoubleFree,
}

impl fmt::Display for Error {
    #[inline]
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Error::Unallocated => f.write_str("an unallocated entity cannot be freed"),
            Error::DoubleFree => f.write_str("an entity cannot be freed twice"),
        }
    }
}

impl error::Error for Error {}

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

    #[test]
    fn alloc_free_and_reuse() {
        let mut entity_allocator = Allocator::new();

        let e0 = entity_allocator.alloc();
        let e1 = entity_allocator.alloc();

        assert_eq!(e0, Entity::from(0));
        assert_eq!(e1, Entity::from(1));

        entity_allocator.free(e0).unwrap();

        let e2 = entity_allocator.alloc();
        let e3 = entity_allocator.alloc();

        assert_eq!(e2, Entity::from(0));
        assert_eq!(e3, Entity::from(2));

        // Double free an entity.
        entity_allocator.free(e3).unwrap();
        let err = entity_allocator.free(e3).unwrap_err();

        assert_eq!(err, Error::DoubleFree);

        // Free an unallocated entity.
        let err = entity_allocator.free(Entity::from(99)).unwrap_err();

        assert_eq!(err, Error::Unallocated);
    }
}