Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / red_black_tree_1.lucb

#==============================================================================================
#
#   red_black_tree_1 - BaseRedBlackTree<K>: the balancing shared by RedBlackTree and
#                      IntrusiveRedBlackTree
#
#   DESCRIPTION:
#       Port of AK/RedBlackTree.h (lines 1-432). K is an integral key compared with
#       `compare` (`K: Comparable`). Nodes are BaseRedBlackTreeNode[K]; the trees that derive
#       from the base embed it (and their nodes embed the base node) as their first field, so
#       the base functions are reached through a cast, as the donor's static_casts do.
#
#==============================================================================================

# The node's key compared with `key`: negative, zero or positive.
func red_black_tree_key_compare[K: luce.Comparable](a: K, b: K) -> i64:
    return a.compare(b)

## Ported from AK/RedBlackTree.h:22 AK::BaseRedBlackTree::size.
pub func base_red_black_tree_size[K](this: const BaseRedBlackTree[K]*) -> usize:
    return this.m_size

## Ported from AK/RedBlackTree.h:23 AK::BaseRedBlackTree::is_empty.
pub func base_red_black_tree_is_empty[K](this: const BaseRedBlackTree[K]*) -> bool:
    return this.m_size == 0

## Ported from AK/RedBlackTree.h:38 AK::BaseRedBlackTree::Node::Node(K key).
pub func base_red_black_tree_node_construct_opaque[K](this: BaseRedBlackTreeNode[K]*, key: K):
    this.left_child = none
    this.right_child = none
    this.parent = none
    this.color = RedBlackTreeColor.red
    this.key = key

## Ported from AK/RedBlackTree.h:42 AK::BaseRedBlackTree::Node::Node(): the key is left as is.
pub func base_red_black_tree_node_construct[K](this: BaseRedBlackTreeNode[K]*):
    this.left_child = none
    this.right_child = none
    this.parent = none
    this.color = RedBlackTreeColor.red

## Ported from AK/RedBlackTree.h:52 AK::BaseRedBlackTree::rotate_left.
pub func base_red_black_tree_rotate_left[K](this: BaseRedBlackTree[K]*, subtree_root: BaseRedBlackTreeNode[K]*):
    let pivot = subtree_root.right_child else trap("VERIFY: rotate_left without a right child")
    let parent = subtree_root.parent

    # stage 1 - subtree_root's right child is now pivot's left child
    subtree_root.right_child = pivot.left_child
    if let right = subtree_root.right_child:
        right.parent = subtree_root

    # stage 2 - pivot's left child is now subtree_root
    pivot.left_child = subtree_root
    subtree_root.parent = pivot

    # stage 3 - update pivot's parent
    pivot.parent = parent
    if let p = parent:
        if p.left_child == (BaseRedBlackTreeNode[K]*?)subtree_root:  # we are the left child
            p.left_child = pivot
        # we are the right child
        else:
            p.right_child = pivot
    # new root
    else:
        this.m_root = pivot

## Ported from AK/RedBlackTree.h:79 AK::BaseRedBlackTree::rotate_right.
pub func base_red_black_tree_rotate_right[K](this: BaseRedBlackTree[K]*, subtree_root: BaseRedBlackTreeNode[K]*):
    let pivot = subtree_root.left_child else trap("VERIFY: rotate_right without a left child")
    let parent = subtree_root.parent

    # stage 1 - subtree_root's left child is now pivot's right child
    subtree_root.left_child = pivot.right_child
    if let left = subtree_root.left_child:
        left.parent = subtree_root

    # stage 2 - pivot's right child is now subtree_root
    pivot.right_child = subtree_root
    subtree_root.parent = pivot

    # stage 3 - update pivot's parent
    pivot.parent = parent
    if let p = parent:
        if p.left_child == (BaseRedBlackTreeNode[K]*?)subtree_root:  # we are the left child
            p.left_child = pivot
        # we are the right child
        else:
            p.right_child = pivot
    # new root
    else:
        this.m_root = pivot

