incular-core 0.1.1

//! Safe generational storage used by retained framework trees.

use std::fmt;

/// Stable slot identity. A removed slot increments its generation before reuse.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct ArenaId {
    index: u32,
    generation: u32,
}

impl ArenaId {
    #[must_use]
    pub const fn from_parts(index: u32, generation: u32) -> Self {
        Self { index, generation }
    }

    #[must_use]
    pub const fn index(self) -> u32 {
        self.index
    }

    /// Slot generation, bumped on removal so reused slots are distinguishable.
    #[must_use]
    pub const fn generation(self) -> u32 {
        self.generation
    }
}

impl fmt::Debug for ArenaId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "ArenaId({}, {})", self.index, self.generation)
    }
}

struct Slot<T> {
    generation: u32,
    value: Option<T>,
}

/// Compact safe arena used by persistent framework trees. It never exposes
/// references across mutations, so tree algorithms can remain ordinary
/// `&mut self` code.
pub struct Arena<T> {
    slots: Vec<Slot<T>>,
    free: Vec<u32>,
    len: usize,
}

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

impl<T> Arena<T> {
    #[must_use]
    pub const fn new() -> Self {
        Self {
            slots: Vec::new(),
            free: Vec::new(),
            len: 0,
        }
    }

    pub fn insert(&mut self, value: T) -> ArenaId {
        if let Some(index) = self.free.pop() {
            let slot = &mut self.slots[index as usize];
            debug_assert!(slot.value.is_none());
            slot.value = Some(value);
            self.len += 1;
            ArenaId::from_parts(index, slot.generation)
        } else {
            let index = u32::try_from(self.slots.len()).expect("arena identity space exhausted");
            if self.slots.len() == self.slots.capacity() {
                // Grow by half instead of doubling. Retained trees settle at
                // arbitrary sizes and their slots are large, so doubling can
                // leave nearly half of a big allocation unused; 1.5x growth
                // keeps inserts amortized O(1) with much less slack.
                self.slots.reserve_exact((self.slots.len() / 2).max(8));
            }
            self.slots.push(Slot {
                generation: 0,
                value: Some(value),
            });
            self.len += 1;
            ArenaId::from_parts(index, 0)
        }
    }

    #[must_use]
    pub fn get(&self, id: ArenaId) -> Option<&T> {
        let slot = self.slots.get(id.index as usize)?;
        (slot.generation == id.generation)
            .then_some(slot.value.as_ref())
            .flatten()
    }

    pub fn get_mut(&mut self, id: ArenaId) -> Option<&mut T> {
        let slot = self.slots.get_mut(id.index as usize)?;
        (slot.generation == id.generation)
            .then_some(slot.value.as_mut())
            .flatten()
    }

    pub fn remove(&mut self, id: ArenaId) -> Option<T> {
        let slot = self.slots.get_mut(id.index as usize)?;
        if slot.generation != id.generation {
            return None;
        }
        let value = slot.value.take()?;
        if let Some(next_generation) = slot.generation.checked_add(1) {
            slot.generation = next_generation;
            self.free.push(id.index);
        }
        self.len -= 1;
        Some(value)
    }

    #[must_use]
    pub fn contains(&self, id: ArenaId) -> bool {
        self.get(id).is_some()
    }

    #[must_use]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn iter(&self) -> impl Iterator<Item = (ArenaId, &T)> {
        self.slots.iter().enumerate().filter_map(|(index, slot)| {
            slot.value.as_ref().map(|value| {
                (
                    ArenaId::from_parts(
                        u32::try_from(index).expect("arena index was validated on insertion"),
                        slot.generation,
                    ),
                    value,
                )
            })
        })
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = (ArenaId, &mut T)> {
        self.slots
            .iter_mut()
            .enumerate()
            .filter_map(|(index, slot)| {
                let generation = slot.generation;
                slot.value.as_mut().map(|value| {
                    (
                        ArenaId::from_parts(
                            u32::try_from(index).expect("arena index was validated on insertion"),
                            generation,
                        ),
                        value,
                    )
                })
            })
    }
}