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 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344
//! //! **rose_tree** is a rose tree (aka multi-way tree) data structure library. //! //! The most prominent type is [**RoseTree**](./struct.RoseTree.html) - a wrapper around [petgraph] //! (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/index.html)'s [**Graph**] //! (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/graph/struct.Graph.html) //! data structure, exposing a refined API targeted towards rose tree related functionality. //! #![forbid(unsafe_code)] #![warn(missing_docs)] pub extern crate petgraph; use petgraph as pg; use petgraph::graph::IndexType; pub use petgraph::graph::NodeIndex; type DefIndex = u32; /// The PetGraph to be used internally within the RoseTree for storing/managing nodes and edges. pub type PetGraph<N, Ix> = pg::Graph<N, (), pg::Directed, Ix>; /// An indexable tree data structure with a variable and unbounded number of branches per node. /// /// Also known as a multi-way tree. /// /// See the [wikipedia article on the "Rose tree" data /// structure](https://en.wikipedia.org/wiki/Rose_tree). /// /// Note: The following documentation is adapted from petgraph's [**Graph** documentation] /// (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/graph/struct.Graph.html). /// /// **RoseTree** is parameterized over the node weight **N** and **Ix** which is the index type /// used. /// /// A wrapper around petgraph's **Graph** data structure with a refined API specifically targeted /// towards use as a **RoseTree**. /// /// **NodeIndex** is a type that acts as a reference to nodes, but these are only stable across /// certain operations. **Removing nodes may shift other indices.** Adding kids to the **RoseTree** /// keeps all indices stable, but removing a node will force the last node to shift its index to /// take its place. /// /// The fact that the node indices in the **RoseTree** are numbered in a compact interval from 0 to /// *n*-1 simplifies some graph algorithms. /// /// The **Ix** parameter is u32 by default. The goal is that you can ignore this parameter /// completely unless you need a very large **RoseTree** -- then you can use usize. /// /// The **RoseTree** also offers methods for accessing the underlying **Graph**, which can be useful /// for taking advantage of petgraph's various graph-related algorithms. #[derive(Clone, Debug)] pub struct RoseTree<N, Ix: IndexType = DefIndex> { /// A graph for storing all nodes and edges between them that represent the tree. graph: PetGraph<N, Ix>, } /// An iterator that yeilds an index to the parent of the current child before the setting the /// parent as the new current child. This occurs recursively until the root index is yeilded. pub struct ParentRecursion<'a, N: 'a, Ix: IndexType> { rose_tree: &'a RoseTree<N, Ix>, child: NodeIndex<Ix>, } /// An iterator yielding indices to the children of some node. pub type Children<'a, Ix> = pg::graph::Neighbors<'a, (), Ix>; /// An iterator yielding indices to the siblings of some child node. pub struct Siblings<'a, Ix: IndexType> { child: NodeIndex<Ix>, maybe_siblings: Option<Children<'a, Ix>>, } /// A "walker" object that can be used to step through the children of some parent node. pub struct WalkChildren<Ix: IndexType> { walk_edges: pg::graph::WalkNeighbors<Ix>, } /// A "walker" object that can be used to step through the siblings of some child node. pub struct WalkSiblings<Ix: IndexType> { child: NodeIndex<Ix>, maybe_walk_children: Option<WalkChildren<Ix>>, } /// `RoseTree`'s API ensures that it always has a "root" node and that its index is always 0. pub const ROOT: usize = 0; impl<N, Ix> RoseTree<N, Ix> where Ix: IndexType, { /// Create a new `RoseTree` along with some root node. /// Returns both the `RoseTree` and an index into the root node in a tuple. pub fn new(root: N) -> (Self, NodeIndex<Ix>) { Self::with_capacity(1, root) } /// Create a new `RoseTree` with estimated capacity and some root node. /// Returns both the `RoseTree` and an index into the root node in a tuple. pub fn with_capacity(nodes: usize, root: N) -> (Self, NodeIndex<Ix>) { let mut graph = PetGraph::with_capacity(nodes, nodes); let root = graph.add_node(root); (RoseTree { graph }, root) } /// The total number of nodes in the RoseTree. pub fn node_count(&self) -> usize { self.graph.node_count() } /// Borrow the `RoseTree`'s underlying `PetGraph<N, Ix>`. /// All existing `NodeIndex`s may be used to index into this graph the same way they may be /// used to index into the `RoseTree`. pub fn graph(&self) -> &PetGraph<N, Ix> { &self.graph } /// Take ownership of the RoseTree and return the internal PetGraph<N, Ix>. /// All existing `NodeIndex`s may be used to index into this graph the same way they may be /// used to index into the `RoseTree`. pub fn into_graph(self) -> PetGraph<N, Ix> { let RoseTree { graph } = self; graph } /// Add a child node to the node at the given NodeIndex. /// Returns an index into the child's position within the tree. /// /// Computes in **O(1)** time. /// /// **Panics** if the given parent node doesn't exist. /// /// **Panics** if the Graph is at the maximum number of edges for its index. pub fn add_child(&mut self, parent: NodeIndex<Ix>, kid: N) -> NodeIndex<Ix> { let kid = self.graph.add_node(kid); self.graph.add_edge(parent, kid, ()); kid } /// Borrow the weight from the node at the given index. pub fn node_weight(&self, node: NodeIndex<Ix>) -> Option<&N> { self.graph.node_weight(node) } /// Mutably borrow the weight from the node at the given index. pub fn node_weight_mut(&mut self, node: NodeIndex<Ix>) -> Option<&mut N> { self.graph.node_weight_mut(node) } /// Index the `RoseTree` by two node indices. /// /// **Panics** if the indices are equal or if they are out of bounds. pub fn index_twice_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> (&mut N, &mut N) { self.graph.index_twice_mut(a, b) } /// Remove all nodes in the `RoseTree` except for the root. pub fn remove_all_but_root(&mut self) { // We can assume that the `root`'s index is zero, as it is always the first node to be // added to the RoseTree. if let Some(root) = self.graph.remove_node(NodeIndex::new(0)) { self.graph.clear(); self.graph.add_node(root); } } /// Removes and returns the node at the given index. /// /// The parent of `node` will become the new parent for all of its children. /// /// The root node cannot be removed. If its index is given, `None` will be returned. /// /// Note: this method may shift other node indices, invalidating previously returned indices! pub fn remove_node(&mut self, node: NodeIndex<Ix>) -> Option<N> { // Check if an attempt to remove the root node has been made. if node.index() == ROOT || self.graph.node_weight(node).is_none() { return None; } // Now that we know we're not the root node, we know that we **must** have some parent. let parent = self.parent(node).expect("No parent node found"); // For each of `node`'s children, set their parent to `node`'s parent. let mut children = self.graph.neighbors_directed(node, pg::Outgoing).detach(); while let Some((child_edge, child_node)) = children.next(&self.graph) { self.graph.remove_edge(child_edge); self.graph.add_edge(parent, child_node, ()); } // Finally, remove our node and return it. self.graph.remove_node(node) } /// Removes the node at the given index along with all their children, returning them as a new /// RoseTree. /// /// If there was no node at the given index, `None` will be returned. pub fn remove_node_with_children(&mut self, _node: NodeIndex<Ix>) -> Option<RoseTree<N, Ix>> { unimplemented!(); } /// An index to the parent of the node at the given index if there is one. pub fn parent(&self, child: NodeIndex<Ix>) -> Option<NodeIndex<Ix>> { self.graph.neighbors_directed(child, pg::Incoming).next() } /// An iterator over the given child's parent, that parent's parent and so forth. /// /// The returned iterator yields `NodeIndex<Ix>`s. pub fn parent_recursion(&self, child: NodeIndex<Ix>) -> ParentRecursion<N, Ix> { ParentRecursion { rose_tree: self, child, } } /// An iterator over all nodes that are children to the node at the given index. /// /// The returned iterator yields `NodeIndex<Ix>`s. pub fn children(&self, parent: NodeIndex<Ix>) -> Children<Ix> { self.graph.neighbors_directed(parent, pg::Outgoing) } /// A "walker" object that may be used to step through the children of the given parent node. /// /// Unlike the `Children` type, `WalkChildren` does not borrow the `RoseTree`. pub fn walk_children(&self, parent: NodeIndex<Ix>) -> WalkChildren<Ix> { let walk_edges = self.graph.neighbors_directed(parent, pg::Outgoing).detach(); WalkChildren { walk_edges } } /// An iterator over all nodes that are siblings to the node at the given index. /// /// The returned iterator yields `NodeIndex<Ix>`s. pub fn siblings(&self, child: NodeIndex<Ix>) -> Siblings<Ix> { let maybe_siblings = self.parent(child).map(|parent| self.children(parent)); Siblings { child, maybe_siblings, } } /// A "walker" object that may be used to step through the siblings of the given child node. /// /// Unlike the `Siblings` type, `WalkSiblings` does not borrow the `RoseTree`. pub fn walk_siblings(&self, child: NodeIndex<Ix>) -> WalkSiblings<Ix> { let maybe_walk_children = self.parent(child).map(|parent| self.walk_children(parent)); WalkSiblings { child, maybe_walk_children, } } } impl<N, Ix> ::std::ops::Index<NodeIndex<Ix>> for RoseTree<N, Ix> where Ix: IndexType, { type Output = N; fn index(&self, index: NodeIndex<Ix>) -> &N { &self.graph[index] } } impl<N, Ix> ::std::ops::IndexMut<NodeIndex<Ix>> for RoseTree<N, Ix> where Ix: IndexType, { fn index_mut(&mut self, index: NodeIndex<Ix>) -> &mut N { &mut self.graph[index] } } impl<'a, Ix> Iterator for Siblings<'a, Ix> where Ix: IndexType, { type Item = NodeIndex<Ix>; fn next(&mut self) -> Option<NodeIndex<Ix>> { let Siblings { child, ref mut maybe_siblings, } = *self; maybe_siblings.as_mut().and_then(|siblings| { siblings.next().and_then(|sibling| { if sibling != child { Some(sibling) } else { siblings.next() } }) }) } } impl<'a, N, Ix> Iterator for ParentRecursion<'a, N, Ix> where Ix: IndexType, { type Item = NodeIndex<Ix>; fn next(&mut self) -> Option<NodeIndex<Ix>> { let ParentRecursion { ref mut child, ref rose_tree, } = *self; rose_tree.parent(*child).map(|parent| { *child = parent; parent }) } } impl<Ix> WalkChildren<Ix> where Ix: IndexType, { /// Fetch the next child index in the walk for the given `RoseTree`. pub fn next<N>(&mut self, tree: &RoseTree<N, Ix>) -> Option<NodeIndex<Ix>> { self.walk_edges.next(&tree.graph).map(|(_, n)| n) } } impl<Ix> WalkSiblings<Ix> where Ix: IndexType, { /// Fetch the next sibling index in the walk for the given `RoseTree`. pub fn next<N>(&mut self, tree: &RoseTree<N, Ix>) -> Option<NodeIndex<Ix>> { let WalkSiblings { child, ref mut maybe_walk_children, } = *self; maybe_walk_children.as_mut().and_then(|walk_children| { walk_children.next(tree).and_then(|sibling| { if child != sibling { Some(sibling) } else { walk_children.next(tree) } }) }) } }