## Ported from AK/RedBlackTree.h:106 AK::BaseRedBlackTree::find.
pub func base_red_black_tree_find[K: luce.Comparable](node: BaseRedBlackTreeNode[K]*?, key: K) -> BaseRedBlackTreeNode[K]*?:
    var current = node
    while let n = current:
        if red_black_tree_key_compare(n.key, key) == 0:
            break
        if red_black_tree_key_compare(key, n.key) < 0:
            current = n.left_child
        else:
            current = n.right_child
    return current

## Ported from AK/RedBlackTree.h:118 AK::BaseRedBlackTree::find_largest_not_above.
pub func base_red_black_tree_find_largest_not_above[K: luce.Comparable](node: BaseRedBlackTreeNode[K]*?, key: K) -> BaseRedBlackTreeNode[K]*?:
    var candidate: BaseRedBlackTreeNode[K]*? = none
    var current = node
    while let n = current:
        if red_black_tree_key_compare(key, n.key) == 0:
            return n
        if red_black_tree_key_compare(key, n.key) < 0:
            current = n.left_child
        else:
            candidate = n
            current = n.right_child
    return candidate

## Ported from AK/RedBlackTree.h:134 AK::BaseRedBlackTree::find_smallest_not_below.
pub func base_red_black_tree_find_smallest_not_below[K: luce.Comparable](node: BaseRedBlackTreeNode[K]*?, key: K) -> BaseRedBlackTreeNode[K]*?:
    var candidate: BaseRedBlackTreeNode[K]*? = none
    var current = node
    while let n = current:
        if red_black_tree_key_compare(n.key, key) == 0:
            return n

        if red_black_tree_key_compare(n.key, key) <= 0:
            current = n.right_child
        else:
            candidate = n
            current = n.left_child
    return candidate

## Ported from AK/RedBlackTree.h:151 AK::BaseRedBlackTree::insert.
pub func base_red_black_tree_insert[K: luce.Comparable](this: BaseRedBlackTree[K]*, node: BaseRedBlackTreeNode[K]*):
    var parent: BaseRedBlackTreeNode[K]*? = none
    var temp = this.m_root
    while let t = temp:
        parent = t
        if red_black_tree_key_compare(node.key, t.key) < 0:
            temp = t.left_child
        else:
            temp = t.right_child
    if parent == none:  # new root
        node.color = RedBlackTreeColor.black
        this.m_root = node
        this.m_size = 1
        this.m_minimum = node
        return
    let p = parent else trap("unreachable")
    if red_black_tree_key_compare(node.key, p.key) < 0:  # we are the left child
        p.left_child = node
    # we are the right child
    else:
        p.right_child = node
    node.parent = p

    if p.parent != none:  # no fixups to be done for a height <= 2 tree
        base_red_black_tree_insert_fixups(this, node)

    this.m_size += 1
    let minimum = this.m_minimum else trap("VERIFY: tree without a minimum")
    if minimum.left_child == (BaseRedBlackTreeNode[K]*?)node:
        this.m_minimum = node

# The parent of a node that is known to have one.
func rbt_parent[K](node: BaseRedBlackTreeNode[K]*) -> BaseRedBlackTreeNode[K]*:
    return node.parent else trap("VERIFY: red-black tree node without a parent")

