TreeMap<K, V> structv0.1.0

pub struct TreeMap<K, V> {
    // private fields
}

Move-only: it owns every node and everything in them.

Type parameters

Constructors

TreeMap

pub func TreeMap(
    allocator: Allocator,
    compare: func(K, K) -> Ordering
) -> TreeMap<K, V>

An empty map ordered by compare, which has allocated nothing. allocator is borrowed for the call and kept for the map's life. compare must impose the same order every call; a map whose comparison changes under it loses entries it still holds. Cannot fail. Runs in constant time and allocates nothing.

Returns: an empty collection that has taken no storage yet

Source

Methods

Length

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

How many entries the map holds.

Returns: how many entries it holds

Source

IsEmpty

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

Whether the map holds no entries.

Returns: whether it holds nothing

Source

ContainsKey

pub func ContainsKey(self: &TreeMap<K, V>, key: K) -> bool

Whether key has a value in the map. Runs in time proportional to the height, which is at most twice the logarithm of the length.

Returns: whether an entry with that key is present

Source

Get

pub func Get(self: &TreeMap<K, V>, key: K) -> V?

A copy of the value stored under key, or none.

Returns: a copy of the value, or none when the key is absent

Source

Reference

pub func Reference(self: &TreeMap<K, V>, key: K) -> (*V)?

A borrow of the value stored under key, or none. The borrow stays valid while the map is untouched — and, unlike a hash map's, across insertions and removals of other keys too, since a node keeps its address while the tree is rearranged around it. It ends when this key is removed or the map dies.

Returns: the address of the value, or none when the key is absent

Source

TryReferenceMutable

pub func TryReferenceMutable(
    self: &var TreeMap<K, V>,
    key: K,
    value: *var *var V
) -> bool

Points value at the value stored under key so it can be written through, and reports whether there was one. value is left untouched when this reports false. Two calls rather than an (*var V)? because an option of a writable pointer does not survive lowering; this is the same answer in the shape that does.

Returns: whether the key was present

Source

Insert

pub func Insert(
    self: &var TreeMap<K, V>,
    key: K,
    value: V
) -> ! CollectionError

Stores value under key, replacing and destroying whatever was there. Takes ownership of both. Reports OutOfMemory when the node cannot be allocated, in which case the map is unchanged — but the key and the value are destroyed rather than handed back, since there is nowhere to put them. Replace is the one to use when the displaced value is wanted. Runs in time proportional to the height, with at most two rotations, and allocates one node for a key that is new and nothing at all for one already there.

Returns: nothing when the operation succeeded, or why it did not

Source

Replace

pub func Replace(
    self: &var TreeMap<K, V>,
    key: K,
    value: V
) -> V? ! CollectionError

Stores value under key and hands back the value it displaced, or none for a key that was not there. A failure is reported apart from the absence, so "nothing was there" and "nothing was stored" never meet.

Returns: the value that was there, or none when the key was absent

Source

Remove

pub func Remove(self: &var TreeMap<K, V>, key: K) -> V?

Takes the entry stored under key out of the map and hands its value back, or none. Cannot fail. Runs in time proportional to the height, with at most three rotations, and allocates nothing.

Returns: the value that was stored, or none when the key was absent

Source

RemoveEntry

pub func RemoveEntry(
    self: &var TreeMap<K, V>,
    key: K
) -> KeyValue<K, V>?

Takes the entry stored under key out and hands back the key as well as the value, or none. The key that comes back is the one the map was holding, which for a key type where equal is not identical is the one every entry below it was ordered against, not the one just passed in.

Returns: the whole entry, or none when the key was absent

Source

Clear

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

Destroys every entry, leaving an empty map that is still usable.

Source

First

pub func First(self: &TreeMap<K, V>) -> KeyValue<K, V>?

The entry with the smallest key, or none for an empty map. Runs in time proportional to the height and allocates nothing.

Returns: the entry with the smallest key, or none when empty

Source

Last

pub func Last(self: &TreeMap<K, V>) -> KeyValue<K, V>?

The entry with the largest key, or none for an empty map.

Returns: the entry with the largest key, or none when empty

Source

Floor

pub func Floor(
    self: &TreeMap<K, V>,
    key: K
) -> KeyValue<K, V>?

