Struct id_tree::Tree [−] [src]

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>
[src]

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

Sets the root of the Tree.

If there is already a root Node present in the tree, that Node is set as the first child of the new root.

use id_tree::Tree;
use id_tree::Node;

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

tree.set_root(Node::new(5));

Add a new Node to the tree as the child of a Node specified by the given NodeId.

Returns a Result containing the NodeId of the child that was added or a NodeIdError if one occurred.

Note: Adds the new Node to the end of its children.

use id_tree::Tree;
use id_tree::Node;

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

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

tree.insert_with_parent(child_node, &root_id);

Get an immutable reference to a Node.

If the NodeId provided is invalid (whether the Node in question has already been removed, or the NodeId belongs to a different Tree), this function returns a None value.

use id_tree::Tree;
use id_tree::Node;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(Node::new(5));

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

Get a mutable reference to a Node.

If the NodeId provided is invalid (whether the Node in question has already been removed, or the NodeId belongs to a different Tree), this function returns a None value.

use id_tree::Tree;
use id_tree::Node;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(Node::new(5));

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

Remove a Node from the Tree and move its children up one "level" in the Tree if possible.

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

In other words, this Node's children will point to its parent as their parent instead of this Node. In addition, this Node's parent will have this Node's children added as its own children. If this Node has no parent, then calling this function is the equivalent of calling remove_node_orphan_children.

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::Tree;
use id_tree::Node;

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

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

let child_id = tree.insert_with_parent(child_node, &root_id).ok().unwrap();
tree.insert_with_parent(grandchild_node, &root_id);

let root_node = tree.remove_node_lift_children(child_id);

Remove a Node from the Tree and leave all of its children in the Tree.

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::Tree;
use id_tree::Node;

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

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

let child_id = tree.insert_with_parent(child_node, &root_id).ok().unwrap();
tree.insert_with_parent(grandchild_node, &root_id);

let root_node = tree.remove_node_orphan_children(child_id);

Remove a Node from the Tree including all its children recursively.

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

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

NOTE: Please keep in mind: Children of this NodeId are removed during this method call, so NodeIds that previously pointed to them will no longer be valid after calling this method. This means even without using Clone you might end up with copies of invalid Id's. Use with caution.

If the caller needs a copy of the parent 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::Tree;
use id_tree::Node;

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

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

let child_id = tree.insert_with_parent(child_node, &root_id).ok().unwrap();
tree.insert_with_parent(grandchild_node, &child_id).unwrap();

let child_node = tree.remove_node_drop_children(child_id);

Moves a Node inside a Tree to a new parent leaving all children in their place.

If the new parent (let's call it B) is a descendant of the Node being moved (A), then the direct child of A on the path from A to B will be shifted upwards to take the place of its parent (A). All other children of A will be left alone, meaning they will travel with it down the Tree.

Please note that during the "shift-up" part of the above scenario, the Node being shifted up will always be added as the last child of its new parent.

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

use id_tree::Tree;
use id_tree::Node;

let root_node = Node::new(1);
let first_child_node = Node::new(2);
let second_child_node = Node::new(3);
let grandchild_node = Node::new(4);

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

let first_child_id  = tree.insert_with_parent(first_child_node,  &root_id).ok().unwrap();
let second_child_id = tree.insert_with_parent(second_child_node, &root_id).ok().unwrap();
let grandchild_id   = tree.insert_with_parent(grandchild_node, &first_child_id).ok().unwrap();

tree.move_node_to_parent(&grandchild_id, &second_child_id).unwrap();

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::Tree;
use id_tree::Node;

let root_node = Node::new(100);
let first_child = Node::new(1);
let second_child = Node::new(2);
let third_child = Node::new(0);

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

tree.insert_with_parent(first_child, &root_id).unwrap();
tree.insert_with_parent(second_child, &root_id).unwrap();
tree.insert_with_parent(third_child, &root_id).unwrap();

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

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::Tree;
use id_tree::Node;

let root_node = Node::new(100);
let first_child = Node::new(1);
let second_child = Node::new(2);
let third_child = Node::new(0);

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

tree.insert_with_parent(first_child, &root_id).unwrap();
tree.insert_with_parent(second_child, &root_id).unwrap();
tree.insert_with_parent(third_child, &root_id).unwrap();

tree.sort_children_by_data(&root_id);

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::Tree;
use id_tree::Node;

let root_node = Node::new(100);
let first_child = Node::new(1);
let second_child = Node::new(2);
let third_child = Node::new(0);

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

tree.insert_with_parent(first_child, &root_id).unwrap();
tree.insert_with_parent(second_child, &root_id).unwrap();
tree.insert_with_parent(third_child, &root_id).unwrap();

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

Swaps two Nodes including their children given their NodeIds.

If one Node is a descendant of the other getting swapped, the former upper Node is attached as the last child of the former lower Node after the swap. (The lower will take the uppers original position as usual.) The subtree of the former upper node is not touched except that the lower Node is moved including all its children.

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 Id.

use id_tree::Tree;
use id_tree::Node;

let root_node = Node::new(1);
let first_child_node = Node::new(2);
let second_child_node = Node::new(3);
let grandchild_node = Node::new(4);

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(root_node);

let first_child_id  = tree.insert_with_parent(first_child_node,  &root_id).ok().unwrap();
let second_child_id = tree.insert_with_parent(second_child_node, &root_id).ok().unwrap();
let grandchild_id   = tree.insert_with_parent(grandchild_node, &second_child_id).unwrap();

tree.swap_sub_tree(&first_child_id, &grandchild_id).unwrap();

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

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

use id_tree::Tree;
use id_tree::Node;

let mut tree: Tree<i32> = Tree::new();
let root_id = tree.set_root(Node::new(5));

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