## Ported from AK/RedBlackTree.h:184 AK::BaseRedBlackTree::insert_fixups.
pub func base_red_black_tree_insert_fixups[K](this: BaseRedBlackTree[K]*, node_: BaseRedBlackTreeNode[K]*):
    assert(node_.color == RedBlackTreeColor.red)
    var node = node_
    while true:
        let node_parent = node.parent else break
        if node_parent.color != RedBlackTreeColor.red:
            break
        let grand_parent = rbt_parent(node_parent)
        if grand_parent.right_child == (BaseRedBlackTreeNode[K]*?)node_parent:
            let uncle = grand_parent.left_child
            if not rbt_is_black(uncle):
                node_parent.color = RedBlackTreeColor.black
                rbt_node(uncle).color = RedBlackTreeColor.black
                grand_parent.color = RedBlackTreeColor.red
                node = grand_parent
            else:
                if node_parent.left_child == (BaseRedBlackTreeNode[K]*?)node:
                    node = node_parent
                    base_red_black_tree_rotate_right(this, node)
                rbt_parent(node).color = RedBlackTreeColor.black
                grand_parent.color = RedBlackTreeColor.red
                base_red_black_tree_rotate_left(this, grand_parent)
        else:
            let uncle = grand_parent.right_child
            if not rbt_is_black(uncle):
                node_parent.color = RedBlackTreeColor.black
                rbt_node(uncle).color = RedBlackTreeColor.black
                grand_parent.color = RedBlackTreeColor.red
                node = grand_parent
            else:
                if node_parent.right_child == (BaseRedBlackTreeNode[K]*?)node:
                    node = node_parent
                    base_red_black_tree_rotate_left(this, node)
                rbt_parent(node).color = RedBlackTreeColor.black
                grand_parent.color = RedBlackTreeColor.red
                base_red_black_tree_rotate_right(this, grand_parent)
    let root = this.m_root else trap("VERIFY: tree without a root")
    root.color = RedBlackTreeColor.black  # the root should always be black

## Ported from AK/RedBlackTree.h:226 AK::BaseRedBlackTree::remove.
pub func base_red_black_tree_remove[K](this: BaseRedBlackTree[K]*, node: BaseRedBlackTreeNode[K]*):
    let self_node: BaseRedBlackTreeNode[K]*? = node

    # special case: deleting the only node
    if this.m_size == 1:
        this.m_root = none
        this.m_minimum = none
        this.m_size = 0
        return

    if this.m_minimum == self_node:
        this.m_minimum = base_red_black_tree_successor(node)

    # removal assumes the node has 0 or 1 child, so if we have 2, relink with the successor first (by definition the successor has no left child)
    # FIXME: since we dont know how a value is represented in the node, we can't simply swap the values and keys, and instead we relink the nodes
    #  in place, this is quite a bit more expensive, as well as much less readable, is there a better way?
    if node.left_child != none and node.right_child != none:
        let node_left = node.left_child else trap("unreachable")
        let node_right = node.right_child else trap("unreachable")
        # this is always non-null as all nodes besides the maximum node have a successor, and the maximum node has no right child
        let successor_node = base_red_black_tree_successor(node) else trap("VERIFY: no successor")
        let neighbor_swap = successor_node.parent == self_node
        node_left.parent = successor_node
        if not neighbor_swap:
            node_right.parent = successor_node
        if let parent = node.parent:
            if parent.left_child == self_node:
                parent.left_child = successor_node
            else:
                parent.right_child = successor_node
        else:
            this.m_root = successor_node
        if let successor_right = successor_node.right_child:
            successor_right.parent = node
        if neighbor_swap:
            successor_node.parent = node.parent
            node.parent = successor_node
        else:
            if let successor_parent = successor_node.parent:
                if successor_parent.left_child == (BaseRedBlackTreeNode[K]*?)successor_node:
                    successor_parent.left_child = node
                else:
                    successor_parent.right_child = node
            else:
                this.m_root = node
            swap_5(&node.parent, &successor_node.parent)
        swap_5(&node.left_child, &successor_node.left_child)
        if neighbor_swap:
            node.right_child = successor_node.right_child
            successor_node.right_child = node
        else:
            swap_5(&node.right_child, &successor_node.right_child)
        swap_5(&node.color, &successor_node.color)

    let child = node.left_child if node.left_child != none else node.right_child

    if let c = child:
        c.parent = node.parent
    if let parent = node.parent:
        if parent.left_child == self_node:
            parent.left_child = child
        else:
            parent.right_child = child
    else:
        this.m_root = child

    # if the node is red then child must be black, and just replacing the node with its child should result in a valid tree (no change to black height)
    if node.color != RedBlackTreeColor.red:
        base_red_black_tree_remove_fixups(this, child, node.parent)

    this.m_size -= 1

# Whether a possibly-null node is black (a null node counts as black).
func rbt_is_black[K](node: BaseRedBlackTreeNode[K]*?) -> bool:
    let n = node else return true
    return n.color == RedBlackTreeColor.black

