Crate id_tree 

A library for creating and modifying Tree structures.

Overview

In this implementation, the Tree owns all of the Nodes and all inter-Node relationships are managed with NodeIds.

Trees in this library are “just” trees. They do not allow cycles. They do not allow the creation of arbitrary Graph structures. There is no weight associated with edges between Nodes. In addition, each Node can have an arbitrary number of child Nodes.

It is important to note that this library does not support comparison-based Node insertion. In other words, this is not a Binary Search Tree (or any other kind of search tree) library. It is purely a library for storing data in a hierarchical manner. The caller must know the structure that they wish to build and then use this library to do so; this library will not make those structural decisions for you.

Example Usage

use id_tree::*;

fn main() {
    use id_tree::InsertBehavior::*;

    //      0
    //     / \
    //    1   2
    //   / \
    //  3   4
    let mut tree: Tree<i32> = TreeBuilder::new()
        .with_node_capacity(5)
        .build();

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

    println!("Pre-order:");
    for node in tree.traverse_pre_order(&root_id).unwrap() {
        print!("{}, ", node.data());
    }
    // results in the output "0, 1, 3, 4, 2, "
}

Project Goals

• Allow caller control of as many allocations as possible (through pre-allocation)
• Fast Node insertion and removal
• Arbitrary Tree structure creation and manipulation

Non-Goals

• Arbitrary Graph structure creation and manipulation
• Comparison-based node insertion of any kind

Drawbacks of this Library

Sadly, Rust’s ownership/reference system is sidestepped a bit by this implementation and this can cause issues if the caller doesn’t pay attention to what they are doing with NodeIds.

We try to solve these issues with very careful usage of NodeIds so that the caller doesn’t have to be bothered (too much) with these concerns.

Please see the Potential NodeId Issues section of the NodeId documentation for more info on what these issues are and how this library attempts to solve them.

Structs

AncestorIds

An Iterator over the ancestors of a Node.

Ancestors

An Iterator over the ancestors of a Node.

Children

An Iterator over the children of a Node.

ChildrenIds

An Iterator over the children of a Node.

LevelOrderTraversal

An Iterator over the sub-tree relative to a given Node.

LevelOrderTraversalIds

An Iterator over the sub-tree relative to a given Node.

Node

A container that wraps data in a given Tree.

NodeBuilder

A Node builder that provides more control over how a Node is created.

NodeId

An identifier used to differentiate between Nodes within a Tree.

PostOrderTraversal

An Iterator over the sub-tree relative to a given Node.

PostOrderTraversalIds

An Iterator over the sub-tree relative to a given Node.

PreOrderTraversal

An Iterator over the sub-tree relative to a given Node.

PreOrderTraversalIds

An Iterator over the sub-tree relative to a given Node.

Tree

A tree structure consisting of Nodes.

TreeBuilder

A Tree builder that provides more control over how a Tree is created.

Enums

InsertBehavior

Describes the possible behaviors of the Tree::insert method.

MoveBehavior

Describes the possible behaviors of the Tree::move_node method.

NodeIdError

Enum for all of the possible NodeId errors that could occur.

RemoveBehavior

Describes the possible behaviors of the Tree::remove_node method.

SwapBehavior

Describes the possible behaviors of the Tree::swap_nodes method.