1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
//! # 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); } }