1 files changed, 216 insertions, 0 deletions
diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs
new file mode 100644
index 0000000..ee3d7f8
--- /dev/null
+++ b/ecs/src/component/storage/archetype.rs
@@ -0,0 +1,216 @@
+use std::borrow::Borrow;
+use std::hash::{DefaultHasher, Hash, Hasher};
+use std::slice::Iter as SliceIter;
+
+use hashbrown::HashMap;
+
+use crate::component::Metadata as ComponentMetadata;
+use crate::uid::{Kind as UidKind, Uid};
+use crate::util::HashMapExt;
+use crate::EntityComponent;
+
+#[derive(Debug)]
+pub struct Archetype
+{
+    id: Id,
+    entities: Vec<ArchetypeEntity>,
+    entity_index_lookup: HashMap<Uid, usize>,
+    component_index_lookup: HashMap<Uid, usize>,
+}
+
+impl Archetype
+{
+    pub fn new(id: Id, component_ids: impl IntoIterator<Item: Borrow<Uid>>) -> Self
+    {
+        Self {
+            id,
+            entities: Vec::new(),
+            entity_index_lookup: HashMap::new(),
+            component_index_lookup: component_ids
+                .into_iter()
+                .enumerate()
+                .map(|(index, id)| (*id.borrow(), index))
+                .collect(),
+        }
+    }
+
+    pub fn id(&self) -> Id
+    {
+        self.id
+    }
+
+    pub fn is_superset(&self, other: &Self) -> bool
+    {
+        self.component_index_lookup
+            .keys_is_superset(&other.component_index_lookup)
+    }
+
+    pub fn get_entity_by_id(&self, entity_uid: Uid) -> Option<&ArchetypeEntity>
+    {
+        let index = *self.entity_index_lookup.get(&entity_uid)?;
+
+        Some(self.entities.get(index).unwrap_or_else(|| {
+            panic!(
+                "In invalid state! Index of entity with ID {entity_uid:?} is out of bounds"
+            );
+        }))
+    }
+
+    pub fn push_entity(&mut self, entity: ArchetypeEntity)
+    {
+        self.entity_index_lookup
+            .insert(entity.uid, self.entities.len());
+
+        self.entities.push(entity);
+    }
+
+    pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity>
+    {
+        //debug_assert_eq!(entity_uid.kind(), UidKind::Entity);
+
+        let entity_index = self.entity_index_lookup.remove(&entity_uid)?;
+
+        if self.entities.len() == 1 {
+            return Some(self.entities.remove(entity_index));
+        }
+
+        let last_entity_uid = self
+            .entities
+            .last()
+            .expect(concat!(
+                "Invalid state. No entities in archetype but entry was ",
+                "removed successfully from entity index lookup"
+            ))
+            .uid;
+
+        // By using swap_remove, no memory reallocation occurs and only one index in the
+        // entity lookup needs to be updated
+        let removed_entity = self.entities.swap_remove(entity_index);
+
+        self.entity_index_lookup
+            .insert(last_entity_uid, entity_index);
+
+        Some(removed_entity)
+    }
+
+    pub fn entities(&self) -> EntityIter<'_>
+    {
+        EntityIter { iter: self.entities.iter() }
+    }
+
+    pub fn entity_cnt(&self) -> usize
+    {
+        self.entities.len()
+    }
+
+    pub fn component_cnt(&self) -> usize
+    {
+        self.component_index_lookup.len()
+    }
+
+    pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize>
+    {
+        self.component_index_lookup.get(&component_id).copied()
+    }
+
+    pub fn component_ids_unsorted(&self) -> impl Iterator<Item = Uid> + '_
+    {
+        self.component_index_lookup.keys().copied()
+    }
+
+    pub fn has_component_with_id(&self, component_id: Uid) -> bool
+    {
+        debug_assert_eq!(component_id.kind(), UidKind::Component);
+
+        self.component_index_lookup.contains_key(&component_id)
+    }
+}
+
+#[derive(Debug)]
+pub struct EntityIter<'archetype>
+{
+    iter: SliceIter<'archetype, ArchetypeEntity>,
+}
+
+impl<'archetype> Iterator for EntityIter<'archetype>
+{
+    type Item = &'archetype ArchetypeEntity;
+
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        self.iter.next()
+    }
+}
+
+#[derive(Debug)]
+pub struct ArchetypeEntity
+{
+    pub uid: Uid,
+    pub components: Vec<EntityComponent>,
+}
+
+/// Archetype ID.
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
+pub struct Id
+{
+    hash: u64,
+}
+
+impl Id
+{
+    pub fn new(component_ids: &impl AsRef<[Uid]>) -> Self
+    {
+        if component_ids.as_ref().len() == 0 {
+            return Self { hash: 0 };
+        }
+
+        debug_assert!(
+            component_ids.as_ref().is_sorted(),
+            "Cannot create archetype ID from unsorted component IDs"
+        );
+
+        let mut hasher = DefaultHasher::new();
+
+        for component_id in component_ids.as_ref() {
+            component_id.hash(&mut hasher);
+        }
+
+        Self { hash: hasher.finish() }
+    }
+
+    pub fn from_components_metadata(
+        components_metadata: &impl AsRef<[ComponentMetadata]>,
+    ) -> Self
+    {
+        if components_metadata.as_ref().len() == 0 {
+            return Self { hash: 0 };
+        }
+
+        debug_assert!(
+            components_metadata
+                .as_ref()
+                .is_sorted_by_key(|comp_metadata| comp_metadata.id),
+            "Cannot create archetype ID from a unsorted component metadata list"
+        );
+
+        let component_ids =
+            components_metadata
+                .as_ref()
+                .iter()
+                .filter_map(|component_metadata| {
+                    if component_metadata.is_optional {
+                        return None;
+                    }
+
+                    Some(component_metadata.id)
+                });
+
+        let mut hasher = DefaultHasher::new();
+
+        for component_id in component_ids {
+            component_id.hash(&mut hasher);
+        }
+
+        Self { hash: hasher.finish() }
+    }
+}