Class in collections::tree coil-stdlib

`TreeMap`

class TreeMap<K, V>

Import

use collections::tree::{TreeMap};

Source: src/collections/tree.hy

An ordered map from keys of type K to values of type V.

Keys need Ord and Eq. Iteration visits entries in ascending key order, and min_key / max_key give the ends. The tree is not rebalanced: inserting keys that are already sorted makes lookups linear, so prefer HashMap when you do not need the order.

Fields#

Field	Type	Description
`keys`	`Vec<K>`	Node keys, including removed nodes. Prefer iteration.
`vals`	`Vec<V>`	Node values parallel to `keys`.
`left`	`Vec<int>`	Index of each node’s left child, or `-1`.
`right`	`Vec<int>`	Index of each node’s right child, or `-1`.
`root`	`int`	Index of the root node, or `-1` when the map is empty.

Associated functions#

Name	Description
`new`	Creates an empty map.
`empty`	Creates an empty map; the same as `TreeMap::new`.

Methods#

Name	Description
`size`	Returns the number of entries.
`is_empty`	Returns `true` when the map has no entries.
`clear`	Removes every entry.
`iter`	Returns an iterator over the entries in ascending key order.
`insert`	Stores `v` under `k`, replacing any value already there.
`contains`	Returns `true` when the map has an entry for `k`.
`get_or`	Returns the value stored under `k`, or `fallback` when there is none.
`get`	Returns the value stored under `k`, or `None` when there is none.
`remove`	Removes the entry for `k`.
`min_key`	Returns the smallest key, or `fallback` when the map is empty.
`max_key`	Returns the largest key, or `fallback` when the map is empty.

Trait implementations#

IntoIterator for TreeMap<K, V>

Invariants#

Checked according to --contracts (see Contracts).

invariant self.len >= 0 && self.len <= self.keys.len()
invariant self.vals.len() == self.keys.len()
invariant self.left.len() == self.keys.len() && self.right.len() == self.keys.len()
invariant (self.root < 0) == (self.len == 0)

Examples#

use collections::tree::{TreeMap};
use tests::assert;
let m: TreeMap<int, string> = TreeMap::new();
m.insert(30, "c");
m.insert(10, "a");
m.insert(20, "b");
let order = "";
for e in m {
    order = order + e.value;
}
assert!(order == "abc");
assert!(m.min_key(0) == 10);