Struct WalkMutOwned

pub struct WalkMutOwned<'r, TP: TreeProperties + 'r, D = (), A = ()> { /* private fields */ }

Walk owned mutable tree up and down

Some algorithms need to remember how they reached the current node via WalkedDirection as D.

When walking manually it might be useful to be able to store additional data via A.

Implementations

impl<'r, TP, D, A> WalkMutOwned<'r, TP, D, A>

where TP: TreeProperties,

pub fn up(&mut self) -> Option<D>

Walk up to parent node or tree if not at tree

pub fn up_with(&mut self) -> Option<(D, A)>

Walk up to parent node or tree if not at tree

pub fn current(&self) -> NodeOrTree<Option<&Node<TP>>, &Node<TP>>

Current node or tree

pub fn current_mut( &mut self, ) -> NodeOrTree<Option<&mut Node<TP>>, &mut Node<TP>>

Current mutable node or tree

If you need the result to outlive the destruction of the WalkMutOwned value, see into_current_mut.

pub fn into_current_mut( self, ) -> NodeOrTree<Option<&'r mut Node<TP>>, &'r mut Node<TP>>

Extract mutable node or tree

Also see current_mut

impl<'r, TP> WalkMutOwned<'r, TP, WalkedDirection, ()>

where TP: TreeProperties + 'r,

pub fn delete_current(&mut self) -> Option<WalkedDirection>

Delete current node (or tree)

Afterwards the current node is the previous parent node, which was replaced by the sibling, or the (empty) tree when removing the last node.

Returns what up_with would have returned.

impl<'r, TP, A> WalkMutOwned<'r, TP, WalkedDirection, A>

where TP: TreeProperties + 'r,

pub fn delete_current_with(&mut self) -> Option<(WalkedDirection, A)>

Delete current node (or tree)

Afterwards the current node is the previous parent node, which was replaced by the sibling, or the (empty) tree when removing the last node.

Returns what up_with would have returned.

pub fn compact_if_empty<F>(&mut self, is_empty: F)

where F: Fn(&TP::Value) -> bool,

Remove empty leaf nodes if possible

A node is considered “empty” if the passed function considers its value empty.

Calls this if the current value might just have become empty.

Empty leafs can only be removed if the parent node is empty too, or both siblings are empty leafs (then the parent becomes a leaf node).

• if current node isn’t empty nothing changes
• if current node is an empty leaf node:
  • parent and sibling shouldn’t have both been empty, as previous compact_if_empty calls would have cleaned that up
  • if parent is empty: remove leaf and parent, replace parent with sibling. current points to sibling afterwards.
  • if sibling is an empty leaf: make parent a leaf, current points to parent afterwards.
  • otherwise no tree changes, but current points to parent afterwards.
• if current node has an empty leaf child node, remove that child node and current node. I.e. replace current node with other child; current points to that child afterwards. Other child node shouldn’t be an empty leaf, as previous compact_if_empty calls would have cleaned that up.
• if current points to tree or root node, clear tree if it is an empty node

impl<'r, TP, D, A> WalkMutOwned<'r, TP, D, A>

where TP: TreeProperties + 'r, D: From<WalkedDirection>,

pub fn down_root_with(&mut self, add: A) -> bool

Walk down from tree to root node (if at tree and not empty)

pub fn down_left_with(&mut self, add: A) -> bool

Walk down to left node if present and not currently at tree

pub fn down_right_with(&mut self, add: A) -> bool

Walk down to right node if present and not currently at tree

pub fn down_with(&mut self, side: bool, add: A) -> bool

Walk down to specified node if present and not currently at tree

false picks left and true picks right.

impl<'r, TP, D> WalkMutOwned<'r, TP, D, ()>

where TP: TreeProperties + 'r, D: From<WalkedDirection>,

pub fn down_root(&mut self) -> bool

Walk down from tree to root node (if at tree and not empty)

pub fn down_left(&mut self) -> bool

Walk down to left node if present and not currently at tree

pub fn down_right(&mut self) -> bool

Walk down to right node if present and not currently at tree

pub fn down(&mut self, side: bool) -> bool

Walk down to specified node if present and not currently at tree

false picks left and true picks right.

impl<'r, TP, D> WalkMutOwned<'r, TP, D>

where TP: TreeProperties + 'r, D: From<WalkedDirection>,

pub fn path(&mut self, key: TP::Key) -> WalkMutOwnedPath<'r, '_, TP, D>

Start iterator to walk to deepest node that is a prefix of the target key

While consuming the iterator the stack is updated with the position of the returned nodes.

When self was in a mismatching subtree (i.e. not a prefix of the target key) before the iterator won’t find anything.

pub fn goto_insert(&mut self, key: &TP::Key) -> Option<InsertPosition>

Walk to node where we’d have to insert key at

Returns None if tree is empty.

impl<'r, TP, D> WalkMutOwned<'r, TP, D>

where TP: TreeProperties + 'r, D: From<WalkedDirection>,

pub fn insert(&mut self, key: TP::Key) -> &mut Node<TP>

Insert new (possibly inner) node with exact key in tree, walk to it and return reference to it

impl<'r, TP> WalkMutOwned<'r, TP, WalkedDirection, ()>

where TP: TreeProperties + 'r,

pub fn into_iter_pre_order(self) -> IterMutOwnedPreOrder<'r, TP>

Convert into iterator traversing depth-first pre-order

pub fn next_pre_order(&mut self) -> Option<&mut Node<TP>>

Tree traversal: depth-first pre-order

pub fn into_iter_in_order(self) -> IterMutOwnedInOrder<'r, TP>

Convert into iterator traversing depth-first in-order

pub fn next_in_order(&mut self) -> Option<&mut Node<TP>>

Tree traversal: depth-first in-order

pub fn into_iter_post_order(self) -> IterMutOwnedPostOrder<'r, TP>

Convert into iterator traversing depth-first post-order

pub fn next_post_order(&mut self) -> Option<&mut Node<TP>>

Tree traversal: depth-first post-order

pub fn into_iter_leafs(self) -> IterMutOwnedLeaf<'r, TP>

Convert into iterator over all leafs

pub fn into_iter_full_leafs(self) -> IterMutOwnedLeafFull<'r, TP>

Convert into iterator over all leafs and uncovered parts

pub fn next_leaf(&mut self) -> Option<&mut Node<TP>>

Tree traversal: depth-first in-order leaf nodes only