Struct Tree

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

A tree structure consisting of Nodes.

Panics

While it is highly unlikely, any function that takes a NodeId can panic. This, however, should only happen due to improper NodeId management within id_tree and should have nothing to do with the library user’s code.

If this ever happens please report the issue. Panics are not expected behavior for this library, but they can happen due to bugs.

Implementations

impl<T> Tree<T>

pub fn new() -> Tree<T>

Creates a new Tree with default settings (no root Node and no space pre-allocation).

use id_tree::Tree;

let _tree: Tree<i32> = Tree::new();

pub fn capacity(&self) -> usize

Returns the number of elements the tree can hold without reallocating.

pub fn height(&self) -> usize

Returns the maximum height of the Tree.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
assert_eq!(0, tree.height());

let root_id = tree.insert(Node::new(1), AsRoot).unwrap();
assert_eq!(1, tree.height());

tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
assert_eq!(2, tree.height());

pub fn insert( &mut self, node: Node<T>, behavior: InsertBehavior<'_>, ) -> Result<NodeId, NodeIdError>

Inserts a new Node into the Tree. The InsertBehavior provided will determine where the Node is inserted.

Returns a Result containing the NodeId of the Node that was inserted or a NodeIdError if one occurred.

use id_tree::*;
use id_tree::InsertBehavior::*;

let root_node = Node::new(1);
let child_node = Node::new(2);

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(root_node, AsRoot).unwrap();

tree.insert(child_node, UnderNode(&root_id)).unwrap();

pub fn get(&self, node_id: &NodeId) -> Result<&Node<T>, NodeIdError>

Get an immutable reference to a Node.

Returns a Result containing the immutable reference or a NodeIdError if one occurred.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(5), AsRoot).unwrap();

let root_node: &Node<i32> = tree.get(&root_id).unwrap();

pub fn get_mut(&mut self, node_id: &NodeId) -> Result<&mut Node<T>, NodeIdError>

Get a mutable reference to a Node.

Returns a Result containing the mutable reference or a NodeIdError if one occurred.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(5), AsRoot).unwrap();

let root_node: &mut Node<i32> = tree.get_mut(&root_id).unwrap();

pub fn remove_node( &mut self, node_id: NodeId, behavior: RemoveBehavior, ) -> Result<Node<T>, NodeIdError>

Remove a Node from the Tree. The RemoveBehavior provided determines what happens to the removed Node’s children.

Returns a Result containing the removed Node or a NodeIdError if one occurred.

NOTE: The Node that is returned will have its parent and child values cleared to avoid providing the caller with extra copies of NodeIds should the corresponding Nodes be removed from the Tree at a later time.

If the caller needs a copy of the parent or child NodeIds, they must Clone them before this Node is removed from the Tree. Please see the Potential NodeId Issues section of the NodeId documentation for more information on the implications of calling Clone on a NodeId.

use id_tree::*;
use id_tree::InsertBehavior::*;
use id_tree::RemoveBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();

let child_id = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
let grandchild_id = tree.insert(Node::new(2), UnderNode(&child_id)).unwrap();

let child = tree.remove_node(child_id, DropChildren).unwrap();

pub fn move_node( &mut self, node_id: &NodeId, behavior: MoveBehavior<'_>, ) -> Result<(), NodeIdError>

Moves a Node in the Tree to a new location based upon the MoveBehavior provided.

use id_tree::*;
use id_tree::InsertBehavior::*;
use id_tree::MoveBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(1), AsRoot).unwrap();
let child_id = tree.insert(Node::new(2),  UnderNode(&root_id)).unwrap();
let grandchild_id = tree.insert(Node::new(3), UnderNode(&child_id)).unwrap();

tree.move_node(&grandchild_id, ToRoot).unwrap();

assert_eq!(tree.root_node_id(), Some(&grandchild_id));

pub fn sort_children_by<F>( &mut self, node_id: &NodeId, compare: F, ) -> Result<(), NodeIdError>

where F: FnMut(&Node<T>, &Node<T>) -> Ordering,

Sorts the children of one node, in-place, using compare to compare the nodes

This sort is stable and O(n log n) worst-case but allocates approximately 2 * n where n is the length of children

Returns an empty Result containing a NodeIdError if one occurred.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(100), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
tree.insert(Node::new(0), UnderNode(&root_id)).unwrap();

tree.sort_children_by(&root_id, |a, b| a.data().cmp(b.data())).unwrap();

pub fn sort_children_by_data( &mut self, node_id: &NodeId, ) -> Result<(), NodeIdError>

where T: Ord,

Sorts the children of one node, in-place, comparing their data

