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.
If successful, returns whether or not the previous current value was the left son.
If already at the root of the tree, returns Err(())
.
fn far_left_summary(&self) -> D::Summary
fn far_left_summary(&self) -> D::Summary
Returns a summary of all the values to the left of this point, That are not children of this point.
fn far_right_summary(&self) -> D::Summary
fn far_right_summary(&self) -> D::Summary
Returns a summary of all the values to the right of this point, That are not children of this point.
Provided methods
fn go_to_root(&mut self)
fn go_to_root(&mut self)
Goes to the root. May restructure the tree while doing so. For example, in splay trees, this splays the current node.
fn next_empty(&mut self) -> Result<(), ()>
fn next_empty(&mut self) -> Result<(), ()>
If the walker is at an empty position, return an error. Goes to the next empty position.
May restructure the tree while doing so.
fn previous_empty(&mut self) -> Result<(), ()>
fn previous_empty(&mut self) -> Result<(), ()>
If the walker is at an empty position, return an error. Goes to the previous empty position.
May restructure the tree while doing so.
fn next_filled(&mut self) -> Result<(), ()>
fn next_filled(&mut self) -> Result<(), ()>
Finds the next filled node. If there isn’t any, moves to root and return Err(()).
May restructure the tree while doing so.
fn previous_filled(&mut self) -> Result<(), ()>
fn previous_filled(&mut self) -> Result<(), ()>
Finds the previous filled node. If there isn’t any, moves to root and return Err(()).
May restructure the tree while doing so.
fn search_subtree<L: Locator<D>>(&mut self, locator: L)
fn search_subtree<L: Locator<D>>(&mut self, locator: L)
Finds any node that the locator Accept
s. 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.
fn left_summary(&self) -> D::Summary
fn left_summary(&self) -> D::Summary
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.
fn right_summary(&self) -> D::Summary
fn right_summary(&self) -> D::Summary
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.