Trait NodeMut

pub trait NodeMut: Node + Sized {
    type NodePtr: Sized + DerefMut<Target = Self>;

    // Required methods
    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>;

    // Provided methods
    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.

Required Associated Types

type NodePtr: Sized + DerefMut<Target = Self>

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.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<T> NodeMut for CountNode<T>

type NodePtr = Box<CountNode<T>>

impl<T> NodeMut for TestNode<T>

type NodePtr = Box<TestNode<T>>