Module grove::locators [−][src]
Expand description
The locator module provides an interface for locating a specific value or a segment, generalizing the search in a binary search tree.
Locators are supposed to represent a segment of the tree. See Locator
.
Functions like search, which logically expect only one accepted node, and not a segment, will use any node that is accepted. Functions like insertions, will expect a locator that doesn’t accept any node, but leads the locator into a space between nodes, where the node will be inserted.
Structs
A Wrapper for two other locators, that finds the segment between them.
More specifically, if the two segments intersect, this finds the intersection.
If they don’t intersect, this finds the segment that is between the two segments.
For example, the Between of ranges [3,6)
and [8,12)
will be [6,8)
,
This struct says you want your locator to be based on your values’ keys, through the
data::Keyed
trait.
For example, a ByKey(3..9)
locator will accept
elements with keys in the range 3..9
. Of course, this is a legal locator only if
the elements are sorted by their keys.
A Wrapper for other locators what will find exactly the left edge of the previous locator. So, this is always a splitting locator.
A Wrapper for other locators what will find the segment to the left
of the previous locator. So, LeftOf(5..8)
is equivalent to 0..5
.
A Wrapper for other locators what will find exactly the right edge of the previous locator. So, this is always a splitting locator.
A Wrapper for other locators what will find the segment to the right
of the previous locator. So, RightOf(5..8)
is equivalent to 8..
.
A Wrapper for two other locators, that finds the smallest segment containing both of them.
For example, the Union of ranges [3,6)
and [8,12)
will be [3,12)
.
Enums
This is the result type that a locator
returns when queried about a specific node.
See Locator
.
Traits
Locators are type that represent a segment of the tree. When the locator is used, we query the locator about the current node. The locator has to reply:
Functions
Returns the result of the locator at the walker Returns None if the walker is at an empty position
Returns the result of the locator at the walker Returns None if the walker is at an empty position