causal-agent / ego-tree

Vec-backed ID-tree

Ego Tree

ego-tree is a Rust crate that provides a Vec-backed ID-tree implementation. It offers a flexible and efficient way to create and manipulate tree structures in Rust, with a focus on performance and ease of use.

ego-tree is on Crates.io and GitHub.

Design Philosophy

The design of ego-tree is centered around the following principles:

1. Efficiency: The tree structure is backed by a Vec, allowing for fast, cache-friendly operations and efficient memory usage.

2. Flexibility: Nodes can have any number of children, allowing for the representation of various tree structures.

3. Stability: Node references remain valid even after modifying the tree structure, thanks to the use of stable NodeId indices.

4. Safety: The API is designed to prevent common errors, such as creating cycles or detaching the root node.

5. Ergonomics: The crate provides both low-level operations and high-level conveniences like the tree! macro for easy tree construction.

Key Design Choices

Vec-Backed Structure

Unlike traditional pointer-based trees, ego-tree uses a Vec to store all nodes. This design choice offers several advantages:

• Improved cache locality, potentially leading to better performance
• Simplified memory management
• Easier serialization and deserialization
• Constant-time access to any node by its ID

Node IDs

Nodes are identified by NodeIds, which are wrappers around indices into the underlying Vec. This approach allows for:

• Stable references to nodes, even as the tree structure changes
• Efficient node lookup (O(1) time complexity)
• Compact representation of relationships between nodes

Immutable and Mutable Node References

The crate provides both NodeRef (immutable) and NodeMut (mutable) types for working with nodes. This separation allows for:

• Clear distinction between read-only and modifying operations
• Prevention of multiple mutable references to the same node, enforcing Rust's borrowing rules
• Efficient implementation of various tree traversal iterators

Orphan Nodes

Nodes can be detached from the tree but not removed entirely. This design choice:

• Simplifies certain tree manipulation algorithms
• Allows for temporary detachment and reattachment of subtrees
• Maintains the validity of NodeIds, even for detached nodes

Rich Iterator Support

The crate provides a variety of iterator types for traversing the tree in different ways. This design:

• Allows for efficient and idiomatic tree traversal
• Supports various algorithms and use cases without sacrificing performance
• Leverages Rust's powerful iterator ecosystem

Use Cases

ego-tree is well-suited for applications that require:

• Efficient representation and manipulation of hierarchical data structures
• Frequent traversal and modification of tree structures
• Stable references to tree nodes across operations
• Serialization and deserialization of tree structures

Some potential use cases include:

• DOM-like structures for document processing
• File system representations
• Organizational hierarchies
• Game scene graphs
• Abstract syntax trees for compilers or interpreters

Getting Started

Add this to your Cargo.toml:

[dependencies]
ego-tree = "0.6.2"

Basic usage:

use ego_tree::Tree;

let mut tree = Tree::new(1);
let mut root = tree.root_mut();
root.append(2);
let mut child = root.append(3);
child.append(4);
child.append(5);

For more detailed usage examples and API documentation, please refer to the documentation.

License

This project is licensed under the ISC License.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Credits

ego-tree is created and maintained by the team of rust-scraper.