Struct read_tree::Sapling

pub struct Sapling<T> { /* fields omitted */ }

A builder to construct Trees.

Saplings are the only way of creating trees. New saplings are initialized empty, containing no nodes. Nodes are then added to the sapling until the tree is complete. The sapling can then be turned into a tree.

Nodes are added to saplings using .push(_). Adding a new node also selects it, meaning later calls of .push(_) will attach the new node as a child to this one. To close a node once all its child nodes have been added, call .pop(). When adding a node that will not have any child nodes, use .push_leaf(_); this acts the same as .push(_); .pop();.

When the sapling is complete, turn it into a tree using .build(). This function returns a Result<_, _> to indicate if the sapling was built successfully. To check if a sapling is ready to be built call .is_ready().

Example

let mut sap = read_tree::Sapling::new();
assert!(sap.is_empty());

sap.push(1); // Add a new node to the tree carrying the payload `1`.
sap.push_leaf(11); // Add a child node to node `1`. This node will have no children.

sap.push(12); // Add another child node to `1`. Select this node.
sap.push_leaf(121); // Add leaf nodes to node `12`.
sap.push_leaf(122);

sap.pop(); // Close node `12`.
sap.pop(); // Close node `1`.

assert!(sap.is_ready());
let _tree = sap.build().unwrap();

Methods

impl<T> Sapling<T>

pub fn new() -> Self

Creates a new empty sapling.

An empty sapling is not yet ready to be built. Add at least one node before building it into a tree.

let sap = read_tree::Sapling::<usize>::new();
assert!(sap.is_empty());
assert!(sap.build().is_err());

pub fn with_capacity(len: usize, depth: Option<usize>) -> Self

Creates a new empty sapling with enough capacity to store len many nodes.

The sapling is allowed to receive more than len nodes; this may however cause additional allocations.

The optional parameter depth should predict the maximum depth of the tree. If the depth is unknown use None. The depth should include the root node, can however exclude leaf nodes, if the leaf nodes will be added using .push_leaf(_). Essentially every call to push(_) increases the depth, and every call to pop() decreases it.

pub fn push(&mut self, data: T)

Adds a new node with the payload data to the sapling.

Until .pop() is called new nodes will be attached to this new node. To avoid changing the selected node use .push_leaf(_) instead.

Note that nodes have to be added to the sapling in the correct oder. Once a node has been closed using .pop() its subtree is finalized and can no longer be changed.

pub fn push_leaf(&mut self, data: T)

Adds a new leaf node with the payload data to the sapling.

pub fn push_tree(&mut self, tree: Tree<T>) -> Sapling<T>

Adds another tree to the selected node in the sapling. Does not change the selected node, similar to .push_leaf(_).

Empties tree in the process and returns it as an empty sapling.

pub fn peek(&self) -> Option<&T>

Returns a reference to the payload of the selected node. Returns None if no node is currently selected; this happens when the sapling is empty or after a root node was closed.

Example

let mut sap = read_tree::Sapling::new();
sap.push(0);
sap.push(1);

assert_eq!(sap.pop(), Some(&1));

assert_eq!(sap.peek(), Some(&0));
assert_eq!(sap.pop(), Some(&0));

sap.build().unwrap();

pub fn pop(&mut self) -> Option<&T>

Closes the current node.

The subtree under the current node is complete and will be closed. From now on new nodes will be attached to the parent of the closed node.

Returns a reference to the payload of the closed node. Returns None if no node is currently selected; this happens when the sapling is empty or after a root node was closed.

Examples

let mut sap = read_tree::Sapling::new();
sap.push(0);
assert_eq!(sap.pop(), Some(&0));
sap.build().unwrap();

let mut sap = read_tree::Sapling::<usize>::new();
assert_eq!(sap.pop(), None);

let mut sap = read_tree::Sapling::new();
sap.push_leaf(0);
assert_eq!(sap.pop(), None);

pub fn pop_all(&mut self)

Closes all open nodes.

Example

let mut sap = read_tree::Sapling::new();
sap.push(0);
sap.push(1);
sap.push(2);
sap.pop_all();

let _tree = sap.build().unwrap();

pub fn pop_as_leaf(&mut self) -> Option<&T>

Closes the current node and makes it a leaf node.

Any nodes that were attached to the current node will be attached to its parent node instead.

Example

let mut sap = read_tree::Sapling::new();
sap.push(0);
sap.push(1);
sap.push_leaf(2);

// make `1` a leaf node; changing `2` to be a child of `0`
sap.pop_as_leaf();
sap.pop();
let tree = sap.build().unwrap();
let mut iter = tree.root().children();

assert_eq!(iter.next().unwrap().data(), &1);
assert_eq!(iter.next().unwrap().data(), &2);

pub fn pop_as_leaf_all(&mut self)

Closes all open nodes and makes them all leaf nodes.

If there are open nodes in the sapling, this will cause multiple root nodes.

Example

let mut sap = read_tree::Sapling::new();
sap.push(0);
sap.push(1);
sap.pop_as_leaf_all();
assert_eq!(sap.build().unwrap_err().1, read_tree::Error::MultipleRoots);

pub fn clear(&mut self)

Removes all nodes from the sapling, making it empty.

Example

let mut sap = read_tree::Sapling::new();
sap.push_leaf(0);
assert_eq!(sap.is_empty(), false);

sap.clear();
assert_eq!(sap.is_empty(), true);

pub fn is_empty(&self) -> bool

Returns true if the sapling contains no nodes. Use push(_) to add nodes.

pub fn is_ready(&self) -> bool

Return true if the sapling is ready to be built.

Verifies that the sapling is not empty and has no open nodes. It does not verify the number of root nodes of the sapling. Building into a Tree may still fail because trees do not allow multiple root nodes.

pub fn build(self) -> Result<Tree<T>, (Sapling<T>, Error)>

Builds the sapling into a tree.

Consumes the sapling in the process. Fails when the sapling is incomplete or has multiple roots. When failing to build the sapling, the sapling is returned unmodified with the error.

impl<T: Clone> Sapling<T>

pub fn push_node(&mut self, node: Node<T>)

Clones the contents of a node and attaches the cloned subtree to the sapling.

This is a relatively expensive step. The tree that node references is unaffected.

Trait Implementations

impl<T: Debug> Debug for Sapling<T>

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

Formats the value using the given formatter.