generic_tree/

lib.rs

//! This crate provides a very simple, intuitive API for storing data in a tree-like structure.
//!
//! # Example
//!
//! ```
//! use generic_tree::{Tree, Node};
//!
//! struct Data;
//!
//! // Create a root Node
//! let mut root = Node::new("root", Data);
//!
//! // Create a tree from it
//! let mut tree = Tree::init(root);
//!
//! // Create a child
//! let child = Node::new("child", Data);
//!
//! // And add it as a child of `root`
//! tree.add_node(&["root"], child);
//!
//! // Get a reference to the child
//! let child = tree.get_node(&["root", "child"]).unwrap();
//! ```

/// A Tree represents and owns a collection of Nodes. It should be the go-to point for interacting
/// with elements wihtin the structure.
pub struct Tree<K, V> {
    root: Node<K, V>,
}

/// A single building block to represent an element within a Tree. Itself can contain a list of
/// more Nodes.
/// It should eventually be part of a Tree and it shouldn't be necessary to keep it around on its
/// own.
pub struct Node<K, V> {
    key: K,
    value: V,
    children: Vec<Box<Node<K, V>>>,
}

#[derive(Debug)]
pub enum Error {
    InvalidPath,
}

impl<K, V> Tree<K, V>
where
    K: PartialEq,
{
    /// Create a new tree, given the root Node `root`.
    pub fn init(root: Node<K, V>) -> Self {
        Self { root }
    }

    /// Get a reference to a specific Node from the tree, resolved by the list provided by `path`.
    ///
    /// # Errors
    /// Returns an `Err` if `path` doesn't resolve to a Node.
    ///
    /// # Examples
    ///
    /// ```
    /// # use generic_tree::{Tree, Node};
    /// let mut root = Node::new("root", 1);
    /// let child = Node::new("child", 2);
    /// root.add_child(child);
    ///
    /// let mut tree = Tree::init(root);
    ///
    /// assert!(tree.get_node(&["root"]).is_ok());
    /// assert!(tree.get_node(&["root", "child"]).is_ok());
    /// assert!(tree.get_node(&["boot"]).is_err());
    /// assert!(tree.get_node(&["root", "child", "noop"]).is_err());
    /// ```
    pub fn get_node<Q>(&self, path: &[Q]) -> Result<&Node<K, V>, Error>
    where
        Q: PartialEq<K>,
    {
        if &path[0] == self.root.key() {
            self.root.get_child(&path[1..])
        } else {
            Err(Error::InvalidPath)
        }
    }

    /// Get a mutable reference to a specific Node from the tree, resolved by the list provided by `path`.
    ///
    /// # Errors
    /// Returns an `Err` if `path` doesn't resolve to a Node.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::{Tree, Node};
    ///
    /// let mut root = Node::new("root", 1);
    /// let child = Node::new("child", 2);
    /// root.add_child(child);
    ///
    /// let mut tree = Tree::init(root);
    ///
    /// let mut node = tree.get_mut_node(&["root", "child"]).unwrap();
    /// assert_eq!(node.value(), &2);
    ///
    /// *node.mut_value() = 42;
    /// # assert_eq!(node.value(), &42);
    /// ```
    pub fn get_mut_node<Q>(&mut self, path: &[Q]) -> Result<&mut Node<K, V>, Error>
    where
        Q: PartialEq<K>,
    {
        if &path[0] == self.root.key() {
            self.root.get_mut_child(&path[1..])
        } else {
            Err(Error::InvalidPath)
        }
    }

    /// Add a Node as a child to the Node resolved by `path`. If there was already a Node with the
    /// same key, that old Node is returned.
    ///
    /// # Errors
    /// Returns an `Err` if `path` doesn't resolve to a Node.
    ///
    /// # Examples
    ///
    /// ```
    /// # use generic_tree::{Tree, Node};
    /// let mut root = Node::new("root", 1);
    /// let mut tree = Tree::init(root);
    /// # assert!(tree.get_node(&["root", "child"]).is_err());
    ///
    /// let child = Node::new("child", 2);
    /// tree.add_node(&["root"], child);
    /// # assert!(tree.get_node(&["root", "child"]).is_ok());
    /// # // Add a second child and verify the first one is returned
    /// # let child = Node::new("child", 3);
    /// # let old_child = tree.add_node(&["root"], child).unwrap().unwrap();
    /// # assert_eq!(old_child.value(), &2);
    /// ```
    pub fn add_node<Q>(
        &mut self,
        path: &[Q],
        node: Node<K, V>,
    ) -> Result<Option<Box<Node<K, V>>>, Error>
    where
        Q: PartialEq<K>,
    {
        if path.is_empty() {
            return Err(Error::InvalidPath);
        }

        if &path[0] == self.root.key() {
            self.root.add_child_at_path(&path[1..], node)
        } else {
            Err(Error::InvalidPath)
        }
    }

    /// Remove a Node from the tree resolved by `path`.
    ///
    /// # Errors
    /// Returns an `Err` if `path` doesn't resolve to a Node.
    ///
    /// # Examples
    ///
    /// ```
    /// # use generic_tree::{Tree, Node};
    /// let mut root = Node::new("root", 1);
    /// let child = Node::new("child", 2);
    /// root.add_child(child);
    /// let mut tree = Tree::init(root);
    /// # assert!(tree.get_node(&["root", "child"]).is_ok());
    ///
    /// assert!(tree.remove_node(&["root", "child"]).is_ok());
    /// ```
    pub fn remove_node<Q>(&mut self, path: &[Q]) -> Result<Box<Node<K, V>>, Error>
    where
        Q: PartialEq<K>,
    {
        // An empty path is not allowed. Furthermore, a path containing a single element could only
        // match the root itself, and can't be removed. For this, use `remove_root`.
        if path.len() < 2 {
            return Err(Error::InvalidPath);
        }

        if &path[0] == self.root.key() {
            self.root.remove_child(&path[1..])
        } else {
            Err(Error::InvalidPath)
        }
    }
}