This sort is stable and O(n log n) worst-case but allocates approximately 2 * n where n is the length of children

Returns an empty Result containing a NodeIdError if one occurred.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(100), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
tree.insert(Node::new(0), UnderNode(&root_id)).unwrap();

tree.sort_children_by_data(&root_id).unwrap();

pub fn sort_children_by_key<B, F>( &mut self, node_id: &NodeId, f: F, ) -> Result<(), NodeIdError>

where B: Ord, F: FnMut(&Node<T>) -> B,

Sorts the children of one node, in-place, using f to extract a key by which to order the sort by.

This sort is stable and O(n log n) worst-case but allocates approximately 2 * n where n is the length of children

Returns an empty Result containing a NodeIdError if one occurred.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(100), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
tree.insert(Node::new(0), UnderNode(&root_id)).unwrap();

tree.sort_children_by_key(&root_id, |x| x.data().clone()).unwrap();

pub fn make_nth_sibling( &mut self, node: &NodeId, pos: usize, ) -> Result<(), NodeIdError>

Moves the node to a position amongst sibling nodes. If the pos provided is too large then the node in question will be placed after all of its other siblings.

Any children will remain attached to this node.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut my_tree = TreeBuilder::<i32>::new()
        .with_node_capacity(5)
        .build();

let root_id: NodeId = my_tree.insert(Node::new(0), AsRoot).unwrap();
let c1: NodeId = my_tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
let _c2 = my_tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
let _c3 = my_tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
let _c4 = my_tree.insert(Node::new(4), UnderNode(&root_id)).unwrap();

let expected_values = [1, 2, 3, 4];
for (child, expected) in my_tree.children(&root_id).unwrap().zip(expected_values.iter()) {
    assert_eq!(child.data(), expected);
}

my_tree.make_nth_sibling(&c1, 3).unwrap();

let expected_values = [2, 3, 4, 1];
for (child, expected) in my_tree.children(&root_id).unwrap().zip(expected_values.iter()) {
    assert_eq!(child.data(), expected);
}

pub fn make_first_sibling( &mut self, node_id: &NodeId, ) -> Result<bool, NodeIdError>

Puts the node in the first position relative to other sibling nodes.

Any children will remain attached to this node.

Returns false if the node was already the first node or the root node.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(1), AsRoot).unwrap();

let first_child_id = tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
let second_child_id = tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
let grandchild_id = tree.insert(Node::new(4), UnderNode(&second_child_id)).unwrap();

assert_eq!(tree.get(&root_id).unwrap().children()[0], first_child_id);
assert_eq!(tree.get(&root_id).unwrap().children()[1], second_child_id);
assert!(tree.get(&second_child_id).unwrap().children().contains(&grandchild_id));

assert!(!tree.make_first_sibling(&root_id).unwrap());
assert!(!tree.make_first_sibling(&grandchild_id).unwrap());
assert!(tree.make_first_sibling(&second_child_id).unwrap());

assert_eq!(tree.get(&root_id).unwrap().children()[0], second_child_id);
assert_eq!(tree.get(&root_id).unwrap().children()[1], first_child_id);
assert!(tree.get(&second_child_id).unwrap().children().contains(&grandchild_id));

pub fn make_last_sibling( &mut self, node_id: &NodeId, ) -> Result<bool, NodeIdError>

Puts the node in the last position relative to other sibling nodes.

Any children will remain attached to this node.

Returns false if the node was already the first node or the root node.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(1), AsRoot).unwrap();

let first_child_id = tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
let second_child_id = tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
let grandchild_id = tree.insert(Node::new(4), UnderNode(&second_child_id)).unwrap();

assert_eq!(tree.get(&root_id).unwrap().children()[0], first_child_id);
assert_eq!(tree.get(&root_id).unwrap().children()[1], second_child_id);
assert!(tree.get(&second_child_id).unwrap().children().contains(&grandchild_id));

assert!(tree.make_last_sibling(&first_child_id).unwrap());
assert!(!tree.make_last_sibling(&root_id).unwrap());
assert!(!tree.make_last_sibling(&grandchild_id).unwrap());

assert_eq!(tree.get(&root_id).unwrap().children()[0], second_child_id);
assert_eq!(tree.get(&root_id).unwrap().children()[1], first_child_id);
assert!(tree.get(&second_child_id).unwrap().children().contains(&grandchild_id));

pub fn swap_nodes( &mut self, first_id: &NodeId, second_id: &NodeId, behavior: SwapBehavior, ) -> Result<(), NodeIdError>

Swap Nodes in the Tree based upon the SwapBehavior provided.

Both NodeIds are still valid after this process and are not swapped.

This keeps the positions of the Nodes in their parents’ children collection.

