Struct outils::tree::generic::Forest

pub struct Forest<V> where
    V: ValueType,  { /* fields omitted */ }

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, where V must implement the trait ValueType

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, 

pub fn new(size: usize) -> Self

Construct a new empty Forest with an initial capacity of size.

pub fn first_child(&self, parent: NodeIndex) -> Option<NodeIndex>

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>

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>

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>

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>

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, 

fn children(
    &'slf self,
    node: NodeIndex
) -> Box<dyn Iterator<Item = NodeIndex> + 'slf>

Returns a boxed iterator over the children of the tree node node.

impl<V: Clone> Clone for Forest<V> where
    V: ValueType, 

fn clone(&self) -> Forest<V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V: Debug> Debug for Forest<V> where
    V: ValueType, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<V> GenericForest<V, usize> for Forest<V> where
    V: ValueType, 

fn insert(&mut self, value: V) -> NodeIndex

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>

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>

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>

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>

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>

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 in child.
• either parent or child is not a valid node index.

fn set_as_child_at(
    &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 in child.
• either parent or child is not a valid node index.

fn remove_as_child(&mut self, node: NodeIndex) -> Result<(), TreeError>

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, 

type Output = V

The returned type after indexing.

fn index(&self, index: NodeIndex) -> &V

Performs the indexing (container[index]) operation.

impl<V> IndexMut<NodeIndex<usize>> for Forest<V> where
    V: ValueType, 

fn index_mut(&mut self, index: NodeIndex) -> &mut V

Performs the mutable indexing (container[index]) operation.

impl<V> Tgf for Forest<V> where
    V: ValueType, 

fn to_tgf(&self) -> String

Returns a TGF representation of Self.

impl<V> Traversable<V, usize> for Forest<V> where
    V: ValueType, 

fn root(&self, node: NodeIndex) -> Option<NodeIndex>

Returns the index of the root node of the tree containing the tree node indexed by node.

fn value(&self, node: NodeIndex) -> Option<&V>

Immutably access the value stored in the tree node indexed by node.

fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>

Mutably access the value stored in the tree node indexed by node.

fn parent(&self, node: NodeIndex) -> Option<NodeIndex>

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>

Returns the index of the child node at position pos of the tree node indexed by node.

fn child_count(&self, node: NodeIndex) -> usize

Returns the number of child nodes of the tree node indexed by node.

fn node_count(&self) -> usize

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, 

fn values(&'slf self) -> Box<dyn Iterator<Item = (NodeIndex, &'slf V)> + 'slf>

Returns a boxed iterator over the stored values and their corresponding tree node indices held by self.