Struct charcoal::FreeformTree [−][src]
A freeform tree.
See the module-level documentation for more.
Implementations
impl<B, L, K, S> FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
pub fn new(root: L) -> Self
[src]
freeform_tree
only.Creates a freeform tree with the specified value for the root node.
Example
// The only way to create a tree... let tree = FreeformTree::<_>::new(87); // ...is to simply create the root leaf node and storage. The turbofish there is needed to // state that we are using the default storage method instead of asking the compiler to // infer it, which would be impossible. // No other nodes have been created yet: assert!(tree.root().is_leaf());
pub fn with_capacity(capacity: usize, root: L) -> Self
[src]
freeform_tree
only.Creates a freeform tree with the specified capacity for the storage.
Panics
The storage may panic if it has fixed capacity and the specified value does not match it.
Example
// Let's create a tree, but with some preallocated space for more nodes: let mut tree = FreeformTree::<_>::with_capacity(5, "Variable Names"); // The turbofish there is needed to state that we are using the default storage method // instead of asking the compiler to infer it, which would be impossible. // Capacity does not affect the actual nodes: assert!(tree.root().is_leaf()); // Not until we create them ourselves: tree.root_mut().make_branch([ "Foo", "Bar", "Baz", "Quux", ].iter().copied()); // If the default storage is backed by a dynamic memory allocation, // at most one has happened to this point.
pub fn root(&self) -> NodeRef<'_, B, L, K, S>
[src]
freeform_tree
only.Returns a reference to the root node of the tree.
Example
// A tree always has a root node: let tree = FreeformTree::<_>::new("Root"); assert_eq!( // The into_inner() call extracts data from a NodeValue, which is used to generalize // tres to both work with same and different types for payloads of leaf and branch // nodes. *tree.root().value().into_inner(), "Root", );
pub fn root_mut(&mut self) -> NodeRefMut<'_, B, L, K, S>
[src]
freeform_tree
only.Returns a mutable reference to the root node of the tree, allowing modifications to the entire tree.
Example
// A tree always has a root node: let mut tree = FreeformTree::<_>::new("Root"); let mut root_mut = tree.root_mut(); // The into_inner() call extracts data from a NodeValue, which is used to generalize trees // to both work with same and different types for payloads of leaf and branch nodes. *(root_mut.value_mut().into_inner()) = "The Source of the Beer";
pub fn num_nodes(&self) -> usize
[src]
freeform_tree
only.Returns the number of nodes in the tree.
pub fn capacity(&self) -> usize
[src]
freeform_tree
only.Returns the additional number of nodes which the tree can store without the need to reallocate.
pub fn reserve(&mut self, additional: usize)
[src]
freeform_tree
only.Reserves capacity for at least additional more elements to be inserted in the given storage. The storage may reserve more space to avoid frequent reallocations. After calling reserve
, capacity will be greater than or equal to self.len()
+ additional
. Does nothing if capacity is already sufficient.
pub fn shrink_to_fit(&mut self)
[src]
freeform_tree
only.Shrinks the capacity of the storage as much as possible.
It will drop down as close as possible to the current length, though dynamically allocated storages may not always reallocate exactly as much as it is needed to store all elements and none more.
impl<B, L, S> FreeformTree<B, L, usize, SparseStorage<Node<B, L, usize>, S>> where
S: ListStorage<Element = SparseStorageSlot<Node<B, L, usize>>>,
[src]
S: ListStorage<Element = SparseStorageSlot<Node<B, L, usize>>>,
pub fn defragment(&mut self)
[src]
freeform_tree
only.Removes all holes from the sparse storage.
Under the hood, this uses defragment_and_fix
. It’s not possible to defragment without fixing the indicies, as that might cause undefined behavior.
Example
use charcoal::freeform_tree::SparseVecFreeformTree; // Create a tree which explicitly uses sparse storage: let mut tree = SparseVecFreeformTree::new(0); // This is already the default, but for the sake of this example we'll stay explicit. // Add some elements for the holes to appear: tree.root_mut().make_branch([ 1, 2, 3, 4, 5, ].iter().copied()).unwrap(); // You can replace this with proper error handling tree .root_mut() .first_child_mut() .unwrap() // This too .make_branch([ 6, 7, 8, 9, 10, ].iter().copied()) .unwrap(); // And this tree .root_mut() .first_child_mut() .unwrap() // Same as above .try_remove_children(drop) .unwrap(); // Same here // We ended up creating 5 holes: assert_eq!(tree.num_holes(), 5); // Let's patch them: tree.defragment(); // Now there are none: assert_eq!(tree.num_holes(), 0);
pub fn num_holes(&self) -> usize
[src]
freeform_tree
only.Returns the number of holes in the storage. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.
Example
See the example in defragment
.
pub fn is_dense(&self) -> bool
[src]
freeform_tree
only.Returns true
if there are no holes in the storage, false
otherwise. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.
Example
See the example in defragment
.
Trait Implementations
impl<B: Clone, L: Clone, K: Clone, S: Clone> Clone for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.fn clone(&self) -> FreeformTree<B, L, K, S>
[src]
pub fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<B: Copy, L: Copy, K: Copy, S: Copy> Copy for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.impl<B: Debug, L: Debug, K: Debug, S: Debug> Debug for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.impl<B, L, K, S> Default for FreeformTree<B, L, K, S> where
L: Default,
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
L: Default,
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.impl<B: Eq, L: Eq, K: Eq, S: Eq> Eq for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.impl<B: Hash, L: Hash, K: Hash, S: Hash> Hash for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.fn hash<__H: Hasher>(&self, state: &mut __H)
[src]
pub fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<B: PartialEq, L: PartialEq, K: PartialEq, S: PartialEq> PartialEq<FreeformTree<B, L, K, S>> for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.fn eq(&self, other: &FreeformTree<B, L, K, S>) -> bool
[src]
fn ne(&self, other: &FreeformTree<B, L, K, S>) -> bool
[src]
impl<B, L, K, S> StructuralEq for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.impl<B, L, K, S> StructuralPartialEq for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.impl<B, L, K, S> Traversable for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.type Leaf = L
The payload of the node if it’s a leaf node.
type Branch = B
The payload of the node if it’s a branch node.
type Cursor = K
The type for the cursor which will be used for keeping track of the traversed nodes. Read more
fn advance_cursor<V>(
&self,
cursor: Self::Cursor,
direction: VisitorDirection<Self::Cursor, V>
) -> CursorResult<Self::Cursor>
[src]
&self,
cursor: Self::Cursor,
direction: VisitorDirection<Self::Cursor, V>
) -> CursorResult<Self::Cursor>
fn cursor_to_root(&self) -> Self::Cursor
[src]
fn value_of(
&self,
cursor: &Self::Cursor
) -> NodeValue<&Self::Branch, &Self::Leaf>
[src]
&self,
cursor: &Self::Cursor
) -> NodeValue<&Self::Branch, &Self::Leaf>
fn parent_of(&self, cursor: &Self::Cursor) -> Option<Self::Cursor>
[src]
fn num_children_of(&self, cursor: &Self::Cursor) -> usize
[src]
fn nth_child_of(
&self,
cursor: &Self::Cursor,
child_num: usize
) -> Option<Self::Cursor>
[src]
&self,
cursor: &Self::Cursor,
child_num: usize
) -> Option<Self::Cursor>
fn step<V>(
&self,
visitor: V,
cursor: CursorResult<Self::Cursor>
) -> Step<Self::Cursor, V::Output> where
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
[src]
&self,
visitor: V,
cursor: CursorResult<Self::Cursor>
) -> Step<Self::Cursor, V::Output> where
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
fn traverse<V>(&self, visitor: V) -> V::Output where
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
[src]
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
fn traverse_from<V>(
&self,
starting_cursor: Self::Cursor,
visitor: V
) -> V::Output where
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
[src]
&self,
starting_cursor: Self::Cursor,
visitor: V
) -> V::Output where
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
impl<B, L, K, S> TraversableMut for FreeformTree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
freeform_tree
only.const CAN_REMOVE_INDIVIDUAL_CHILDREN: bool
[src]
type PackedChildren = Empty<L>
A container for the leaf children of a branch node.
fn value_mut_of(
&mut self,
cursor: &Self::Cursor
) -> NodeValue<&mut Self::Branch, &mut Self::Leaf>
[src]
&mut self,
cursor: &Self::Cursor
) -> NodeValue<&mut Self::Branch, &mut Self::Leaf>
fn try_remove_leaf<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL
) -> Result<Self::Leaf, TryRemoveLeafError>
[src]
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL
) -> Result<Self::Leaf, TryRemoveLeafError>
fn try_remove_branch_into<BtL: FnOnce(Self::Branch) -> Self::Leaf, C: FnMut(Self::Leaf)>(
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL,
collector: C
) -> Result<Self::Branch, TryRemoveBranchError>
[src]
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL,
collector: C
) -> Result<Self::Branch, TryRemoveBranchError>
fn try_remove_children_into<BtL: FnOnce(Self::Branch) -> Self::Leaf, C: FnMut(Self::Leaf)>(
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL,
collector: C
) -> Result<(), TryRemoveChildrenError>
[src]
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL,
collector: C
) -> Result<(), TryRemoveChildrenError>
const CAN_PACK_CHILDREN: bool
[src]
fn try_remove_branch<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<(Self::Branch, Self::PackedChildren), TryRemoveBranchError>
[src]
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<(Self::Branch, Self::PackedChildren), TryRemoveBranchError>
fn try_remove_children<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<Self::PackedChildren, TryRemoveChildrenError>
[src]
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<Self::PackedChildren, TryRemoveChildrenError>
fn step_mut<V: VisitorMut>(
&mut self,
visitor: V,
cursor: CursorResult<Self::Cursor>
) -> Step<Self::Cursor, V::Output> where
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
[src]
&mut self,
visitor: V,
cursor: CursorResult<Self::Cursor>
) -> Step<Self::Cursor, V::Output> where
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
fn traverse_mut<V: VisitorMut>(&mut self, visitor: V) -> V::Output where
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
[src]
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
fn traverse_mut_from<V: VisitorMut>(
&mut self,
starting_cursor: Self::Cursor,
visitor: V
) -> V::Output where
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
[src]
&mut self,
starting_cursor: Self::Cursor,
visitor: V
) -> V::Output where
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
Auto Trait Implementations
impl<B, L, K, S> RefUnwindSafe for FreeformTree<B, L, K, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
K: RefUnwindSafe,
S: RefUnwindSafe,
impl<B, L, K, S> Send for FreeformTree<B, L, K, S> where
K: Send,
S: Send,
K: Send,
S: Send,
impl<B, L, K, S> Sync for FreeformTree<B, L, K, S> where
K: Sync,
S: Sync,
K: Sync,
S: Sync,
impl<B, L, K, S> Unpin for FreeformTree<B, L, K, S> where
K: Unpin,
S: Unpin,
K: Unpin,
S: Unpin,
impl<B, L, K, S> UnwindSafe for FreeformTree<B, L, K, S> where
K: UnwindSafe,
S: UnwindSafe,
K: UnwindSafe,
S: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Slottable for T where
T: Copy,
[src]
T: Copy,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,