bag/

lib.rs

//! # Bag
//! `bag` is a simple, insert only graph. It is simple to understand conceptually, and modify if needed.
//! Data is represented as `NodeID`s, which can be used to retrieve pointers to `Node`s stored in the `GraphStore`.
//! These `Node`s point to their parents and children by holding their `NodeID`s.
//! These `Node`s also hold a datatype `<T>` (the type of the node and graph), which you can use to store your program
//! specific data.

pub type NodeID = usize;

///
/// A generic container for a node
///
/// A `Node<T>` contains the following:
///     - An optional identifier for a parent `Node<T>`
///     - A `Vec` of identifiers for children `Node<T>`s
///     - A publicly visible member of type `T` to hold program specific data
///
#[derive(Debug)]
pub struct Node<T> {
    parent: Option<NodeID>,
    children: Vec<NodeID>,
    pub data: T,
}

impl<T> Node<T> {
    ///
    /// Constructs a new `Node<T>`
    ///
    /// Accepts the node's data of type `T`. By default,
    /// `Node<T>`s have no parent, this is set on insertion
    /// into the graph.
    ///
    /// # Example
    ///
    /// ```
    /// use bag::Node;
    /// #[derive(Debug,Eq,PartialEq)]
    /// struct InternalData {
    ///     name: String,
    ///     id: i32
    /// }
    /// let node = Node::new(InternalData{name: "NodeTest".to_string(), id: 42});
    /// assert_eq!(*node.parent(), None);
    /// assert_eq!(*node.children(), Vec::new());
    /// assert_eq!(node.data, InternalData{name: "NodeTest".to_string(), id:42});
    /// ```
    ///
    pub fn new(data: T) -> Self {
        Node { parent: None, children: Vec::new(), data }
    }
    pub fn parent(&self) -> &Option<NodeID> {
        &self.parent
    }
    pub fn children(&self) -> &Vec<NodeID> {
        &self.children
    }
}

///
/// A generic container for a graph
///
/// A `GraphStore<T>` is a struct that contains the actual graph representation.
/// Try not to loose it.
///
///
/// # Example
///
/// ```
/// use bag::{GraphStore, Node};
/// let root_node = Node::new("String".to_string());
/// let (mut graph, root_node_id) = GraphStore::new(root_node);
/// assert_eq!(*graph.get(root_node_id).unwrap().parent(), None);
/// ```
///
#[derive(Debug)]
pub struct GraphStore<T> {
    graph: Vec<Node<T>>
}

impl<T> GraphStore<T> {
    ///
    /// Constructs a new `GraphStore<T>` and handle to the root `Node<T>`
    ///
    /// Accepts a root node of type `Node<T>` (this is the only node held in the graph that can have a `None`
    /// for it's parent (though it may have a `Some(parent)` if the graph is cyclic at the root.
    ///
    pub fn new(root_node: Node<T>) -> (Self, NodeID) {
        let mut tree = GraphStore { graph: Vec::new() };
        let root_nodeid = tree.insert(root_node);
        (tree, root_nodeid)
    }

    ///
    /// Returns an option with a reference to the node represented by `NodeID`, if found
    ///
    /// `get` searches the `GraphStore<T>` for a node with the `NodeID` passed as `node`.
    /// If it is found, a non-mutable reference to it is returned in a `Some`, otherwise a `None` is returned.
    pub fn get(&self, node: NodeID) -> Option<&Node<T>> {
        self.graph.get(node)
    }

    ///
    /// Returns an option with a mutable reference to the node represented by `NodeID`, if found
    ///
    /// `get_mut` searches the `GraphStore<T>` for a node with the `NodeID` passed as `node`.
    /// If it is found, a mutable reference to it is returned in a `Some`, otherwise a `None` is returned.
    pub fn get_mut(&mut self, node: NodeID) -> Option<&mut Node<T>> {
        self.graph.get_mut(node)
    }

    ///
    /// Returns an option with a reference to a Vec of a `Node<T>`s sublings, if found
    ///
    /// `get_siblings_id` searches the `GraphStore<T>` for a node with the `NodeID` passed as `node`.
    /// If it is found, a non-mutable reference to it's parent's children is returned in a `Some`, otherwise a `None` is returned.
    /// Note that `node` is itself included in the returned `Vec<NodeID>`.
    pub fn get_siblings_id(&self, node: NodeID) -> Option<&Vec<NodeID>> {
        match self.get(node) {
            Some(node) => {
                match node.parent {
                    Some(parent_id) => Some(self.get(parent_id).unwrap().children()),
                    None => return None
                }
            }
            None => None
        }
    }
    /*
        Inserts a node into the tree and returns it's `NodeID`
    */
    fn insert(&mut self, node: Node<T>) -> NodeID {
        self.graph.push(node);
        self.graph.len() - 1
    }
    ///
    /// Inserts a node into the graph
    ///
    /// `insert_child` accepts a parent `NodeID` and takes ownership of an inserted `Node<T>`.
    /// If the parent `NodeID` is valid, the `Node<T>` is inserted into the graph. The child's parent
    /// pointer is then set to the `NodeID` of the parent, and the parent's child `Vec<NodeID` is updated
    /// to include the `NodeID` of the child. Returns a `Result<NodeID, &'static str` representing success or failure
    /// of the insertion.
    pub fn insert_child(&mut self, parent_id: &NodeID, mut inserted: Node<T>) -> Result<NodeID, &'static str> {
        /*
            This is an unusual piece of code, but seems to be the simplest way to get around mutable and immutable borrows.
            The tree_len is the index of the item to be inserted (because the item is not yet inserted, and the Vec<Node<T>> is 0 indexed).
            Once this is immutable held in tree_len, we can mutably borrow the Vec to insert the element into the parent node.
            We then insert the child into the Vec<Node<T>>.
        */
        let tree_len = self.graph.len();
        match self.get_mut(*parent_id) {
            Some(parent) => {
                inserted.parent = Some(*parent_id);
                parent.children.push(tree_len)
            }
            None => return Err("Parent not found by NodeID")
        };
        self.insert(inserted);
        Ok(tree_len)
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn create_new_node_and_test_invariants() {
        use Node;
        #[derive(Debug, Eq, PartialEq)]
        struct InternalData {
            name: String,
            id: i32,
        }
        let node = Node::new(InternalData { name: "NodeTest".to_string(), id: 42 });
        assert_eq!(*node.parent(), None);
        assert_eq!(*node.children(), Vec::new());
        assert_eq!(node.data, InternalData { name: "NodeTest".to_string(), id: 42 });
    }

    #[test]
    fn create_new_graph_store_and_test_invariants() {
        use {GraphStore, Node};
        let root_node = Node::new("String".to_string());
        let (graph, root_node_id) = GraphStore::new(root_node);
        assert_eq!(*graph.get(root_node_id).unwrap().parent(), None);
    }
}