Struct MutCursorRootedVec 

pub struct MutCursorRootedVec<'l, RootT: 'l, NodeT: ?Sized + 'l> { /* private fields */ }

Available on crate feature alloc only.

Similar to MutCursorVec, but provides for a RootT type at the bottom of the stack that is different from the NodeT types above it. This is useful when the bottom of the stack is a container type, or a smart-pointer type such as Rc, Arc, or RefMut.

Usage

This type can own (as opposed to just borrow) the root object from which the rest of the stack descends, however this comes with several complications.

StableDeref Requirement

To ensure moving the MutCursorRootedVec doesn’t invalidate any pointers, you must provide a type that implements DerefMut<Target = NodeT> and the StableDeref marker trait. This can be an intermediate type, and needn’t be RootT itself.

Associated Lifetime

MutCursorRootedVec can be used without an associated lifetime. For API soundness, however, you still must define a “lower bound” for type validity. In many cases you can simply use 'static. This requires RootT: 'static and NodeT: 'static which are validity bounds on the types but these don’t imply that any data must actually live that long at run-time.

To give another example: If RootT is a container type SomeRoot<'a> containing &'a mut NodeT that you want to advance into, you could use MutCursorRootedVec<'a, SomeRoot<'a>, NodeT>.

Additional

MutCursorRootedVec doesn’t implement Deref, and accessors return Option, so therefore it is allowed to be empty, unlike some of the other types in this crate.

MutCursorRootedVec is not available if the alloc feature is disabled. (The feature is enabled by default.)

Examples

For usage with an Rc or Arc, check out the unique module.

The example code below begins traversal from a container (Vec), which implements StableDeref.

let mut tree_vec = vec![TreeNode::new(5)];
let mut node_stack = MutCursorRootedVec::<'static, Vec<TreeNode>, TreeNode>::new(tree_vec);

// Begin traversal from the root
// - The first closure arg provides a reference that is guaranteed to be stable in memory
// - The second closure arg provides a reference to the NodeT to traverse from
node_stack.advance_from_root_twostep(|v| Some(v), |slice_ref| slice_ref.get_mut(0));

// Traverse to the last node
while node_stack.advance(|node| {
    node.traverse()
}) {}

assert_eq!(node_stack.top().unwrap().val, 0);
assert_eq!(node_stack.depth(), 6);

Implementations

impl<'l, RootT: 'l, NodeT: ?Sized + 'l> MutCursorRootedVec<'l, RootT, NodeT>

pub fn new(root: RootT) -> Self

Returns a new MutCursorRootedVec with a reference to the specified root

pub fn new_with_capacity(root: RootT, capacity: usize) -> Self

Returns a new MutCursorRootedVec with a reference to the specified root, and an allocated buffer for capacity references

pub fn is_root(&self) -> bool

Returns true if the stack contains only the root, otherwise returns false if the stack contains one or more node references

pub fn root(&self) -> Option<&RootT>

Returns a const reference from the mutable reference to the root, or None if the stack contains additional nodes obscuring the root

pub fn top(&self) -> Option<&NodeT>

Returns a const reference from the mutable reference on the top of the stack, or None if the stack contains only the root

pub fn root_mut(&mut self) -> Option<&mut RootT>

Returns the mutable reference on the root of the stack, or None if the stack contains additional references obscuring the root

pub fn take_root(&mut self) -> Option<RootT>

Removes and returns the mutable reference on the root of the stack, or None if the root has already been taken

This method effectively dumps the entire stack contents.

pub fn replace_root(&mut self, root: RootT)

Replaces the root of the stack with the provided value

Panics if the stack contains any references above the root

pub fn top_mut(&mut self) -> Option<&mut NodeT>

Returns the mutable reference on the top of the stack, or None if the stack contains only the root

pub fn top_or_advance_mut<F, NodeRef>(&mut self, step_f: F) -> &mut NodeT

where F: FnOnce(&mut RootT) -> &mut NodeRef, NodeRef: DerefMut<Target = NodeT> + StableDeref + 'l,

Returns the mutable reference on the top of the stack. If the stack contains only the root, this method will behave as if advance_if_empty was called prior to top_mut.

Panics if the root has been taken via Self::take_root

pub fn top_or_advance_mut_twostep<F, G, IntermediateRef>( &mut self, step_f1: F, step_f2: G, ) -> &mut NodeT

where F: FnOnce(&mut RootT) -> &mut IntermediateRef, IntermediateRef: DerefMut + StableDeref + 'l, G: FnOnce(&mut IntermediateRef::Target) -> &mut NodeT,

