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
sourceimpl<T> VecTree<T>
impl<T> VecTree<T>
sourcepub fn new() -> VecTree<T>
pub fn new() -> VecTree<T>
Constructs a new, empty VecTree
.
Examples
use vec_tree::VecTree;
let mut tree = VecTree::<usize>::new();
sourcepub fn with_capacity(n: usize) -> VecTree<T>
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());
sourcepub fn try_insert(&mut self, data: T, parent_id: Index) -> Result<Index, T>
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);
}
};
sourcepub fn insert(&mut self, data: T, parent_id: Index) -> Index
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);
sourcepub fn try_insert_root(&mut self, data: T) -> Result<Index, T>
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);
}
};
sourcepub fn insert_root(&mut self, data: T) -> Index
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);
sourcepub fn remove(&mut self, node_id: Index) -> Option<T>
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);
sourcepub fn contains(&self, node_id: Index) -> bool
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)
sourcepub fn get(&self, node_id: Index) -> Option<&T>
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());
sourcepub fn get_mut(&mut self, node_id: Index) -> Option<&mut T>
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());
sourcepub fn get_root_index(&self) -> Option<Index>
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);
sourcepub fn capacity(&self) -> usize
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);
sourcepub fn clear(&mut self)
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);
sourcepub fn parent(&self, node_id: Index) -> Option<Index>
pub fn parent(&self, node_id: Index) -> Option<Index>
Return an iterator of references to this node’s parent.
sourcepub fn children(&self, node_id: Index) -> ChildrenIter<'_, T> ⓘ
pub fn children(&self, node_id: Index) -> ChildrenIter<'_, T> ⓘ
Return an iterator of references to this node’s children.
sourcepub fn preceding_siblings(&self, node_id: Index) -> PrecedingSiblingsIter<'_, T> ⓘ
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.
sourcepub fn following_siblings(&self, node_id: Index) -> FollowingSiblingsIter<'_, T> ⓘ
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.
sourcepub fn ancestors(&self, node_id: Index) -> AncestorsIter<'_, T> ⓘ
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.
sourcepub fn descendants(&self, node_id: Index) -> DescendantsIter<'_, T> ⓘ
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.
sourcepub fn descendants_with_depth(
&self,
node_id: Index
) -> DescendantsWithDepthIter<'_, T> ⓘ
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.