Struct vec_tree::VecTree

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

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

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

Implementations

impl<T> VecTree<T>

pub fn new() -> VecTree<T>

Constructs a new, empty VecTree.

Examples

use vec_tree::VecTree;

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

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());

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);

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);
    }
};

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);

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);
    }
};

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);

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);

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));

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

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());

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());

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);

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);

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);

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

Return an iterator of references to this node’s parent.

pub fn children(&self, node_id: Index) -> ChildrenIter<'_, T>

Return an iterator of references to this node’s children.

pub fn preceding_siblings(&self, node_id: Index) -> PrecedingSiblingsIter<'_, T>

Return an iterator of references to this node and the siblings before it.

Call .next().unwrap() once on the iterator to skip the node itself.

pub fn following_siblings(&self, node_id: Index) -> FollowingSiblingsIter<'_, T>

Return an iterator of references to this node and the siblings after it.

Call .next().unwrap() once on the iterator to skip the node itself.

pub fn ancestors(&self, node_id: Index) -> AncestorsIter<'_, T>

Return an iterator of references to this node and its ancestors.

Call .next().unwrap() once on the iterator to skip the node itself.

pub fn descendants(&self, node_id: Index) -> DescendantsIter<'_, T>

Return an iterator of references to this node and its descendants, in tree order.

Parent nodes appear before the descendants. Call .next().unwrap() once on the iterator to skip the node itself.

pub fn descendants_with_depth(
    &self,
    node_id: Index
) -> DescendantsWithDepthIter<'_, T>

Return an iterator of references to this node and its descendants, with deoth in the tree, in tree order.

Parent nodes appear before the descendants. Call .next().unwrap() once on the iterator to skip the node itself.

Trait Implementations

impl<T: Clone> Clone for VecTree<T>

fn clone(&self) -> VecTree<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for VecTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for VecTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Index<Index> for VecTree<T>

type Output = T

The returned type after indexing.

fn index(&self, index: Index) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<Index> for VecTree<T>

fn index_mut(&mut self, index: Index) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.