Arena based tree structure
An arena based tree structure, backed by a custom allocator (ultimately
built on Vec
) that makes node removal a possibility. On top of the basic
node insertion and removal operations, there are also many kinds of
immutable and mutable iterators provided for various kinds of tree traversal
operations.
Most of the code in the crate is unsafe
free, except for the mutable
iterators, where the unsafe
code is lifted from the core Rust
implementation of IterMut
.
General Guide to the API
The crate consists of three main struct
s: [Arena<T>
], [Token
] and
[Node<T>
]. Arena<T>
provides the arena in which all data is stored.
The data can then be accessed by indexing Arena<T>
with Token
. Node<T>
is a container that encapsulates the data on the tree.
As a general rule of thumb, methods that affect the memory layout such as
splitting and merging arenas, or methods to create and destroy nodes regardless
of existing tree structures like creating a free node, are defined on
Arena<T>
. Methods that alter pre-existing tree structures such as adding
nodes with respect to existing ones ([append
] or [insert_after
] for
instance) or splitting and attaching existing trees are defined on Tokens
.
When it comes to iterating, iterators can be created from methods on both
Token
and Node<T>
. There are two versions of iterators, iterators over
tokens or references to the nodes. Both can be created by methods on Token
and Node<T>
. However, due to the rules of borrow checking, mutable
iterators over the node references are only defined on Token
.
Crate Feature Flags
serde
: support for serde 1.x. Optional feature/dependency.
Usage Examples
The crate consists of three main struct
s: Arena<T>
, Token
and
Node<T>
. Arena<T>
provides the arena in which all data is stored. The
data can then be accessed by indexing Arena<T>
with Token
. Node<T>
is a
container that encapsulates the data on the tree.
We can start by initializing an empty arena and add stuff to it at a later time:
use Arena;
let mut arena = default;
assert!;
// add stuff to the arena when we feel like it
let root_data = "Indo-European";
let root_node_token = arena.new_node;
assert_eq!
Another way is to directly initialize an arena with a node:
use Arena;
let root_data = "Indo-European";
let = with_data;
assert_eq!
To add more data to the tree, call the append
method on the tokens (we can't
do this directly to the nodes because of the limitations of borrow checking).
use Arena;
let root_data = "Indo-European";
let = with_data;
root_token.append;
assert_eq!;
To access/modify existing nodes in the tree, we can use indexing or
get
/get_mut
.
use Arena;
let root_data = "Indo-European";
let = with_data;
// add some more stuff to the tree
let branch1 = root_token.append;
let branch2 = root_token.append;
let branch3 = root_token.append;
let lang1 = branch2.append;
let lang2 = branch2.append;
let lang3 = branch3.append;
// Access data by indexing the arena by a token. This operation panics if the
// token is invalid.
assert_eq!;
// Access data by calling "get" on the arena with a token.
assert_eq!;
// We can also do so mutably (with "get" or through indexing). As you can
// see, calling the "get" functions is more verbose but you get to avoid
// surprise panic attacks (if you don't unwrap like I do here).
arena.get_mut.unwrap.data = "Icelandic";
assert_eq!;
// On the flip side, we can access the corresponding token if we already
// have the node
let branch3_node = &arena;
assert_eq!;
We can iterate over the elements by calling iterators on both the tokens or the
nodes. Check the documentation of Token
or Node<T>
for a list of
iterators. There is a version of each of the iterators that iterates over tokens
instead of node references. See the docs for details.
use Arena;
let root_data = "Indo-European";
let = with_data;
// add some more stuff to the tree
let branch1 = root_token.append;
let branch2 = root_token.append;
let branch3 = root_token.append;
let lang1 = branch2.append;
let lang2 = branch2.append;
let lang3 = branch3.append;
// Getting an iterator from a token and iterate
let children: = root_token.children.map.collect;
assert_eq!;
// Getting an iterator from a node reference (that is if you already have it
// around. To go out of your way to get the node reference before getting
// the iterator seems kind of dumb).
let polish = &arena;
let ancestors: = polish.ancestors.map.collect;
assert_eq!;
// We can also iterate mutably. Unfortunately we can only get mutable
// iterators from the tokens but not from the node references because of
// borrow checking.
for lang in branch2.children_mut
assert_eq!;
assert_eq!;
To remove a single node from the arena, use the remove
method. This will
detach all the children of the node from the tree (but not remove them from
memory).
use Arena;
use TraversalOrder;
// root node that we will attach subtrees to
let root_data = "Indo-European";
let = with_data;
// the Germanic branch
let germanic = root.append;
let west = germanic.append;
let scots = west.append;
let english = west.append;
// detach the west branch from the main tree
let west_children = arena.remove;
// the west branch is gone from the original tree
let mut iter = root.subtree
.map;
assert_eq!;
assert_eq!;
assert!;
// its children are still areound
let mut iter = west_children.iter.map;
assert_eq!;
assert_eq!;
assert!;
To uproot a tree from the arena, call the uproot
method on the arena.
Note that will also remove all descendants of the node. After removal, the
"freed" memory will be reused if and when new data is inserted.
use Arena;
let root_data = "Indo-European";
let = with_data;
// add some more stuff to the tree
let branch1 = root_token.append;
let branch2 = root_token.append;
let branch3 = root_token.append;
let lang1 = branch2.append;
let lang2 = branch2.append;
let lang3 = branch3.append;
assert_eq!;
arena.uproot; // boring languages anyway
assert_eq!;
## License
MIT