Trait binary_tree::NodeMut
[−]
[src]
pub trait NodeMut: Node + Sized { type NodePtr: Sized + DerefMut<Target=Self>; fn detach_left(&mut self) -> Option<Self::NodePtr>; fn detach_right(&mut self) -> Option<Self::NodePtr>; fn insert_left(&mut self, tree: Option<Self::NodePtr>) -> Option<Self::NodePtr>; fn insert_right(&mut self, tree: Option<Self::NodePtr>) -> Option<Self::NodePtr>; fn value_mut(&mut self) -> &mut Self::Value; fn into_parts(self) -> (Self::Value, Option<Self::NodePtr>, Option<Self::NodePtr>); fn left_mut(&mut self) -> Option<&mut Self>; fn right_mut(&mut self) -> Option<&mut Self>; fn rotate_left(&mut self) -> Result<(), ()> { ... } fn rotate_right(&mut self) -> Result<(), ()> { ... } fn walk_mut<'a, FI, FS>(&'a mut self, step_in: FI, stop: FS) where FI: FnMut(&Self) -> WalkAction, FS: FnOnce(&'a mut Self) { ... } fn walk_reshape<FI, FS, FO>(&mut self, step_in: FI, stop: FS, step_out: FO) where FI: FnMut(&mut Self) -> WalkAction, FS: FnOnce(&mut Self), FO: FnMut(&mut Self, WalkAction) { ... } fn insert_before<F>(&mut self, new_node: Self::NodePtr, step_out: F) where F: FnMut(&mut Self, WalkAction) { ... } fn walk_extract<FI, FE, FO>(&mut self, step_in: FI, extract: FE, step_out: FO) -> Option<Self::NodePtr> where FI: FnMut(&mut Self) -> WalkAction, FE: FnOnce(&mut Self, &mut Option<Self::NodePtr>), FO: FnMut(&mut Self, WalkAction) { ... } fn try_remove<F>(&mut self, step_out: F) -> Option<Self::NodePtr> where F: FnMut(&mut Self, WalkAction) { ... } }
Mutating methods on a Binary Tree node.
Associated Types
Required Methods
fn detach_left(&mut self) -> Option<Self::NodePtr>
Try to detach the left sub-tree
fn detach_right(&mut self) -> Option<Self::NodePtr>
Try to detach the right sub-tree
fn insert_left(&mut self, tree: Option<Self::NodePtr>) -> Option<Self::NodePtr>
Replace the left subtree with tree
and return the old one.
fn insert_right(&mut self, tree: Option<Self::NodePtr>) -> Option<Self::NodePtr>
Replace the right subtree with tree
and return the old one.
fn value_mut(&mut self) -> &mut Self::Value
Returns a mutable reference to the value of the current node.
fn into_parts(self) -> (Self::Value, Option<Self::NodePtr>, Option<Self::NodePtr>)
Consume a Node and return its parts: (value, left, right)
fn left_mut(&mut self) -> Option<&mut Self>
Returns a mutable reference to the left child
fn right_mut(&mut self) -> Option<&mut Self>
Returns a mutable reference to the right child
Provided Methods
fn rotate_left(&mut self) -> Result<(), ()>
Try to rotate the tree left if right subtree exists
fn rotate_right(&mut self) -> Result<(), ()>
Try to rotate the tree right if left subtree exists
fn walk_mut<'a, FI, FS>(&'a mut self, step_in: FI, stop: FS) where FI: FnMut(&Self) -> WalkAction, FS: FnOnce(&'a mut Self)
Simple mutable walk
Note that the type of step_in
is almost identical to that in
Node::walk
, but not exactly so. Here, step_in
does not get a
reference which lives as long as self
so that it cannot leak
references out to its environment.
fn walk_reshape<FI, FS, FO>(&mut self, step_in: FI, stop: FS, step_out: FO) where FI: FnMut(&mut Self) -> WalkAction, FS: FnOnce(&mut Self), FO: FnMut(&mut Self, WalkAction)
Walks down the tree by detaching subtrees, then up reattaching them
back. step_in
should guide the path taken, stop
will be called on
the node where either step_in
returned Stop
or it was not possible
to proceed. Then step_out
will be called for each node along the way
to root, except the final one (that for which stop
was called).
fn insert_before<F>(&mut self, new_node: Self::NodePtr, step_out: F) where F: FnMut(&mut Self, WalkAction)
Insert new_node
in-order before self
. step_out
will be invoked for
all nodes in path from (excluding) the point of insertion, to
(including) self
, unless self
is the point of insertion.
fn walk_extract<FI, FE, FO>(&mut self, step_in: FI, extract: FE, step_out: FO) -> Option<Self::NodePtr> where FI: FnMut(&mut Self) -> WalkAction, FE: FnOnce(&mut Self, &mut Option<Self::NodePtr>), FO: FnMut(&mut Self, WalkAction)
Extract out a node. This can be used in conjuction with try_remove
to
remove any node except the root.
The closure extract
should try to take out the desired node from its
first argument and move it to its second argument (possibly using
try_remove
). If it was unable to do it, the final node that was
visited will be taken out and returned, unless it is the root itself.
Note that, similar to walk_reshape
, step_out
is not called for the
finally visited node (that for which extract
was called).
See the source of CountTree::remove
for an example use.
fn try_remove<F>(&mut self, step_out: F) -> Option<Self::NodePtr> where F: FnMut(&mut Self, WalkAction)
Replace this node with one of its descendant, returns None
if it has
no children.