Tree<K, V> structv0.1.0

pub struct Tree<K, V> {
    pub root: *var TreeNode<K, V>;
    pub length: uint;
    // private fields
}

Owns every node and everything in them, so it prohibits copying and destroys them with ~Tree.

Type parameters

Fields

Constructors

Tree

pub func Tree(allocator: Allocator) -> Tree<K, V>

An empty tree that has allocated nothing. allocator is borrowed for the call and kept for the tree's life. Cannot fail. Runs in constant time and allocates nothing.

Returns: an empty tree that has taken no storage yet

Source

Associated functions

Minimum

pub func Minimum(from: *var TreeNode<K, V>) -> *var TreeNode<K, V>

The node holding the smallest key of the subtree at from, or null when from is null. Runs in time proportional to the height and allocates nothing.

Returns: the leftmost node of that subtree, or null when it is empty

Source

Maximum

pub func Maximum(from: *var TreeNode<K, V>) -> *var TreeNode<K, V>

The node holding the largest key of the subtree at from, or null when from is null. Runs in time proportional to the height and allocates nothing.

Returns: the rightmost node of that subtree, or null when it is empty

Source

Successor

pub func Successor(node: *var TreeNode<K, V>) -> *var TreeNode<K, V>

The node holding the next key after node's, or null when node holds the largest or is itself null. Descends into the right subtree where there is one, and otherwise climbs past every ancestor node is the right child of — arriving at the first ancestor reached from the left, whose key is the next one up. Runs in time proportional to the height for a single step, but a walk of the whole tree by successor is linear in the length: every edge is crossed exactly twice across the walk. Allocates nothing.

Returns: the node with the next key in order, or null after the last

Source

Predecessor

pub func Predecessor(node: *var TreeNode<K, V>) -> *var TreeNode<K, V>

The node holding the key before node's, or null when node holds the smallest or is itself null. The mirror of Successor, with the same costs.

Returns: the node with the previous key in order, or null before the first

Source

Methods

Length

pub func Length(self: &Tree<K, V>) -> uint

How many entries the tree holds. self is borrowed. Cannot fail; runs in constant time and allocates nothing.

Returns: how many nodes it holds

Source

IsEmpty

pub func IsEmpty(self: &Tree<K, V>) -> bool

Whether the tree holds no entries. self is borrowed. Cannot fail; runs in constant time and allocates nothing.

Returns: whether it holds nothing

Source

Find

pub func Find(
    self: &Tree<K, V>,
    key: K,
    compare: func(K, K) -> Ordering
) -> *var TreeNode<K, V>

The node holding key, or null when the tree does not have it. self is borrowed. compare must impose the same order every call, and the same one every earlier insertion used — a tree searched by a different order than it was built with misses entries it holds. Runs in time proportional to the height, which the colouring holds to at most twice the logarithm of the length. Allocates nothing.

Returns: the node with that key, or null when it is absent

Source

Above

pub func Above(
    self: &Tree<K, V>,
    key: K,
    compare: func(K, K) -> Ordering
) -> *var TreeNode<K, V>

The node holding the smallest key strictly above key, or null when no key is above it. key need not be in the tree. The descent keeps the last node it passed on the high side, which is the answer wherever it ends: once it has gone left of a key, nothing further down is larger than that key. This is what lets a walk survive removing what it is standing on. Successor needs its node still linked into the tree, and removal relinks nodes around it; asking by key instead needs nothing to have stayed put, at the price of a descent per step rather than an edge. Runs in time proportional to the height and allocates nothing.

Returns: the node with the smallest key above this one, or null

Source

Below

pub func Below(
    self: &Tree<K, V>,
    key: K,
    compare: func(K, K) -> Ordering
) -> *var TreeNode<K, V>

The node holding the largest key strictly below key, or null when no key is below it. The mirror of Above, with the same costs and the same use.

Returns: the node with the largest key below this one, or null

Source

Attach

pub func Attach(
    self: &var Tree<K, V>,
    key: K,
    value: V,
    compare: func(K, K) -> Ordering
) -> V? ! CollectionError

Puts key and value into the tree, replacing the value already stored under an equal key. Takes ownership of both. Hands back the value an equal key already had, or none when the key is new — so a caller learns whether anything was displaced without a lookup first, and gets the displaced value rather than having it quietly destroyed. When the key is already present the new key is destroyed rather than stored, since the one in the tree is equal to it and is what everything already hanging below it was ordered against. Reports OutOfMemory when the node cannot be allocated, having changed nothing — but key and value are destroyed rather than handed back, because there is nowhere left to put them. Runs in time proportional to the height, with at most two rotations. Allocates one node for a new key and nothing at all for one already present.

Returns: the value an equal key already held, or none when the key is new

Source

Detach

pub func Detach(
    self: &var Tree<K, V>,
    node: *var TreeNode<K, V>
) -> KeyValue<K, V>

Takes node out of the tree and hands back what it held. node must be a node of this tree, and is freed here — nothing may read through it afterwards. The key and value become the caller's, in the pair a hash map hands its entries back in. A node with two children is not emptied into: the successor is relinked in its place instead, so the entry that stays keeps the address it had and any pointer to it stays good. That is the whole reason the nodes are separate allocations, and it is why removal moves six pointers where copying two fields would do. Cannot fail. Runs in time proportional to the height, with at most three rotations, and allocates nothing.

Returns: the entry the node held

Source

Clear

pub func Clear(self: &var Tree<K, V>)

Destroys every entry and gives every node back to the allocator, leaving an empty tree. self is borrowed mutably and stays usable: entries may be attached again afterwards, and nothing has been kept back to make that cheaper, since a tree has no capacity to keep. Cannot fail. Runs in time proportional to the length and allocates nothing.

Source

Destructor

func ~Tree(self: &var Tree<K, V>)

Destroys every entry and gives every node back. Runs when the tree dies. Never called directly; a tree is move-only, so there is exactly one of these per tree however many times it was passed along.

Source

Related

TreeNode<K, V>

pub struct TreeNode<K, V> {
    pub key: K;
    pub value: V;
    pub left: *var TreeNode<K, V>;
    pub right: *var TreeNode<K, V>;
    pub parent: *var TreeNode<K, V>;
    pub red: bool;
}

One node of a red-black tree. Its own allocation, so its address survives any rearrangement of the tree around it.

Source

Type parameters

Fields