Crate libtree

libtree : a crate for game tree

libtree is a crate that implements trees in Rust, taking huge inspirations from Rust with too many linked lists (so it is as useless and stupid as it’s inspiration). The main purpose of this crate was to implements tree for game tree needed in a crate for game theory.

Nomenclature

Just a bit of nomemclature to be make my documentation slighty more readable.

• a node is a set of pointers (one for the father and another collection for the childs) and also stores an element, often abbreviated into elem or el.
• a tree is composed of two pointers towards nodes :
  • ‘current’, where you are in the tree.
  • ‘root’, explicit.
• the subtree will designates the tree that is rooted at ‘current’ in a tree.
• a cursor is another pointer to a node of the tree, but without a root associated.

Showcase

Creation and adding elements

libtree provides the Tree structure to create a store a tree, and add new element to it.

use libtree::Tree;
let mut tree = Tree::from_element(1);
tree.push(2);

Navigation

By navigation, we mean moving around ‘current’ in the tree. But as the term move has already a signication in Rust, we use the term navigation in this crate. Tree supports three type of navigation :

• navigate_to(idx) which navigates ‘current’ to its idx child (if possible).
• ascend() which navigates ‘current’ to its father (if possible i.e. not at ‘root’).
• go_to_root() which navigates ‘current’ to ‘root’.

assert_eq!(tree.peek(), &1);
tree.navigate_to(0);
assert_eq!(tree.peek(), &2);
tree.push(3);
tree.ascend();
assert_eq!(tree.into_vec(), vec![1, 2, 3]);

Joining and splitting

Trees can be joined and splitted. Splitting tree is for the moment the best way to drop unwantted part of the tree.

let mut tree1 = Tree::from_element(1);
tree1.push_iter(vec![2, 3]);
let mut tree2 = Tree::from_element(4);
tree2.push_iter(vec![5, 6]);
tree1.join(tree2, 0);
// exploration is always made in depth first way
assert_eq!(tree1.iter().collect::<Vec<&i32>>(), vec![&1, &4, &5, &6, &2, &3]);
let mut tree2 = tree1.split(0);
assert_eq!(tree2.into_vec(), vec![4, 5, 6]);

Cursors

Cursors are of three differents types and allows concurrent exploration of the tree.

let mut cursor1 = tree1.cursor();
let cursor2 = tree1.cursor();
cursor1.navigate_to(1);
assert_eq!(cursor1.peek(), &3);
assert_eq!(cursor2.peek(), &1);

Subtrees

Most exploration methods when called will only explore the subtree rooted as ‘current’ (for a tree or a cursor).

let mut tree = Tree::from_element(1);
tree.push_iter(vec![4, 2, 1]);
tree.navigate_to(0);
tree.push_iter(vec![5, 6]);
assert_eq!(tree.iter().collect::<Vec<&i32>>(), vec![&4, &5, &6]);
let mut cursor = tree.cursor_mut();
cursor.ascend();
cursor.navigate_to(1);
cursor.push(10);
assert_eq!(cursor.iter_mut().collect::<Vec<&mut i32>>(), vec![&mut 2, &mut 10]);

Structs

Cursor

Equivalent of immutable reference for crate::Tree

CursorMut

Equivalent of mutable reference for crate::Tree

Tree

The main structure in this tree crate

UnsafeCursor

An unsafe version of CursorMut