StableRBTree

Red-Black Trees

type Color = {#R; #B}

Node color: red or black.

type Tree<K, V> = {#node : (Color, Tree<K, V>, (K, ?V), Tree<K, V>); #leaf}

Ordered, (red-black) tree of entries.

`public func init<K, V>() : Tree<K, V>`

Initializes an empty Red-Black Tree of type <K, V> Returns this empty Red-Black Tree

`public func share<K, V>(tree : Tree<K, V>) : Tree<K, V>`

Tree as sharable data.

Get non-OO, purely-functional representation: for drawing, pretty-printing and non-OO contexts (e.g., async args and results):

`public func get<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K ) : ?V`

Returns the value associated with a given key.

`public func replace<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K, v : V ) : (?V, Tree<K, V>)`

Replace the value associated with a given key. Returns the replaced value (if exists) and the new tree

`public func put<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K, v : V ) : Tree<K, V>`

Put an entry: A value associated with a given key. Returns the new tree

`public func delete<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K ) : Tree<K, V>`

Delete the entry associated with a given key. Returns the new tree

`public func remove<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K ) : (?V, Tree<K, V>)`

Remove the entry associated with a given key. Returns the removed entry (if exists) and the new tree

`public func update<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K, updateFunction : (?V) -> V ) : (?V, Tree<K, V>)`

Apply an update function to an entry associated with a given key, or create that entry if it does not yet exist. Returns the old value and the new tree

`public func split<K, V>(tree : Tree<K, V>, compareTo : (K, K) -> O.Order) : ?(Tree<K, V>, Tree<K, V>)`

Splits a Red-Black Tree (t) into two Red-Black Trees (t1, t2). All of the nodes' keys in the first Red-Black Tree returned will be less than the nodes' keys in the second Red-Black Tree returned.

Note: this implementation mutates the tree passed in as it re-inserts the root node key values into the left child

Implementation: Splits a Red-Black tree into it's left child and right child trees, then inserts the root node into the tree of the left child. Returns the right child Red-Black Tree, and the result of reinserting the root node into the left child Red-Black Tree. Transforms the roots of both trees it returns to black to protect the tree's invariants

Edge cases

If the root is a #leaf (empty), returns two #leaf (empty) Red-Black Trees
If the tree contains a single #node at the root (both children are leaves, returns that node and a #leaf
If the tree contains a #node at the root and one child is a #leaf returns the a new tree with the root key and node's key and value, and the child which is a #node
If the root node was deleted (with a null value), just returns the left and right child Red-Black Trees. For an explanation of how functional Red-Black Trees handle deletion, see https://matt.might.net/papers/germane2014deletion.pdf
If an invalid Red-Black Tree in terms of being unbalanced is passed to this function, the split will return null. This is done instead of splitting the tree, in order to prevent a loss of data in the Red-Black Tree

`public func entries<K, V>(tree : Tree<K, V>) : I.Iter<(K, V)>`

An iterator for the key-value entries of the map, in ascending key order.

iterator is persistent, like the tree itself

`public func entriesRev<K, V>(tree : Tree<K, V>) : I.Iter<(K, V)>`

An iterator for the key-value entries of the map, in descending key order.

iterator is persistent, like the tree itself

type Direction = {#fwd; #bwd}

Direction of iteration (forwards or backwards)

`public func iter<K, V>(t : Tree<K, V>, dir : Direction) : I.Iter<(K, V)>`

An iterator for the entries of the map, in ascending (#fwd) or descending (#bwd) order.

type ScanLimitResult<K, V> = { results : [(K, V)]; nextKey : ?K }

`public func scanLimit<K, V>( t : Tree<K, V>, compareTo : (K, K) -> O.Order, lowerBound : K, upperBound : K, dir : Direction, limit : Nat ) : ScanLimitResult<K, V>`

Performs a in-order scan of the Red-Black Tree between the provided key bounds, returning a number of matching entries in the direction specified (forwards/backwards) limited by the limit parameter specified in an array formatted as (K, V) for each entry

`public func bal<K, V>( color : Color, lt : Tree<K, V>, kv : (K, ?V), rt : Tree<K, V> ) : Tree<K, V>`

`public func size<K, V>(t : Tree<K, V>) : Nat`

The size of the tree as the number of key-value entries.

`public func equalIgnoreDeleted<K, V>( t1 : Tree<K, V>, t2 : Tree<K, V>, keyEquals : (K, K) -> Bool, valueEquals : (V, V) -> Bool ) : Bool`

For most purposes, one should prefer this equalIgnoreDeleted function as opposed to equalIncludeDeleted.

Functional Red-Black trees do not have efficient operations for deleting a red black tree. For reference, see https://matt.might.net/papers/germane2014deletion.pdf.

Therefore, "deleting" a node is represented as setting the value to null for a specific key.

The equalIgnoreDeleted function returns a boolean value indicating if two Red-Black Trees are equivalent, ignoring node coloring and focusing solely on node location and key value equality as per the keyEquals and valueEquals methods supplied.

Note the difference betweenn equalIgnoreDeleted and equalIncludeDeleted in the result of the last line in the following example.

Example:

var t1 = RBT.init<Nat, Text>();
var t2 = RBT.init<Nat, Text>();
t1 := RBT.put<Nat, Text>(t1, Nat.compare, 35, "john");
t2 := RBT.put<Nat, Text>(t1, Nat.compare, 35, "john");
RBT.equalIgnoreDeleted<Nat, Text>(t1, t2, Nat.equal, Text.equal); // true
RBT.equalIncludeDeleted<Nat, Text>(t1, t2, Nat.equal, Text.equal); // true

t1 := RBT.put<Nat, Text>(t1, Nat.compare, 31, "alice");
t1 := RBT.delete<Nat, Text>(t1, Nat.compare, 31);
RBT.equalIgnoreDeleted<Nat, Text>(t1, t2, Nat.equal, Text.equal); // true
RBT.equalIncludeDeleted<Nat, Text>(t1, t2, Nat.equal, Text.equal); // false

`public func equalIncludeDeleted<K, V>( t1 : Tree<K, V>, t2 : Tree<K, V>, keyEquals : (K, K) -> Bool, valueEquals : (V, V) -> Bool ) : Bool`

Functional Red-Black trees do not have efficient operations for deleting a red black tree. Therefore, "deleting" a node is represented as setting the value to null for a specific key.

Returns a boolean value indicating if two Red-Black Trees are equivalent, including node coloring and deleted "null" nodes, as well as node location and key value equality as per the keyEquals and valueEquals methods supplied

Example:

var t1 = RBT.init<Nat, Text>();
var t2 = RBT.init<Nat, Text>();
t1 := RBT.put<Nat, Text>(t1, Nat.compare, 35, "john");
t2 := RBT.put<Nat, Text>(t1, Nat.compare, 35, "john");
RBT.equalIncludeDeleted<Nat, Text>(t1, t2, Nat.equal, Text.equal); // true

t1 := RBT.put<Nat, Text>(t1, Nat.compare, 31, "alice");
t1 := RBT.delete<Nat, Text>(t1, Nat.compare, 31);
RBT.equalIncludeDeleted<Nat, Text>(t1, t2, Nat.equal, Text.equal); // false

StableRBTree

type Color = {#R; #B}

type Tree<K, V> = {#node : (Color, Tree<K, V>, (K, ?V), Tree<K, V>); #leaf}

public func init<K, V>() : Tree<K, V>

public func share<K, V>(tree : Tree<K, V>) : Tree<K, V>

public func get<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K) : ?V

public func replace<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K, v : V) : (?V, Tree<K, V>)

public func put<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K, v : V) : Tree<K, V>

public func delete<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K) : Tree<K, V>

public func remove<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K) : (?V, Tree<K, V>)

public func update<K, V>( tree : Tree<K, V>, compareTo : (K, K) -> O.Order, k : K, updateFunction : (?V) -> V) : (?V, Tree<K, V>)

public func split<K, V>(tree : Tree<K, V>, compareTo : (K, K) -> O.Order) : ?(Tree<K, V>, Tree<K, V>)

public func entries<K, V>(tree : Tree<K, V>) : I.Iter<(K, V)>

public func entriesRev<K, V>(tree : Tree<K, V>) : I.Iter<(K, V)>