grapes 0.3.0

//! Persistent [Arena] & related items
//!
//! An [Arena] is a data structure that maps [EntryId]s to values of some type.
//!
//! When you insert an item, you get the corresponding ID, and that ID won't change for as long as the item stays in the Arena. You can then retrieve or remove an item by its ID.
//!
//! This is useful for building graph-like data structures – for example, you can describe the relationships between nodes by using their IDs. The tree and graph datastructures in this library are built on top of this Arena.

use std::iter::Enumerate;
use std::mem::swap;
use std::ops::{Index, IndexMut};

use imbl::vector::Iter;
use imbl::Vector;

// todo: the current implementation of this immutable arena is very naively implemented – we're simply copying how it would be implemented with a regular Vec, and swapping it out for an immutable Vector. there are likely much better implementations possible with a custom clever immutable data structure. don't do anything before benchmarking though

/// A persistent Arena – a collection of items with stable IDs
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Arena<T: Clone> {
    entries: Vector<Entry<T>>,
    first_free: Option<EntryId>,
}

#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
/// The ID of an entry in an Arena
pub struct EntryId(pub(crate) usize);

#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
enum Entry<T> {
    Some(T),
    Free { next_free: Option<EntryId> },
}

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

impl<T: Clone> Arena<T> {
    /// Constructs a new, empty Arena.
    #[must_use]
    pub fn new() -> Self {
        Self {
            entries: Vector::new(),
            first_free: None,
        }
    }

    /// Verifies that the Arena is in a valid state
    ///
    /// All arenas must be valid; an invalid arena indicates a bug in the library code
    ///
    /// The Free linked list must:
    /// - Contain all free entries, and only free entries
    /// - Not be circular
    ///
    /// Panics if the state is invalid
    #[cfg(test)]
    pub(crate) fn validate(&self) {
        use std::collections::HashSet;

        let expected_free_indices: HashSet<_> = self
            .entries
            .iter()
            .enumerate()
            .filter_map(|(index, entry)| match entry {
                Entry::Free { .. } => Some(EntryId(index)),
                _ => None,
            })
            .collect();

        let mut found_free_indices = HashSet::new();

        let mut free_cursor = self.first_free;
        while let Some(index) = free_cursor {
            let had_value = !found_free_indices.insert(index);

            assert!(
                !had_value,
                "Circular Free list: index {:?} encountered twice",
                index
            );

            match self.entries[index.0] {
                Entry::Some(_) => {
                    panic!(
                        "Index {:?} present in Free list, but is in fact occupied",
                        index
                    )
                }
                Entry::Free { next_free } => {
                    free_cursor = next_free;
                }
            }
        }

        assert_eq!(expected_free_indices, found_free_indices);
    }

    /// Insert a new item into the Arena
    ///
    /// Returns the index of the new item
    pub fn insert(&mut self, value: T) -> EntryId {
        match self.first_free {
            None => {
                self.entries.push_back(Entry::Some(value));
                EntryId(self.entries.len() - 1)
            }
            Some(index) => {
                let mut entry = Entry::Some(value);
                swap(&mut self.entries[index.0], &mut entry);

                match entry {
                    Entry::Some(_) => {
                        panic!("Corrupt free list: pointed to occupied entry")
                    }
                    Entry::Free { next_free } => {
                        self.first_free = next_free;
                    }
                }

                index
            }
        }
    }

    /// Remove an item at the specified index
    ///
    /// Returns the item if it exists; [None] otherwise
    pub fn remove(&mut self, index: EntryId) -> Option<T> {
        let entry = match self.entries.get_mut(index.0) {
            Some(entry @ Entry::Some(_)) => entry,
            _ => return None,
        };

        let mut new_entry = Entry::Free {
            next_free: self.first_free,
        };
        swap(entry, &mut new_entry);
        // swapped; rename to reflect new contents
        let old_entry = new_entry;

        let removed = match old_entry {
            Entry::Some(value) => Some(value),
            Entry::Free { .. } => unreachable!(),
        };

        self.first_free = Some(index);
        removed
    }

