Module grove::locators

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

BetweenLocator

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

ByKey

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.

LeftEdgeOf

A Wrapper for other locators what will find exactly the left edge of the previous locator. So, this is always a splitting locator.

LeftOf

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.

RightEdgeOf

A Wrapper for other locators what will find exactly the right edge of the previous locator. So, this is always a splitting locator.

RightOf

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

UnionLocator

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

LocResult

This is the result type that a locator returns when queried about a specific node. See Locator.

Traits

Locator

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

clone_locate

Returns the result of the locator at the walker Returns None if the walker is at an empty position

query_locator

Returns the result of the locator at the walker Returns None if the walker is at an empty position