1 files changed, 141 insertions, 0 deletions
diff --git a/engine/src/util.rs b/engine/src/util.rs
index 688778b..f820b64 100644
--- a/engine/src/util.rs
+++ b/engine/src/util.rs
@@ -204,6 +204,147 @@ where
     }
 }
 
+#[derive(Debug)]
+pub struct BitArray<const SIZE: usize, const BITS_PER_ITEM: usize>
+{
+    inner: [u8; SIZE],
+}
+
+impl<const SIZE: usize, const BITS_PER_ITEM: usize> BitArray<SIZE, BITS_PER_ITEM>
+{
+    const ITEM_MASK: u8 = !(u8::MAX << BITS_PER_ITEM);
+
+    pub fn new() -> Self
+    {
+        assert!(BITS_PER_ITEM > 1);
+        assert!(BITS_PER_ITEM <= 8);
+        assert_eq!(BITS_PER_ITEM % 2, 0);
+
+        Self { inner: [0; SIZE] }
+    }
+
+    pub fn get(&self, item_index: usize) -> u8
+    {
+        let bit_index = item_index * BITS_PER_ITEM;
+
+        let byte_index = bit_index / 8;
+
+        let bit_index_in_byte = bit_index - (byte_index * 8);
+
+        (self.inner[byte_index] >> (bit_index_in_byte)) & Self::ITEM_MASK
+    }
+
+    #[tracing::instrument(skip_all)]
+    pub fn set(&mut self, item_index: usize, item_bits: u8)
+    {
+        let item_bits = item_bits & Self::ITEM_MASK;
+
+        let bit_index = item_index * BITS_PER_ITEM;
+
+        let byte_index = bit_index / 8;
+
+        let bit_index_in_byte = bit_index - (byte_index * 8);
+
+        tracing::trace!(
+            item_bits,
+            bit_index,
+            byte_index,
+            bit_index_in_byte,
+            "Setting item bits"
+        );
+
+        self.inner[byte_index] &= !(Self::ITEM_MASK << bit_index_in_byte);
+
+        self.inner[byte_index] |= item_bits << bit_index_in_byte;
+    }
+
+    pub fn clear(&mut self)
+    {
+        self.inner.fill(0);
+    }
+
+    pub fn iter_occupied(&self) -> BitArrayOccupiedIter<'_, BITS_PER_ITEM>
+    {
+        BitArrayOccupiedIter {
+            inner: self.inner.iter().copied().enumerate(),
+            byte: None,
+            mask: u8::MAX,
+        }
+    }
+
+    pub fn bytes_mut(&mut self) -> &mut [u8]
+    {
+        &mut self.inner
+    }
+}
+
+impl<const SIZE: usize, const BITS_PER_ITEM: usize> Default
+    for BitArray<SIZE, BITS_PER_ITEM>
+{
+    fn default() -> Self
+    {
+        Self::new()
+    }
+}
+
+pub struct BitArrayOccupiedIter<'a, const BITS_PER_ITEM: usize>
+{
+    inner: std::iter::Enumerate<std::iter::Copied<std::slice::Iter<'a, u8>>>,
+    byte: Option<(u8, usize)>,
+    mask: u8,
+}
+
+impl<const BITS_PER_ITEM: usize> BitArrayOccupiedIter<'_, BITS_PER_ITEM>
+{
+    const ITEM_MASK: u8 = !(u8::MAX << BITS_PER_ITEM);
+}
+
+impl<const BITS_PER_ITEM: usize> Iterator for BitArrayOccupiedIter<'_, BITS_PER_ITEM>
+{
+    type Item = (usize, u8);
+
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        let (byte_masked, byte_index, item_bit_index_in_byte) = loop {
+            let current = self.byte.and_then(|(byte, byte_index)| {
+                let byte_masked = byte & self.mask;
+
+                let lowest_one = byte_masked.lowest_one()?;
+
+                let item_bit_index_in_byte = match lowest_one as usize % BITS_PER_ITEM {
+                    0 => lowest_one as usize,
+                    remainder => lowest_one as usize - remainder,
+                };
+
+                Some((byte_masked, byte_index, item_bit_index_in_byte))
+            });
+
+            let Some((byte_masked, byte_index, item_bit_index_in_byte)) = current else {
+                let (next_byte_index, next_byte) = self.inner.next()?;
+
+                self.byte = Some((next_byte, next_byte_index));
+                self.mask = u8::MAX;
+
+                continue;
+            };
+
+            break (byte_masked, byte_index, item_bit_index_in_byte);
+        };
+
+        let item_bits = (byte_masked >> (item_bit_index_in_byte)) & Self::ITEM_MASK;
+
+        self.mask &= (!Self::ITEM_MASK) << item_bit_index_in_byte;
+
+        let item_index_in_byte = item_bit_index_in_byte as usize / BITS_PER_ITEM;
+
+        let prev_bytes_item_cnt = (byte_index * 8) / BITS_PER_ITEM;
+
+        let index = prev_bytes_item_cnt + item_index_in_byte;
+
+        Some((index, item_bits))
+    }
+}
+
 macro_rules! try_option {
     ($expr: expr) => {
         match $expr {