grapes 0.3.0

//! Persistent [MapTree] & related items
//!
//! Just like [Tree](crate::tree::Tree), [MapTree] maintains a hierarchy of nodes. [MapTree] always has at least one item, the root node. The root node may have children nodes, and those nodes may have children of their own – this goes down as deep as you need!
//!
//! Every node has exactly one parent, except for the root node, which has no parent.
//!
//! A node's children is logically a list – so the order of the children is specified, and you can change it if you want.
//!
//! In addition to the hierarchy (and unlike [Tree](crate::tree::Tree)), [MapTree] maintains a mapping of arbitrary keys (which you specify) to nodes. Every node has a key – you can directly retrieve a node if you know its key. If you don't need this mapping, and would rather have auto-generated IDs, you can use the [Tree](crate::tree::Tree) instead.

use std::hash::Hash;

use crate::tree;
use crate::tree::{NodeId, Tree};
use imbl::HashMap;

pub use children::*;
pub use error::*;
pub use location::*;
pub use node_mut::*;
pub use node_ref::*;

mod children;
mod error;
mod location;
mod node_mut;
mod node_ref;

/// A node entry in a [MapTree]
///
/// This consists of a value and the associated key
#[derive(Clone, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Entry<Key: Hash + Eq + Clone, T: Clone> {
    value: T,
    key: Key,
}

impl<Key: Hash + Eq + Clone, T: Clone> Entry<Key, T> {
    pub(crate) fn new(key: Key, value: T) -> Self {
        Self { value, key }
    }

    /// Get the node's value
    #[must_use]
    pub fn value(&self) -> &T {
        &self.value
    }

    /// Get a mutable reference to the node's value
    #[must_use]
    pub fn value_mut(&mut self) -> &mut T {
        &mut self.value
    }

    /// Get the node's key
    #[must_use]
    pub fn key(&self) -> &Key {
        &self.key
    }
}

/// A persistent, indexable, hierarchical data structure that maintains a key-node mapping
///
/// See the [module docs](crate::map_tree) for more information
#[derive(Clone, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct MapTree<Key: Hash + Eq + Clone, T: Clone> {
    tree: Tree<Entry<Key, T>>,
    map: HashMap<Key, NodeId>,
}

/// Error when inserting a node into a [MapTree]
#[derive(Debug, Clone, Copy)]
pub enum InsertError<Key> {
    /// The specified key is already present in the tree
    KeyAlreadyExists(Key),
    /// The specified location referenced a node ID that doesn't exist
    NoSuchNode(Key),
    /// Attempted to place the node as a sibling of the root node; this is not allowed
    RootCannotHaveSiblings,
}

impl<Key: Hash + Eq + Clone, T: Clone> MapTree<Key, T> {
    /// Create a new Tree with the specified root node key and value
    #[must_use]
    pub fn new_with_root(key: Key, value: T) -> Self {
        let tree = Tree::new_with_root(Entry::new(key.clone(), value));
        Self {
            map: HashMap::unit(key, tree.root().id()),
            tree,
        }
    }

    /// Insert a new node at the specified location
    ///
    /// Error if the location is invalid:
    /// - The root node cannot have siblings
    /// - The location must reference only existing nodes
    ///
    /// Also, errors if the specified key is already present in the [MapTree].
    pub fn insert(
        &mut self,
        key: Key,
        value: T,
        location: Location<Key>,
    ) -> Result<(), InsertError<Key>> {
        if self.map.contains_key(&key) {
            return Err(InsertError::KeyAlreadyExists(key));
        }

        let mapped_location = location.into_tree_location(|key| {
            self.map
                .get(&key)
                .copied()
                .ok_or(InsertError::NoSuchNode(key))
        })?;

        let new_id = self
            .tree
            .insert(Entry::new(key.clone(), value), mapped_location)
            .map_err(|error| match error {
                tree::InvalidLocation::NoSuchNode(_) => {
                    unreachable!()
                }
                tree::InvalidLocation::RootCannotHaveSiblings => {
                    InsertError::RootCannotHaveSiblings
                }
            })?;
        self.map.insert(key, new_id);

        Ok(())
    }

    /// Get a reference to the root node
    ///
    /// The tree will always have a root node
    #[must_use]
    pub fn root(&self) -> NodeRef<Key, T> {
        NodeRef::new(self.tree.root())
    }

    /// Get a mutable reference to the root node
    ///
    /// The tree will always have a root node
    #[must_use]
    pub fn root_mut(&mut self) -> NodeMut<Key, T> {
        NodeMut::new(self.tree.root_mut(), &mut self.map)
    }

    /// Get a node by its Key
    ///
    /// If there is no such node, returns [None]
    #[must_use]
    pub fn get(&self, key: &Key) -> Option<NodeRef<Key, T>> {
        let id = self.map.get(key)?;
        let inner = self.tree.get(*id)?;
        Some(NodeRef::new(inner))
    }

    /// Get a mutable reference to a node by its Key
    ///
    /// If there is no such node, returns [None]
    #[must_use]
    pub fn get_mut(&mut self, key: &Key) -> Option<NodeMut<Key, T>> {
        let id = self.map.get(key)?;
        let inner = self.tree.get_mut(*id)?;
        Some(NodeMut::new(inner, &mut self.map))
    }
}

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

    #[test]
    fn new_with_root() {
        let tree = MapTree::new_with_root("hello", 42);
        assert_eq!(tree.root().key(), &"hello");
        assert_eq!(tree.root().data(), &42);
    }
}