skog

Swedish for "forest". A pure rust implementation of Adobe's stlab::forest data structure.

Introduction

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>

Cursors

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.

Status

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.