Struct Sapling

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

A builder to construct Tree<T>s and PolyTree<T>s.

Saplings are the only way of creating a Tree<T>. 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 the sapling is complete, turn it into a Tree<T> using build. This method returns a Result<Tree<T>, BuildError<T>> to indicate if the sapling was built successfully. In case of an error BuildError<T> will contain the sapling.

Examples

use read_tree::{Sapling, Tree};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut sap = 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()?;

    Ok(())
}

Implementations

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.

Examples

use read_tree::Sapling;

let sap = 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 further memory allocations. For more information check out Vec::with_capacity.

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. The rule is that every call to push increases the depth, and every call to pop decreases it. Empty saplings start with depth 0 and methods like push_leaf do not affect the depth. If omitted 0 will be used by default.

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

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

The new node is positioned as a child node of the currently selected node. The selected node will be changed to be the new node until the next call of pop. To avoid changing the selection use push_leaf instead; note that this will make it impossible to attach child nodes to the node, forcing it to be a leaf node.

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.

This method is a convenient shortcut that behaves the same as calling push immediately followed by pop.

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

Adds another tree to the selected node in the sapling. This operation does not change the selected node, similar to push_leaf.

Empties tree in the process and returns it as an empty sapling. This allows the caller to reuse the trees internal buffers.

pub fn push_polytree(&mut self, tree: PolyTree<T>) -> Sapling<T>

Adds another poly-tree to the selected node in the sapling. This operation does not change the selected node, similar to push_leaf.

Empties tree in the process and returns it as an empty sapling. This allows the caller to reuse the trees internal buffers.

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

where T: Clone,

Clones the contents of a node and attaches the cloned subtree to the sapling. Requires the payload type T to be Clone.

If T implements Copy, the cloning of the subtree is relatively cheap. See Vec::extend_from_slice for more information.

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.

Examples

use read_tree::Sapling;

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

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

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

assert_eq!(sap.peek(), None);
assert_eq!(sap.pop(), None);

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

Closes the selected node.

The subtree under the selected node is complete and will be closed. From then 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 was selected; this happens when the sapling is empty or after a root node has been closed.

Examples

use read_tree::Sapling;

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

assert!(sap.is_ready());

use read_tree::Sapling;

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

pub fn pop_all(&mut self)

Closes all open nodes.

Examples

use read_tree::Sapling;

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

assert!(sap.is_ready());

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 node will be attached to its parent instead.

Examples

use read_tree::Sapling;

let mut sap = 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.as_node().children();

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

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 create multiple root nodes.

Examples

use read_tree::{BuildError, Sapling};

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

sap.pop_as_leaf_all();
match sap.build().unwrap_err() {
    BuildError::MultipleRoots(_) => (),
    _ => panic!(),
}

pub fn clear(&mut self)

Removes all nodes from the sapling, making it empty.

Examples

use read_tree::Sapling;

let mut sap = 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<T> may still fail because trees do not allow multiple root nodes.

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

Builds the sapling into a Tree<T>.

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 BuildError<T>.

pub fn build_polytree(self) -> Result<PolyTree<T>, BuildError<T>>

Builds the sapling into a PolyTree<T>.

Consumes the sapling in the process. Fails when the sapling is incomplete. When failing to build the sapling, the sapling is returned unmodified with the BuildError<T>.

Trait Implementations

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

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

Formats the value using the given formatter.

impl<T> Default for Sapling<T>

fn default() -> Self

Returns the “default value” for a type.