Returns an empty Result containing a NodeIdError if one occurred on either provided NodeId.

use id_tree::*;
use id_tree::InsertBehavior::*;
use id_tree::SwapBehavior::*;

let mut tree: Tree<i32> = Tree::new();

let root_id = tree.insert(Node::new(1), AsRoot).unwrap();

let first_child_id = tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
let second_child_id = tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
let grandchild_id = tree.insert(Node::new(4), UnderNode(&second_child_id)).unwrap();

tree.swap_nodes(&first_child_id, &grandchild_id, TakeChildren).unwrap();

assert!(tree.get(&second_child_id).unwrap().children().contains(&first_child_id));
assert!(tree.get(&root_id).unwrap().children().contains(&grandchild_id));

pub fn root_node_id(&self) -> Option<&NodeId>

Returns a Some value containing the NodeId of the root Node if it exists. Otherwise a None value is returned.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(5), AsRoot).unwrap();

assert_eq!(&root_id, tree.root_node_id().unwrap());

pub fn ancestors( &self, node_id: &NodeId, ) -> Result<Ancestors<'_, T>, NodeIdError>

Returns an Ancestors iterator (or a NodeIdError if one occurred).

Allows iteration over the ancestor Nodes of a given NodeId directly instead of having to call tree.get(...) with a NodeId each time.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
let node_1 = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut ancestors = tree.ancestors(&node_1).unwrap();

assert_eq!(ancestors.next().unwrap().data(), &0);
assert!(ancestors.next().is_none());

pub fn ancestor_ids( &self, node_id: &NodeId, ) -> Result<AncestorIds<'_, T>, NodeIdError>

Returns an AncestorIds iterator (or a NodeIdError if one occurred).

Allows iteration over the ancestor NodeIds of a given NodeId.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
let node_1 = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut ancestor_ids = tree.ancestor_ids(&node_1).unwrap();

assert_eq!(ancestor_ids.next().unwrap(), &root_id);
assert!(ancestor_ids.next().is_none());

pub fn children(&self, node_id: &NodeId) -> Result<Children<'_, T>, NodeIdError>

Returns a Children iterator (or a NodeIdError if one occurred).

Allows iteration over the child Nodes of a given NodeId directly instead of having to call tree.get(...) with a NodeId each time.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut children = tree.children(&root_id).unwrap();

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

pub fn children_ids( &self, node_id: &NodeId, ) -> Result<ChildrenIds<'_>, NodeIdError>

Returns a ChildrenIds iterator (or a NodeIdError if one occurred).

Allows iteration over the child NodeIds of a given NodeId.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
let node_1 = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut children_ids = tree.children_ids(&root_id).unwrap();

assert_eq!(children_ids.next().unwrap(), &node_1);
assert!(children_ids.next().is_none());

pub fn traverse_pre_order( &self, node_id: &NodeId, ) -> Result<PreOrderTraversal<'_, T>, NodeIdError>

Returns a PreOrderTraversal iterator (or a NodeIdError if one occurred).

Allows iteration over all of the Nodes in the sub-tree below a given Node. This iterator will always include that sub-tree “root” specified by the NodeId given.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut nodes = tree.traverse_pre_order(&root_id).unwrap();

assert_eq!(nodes.next().unwrap().data(), &0);
assert_eq!(nodes.next().unwrap().data(), &1);
assert!(nodes.next().is_none());

pub fn traverse_pre_order_ids( &self, node_id: &NodeId, ) -> Result<PreOrderTraversalIds<'_, T>, NodeIdError>

Returns a PreOrderTraversalIds iterator (or a NodeIdError if one occurred).

Allows iteration over all of the NodeIds in the sub-tree below a given NodeId. This iterator will always include that sub-tree “root” specified by the NodeId given.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut nodes = tree.traverse_pre_order_ids(&root_id).unwrap();

assert_eq!(tree.get(&nodes.next().unwrap()).unwrap().data(), &0);
assert_eq!(tree.get(&nodes.next().unwrap()).unwrap().data(), &1);
assert!(nodes.next().is_none());

pub fn traverse_post_order( &self, node_id: &NodeId, ) -> Result<PostOrderTraversal<'_, T>, NodeIdError>

Returns a PostOrderTraversal iterator (or a NodeIdError if one occurred).

Allows iteration over all of the Nodes in the sub-tree below a given Node. This iterator will always include that sub-tree “root” specified by the NodeId given.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut nodes = tree.traverse_post_order(&root_id).unwrap();

assert_eq!(nodes.next().unwrap().data(), &1);
assert_eq!(nodes.next().unwrap().data(), &0);
assert!(nodes.next().is_none());

