Struct VecTree

Source

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

Expand description

The VecTree allows inserting and removing elements that are referred to by Index.

See the module-level documentation for example usage and motivation.

Implementations§

Source §

impl<T> VecTree<T>

Source

pub fn new() -> VecTree<T>

Constructs a new, empty VecTree.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::<usize>::new();

Source

pub fn with_capacity(n: usize) -> VecTree<T>

Constructs a new, empty VecTree<T> with the specified capacity.

The VecTree<T> will be able to hold n elements without further allocation.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::with_capacity(10);
let root = tree.try_insert_root(0).unwrap();

// These insertions will not require further allocation.
for i in 1..10 {
    assert!(tree.try_insert(i, root).is_ok());
}

// But now we are at capacity, and there is no more room.
assert!(tree.try_insert(99, root).is_err());

Source

pub fn reserve(&mut self, additional_capacity: usize)

Allocate space for additional_capacity more elements in the tree.

§Panics

Panics if this causes the capacity to overflow.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::with_capacity(10);
tree.reserve(5);
assert_eq!(tree.capacity(), 15);

Source

pub fn try_insert(&mut self, data: T, parent_id: Index) -> Result<Index, T>

Attempts to insert data into the tree using existing capacity.

This method will never allocate new capacity in the tree.

If insertion succeeds, then the data’s index is returned. If insertion fails, then Err(data) is returned to give ownership of data back to the caller.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();
let root = tree.insert_root(0);

match tree.try_insert(42, root) {
    Ok(idx) => {
        // Insertion succeeded.
        assert_eq!(tree[idx], 42);
    }
    Err(x) => {
        // Insertion failed.
        assert_eq!(x, 42);
    }
};

Source

pub fn insert(&mut self, data: T, parent_id: Index) -> Index

Insert data into the tree, allocating more capacity if necessary.

The data’s associated index in the tree is returned.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::with_capacity(1);
assert_eq!(tree.capacity(), 1);

let root = tree.insert_root(0);

let idx = tree.insert(42, root);
assert_eq!(tree[idx], 42);
assert_eq!(tree.capacity(), 2);

Source

pub fn try_insert_root(&mut self, data: T) -> Result<Index, T>

Attempts to insert data into the tree as root node using existing capacity.

This method will never allocate new capacity in the tree.

If insertion succeeds, then the data’s index is returned. If insertion fails, then Err(data) is returned to give ownership of data back to the caller.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();

match tree.try_insert_root(42) {
    Ok(idx) => {
        // Insertion succeeded.
        assert_eq!(tree[idx], 42);
    }
    Err(x) => {
        // Insertion failed.
        assert_eq!(x, 42);
    }
};

Source

pub fn insert_root(&mut self, data: T) -> Index

Insert data into the tree as a root node, allocating more capacity if necessary.

The data’s associated index in the tree is returned.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::with_capacity(1);
assert_eq!(tree.capacity(), 1);

let root = tree.insert_root(42);

assert_eq!(tree[root], 42);

Source

pub fn remove(&mut self, node_id: Index) -> Option<T>

Remove the element at index node_id from the tree.

If the element at index node_id is still in the tree, then it is returned. If it is not in the tree, then None is returned.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();
let root = tree.insert_root(42);

assert_eq!(tree.remove(root), Some(42));
assert_eq!(tree.remove(root), None);

Source

pub fn contains(&self, node_id: Index) -> bool

Is the element at index node_id in the tree?

Returns true if the element at node_id is in the tree, false otherwise.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();
let root = tree.insert_root(0);

assert!(tree.contains(root));
tree.remove(root);
assert!(!tree.contains(root));

Source

pub fn append_child(&mut self, node_id: Index, new_child_id: Index)

Source

pub fn get(&self, node_id: Index) -> Option<&T>

Get a shared reference to the element at index node_id if it is in the tree.

If the element at index node_id is not in the tree, then None is returned.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();
let root = tree.insert_root(42);

assert_eq!(tree.get(root), Some(&42));
tree.remove(root);
assert!(tree.get(root).is_none());

Source

pub fn get_mut(&mut self, node_id: Index) -> Option<&mut T>

Get an exclusive reference to the element at index node_id if it is in the tree.

If the element at index node_id is not in the tree, then None is returned.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();
let root = tree.insert_root(42);

*tree.get_mut(root).unwrap() += 1;
assert_eq!(tree.remove(root), Some(43));
assert!(tree.get_mut(root).is_none());

Source

pub fn get_root_index(&self) -> Option<Index>

Get the root node index from the tree.

If no root node is created in the tree, None is returned.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::new();
assert_eq!(tree.get_root_index(), None);

tree.insert_root(42);
let root = tree.get_root_index().unwrap();
assert_eq!(tree[root], 42);

Source

pub fn capacity(&self) -> usize

Get the capacity of this tree.

The capacity is the maximum number of elements the tree can hold without further allocation, including however many it currently contains.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::with_capacity(10);
let root = tree.insert_root(0);

// `try_insert` does not allocate new capacity.
for i in 1..10 {
    assert!(tree.try_insert(i, root).is_ok());
    assert_eq!(tree.capacity(), 10);
}

// But `insert` will if the root is already at capacity.
tree.insert(11, root);
assert!(tree.capacity() > 10);

Source

pub fn clear(&mut self)

Clear all the items inside the tree, but keep its allocation.

§Examples

use vec_tree::VecTree;

let mut tree = VecTree::with_capacity(1);
let root = tree.insert_root(42);
tree.insert(43, root); // The capacity is doubled when reached.

tree.clear();
assert_eq!(tree.capacity(), 2);