The entry with the largest key at or below key, or none when every key is above it. The descent remembers the last node it passed on the low side, which is the answer wherever it ends: once it has gone right of a key, nothing further down is smaller than that key. Runs in time proportional to the height and allocates nothing.

Returns: the entry with the largest key at or below key, or none

Source

Ceiling

pub func Ceiling(
    self: &TreeMap<K, V>,
    key: K
) -> KeyValue<K, V>?

The entry with the smallest key at or above key, or none when every key is below it.

Returns: the entry with the smallest key at or above key, or none

Source

Iterate

pub func Iterate(self: &TreeMap<K, V>) -> TreeMapIterator<K, V>

A walk over this map, smallest key first, leaving it untouched. self is borrowed and must outlive the walk, which must not run across an insertion or a removal.

Returns: a cursor over the entries in key order

Source

Range

pub func Range(
    self: &TreeMap<K, V>,
    start: K,
    end: K
) -> TreeMapRangeIterator<K, V>

A walk over the entries whose keys are at or above start and below end. Half-open, so Range(a, b) and Range(b, c) together give exactly Range(a, c) with nothing repeated and nothing missed. A range whose end is not above its start hands back nothing. Starting costs a descent rather than a walk from the smallest key, so a small range out of a large map is cheap.

Returns: a cursor over the entries whose keys fall in [start, end)

Source

IntoIterator

pub func IntoIterator(self: TreeMap<K, V>) -> TreeMapIntoIterator<K, V>

A walk that consumes this map, smallest key first. Takes ownership; the map is gone afterwards.

Returns: a cursor that consumes the map as it goes, in key order

Source

Related

WriteTreeMapDebug<K, V>

pub func WriteTreeMapDebug<K: Debug, V: Debug>(
    writer: &var TextWriter,
    value: &TreeMap<K, V>,
    spec: FormatSpec
) -> ! FormatError

Writes a borrowed ordered map as {key: value, key: value}, in key order. An empty map is {}. The order is the map's own — the order Iterate walks, the order First and Last name the ends of — so two maps holding the same entries render identically and one map renders identically every time. That is what makes an ordered map's rendering usable in an assertion where a hash map's is not. The walk crosses every edge of the tree twice and allocates nothing, and nothing is taken out of the map: every key and value is shown through a borrow of the node holding it. spec is handed to each unchanged. Reports whatever the writer or an entry's implementation reported, stopping at the first refusal.

Source

Type parameters

Parameters

Returns: success when the whole rendering was accepted

TreeMapIterator<K, V>

pub struct TreeMapIterator<K, V> {
    // private fields
}

A walk over a borrowed map, smallest key first. Copies each entry out as it goes, so the map is untouched and keeps everything it holds.

Source

Type parameters

Methods

Next

pub func Next(self: &var TreeMapIterator<K, V>) -> KeyValue<K, V>?

The next entry in key order, or none when there are no more. Runs in constant amortized time: every edge of the tree is crossed exactly twice across a whole walk.

Returns: the next entry in key order, or none at the end

Source

TreeMapRangeIterator<K, V>

pub struct TreeMapRangeIterator<K, V> {
    // private fields
}

A walk over a borrowed map that stops at a bound.

Source

Type parameters

Methods

Next

pub func Next(self: &var TreeMapRangeIterator<K, V>) -> KeyValue<K, V>?

The next entry below the bound, or none once the walk reaches it.

Returns: the next entry in key order, or none at the end

Source

TreeMapIntoIterator<K, V>

pub struct TreeMapIntoIterator<K, V> {
    // private fields
}

A walk that consumes the map, smallest key first. Owns the nodes, and destroys whatever is left in them when it dies — so a walk stopped part-way destroys the rest exactly once, and nothing already handed out is destroyed twice.

Source

Type parameters

Methods

Next

pub func Next(self: &var TreeMapIntoIterator<K, V>) -> KeyValue<K, V>?

The next entry in key order, or none when there are no more. Takes the smallest entry out of the tree rather than reading past it, which is what makes the entry the caller's and leaves the destructor with one less thing to do. Each step costs a removal, so a whole walk is linearithmic where the borrowed walk is linear — the price of handing out ownership one entry at a time.

Returns: the next entry in key order, or none at the end

Source