RBTree

Red-Black Trees

Color

type Color = {#R : (); #B : ()}

Tree

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

RBTree

class RBTree<X, Y>(compareTo : (X, X) -> O.Order)

share

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

func share() : Tree<X, Y>

get

func get(x : X) : ?Y

replace

func replace(x : X, y : Y) : ?Y

put

func put(x : X, y : Y)

delete

func delete(x : X) : ?Y

entries

func entries() : I.Iter<(X, Y)>

entriesRev

func entriesRev() : I.Iter<(X, Y)>

iter

func iter<X, Y>(t : Tree<X, Y>, dir : {#fwd : (); #bwd : ()}) : I.Iter<(X, Y)>

height

func height<X, Y>(t : Tree<X, Y>) : Nat

size

func size<X, Y>(t : Tree<X, Y>) : Nat