Swedish for "forest". A pure rust implementation of Adobe's stlab::forest data structure.
A "forest" is a tree-like data structure. From Adobe stlab's forest tutorial:
A forest is a node-based (bidirectional) data structure for the representation of a hierarchy. The parent/child relationship between the nodes is maintained in the container class, so any regular type can be stored within without affecting it. It is equipped with a host of powerful iterators for varied methods of traversing the hierarchy, each of which is described below.
The tutorial itself provides a good explanation of basic usage and fellow author Foster Brereton's introductory article is a great insight into the structure of the forest data structure.
In particular, the forest data structure is a great tool for serializing
tree-like data. The dirs
example provides a simple demonstration of this:
Clone Adobe's stlab repository:
git clone https://github.com/stlab/libraries.git
cd libraries
Run dirs
against the repository:
cargo run --example dirs -- $PWD/stlab
Which prints the directory structure as xml:
<stlab>
<cmake>
<stlab>
<coroutines>
</coroutines>
<development>
</development>
</stlab>
</cmake>
<stlab>
<concurrency>
</concurrency>
<algorithm>
</algorithm>
<test>
</test>
<iterator>
</iterator>
</stlab>
<test>
</test>
</stlab>
Because of Rust's stricter ownership model, a direct translation of C++'s iterators can not safely be exposed. Instead, this crate takes the same approach as proposed for Rust's LinkedList and introduces "cursor" types.
Unlike Rust's iterators, it can freely move back-and-forth and sits between two nodes in the forest. Furthermore, it also tracks the "edge" of the node and therefore have similar semantics as C++ forest's iterators.
This is a very early release, and a lot of more tests are necessary.
Compared to the original C++ version, the API has also been very much trimmed to the bare essentials, primarily because of the challenge introduced by Rust's ownership model. But rather than exposing a highly experimental API with high chance of changing in the future, I've chosen to release a smaller but more stable API that I don't expect to change even after 1.0 release.
At current state, the only API change I expect in the future is to change
size
's self
parameter from a mutable reference to an immutable reference.
It is currently a mutable reference so that this implementation can be the same
as the C++ implementation which mutates the inner size
member if it's
detected to be out of date.