Crate id_tree[−][src]
A library for creating and modifying Tree structures.
Overview
In this implementation, the Tree
owns all of the Node
s and all inter-Node
relationships
are managed with NodeId
s.
Tree
s 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
Node
s. In addition, each Node
can have an arbitrary number of child Node
s.
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 NodeId
s.
We try to solve these issues with very careful usage of NodeId
s 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 |
Ancestors | An Iterator over the ancestors of a |
Children | An Iterator over the children of a |
ChildrenIds | An Iterator over the children of a |
LevelOrderTraversal | An Iterator over the sub-tree relative to a given |
LevelOrderTraversalIds | An Iterator over the sub-tree relative to a given |
Node | A container that wraps data in a given |
NodeBuilder | A |
NodeId | An identifier used to differentiate between |
PostOrderTraversal | An Iterator over the sub-tree relative to a given |
PostOrderTraversalIds | An Iterator over the sub-tree relative to a given |
PreOrderTraversal | An Iterator over the sub-tree relative to a given |
PreOrderTraversalIds | An Iterator over the sub-tree relative to a given |
Tree | A tree structure consisting of |
TreeBuilder | A |
Enums
InsertBehavior | Describes the possible behaviors of the |
MoveBehavior | Describes the possible behaviors of the |
NodeIdError | Enum for all of the possible |
RemoveBehavior | Describes the possible behaviors of the |
SwapBehavior | Describes the possible behaviors of the |