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

Try to detach the left sub-tree

Try to detach the right sub-tree

Replace the left subtree with tree and return the old one.

Replace the right subtree with tree and return the old one.

Returns a mutable reference to the value of the current node.

Consume a Node and return its parts: (value, left, right)

Returns a mutable reference to the left child

Returns a mutable reference to the right child

Provided Methods

Try to rotate the tree left if right subtree exists

Try to rotate the tree right if left subtree exists

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.

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).

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.

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.

Replace this node with one of its descendant, returns None if it has no children.

Implementors