Skip to content

A library for creating and modifying Tree structures.

License

Notifications You must be signed in to change notification settings

Granola-Team/id-tree

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

id_tree

Build Status Build status Coverage Status Docs.rs Crates.io

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

Contributors

About

A library for creating and modifying Tree structures.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Rust 100.0%