Struct id_tree::Tree

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

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.

Methods

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 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());

Trait Implementations

impl<T> PartialEq<Tree<T>> for Tree<T> where
    T: PartialEq, 

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]

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

This method tests for !=.

impl<T> Default for Tree<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T> Clone for Tree<T> where
    T: Clone, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Tree<T>

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

Formats the value using the given formatter.