# The node, known to be non-null.
func rbt_node[K](node: BaseRedBlackTreeNode[K]*?) -> BaseRedBlackTreeNode[K]*:
    return node else trap("VERIFY: red-black tree node is null")

## Ported from AK/RedBlackTree.h:307 AK::BaseRedBlackTree::remove_fixups.
# We maintain parent as a separate argument since node might be null
pub func base_red_black_tree_remove_fixups[K](this: BaseRedBlackTree[K]*, node_: BaseRedBlackTreeNode[K]*?, parent_: BaseRedBlackTreeNode[K]*?):
    var node = node_
    var parent = parent_
    while node != this.m_root and rbt_is_black(node):
        let p = rbt_node(parent)
        if p.left_child == node:
            var sibling = rbt_node(p.right_child)
            if sibling.color == RedBlackTreeColor.red:
                sibling.color = RedBlackTreeColor.black
                p.color = RedBlackTreeColor.red
                base_red_black_tree_rotate_left(this, p)
                sibling = rbt_node(p.right_child)
            if rbt_is_black(sibling.left_child) and rbt_is_black(sibling.right_child):
                sibling.color = RedBlackTreeColor.red
                node = p
            else:
                if rbt_is_black(sibling.right_child):
                    rbt_node(sibling.left_child).color = RedBlackTreeColor.black  # null check?
                    sibling.color = RedBlackTreeColor.red
                    base_red_black_tree_rotate_right(this, sibling)
                    sibling = rbt_node(p.right_child)
                sibling.color = p.color
                p.color = RedBlackTreeColor.black
                rbt_node(sibling.right_child).color = RedBlackTreeColor.black  # null check?
                base_red_black_tree_rotate_left(this, p)
                node = this.m_root  # fixed
        else:
            var sibling = rbt_node(p.left_child)
            if sibling.color == RedBlackTreeColor.red:
                sibling.color = RedBlackTreeColor.black
                p.color = RedBlackTreeColor.red
                base_red_black_tree_rotate_right(this, p)
                sibling = rbt_node(p.left_child)
            if rbt_is_black(sibling.left_child) and rbt_is_black(sibling.right_child):
                sibling.color = RedBlackTreeColor.red
                node = p
            else:
                if rbt_is_black(sibling.left_child):
                    rbt_node(sibling.right_child).color = RedBlackTreeColor.black  # null check?
                    sibling.color = RedBlackTreeColor.red
                    base_red_black_tree_rotate_left(this, sibling)
                    sibling = rbt_node(p.left_child)
                sibling.color = p.color
                p.color = RedBlackTreeColor.black
                rbt_node(sibling.left_child).color = RedBlackTreeColor.black  # null check?
                base_red_black_tree_rotate_right(this, p)
                node = this.m_root  # fixed
        parent = rbt_node(node).parent
    rbt_node(node).color = RedBlackTreeColor.black  # by this point node can't be null

## Ported from AK/RedBlackTree.h:364 AK::BaseRedBlackTree::successor.
pub func base_red_black_tree_successor[K](node_: BaseRedBlackTreeNode[K]*) -> BaseRedBlackTreeNode[K]*?:
    var node = node_
    if let right = node.right_child:
        node = right
        while let left = node.left_child:
            node = left
        return node
    var temp = node.parent
    while let t = temp:
        if t.right_child != (BaseRedBlackTreeNode[K]*?)node:
            break
        node = t
        temp = t.parent
    return temp

## Ported from AK/RedBlackTree.h:381 AK::BaseRedBlackTree::predecessor.
pub func base_red_black_tree_predecessor[K](node_: BaseRedBlackTreeNode[K]*) -> BaseRedBlackTreeNode[K]*?:
    var node = node_
    if let left = node.left_child:
        node = left
        while let right = node.right_child:
            node = right
        return node
    var temp = node.parent
    while let t = temp:
        if t.left_child != (BaseRedBlackTreeNode[K]*?)node:
            break
        node = t
        temp = t.parent
    return temp