pub fn traverse_post_order_ids( &self, node_id: &NodeId, ) -> Result<PostOrderTraversalIds, NodeIdError>

Returns a PostOrderTraversalIds iterator (or a NodeIdError if one occurred).

Allows iteration over all of the NodeIds in the sub-tree below a given NodeId. This iterator will always include that sub-tree “root” specified by the NodeId given.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut nodes = tree.traverse_post_order_ids(&root_id).unwrap();

assert_eq!(tree.get(&nodes.next().unwrap()).unwrap().data(), &1);
assert_eq!(tree.get(&nodes.next().unwrap()).unwrap().data(), &0);
assert!(nodes.next().is_none());

pub fn traverse_level_order( &self, node_id: &NodeId, ) -> Result<LevelOrderTraversal<'_, T>, NodeIdError>

Returns a LevelOrderTraversal iterator (or a NodeIdError if one occurred).

Allows iteration over all of the Nodes in the sub-tree below a given Node. This iterator will always include that sub-tree “root” specified by the NodeId given.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut nodes = tree.traverse_level_order(&root_id).unwrap();

assert_eq!(nodes.next().unwrap().data(), &0);
assert_eq!(nodes.next().unwrap().data(), &1);
assert!(nodes.next().is_none());

pub fn traverse_level_order_ids( &self, node_id: &NodeId, ) -> Result<LevelOrderTraversalIds<'_, T>, NodeIdError>

Returns a LevelOrderTraversalIds iterator (or a NodeIdError if one occurred).

Allows iteration over all of the NodeIdss in the sub-tree below a given NodeId. This iterator will always include that sub-tree “root” specified by the NodeId given.

use id_tree::*;
use id_tree::InsertBehavior::*;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();

let mut nodes = tree.traverse_level_order_ids(&root_id).unwrap();

assert_eq!(tree.get(&nodes.next().unwrap()).unwrap().data(), &0);
assert_eq!(tree.get(&nodes.next().unwrap()).unwrap().data(), &1);
assert!(nodes.next().is_none());

impl<T> Tree<T>

where T: Debug,

pub fn write_formatted<W>(&self, w: &mut W) -> Result<(), Error>

where W: Write,

Write formatted tree representation and nodes with debug formatting.

Example:

use id_tree::Tree;
use id_tree::Node;
use id_tree::InsertBehavior::*;

let mut tree = Tree::<i32>::new();
let root_id = tree.insert(Node::new(0), AsRoot).unwrap();
let first_child_id = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
let _ = tree.insert(Node::new(2), UnderNode(&first_child_id)).unwrap();
let _ = tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
let mut s = String::new();
tree.write_formatted(&mut s).unwrap();
assert_eq!(&s, "\
0
├── 1
│   └── 2
└── 3
");

Writes nothing if the tree is empty.

use id_tree::Tree;

let tree = Tree::<i32>::new();
let mut s = String::new();
tree.write_formatted(&mut s).unwrap();
assert_eq!(&s, "");

Trait Implementations

impl<T> Clone for Tree<T>

where T: Clone,

fn clone(&self) -> Tree<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for Tree<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for Tree<T>

fn default() -> Tree<T>

Returns the “default value” for a type.

impl<T> PartialEq for Tree<T>

where T: PartialEq,

fn eq(&self, other: &Tree<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl TreeHelper for Tree<Element>

fn get_element(&self, node_id: &NodeId) -> &Element

Unwraps and gets the underlying Element reference.

⚠ Panics if node_id does not exist.

fn get_element_mut(&mut self, node_id: &NodeId) -> &mut Element

Unwraps and gets the underlying Element reference.

⚠ Panics if node_id does not exist.

fn get_parent(&self, child: &NodeId) -> &Element

Unwraps and gets the parent of the referenced NodeId.

⚠ Panics if child does not exist or if child does not have a parent.

fn get_parent_mut(&mut self, child: &NodeId) -> &mut Element

Unwraps and gets the parent of the referenced NodeId.

⚠ Panics if child does not exist or if child does not have a parent.

fn get_parent_id(&self, child: &NodeId) -> &NodeId

Unwraps and gets the parent ID of the referenced NodeId.

⚠ Panics if child does not exist or if child does not have a parent.

fn splice_subtree( &mut self, parent_id: &NodeId, other: &Tree<Element>, other_id: &NodeId, order: CreateOrder, ) -> NodeId

Splice the subtree of other rooted at other_id into tree under parent_id with the given order

fn write_formatted_names<W: Write>(&self, w: &mut W) -> Result

Write formatted tree representation showing only the names of the nodes (as opposed to the default Tree::write_formatted method).