Struct Arena

Source

pub struct Arena<T> { /* private fields */ }

Expand description

A struct that provides the arena allocator.

Implementations§

Source §

impl<T> Arena<T>

Source

pub fn new() -> Self

Initializes a new Arena<T>.

Source

pub fn is_empty(&self) -> bool

Returns true if the arena is empty.

§Examples:

use atree::Arena;

let mut arena = Arena::default();
assert!(arena.is_empty());

let root_data = 1usize;
arena.new_node(root_data);
assert!(!arena.is_empty());

Source

pub fn node_count(&self) -> usize

Counts the number of nodes currently in the arena.

§Examples:

use atree::Arena;

let root_data = 1usize;
let (mut arena, root_token) = Arena::with_data(root_data);
assert_eq!(arena.node_count(), 1);

let next_node_token = root_token.append(&mut arena, 2usize);
assert_eq!(arena.node_count(), 2);

next_node_token.append(&mut arena, 3usize);
assert_eq!(arena.node_count(), 3);

Source

pub fn capacity(&self) -> usize

Returns the number of nodes the tree can hold without reallocating.

Source

pub fn with_data(data: T) -> (Self, Token)

Initializes arena and initializes a new tree with the given data at the root node.

§Examples:

use atree::Arena;

let root_data = 1usize;
let (mut arena, root_token) = Arena::with_data(root_data);
assert_eq!(arena[root_token].data, 1);

Source

pub fn new_node(&mut self, data: T) -> Token

Creates a new free node in the given arena.

§Examples:

use atree::Arena;

let mut arena = Arena::default();
assert!(arena.is_empty());

let root_data = 1usize;
arena.new_node(root_data);
assert!(!arena.is_empty());

Source

pub fn get(&self, indx: Token) -> Option<&Node<T>>

Gets a reference to a node in the arena.

§Examples:

use atree::Arena;

let root_data = 1usize;
let (mut arena, root_token) = Arena::with_data(root_data);
let next_node_token = root_token.append(&mut arena, 2usize);

// get the node we just inserted
let next_node = arena.get(next_node_token).unwrap();
assert_eq!(next_node.data, 2);

Source

pub fn get_mut(&mut self, indx: Token) -> Option<&mut Node<T>>

Gets a mutable reference to a node in the arena.

§Examples:

use atree::Arena;

let root_data = 1usize;
let (mut arena, root_token) = Arena::with_data(root_data);
let next_node_token = root_token.append(&mut arena, 2usize);

// get the node we just inserted
let next_node = arena.get_mut(next_node_token).unwrap();
// mutate the data as you wish
next_node.data = 10;

Source

pub fn remove(&mut self, token: Token) -> Vec<Token>

Removes the given node from the arena and returns the tokens of its children. Use uproot instead if you no longer need the descendants of the node such that the freed memory could be reused.

§Panics:

Panics if the token does not correspond to a node in the arena.

§Examples:

use atree::Arena;
use atree::iter::TraversalOrder;

// root node that we will attach subtrees to
let root_data = "Indo-European";
let (mut arena, root) = Arena::with_data(root_data);

// the Germanic branch
let germanic = root.append(&mut arena, "Germanic");
let west = germanic.append(&mut arena, "West");
let scots = west.append(&mut arena, "Scots");
let english = west.append(&mut arena, "English");

// detach the west branch from the main tree
let west_children = arena.remove(west);

// the west branch is gone from the original tree
let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    .map(|x| x.data);
assert_eq!(iter.next(), Some("Indo-European"));
assert_eq!(iter.next(), Some("Germanic"));
assert!(iter.next().is_none());

// its children are still areound
let mut iter = west_children.iter().map(|&t| arena[t].data);
assert_eq!(iter.next(), Some("Scots"));
assert_eq!(iter.next(), Some("English"));
assert!(iter.next().is_none());

Source

pub fn uproot(&mut self, token: Token)

Removes the given node along with all its descendants. If you only wanted to remove the node while keeping its children, use remove instead.

§Panics:

Panics if the token does not correspond to a node in the arena.

§Examples:

use atree::Arena;
use atree::iter::TraversalOrder;

let root_data = 1usize;
let (mut arena, root_token) = Arena::with_data(root_data);

let next_node = root_token.append(&mut arena, 2usize);
let nnext_node1 = next_node.append(&mut arena, 3usize);
let nnext_node2 = next_node.append(&mut arena, 4usize);
 
arena.uproot(next_node);
let mut iter = root_token.subtree_tokens(&arena, TraversalOrder::Pre);
assert_eq!(iter.next(), Some(root_token));
assert!(iter.next().is_none());
assert_eq!(arena.node_count(), 1);  // only the root node is left

Source §

impl<T> Arena<T>
where T: Clone,

Source

pub fn split_at(&mut self, token: Token) -> (Self, Token)
where T: Clone,

Moves subtree with the root at the given node into its own arena. To detach a given subtree root node from a tree into its own while remaining in the same arena, use detach instead.

§Panics:

Panics if the token does not correspond to a node in the arena.

§Examples:

use atree::Arena;
use atree::iter::TraversalOrder;

let root_data = "a0";
let (mut arena1, root1) = Arena::with_data(root_data);

let node1 = root1.append(&mut arena1, "a1");
let node2 = root1.append(&mut arena1, "b1");
let grandchild1 = node1.append(&mut arena1, "a2");
let grandchild2 = node2.append(&mut arena1, "b2");

// split tree
let (arena2, root2) = arena1.split_at(node2);

let arena1_elt: Vec<_> = root1.subtree(&arena1, TraversalOrder::Pre)
    .map(|x| x.data).collect();
let arena2_elt: Vec<_> = root2.subtree(&arena2, TraversalOrder::Pre)
    .map(|x| x.data).collect();

assert_eq!(&["a0", "a1", "a2"], &arena1_elt[..]);
assert_eq!(&["b1", "b2"], &arena2_elt[..]);

Source

pub fn copy_and_append_subtree( &mut self, self_token: Token, other_tree: &Arena<T>, other_token: Token, )

Copies a sub-tree from one arena and append to the given node of another. It does so by walking the tree and copying node by node to the target arena. Potentially expensive operation.

§Panics:

Panics if the token does not correspond to a node in the arena.

§Examples:

use atree::Arena;
use atree::iter::TraversalOrder;

let root_data = "John";
let (mut arena1, root_token) = Arena::with_data(root_data);

let node1 = root_token.append(&mut arena1, "Juan");
let node2 = root_token.append(&mut arena1, "Giovanni");
let grandchild1 = node1.append(&mut arena1, "Ivan");
let grandchild2 = node2.append(&mut arena1, "Johann");

// new arena
let mut arena2 = arena1.clone();

// append "node1" from tree2 under "node2" in tree1
arena1.copy_and_append_subtree(node2, &arena2, node1);
let mut subtree = node2.subtree(&arena1, TraversalOrder::Pre);

assert_eq!(subtree.next().unwrap().data, "Giovanni");
assert_eq!(subtree.next().unwrap().data, "Johann");
assert_eq!(subtree.next().unwrap().data, "Juan");
assert_eq!(subtree.next().unwrap().data, "Ivan");
assert!(subtree.next().is_none());