Crates.io | tree-ds |
lib.rs | tree-ds |
version | 0.1.5 |
source | src |
created_at | 2024-05-17 05:30:50.391836 |
updated_at | 2024-07-09 01:48:04.071378 |
description | A library to manipulate tree data structures. |
homepage | |
repository | https://github.com/clementwanjau/tree-ds |
max_upload_size | |
id | 1242841 |
size | 157,546 |
This library provides a tree data structure that can be used to represent hierarchical data in Rust. The library allows you to perform the following operations on a tree:
There are many crates that make tree data structures available in Rust, but this library is unique in that it provides a tree data structure that is feature rich, easy to use and has a simple API. The library is also well-documented and has a comprehensive test suite that ensures that it works as expected. Most importantly, the library is designed to be fast and efficient, making it suitable for use in performance-critical applications.
Add the following to your Cargo.toml
file:
[dependencies]
tree-ds = "0.1"
The basic building block of the library is the Node
struct. The Node
struct
is a generic struct that can hold any type of data. The Node
struct can be created
as follows:
use tree_ds::prelude::*;
let node: Node<String, i32> = Node::new("Root Node".to_string(), Some(100));
Optionally the crate provides an auto_id
feature to automatically generate an id
for the node. This is useful when you are not concerned with the id of the node, and
you want to avoid the overhead of managing the Ids. To enable the auto_id
feature, add the following to your Cargo.toml
file:
[dependencies]
tree-ds = { version = "0.1", features = ["auto_id"] }
Then you can create a node as follows:
use tree_ds::prelude::*;
// Not that in this case, the `Q` type parameter should be of type `AutomatedId` or any other type that implements the `From<u128>` trait.
let node: Node<AutomatedId, &str> = Node::new_with_auto_id(Some("Some Node Value"));
Note: The node id generated in the
no_std
environment may not be unique across serializations and deserializations and disk persistence. This is because theno_std
environment does not have access to thestd::time
module to generate unique ids. Instead it uses theSimpleGenerator
from thesequential_gen
crate to generate unique ids.
The Tree
struct is the main struct that is used to represent a tree. The Tree
struct is generic over the type of data that the nodes in the tree hold. The Tree
struct can be created as follows:
use tree_ds::prelude::*;
let mut tree: Tree<String, i32> = Tree::new(Some("The Tree Name"));
// Proceed to build the tree by adding nodes to it.
A crude example of how to use the library is shown below:
use tree_ds::prelude::{Node, NodeRemovalStrategy, Result, Tree};
fn main() -> Result<()> {
let mut tree = Tree::new(Some("Finances Tree"));
let root = tree.add_node(Node::new("Risk".to_string(), Some(5000)), None)?;
let fixed_income_node = tree.add_node(Node::new("Fixed Income".to_string(), Some(2000)), Some(&root))?;
let equity_node = tree.add_node(Node::new("Equity".to_string(), Some(3000)), Some(&root))?;
let debt_node = tree.add_node(Node::new("Debt".to_string(), Some(1000)), Some(&fixed_income_node))?;
let mutual_funds_node = tree.add_node(Node::new("Mutual Funds".to_string(), Some(1000)), Some(&equity_node))?;
let stocks_node = tree.add_node(Node::new("Stocks".to_string(), Some(2000)), Some(&equity_node))?;
tree.add_node(Node::new("Debt Mutual Funds".to_string(), Some(500)), Some(&debt_node))?;
tree.add_node(Node::new("Equity Mutual Funds".to_string(), Some(500)), Some(&mutual_funds_node))?;
tree.add_node(Node::new("Large Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
tree.add_node(Node::new("Mid Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
tree.add_node(Node::new("Small Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
println!("{}", tree);
tree.remove_node(&stocks_node, NodeRemovalStrategy::RemoveNodeAndChildren)?;
println!("After Removing The Stocks Node");
println!("*******************");
println!("{}", tree);
let equity_sub_tree = tree.get_subtree(&equity_node, None)?;
println!("{}", equity_sub_tree);
Ok(())
}
This will output:
Finances Tree
*************
Risk: 5000
├── Fixed Income: 2000
│ └── Debt: 1000
│ └── Debt Mutual Funds: 500
└── Equity: 3000
├── Mutual Funds: 1000
│ └── Equity Mutual Funds: 500
└── Stocks: 2000
├── Large Cap Stocks: 1000
├── Mid Cap Stocks: 1000
└── Small Cap Stocks: 1000
After Removing The Stocks Node
*******************
Finances Tree
*************
Risk: 5000
├── Fixed Income: 2000
│ └── Debt: 1000
│ └── Debt Mutual Funds: 500
└── Equity: 3000
└── Mutual Funds: 1000
└── Equity Mutual Funds: 500
Equity
******
Equity: 3000
└── Mutual Funds: 1000
└── Equity Mutual Funds: 500
You can traverse the tree using the traverse
method. The traverse
method
returns an iterator that allows you to traverse the tree in any order you want.
The following example shows how to traverse the tree in a pre-order fashion:
use tree_ds::prelude::{Node, Result, Tree, TraversalStrategy};
fn main() -> Result<()> {
let mut tree = Tree::new(None);
let node_1 = tree.add_node(Node::new(1, Some(2)), None)?;
let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1))?;
let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_1))?;
let node_4 = tree.add_node(Node::new(4, Some(5)), Some(&node_2))?;
let node_5 = tree.add_node(Node::new(5, Some(6)), Some(&node_2))?;
let node_6 = tree.add_node(Node::new(6, Some(7)), Some(&node_3))?;
let preorder_nodes = tree.traverse(&node_1, TraversalStrategy::PreOrder)?;
let expected_preorder = vec![node_1, node_2, node_4, node_5, node_3, node_6];
assert_eq!(preorder_nodes, expected_preorder);
let in_order_nodes = tree.traverse(&node_1, TraversalStrategy::InOrder)?;
let expected_in_order = vec![node_4, node_2, node_5, node_1, node_3, node_6];
assert_eq!(in_order_nodes, expected_in_order);
let post_order_nodes = tree.traverse(&node_1, TraversalStrategy::PostOrder)?;
let expected_post_order = vec![node_4, node_5, node_2, node_6, node_3, node_1];
assert_eq!(post_order_nodes, expected_post_order);
Ok(())
}
You can also perform an action on the nodes while traversing the tree on the iterator returned by the traverse
method.
The following example shows how to traverse the tree in a pre-order fashion and perform an action on the nodes:
let nodes = tree.traverse(&node_id, TraversalStrategy::PreOrder)?
.iter()
.map(|node| {
println!("{}", node);
node
})
.collect::<Vec<_>>();
no_std
EnvironmentThis crate supports no_std
environments. To use this crate in a no_std
environment, you need to enable the no_std
feature. You can do this by adding the following to your Cargo.toml
file:
[dependencies]
tree-ds = { version = "0.1", features = ["no_std"] }
All the other features are also equally supported in the no_std
environment.
This project is licensed under the MIT License - see the LICENSE file for details.
Check the CHANGELOG for the latest changes.