[−][src]Struct rose_tree::RoseTree
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.
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.
Methods
impl<N, Ix> RoseTree<N, Ix> where
Ix: IndexType,
[src]
Ix: IndexType,
pub fn new(root: N) -> (Self, NodeIndex<Ix>)
[src]
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 with_capacity(nodes: usize, root: N) -> (Self, NodeIndex<Ix>)
[src]
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 node_count(&self) -> usize
[src]
The total number of nodes in the RoseTree.
pub fn graph(&self) -> &PetGraph<N, Ix>
[src]
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 into_graph(self) -> PetGraph<N, Ix>
[src]
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 add_child(&mut self, parent: NodeIndex<Ix>, kid: N) -> NodeIndex<Ix>
[src]
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 node_weight(&self, node: NodeIndex<Ix>) -> Option<&N>
[src]
Borrow the weight from the node at the given index.
pub fn node_weight_mut(&mut self, node: NodeIndex<Ix>) -> Option<&mut N>
[src]
Mutably borrow the weight from the node at the given index.
pub fn index_twice_mut(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) -> (&mut N, &mut N)
[src]
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) -> (&mut N, &mut N)
Index the RoseTree
by two node indices.
Panics if the indices are equal or if they are out of bounds.
pub fn remove_all_but_root(&mut self)
[src]
Remove all nodes in the RoseTree
except for the root.
pub fn remove_node(&mut self, node: NodeIndex<Ix>) -> Option<N>
[src]
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_with_children(
&mut self,
_node: NodeIndex<Ix>
) -> Option<RoseTree<N, Ix>>
[src]
&mut self,
_node: NodeIndex<Ix>
) -> Option<RoseTree<N, Ix>>
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 parent(&self, child: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>
[src]
An index to the parent of the node at the given index if there is one.
ⓘImportant traits for ParentRecursion<'a, N, Ix>pub fn parent_recursion(&self, child: NodeIndex<Ix>) -> ParentRecursion<N, Ix>
[src]
An iterator over the given child's parent, that parent's parent and so forth.
The returned iterator yields NodeIndex<Ix>
s.
pub fn children(&self, parent: NodeIndex<Ix>) -> Children<Ix>
[src]
An iterator over all nodes that are children to the node at the given index.
The returned iterator yields NodeIndex<Ix>
s.
pub fn walk_children(&self, parent: NodeIndex<Ix>) -> WalkChildren<Ix>
[src]
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
.
ⓘImportant traits for Siblings<'a, Ix>pub fn siblings(&self, child: NodeIndex<Ix>) -> Siblings<Ix>
[src]
An iterator over all nodes that are siblings to the node at the given index.
The returned iterator yields NodeIndex<Ix>
s.
pub fn walk_siblings(&self, child: NodeIndex<Ix>) -> WalkSiblings<Ix>
[src]
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
.
Trait Implementations
impl<N: Clone, Ix: Clone + IndexType> Clone for RoseTree<N, Ix>
[src]
impl<N: Debug, Ix: Debug + IndexType> Debug for RoseTree<N, Ix>
[src]
impl<N, Ix> Index<NodeIndex<Ix>> for RoseTree<N, Ix> where
Ix: IndexType,
[src]
Ix: IndexType,
impl<N, Ix> IndexMut<NodeIndex<Ix>> for RoseTree<N, Ix> where
Ix: IndexType,
[src]
Ix: IndexType,
Auto Trait Implementations
impl<N, Ix> RefUnwindSafe for RoseTree<N, Ix> where
Ix: RefUnwindSafe,
N: RefUnwindSafe,
Ix: RefUnwindSafe,
N: RefUnwindSafe,
impl<N, Ix> Send for RoseTree<N, Ix> where
Ix: Send,
N: Send,
Ix: Send,
N: Send,
impl<N, Ix> Sync for RoseTree<N, Ix> where
Ix: Sync,
N: Sync,
Ix: Sync,
N: Sync,
impl<N, Ix> Unpin for RoseTree<N, Ix> where
Ix: Unpin,
N: Unpin,
Ix: Unpin,
N: Unpin,
impl<N, Ix> UnwindSafe for RoseTree<N, Ix> where
Ix: UnwindSafe,
N: UnwindSafe,
Ix: UnwindSafe,
N: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,