RedBlackTree = type:"RedBlackTree" superTypes:[]

RedBlackTreeNode = type:"RedBlackTreeNode" superTypes:[]
RedBlackTreeEmpty = type:"RedBlackTreeLeaf" superTypes:[RedBlackTreeNode]
RedBlackTreeElem = type:"RedBlackTreeNode" superTypes:[RedBlackTreeNode] # color, left tree, elem, right tree

redBlackTreeWithComparisonFunc:(ltFunc isCallable?) = {
    RedBlackTree(ltFunc, RedBlackTreeEmpty())
}

(t isA: RedBlackTree) isDict? = { .true }

lookup: k in: (t as: RedBlackTree = [ltFunc, node]) = {
    lookup: k inRbNode: node withComparisonFunc:compFunc
}

lookup: k inRbNode: (_ isA: RedBlackTreeEmpty) withComparisonFunc:_ = {
    throw: (NotFound(k))
}

lookup: k inRbNode: (_ as: RedBlackTreeElem = [c, lt, e, rt]) withComparisonFunc:ltFunc = {
    ek = e.key
    switch:[
        [{ltFunc(k, ek)}, {lookup: k inRbNode: lt withComparisonFunc: ltFunc}]
        [{ltFunc(ek, k)}, {lookup: k inRbNode: rt withComparisonFunc: ltFunc}]
        [{.true},         {e.value}]
    ]
}

import stdlib