RBTree
Red-Black Trees
Color
type Color = {#R; #B}
Node color: red or black.
Tree
type Tree<X, Y> = {#node : (Color, Tree<X, Y>, (X, ?Y), Tree<X, Y>); #leaf}
Ordered, (red-black) tree of entries.
RBTree
class RBTree<X, Y>(compareTo : (X, X) -> O.Order)
Create an order map from an order function for its keys.
share
func share() : Tree<X, Y>
Tree as sharable data.
Get non-OO, purely-functional representation: for drawing, pretty-printing and non-OO contexts (e.g., async args and results):
get
func get(x : X) : ?Y
Get the value associated with a given key.
replace
func replace(x : X, y : Y) : ?Y
Replace the value associated with a given key.
put
func put(x : X, y : Y)
Put an entry: A value associated with a given key.
delete
func delete(x : X)
Delete the entry associated with a given key.
remove
func remove(x : X) : ?Y
Remove the entry associated with a given key.
entries
func entries() : I.Iter<(X, Y)>
An iterator for the key-value entries of the map, in ascending key order.
iterator is persistent, like the tree itself
entriesRev
func entriesRev() : I.Iter<(X, Y)>
An iterator for the key-value entries of the map, in descending key order.
iterator is persistent, like the tree itself
iter
func iter<X, Y>(t : Tree<X, Y>, dir : {#fwd; #bwd}) : I.Iter<(X, Y)>
An iterator for the entries of the map, in ascending (#fwd
) or descending (#bwd
) order.
size
func size<X, Y>(t : Tree<X, Y>) : Nat
The size of the tree as the number of key-value entries.