Module grove::trees

The trees module. This module contains:

• Traits that all implementations of trees should implement
• Specific implementations of trees

The SomeWalker trait implements traversing a tree. This includes dealing with the borrow checking problems of recursive structures (using recursive_reference), and rebalancing the tree. Therefore, walkers can’t guarantee that the tree won’t change as you walk through them.

Modules

avl

Implementation of AVL trees. Balanced by keeping track of node ranks, this is a worst-case balancing Algorithm that has a small memory overhead per node.

basic_tree

The basic tree module. This module implements basic unbalanced trees.

slice

A convenience struct that represents a specific segment of a tree.

splay

An implementation of a splay tree

treap

Implementation of treaps

Enums

Side

Used to specify sidedness

Traits

ConcatenableTree

Trait for trees that can concatenate. I wanted this to be the same trait family as SplittableWalker, but the current rustc type solver didn’t let me. It’s enough to only implement any one of the three methods - they’re all implemented in terms of each other.

ModifiableTreeRef

Trait for trees that can be modified, i.e., values can be inserted and deleted.

ModifiableWalker

This is a trait for walkers that allow inserting and deleting values.

SomeEntry

Methods that ask to read the contents of the current tree/subtree. These methods are common to the trees themselves and to the walkers.

SomeTree

This trait is the top-level trait that the different trees implement. Every tree that implements this trait can be used directly by the functions immediately in this trait. More advanced use can be achieved by using walkers, which must be implemented.

SomeTreeRef

This is a workaround for not having Generic Associated Types in Rust yet. Really, the type Self::Walker should have been defined in SomeTree and should have been generic in a lifetime parameter.

SomeWalker

The Walker trait implements walking through a tree. This includes dealing with the borrow checking problems of recursive structures (using Telescope), and rebalancing the tree. Therefore, walkers can’t guarantee that the tree won’t change as you walk through them.

SplittableTreeRef

Trait for trees that can be split and concatenated. Require this kind of tree if you want to use reversal actions on segments of your tree.

SplittableWalker

Walkers that can split a tree into two.