    /// Get the item with the specified index, or [None] if no such item exists
    #[must_use]
    pub fn get(&self, index: EntryId) -> Option<&T> {
        match self.entries.get(index.0) {
            Some(Entry::Some(value)) => Some(value),
            _ => None,
        }
    }

    /// Get a mutable reference to the item with the specified index, or [None] if no such item exists
    #[must_use]
    pub fn get_mut(&mut self, index: EntryId) -> Option<&mut T> {
        match self.entries.get_mut(index.0) {
            Some(Entry::Some(value)) => Some(value),
            _ => None,
        }
    }

    /// Iterate over all items (id and value) in arena in unspecified order
    pub fn iter_items(&self) -> ArenaItems<T> {
        ArenaItems {
            inner: self.entries.iter().enumerate(),
        }
    }
}

impl<T: Clone> Index<EntryId> for Arena<T> {
    type Output = T;

    fn index(&self, index: EntryId) -> &Self::Output {
        match &self.entries[index.0] {
            Entry::Some(value) => value,
            Entry::Free { .. } => panic!("No entry at index {:?}", index),
        }
    }
}

impl<T: Clone> IndexMut<EntryId> for Arena<T> {
    fn index_mut(&mut self, index: EntryId) -> &mut Self::Output {
        match &mut self.entries[index.0] {
            Entry::Some(value) => value,
            Entry::Free { .. } => panic!("No entry at index {:?}", index),
        }
    }
}

#[must_use]
/// Iterator over all items in an Arena
pub struct ArenaItems<'a, T: Clone> {
    inner: Enumerate<Iter<'a, Entry<T>>>,
}

impl<'a, T: Clone> Iterator for ArenaItems<'a, T> {
    type Item = (EntryId, &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (index, entry) = self.inner.next()?;

            if let Entry::Some(data) = entry {
                return Some((EntryId(index), data));
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::arena::Entry::Free;

    use super::*;

    #[test]
    fn insert() {
        let mut arena = Arena::new();
        let a = arena.insert(42);
        let b = arena.insert(43);
        assert_eq!(arena[a], 42);
        assert_eq!(arena[b], 43);

        arena.validate();
    }

    #[test]
    fn get() {
        let mut arena = Arena::new();
        let a = arena.insert(42);
        assert_eq!(arena.get(a).unwrap(), &42);

        arena.validate();
    }

    #[test]
    fn get_out_of_bounds_is_none() {
        let mut arena = Arena::new();
        arena.insert(42);
        assert!(arena.get(EntryId(5)).is_none());

        arena.validate();
    }

    #[test]
    fn get_nonexistent_is_none() {
        let mut arena = Arena::new();
        let a = arena.insert(42);
        assert!(arena.remove(a).is_some());
        assert!(arena.get(a).is_none());

        arena.validate();
    }

    #[test]
    fn remove() {
        let mut arena = Arena::new();
        let a = arena.insert(42);
        assert_eq!(arena.remove(a).unwrap(), 42);
        assert!(arena.get(a).is_none());

        arena.validate();
    }

    #[test]
    fn remove_out_of_bounds_is_none() {
        let mut arena = Arena::new();
        arena.insert(42);
        assert!(arena.remove(EntryId(5)).is_none());

        arena.validate();
    }

    #[test]
    fn remove_nonexistent_is_none() {
        let mut arena = Arena::new();
        let a = arena.insert(42);
        assert!(arena.remove(a).is_some());
        assert!(arena.remove(a).is_none());

        arena.validate();
    }

    #[test]
    #[should_panic]
    fn index_out_of_bounds_panics() {
        let mut arena = Arena::new();
        let _a = arena.insert(42);
        arena[EntryId(5)];
    }

    #[test]
    #[should_panic]
    fn index_nonexistent_panics() {
        let mut arena = Arena::new();
        let a = arena.insert(42);
        arena.remove(a);
        arena[a];
    }

    #[test]
    #[should_panic]
    fn validate() {
        let mut arena = Arena::new();
        let index = arena.insert(0);
        arena.entries[index.0] = Free { next_free: None };

        arena.validate();
    }
}