Returns the mutable reference on the top of the stack. If the stack contains only the root, this method will behave as if advance_if_empty_twostep was called prior to top_mut.

Panics if the root has been taken via Self::take_root

The _twostep version of top_or_advance_mut is useful when you need additional logic to select the NodeT reference, as when RootT is a container.

pub fn into_root(self) -> RootT

Returns the mutable reference on the root of the stack, consuming the stack

Panics if the root of the stack has already been taken via Self::take_root

pub fn depth(&self) -> usize

Returns the number of node references stored in the stack, which corresponds to the number of times backtrack may be called before the stack is empty

The root does not count, so a MutCursorRootedVec containing only the RootT will return depth() == 0.

pub fn capacity(&self) -> usize

Returns the number of node references the stack is capable of holding without reallocation

pub fn advance_if_empty<F, NodeRef>(&mut self, step_f: F)

where F: FnOnce(&mut RootT) -> &mut NodeRef, NodeRef: DerefMut<Target = NodeT> + StableDeref + 'l,

Begins the traversal if the stack contains only the root, otherwise does nothing

Panics if the root has been taken via Self::take_root

pub fn advance_if_empty_twostep<F, G, IntermediateRef>( &mut self, step_f1: F, step_f2: G, )

where F: FnOnce(&mut RootT) -> &mut IntermediateRef, IntermediateRef: DerefMut + StableDeref + 'l, G: FnOnce(&mut IntermediateRef::Target) -> &mut NodeT,

Begins the traversal if the stack contains only the root, otherwise does nothing

Panics if the root has been taken via Self::take_root

The _twostep version of advance_if_empty is useful when you need additional logic to select the NodeT reference, as when RootT is a container.

pub fn advance_from_root<F, NodeRef>(&mut self, step_f: F) -> bool

where F: FnOnce(&mut RootT) -> Option<&mut NodeRef>, NodeRef: DerefMut<Target = NodeT> + StableDeref + 'l,

Begins the traversal by stepping from the root to the first node, pushing the first node reference onto the stack. Always resets the stack.

If the step_f closure returns Some the existing stack will be replaced with the new node. If the step_f closure returns None the stack will be left completely empty.

Panics if the root has been taken via Self::take_root

pub fn advance_from_root_twostep<F, G, IntermediateRef>( &mut self, step_f1: F, step_f2: G, ) -> bool

where F: FnOnce(&mut RootT) -> Option<&mut IntermediateRef>, IntermediateRef: DerefMut + StableDeref + 'l, G: FnOnce(&mut IntermediateRef::Target) -> Option<&mut NodeT>,

Begins the traversal by stepping from the root to the first node, pushing the first node reference onto the stack. Always resets the stack.

If both of the step_f… closures return Some, the existing stack will be replaced with the new node. If either of the step_f… closures returns None the stack will be left completely empty.

Panics if the root has been taken via Self::take_root

The _twostep version of advance_from_root is useful when you need additional logic to select the NodeT reference, as when RootT is a container.

pub fn advance<F>(&mut self, step_f: F) -> bool

where F: FnOnce(&mut NodeT) -> Option<&mut NodeT>,

Steps deeper into the traversal, pushing a new reference onto the top of the stack

If the step_f closure returns Some(), the contained reference is pushed onto the stack and this method returns true. If the closure returns None then the stack is unmodified and this method returns false.

This method will panic if the stack contains only the root. Use Self::advance_from_root

pub fn backtrack(&mut self)

Pops a reference from the stack, exposing the prior reference as the new top

If the last node entry has been removed, only the root will remain. This method will panic if it is called when the stack contains only the root

pub fn try_backtrack_node(&mut self)

Pops a reference from the stack, exposing prior reference as the new top, but, unlike backtrack this method will not pop the bottom NodeT reference, and will never panic!()

This method will do nothing if it is called when depth is <= 1

pub fn to_root(&mut self)

Pops all references from the stack, exposing the root reference via root

This method does nothing if the stack is already at the root.

pub fn to_bottom(&mut self)

Pops all references beyond the first from the stack, exposing the first reference created by advance_from_root as the top

This method does nothing if the stack is already at the root or the first node reference.

Trait Implementations

impl<'l, RootT, NodeT> Send for MutCursorRootedVec<'l, RootT, NodeT>

where RootT: Send, NodeT: Send + ?Sized,

impl<'l, RootT, NodeT> Sync for MutCursorRootedVec<'l, RootT, NodeT>

where RootT: Sync, NodeT: Sync + ?Sized,