[−][src]Struct outils::tree::generic::Forest
Forest<V>
is a general purpose data structure for holding a forest of trees. Its tree nodes
are held in a memory arena and are addressed through their associated NodeIndex
.
Forest
is parameterized over:
- Associated values of type
V
, whereV
must implement the traitValueType
The tree nodes of the forest are organized in a first child/next-sibling representation, augmented by last child/previous sibling links. In other words, the children of tree node are maintained in doubly linked list, where the head and tail of the list are the first and last child values of the children's parent node.
Therefore, no allocations and re-allocations are necessary when adding children to nodes. Re-allocation will only take place if the underlying memory arena has reached its capacity.
However, care must be taken when accessing a child node by its position, that is, by using
the method child(node, pos)
of the Traversal
trait, because to access a child by
its position in the list, the list has to be iterated from the beginning. Using access by
position is therefore not very efficient. This caveat also applies to the generic traversal
iterators provided by the traversal
module, which are build on access by position.
In order to iterate over the children of node, the trait Children
is available.
To illustrate the above explations see the following example:
use outils::prelude::*; use outils::tree::traversal::GeneralDfsValues; let mut forest = Forest::new(10); // Create a root with 9 child nodes. let root = forest.insert(9); for i in (0..9) { forest.insert_child(root, i); } // Inefficient iteration: for pos in (0..9) { let index = forest.child(root, pos).expect("Should not fail here!"); // Inefficient! let value = forest.value(index).expect("Should not fail here!"); assert_eq!(*value, pos); } // Also inefficient is using the provided, generic traversals: let seq: Vec<&usize> = GeneralDfsValues::new(&forest, root).collect(); // Will use child()! assert_eq!(seq, vec![&9, &0, &1, &2, &3, &4, &5, &6, &7, &8]); // Efficient iteration: let mut pos = 0; for child in forest.children(root) { let value = forest.value(child).expect("Should not fail here!"); assert_eq!(*value, pos); pos += 1; }
Implementations
impl<V> Forest<V> where
V: ValueType,
[src]
V: ValueType,
pub fn new(size: usize) -> Self
[src]
Construct a new empty Forest
with an initial capacity of size
.
pub fn first_child(&self, parent: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of the first child node of the tree node indexed by node
. If the node
has no children or node
is not a valid index, None
is returned.
use outils::prelude::*; let mut tree = Forest::new(10); let root = tree.insert(1); let first_child = tree.insert_child(root, 2).expect("Should not fail here"); let second_child = tree.insert_child(root, 3).expect("Should not fail here"); assert_eq!(tree.first_child(root), Some(first_child));
pub fn last_child(&self, parent: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of the last child node of the tree node indexed by node
. If the node
has no children or node
is not a valid index, None
is returned.
use outils::prelude::*; let mut tree = Forest::new(10); let root = tree.insert(1); let first_child = tree.insert_child(root, 2).expect("Should not fail here"); let second_child = tree.insert_child(root, 3).expect("Should not fail here"); assert_eq!(tree.last_child(root), Some(second_child));
pub fn prev_sibling(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of the previous sibling node of the tree node indexed by node
. If the
node is the first child of its parent or node
is not a valid index, None
is returned.
use outils::prelude::*; let mut tree = Forest::new(10); let root = tree.insert(1); let first_child = tree.insert_child(root, 2).expect("Should not fail here"); let second_child = tree.insert_child(root, 3).expect("Should not fail here"); assert_eq!(tree.prev_sibling(second_child), Some(first_child));
pub fn next_sibling(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of the next sibling node of the tree node indexed by node
. If the
node is the last child of its parent or node
is not a valid index, None
is returned.
use outils::prelude::*; let mut tree = Forest::new(10); let root = tree.insert(1); let first_child = tree.insert_child(root, 2).expect("Should not fail here"); let second_child = tree.insert_child(root, 3).expect("Should not fail here"); assert_eq!(tree.next_sibling(first_child), Some(second_child));
pub fn roots(&self) -> &Vec<NodeIndex>
[src]
Returns the list of root node indices of this forest. The values are not returned in any particular order.
use outils::prelude::*; let mut tree = Forest::new(10); let first_root = tree.insert(1); let second_root = tree.insert(2); let roots = tree.roots(); assert!(roots.contains(&first_root)); assert!(roots.contains(&second_root));
Trait Implementations
impl<'slf, V> Children<'slf, usize> for Forest<V> where
V: 'slf + ValueType,
[src]
V: 'slf + ValueType,
impl<V: Clone> Clone for Forest<V> where
V: ValueType,
[src]
V: ValueType,
impl<V: Debug> Debug for Forest<V> where
V: ValueType,
[src]
V: ValueType,
impl<V> GenericForest<V, usize> for Forest<V> where
V: ValueType,
[src]
V: ValueType,
fn insert(&mut self, value: V) -> NodeIndex
[src]
Inserts value
into the forest as a new root node and return the assigned NodeIndex
.
fn insert_child(
&mut self,
parent: NodeIndex,
value: V
) -> Result<NodeIndex, TreeError>
[src]
&mut self,
parent: NodeIndex,
value: V
) -> Result<NodeIndex, TreeError>
Inserts value
into the forest as a new node. which will be the last child of the
node indexed by parent
. If the operation has been completed successfully, the
index of the new child is returned. Otherwise, in particular if parent
is not a
valid node index, an error is returned.
fn insert_child_at(
&mut self,
parent: NodeIndex,
pos: usize,
value: V
) -> Result<NodeIndex, TreeError>
[src]
&mut self,
parent: NodeIndex,
pos: usize,
value: V
) -> Result<NodeIndex, TreeError>
Inserts value
into the forest as a new node. which will be a child of the
node indexed by parent
at the position specified by pos
. If pos
is greater than or
equal to the number of children of parent
, the new child will be the new last child.
If the operation has been completed successfully, the index of the new child is returned.
Otherwise, if parent
is not a valid node index, an error is returned.
fn remove(&mut self, node: NodeIndex) -> Result<V, TreeError>
[src]
Removes the tree node indexed by node
, returning its content in case of a valid index.
If the removed node has children, they will become children of the parent of the removed node,
replacing the removed node. If the removed node has no parent, its children will become roots.
fn remove_subtree(
&mut self,
node: NodeIndex
) -> Result<Vec<(NodeIndex, V)>, TreeError>
[src]
&mut self,
node: NodeIndex
) -> Result<Vec<(NodeIndex, V)>, TreeError>
Removes the tree node indexed by node
and its subtree, returning the contents of the
removed nodes in case of a valid index. The returned values will be collected in pre-order.
fn set_as_child(
&mut self,
parent: NodeIndex,
child: NodeIndex
) -> Result<(), TreeError>
[src]
&mut self,
parent: NodeIndex,
child: NodeIndex
) -> Result<(), TreeError>
Adds the root node child
as the new last child of the node indexed by parent
. If the operation has
been completed successfully, Ok(())
is returned. If the forest has not been changed, an error
is returned. This will be the case if:
- the node indexed by
child
is not a tree root, i.e. has a parent. - the node indexed by
parent
is a node in the tree rooted inchild
. - either
parent
orchild
is not a valid node index.
fn set_as_child_at(
&mut self,
parent: NodeIndex,
child: NodeIndex,
pos: usize
) -> Result<(), TreeError>
[src]
&mut self,
parent: NodeIndex,
child: NodeIndex,
pos: usize
) -> Result<(), TreeError>
Adds the root node child
as a child of the node indexed by parent
at the position specified
by pos
. If pos
is greater than or equal to the number of children of parent
, the new
child will be the new last child. If the operation has been completed successfully, Ok(())
is returned. If the forest has not been changed, an error is returned. This will be the case if:
- the node indexed by
child
is not a tree root, i.e. has a parent. - the node indexed by
parent
is a node in the tree rooted inchild
. - either
parent
orchild
is not a valid node index.
fn remove_as_child(&mut self, node: NodeIndex) -> Result<(), TreeError>
[src]
Removes the node indexed by node
as a child of its parent, thus making it a new root
node of the forest. If the operation has been completed successfully, Ok(())
is returned.
If node
is not a valid not index, an error is returned.
impl<V> Index<NodeIndex<usize>> for Forest<V> where
V: ValueType,
[src]
V: ValueType,
impl<V> IndexMut<NodeIndex<usize>> for Forest<V> where
V: ValueType,
[src]
V: ValueType,
impl<V> Tgf for Forest<V> where
V: ValueType,
[src]
V: ValueType,
impl<V> Traversable<V, usize> for Forest<V> where
V: ValueType,
[src]
V: ValueType,
fn root(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of the root node of the tree containing the tree node indexed by node
.
fn value(&self, node: NodeIndex) -> Option<&V>
[src]
Immutably access the value stored in the tree node indexed by node
.
fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>
[src]
Mutably access the value stored in the tree node indexed by node
.
fn parent(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of parent node tree node indexed by node
.
fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>
[src]
Returns the index of the child node at position pos
of the tree node indexed by node
.
fn child_count(&self, node: NodeIndex) -> usize
[src]
Returns the number of child nodes of the tree node indexed by node
.
fn node_count(&self) -> usize
[src]
Returns the total number of tree nodes of the tree self
.
impl<'slf, V> Values<'slf, V, usize> for Forest<V> where
V: 'slf + ValueType,
[src]
V: 'slf + ValueType,
Auto Trait Implementations
impl<V> RefUnwindSafe for Forest<V> where
V: RefUnwindSafe,
V: RefUnwindSafe,
impl<V> Send for Forest<V> where
V: Send,
V: Send,
impl<V> Sync for Forest<V> where
V: Sync,
V: Sync,
impl<V> Unpin for Forest<V> where
V: Unpin,
V: Unpin,
impl<V> UnwindSafe for Forest<V> where
V: UnwindSafe,
V: 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>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,