impl<K, V> Node<K, V>
where
    K: PartialEq,
{
    /// Creates a new Node.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let node = Node::new("some_key".to_owned(), 42);
    /// assert_eq!(node.key(), "some_key");
    /// assert_eq!(node.value(), &42);
    /// ```
    pub fn new(key: K, value: V) -> Self {
        Self {
            key,
            value,
            children: Vec::new(),
        }
    }

    /// Add a child Node to the current Node. If there already is a child with the same `key`, that
    /// child will be returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let mut parent = Node::new("parent".to_owned(), 2);
    /// let child = Node::new("child".to_owned(), 3);
    ///
    /// assert!(parent.add_child(child).is_none());
    ///
    /// let child = Node::new("child".to_owned(), 4);
    /// let prev_child = parent.add_child(child).unwrap();
    /// assert_eq!(prev_child.value(), &3);
    /// ```
    pub fn add_child(&mut self, child: Node<K, V>) -> Option<Box<Node<K, V>>> {
        let child = Box::new(child);

        let mut old_value = None;
        for i in 0..self.children.len() {
            if self.children[i] == child {
                old_value = Some(self.children.remove(i));
                break;
            }
        }

        self.children.push(child);

        old_value
    }

    /// Add a child Node at a specific descendent path. If there was already such a child, it will
    /// be returned.
    ///
    /// # Errors
    ///
    /// Will return `Err` if `path` can't be resolved.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let mut grandparent = Node::new("grandparent".to_owned(), 1);
    /// let mut parent = Node::new("parent".to_owned(), 2);
    /// grandparent.add_child(parent);
    ///
    /// // Tree structure:
    /// // grandparent -> parent
    /// assert!(grandparent.get_child(&["parent", "child"]).is_err());
    ///
    /// let child = Node::new("child".to_owned(), 3);
    /// assert!(grandparent.add_child_at_path(&["parent"], child).is_ok());
    /// assert!(grandparent.get_child(&["parent", "child"]).is_ok());
    /// ```
    pub fn add_child_at_path<Q>(
        &mut self,
        path: &[Q],
        child: Node<K, V>,
    ) -> Result<Option<Box<Node<K, V>>>, Error>
    where
        Q: PartialEq<K>,
    {
        let parent = self.get_mut_child(path)?;

        Ok(parent.add_child(child))
    }

    /// Get a child node based on a list of keys.
    ///
    /// # Errors
    ///
    /// Will return `Err` if `path` can't be resolved.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let mut grandparent = Node::new("grandparent".to_owned(), 1);
    /// let mut parent = Node::new("parent".to_owned(), 2);
    /// let child = Node::new("child".to_owned(), 3);
    ///
    /// assert!(parent.add_child(child).is_none());
    /// assert!(grandparent.add_child(parent).is_none());
    ///
    /// // Tree structure:
    /// // grandparent -> parent -> child
    /// assert!(grandparent.get_child(&["parent", "child"]).is_ok());
    /// ```
    pub fn get_child<Q>(&self, path: &[Q]) -> Result<&Node<K, V>, Error>
    where
        Q: PartialEq<K>,
    {
        if path.is_empty() {
            return Ok(self);
        }

        let child = &path[0];
        let path = &path[1..];

        for entry in &self.children {
            if child == entry.key() {
                return entry.get_child(path);
            }
        }

        Err(Error::InvalidPath)
    }

    /// Get mutable a child node based on a list of keys.
    ///
    /// # Errors
    ///
    /// Will return `Err` if `path` can't be resolved.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// # let mut grandparent = Node::new("grandparent".to_owned(), 1);
    /// # let mut parent = Node::new("parent".to_owned(), 2);
    /// # let child = Node::new("child".to_owned(), 3);
    ///
    /// # assert!(parent.add_child(child).is_none());
    /// # assert!(grandparent.add_child(parent).is_none());
    ///
    /// // Tree structure:
    /// // grandparent -> parent -> child
    /// assert!(grandparent.get_mut_child(&["parent", "child"]).is_ok());
    /// ```
    pub fn get_mut_child<Q>(&mut self, path: &[Q]) -> Result<&mut Node<K, V>, Error>
    where
        Q: PartialEq<K>,
    {
        if path.is_empty() {
            return Ok(self);
        }

        let child = &path[0];
        let path = &path[1..];

        for entry in &mut self.children {
            if child == entry.key() {
                return entry.get_mut_child(path);
            }
        }

        Err(Error::InvalidPath)
    }

    /// Remove a child node based on a list of keys. A `boxed` Node is returned if found, None
    /// otherwise.
    ///
    /// # Errors
    ///
    /// Will return `Err` if `path` can't be resolved.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let mut grandparent = Node::new("grandparent".to_owned(), 1);
    /// let mut parent = Node::new("parent".to_owned(), 2);
    /// let child = Node::new("child".to_owned(), 3);
    ///
    /// parent.add_child(child);
    /// grandparent.add_child(parent);
    ///
    /// // Tree structure:
    /// // grandparent -> parent -> child
    ///
    /// assert!(grandparent.remove_child(&["parent", "child"]).is_ok());
    /// assert!(grandparent.remove_child(&["parent", "child"]).is_err());
    /// ```
    pub fn remove_child<Q>(&mut self, path: &[Q]) -> Result<Box<Node<K, V>>, Error>
    where
        Q: PartialEq<K>,
    {
        if path.is_empty() {
            return Err(Error::InvalidPath);
        }

        let child = &path[0];
        let path = &path[1..];

        for i in 0..self.children.len() {
            if child == self.children[i].key() {
                if path.is_empty() {
                    return Ok(self.children.remove(i));
                } else {
                    return self.children[i].remove_child(path);
                }
            }
        }

        Err(Error::InvalidPath)
    }

    /// Get a reference the value contained within the node.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let node = Node::new("some_key".to_owned(), 42);
    ///
    /// assert_eq!(node.value(), &42);
    /// ```
    pub fn value(&self) -> &V {
        &self.value
    }

    /// Get a muteable reference to the value contained within the node.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let mut node = Node::new("some_key".to_owned(), 42);
    ///
    /// let mut value = node.mut_value();
    /// assert_eq!(value, &42);
    ///
    /// *value = 43;
    /// assert_eq!(node.value(), &43);
    /// ```
    pub fn mut_value(&mut self) -> &mut V {
        &mut self.value
    }

    /// Get a reference to the key of the node.
    ///
    /// # Examples
    ///
    /// ```
    /// use generic_tree::Node;
    ///
    /// let mut node = Node::new("some_key".to_owned(), 42);
    ///
    /// assert_eq!(node.key(), "some_key");
    /// ```
    pub fn key(&self) -> &K {
        &self.key
    }
}

impl<K, V> PartialEq for Node<K, V>
where
    K: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        self.key == other.key
    }
}

impl<K, V> PartialEq<K> for Node<K, V>
where
    K: PartialEq,
{
    fn eq(&self, other: &K) -> bool {
        &self.key == other
    }
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        match self {
            Error::InvalidPath => write!(f, "InvalidPath"),
        }
    }
}