Trait grove::trees::SomeWalker[−][src]

pub trait SomeWalker<D: Data>: SomeEntry<D> {

Show 15 methods    fn depth(&self) -> usize;

    fn value(&self) -> Option<&D::Value>;

    fn go_left(&mut self) -> Result<(), ()>;

    fn go_right(&mut self) -> Result<(), ()>;

    fn go_up(&mut self) -> Result<Side, ()>;

    fn far_left_summary(&self) -> D::Summary;

    fn far_right_summary(&self) -> D::Summary;

    fn go_to_root(&mut self) { ... }

    fn next_empty(&mut self) -> Result<(), ()> { ... }

    fn previous_empty(&mut self) -> Result<(), ()> { ... }

    fn next_filled(&mut self) -> Result<(), ()> { ... }

    fn previous_filled(&mut self) -> Result<(), ()> { ... }

    fn search_subtree<L: Locator<D>>(&mut self, locator: L) { ... }

    fn left_summary(&self) -> D::Summary { ... }

    fn right_summary(&self) -> D::Summary { ... }

}
Expand description

The Walker trait implements walking through a tree. This includes dealing with the borrow checking problems of recursive structures (using Telescope), and rebalancing the tree. Therefore, walkers can’t guarantee that the tree won’t change as you walk through them.

The walker should be able to walk on any of the existing nodes, or any empty position just near them. i.e., The walker can also be in the position of a son of an existing node, where there isn’t a node yet. The method SomeEntry::is_empty() can tell whether you are at an empty position. Trying to move downward from an empty position produces an error value.

Required methods

Returns the current depth in the tree. The convention is, the root is at depth zero

This function is here since only walkers can guarantee that the current value is clean.

return Err(()) if it is in an empty spot.

returns Err(()) if it is in an empty spot.

If successful, returns whether or not the previous current value was the left son. If already at the root of the tree, returns Err(()).

Returns a summary of all the values to the left of this point, That are not children of this point.

Returns a summary of all the values to the right of this point, That are not children of this point.

Provided methods

Goes to the root. May restructure the tree while doing so. For example, in splay trees, this splays the current node.

If the walker is at an empty position, return an error. Goes to the next empty position.

May restructure the tree while doing so.

If the walker is at an empty position, return an error. Goes to the previous empty position.

May restructure the tree while doing so.

Finds the next filled node. If there isn’t any, moves to root and return Err(()).

May restructure the tree while doing so.

Finds the previous filled node. If there isn’t any, moves to root and return Err(()).

May restructure the tree while doing so.

Finds any node that the locator Accepts. Looks only inside the current subtree. If there isn’t any, it finds the empty location where that node would be instead. Returns a walker at the wanted position.

Returns a summary of all the values to the left of this point. If the walker is in a non empty spot, this does not include the current node.

Returns a summary of all the values to the right of this point. If the walker is in a non empty spot, this does not include the current node.

Implementors