Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.0

0.6.0 / src / ak / red_black_tree_2.lucb

#==============================================================================================
#
#   red_black_tree_2 - RedBlackTree<K, V> and its iterator
#
#   DESCRIPTION:
#       Port of AK/RedBlackTree.h (lines 433-608). A RedBlackTreeNode[K, V] is its base node
#       followed by the value; the tree owns its nodes (managed memory, freed where the donor
#       deletes them). The iterator walks in key order and is a luce-base iterator:
#       `for value in red_black_tree_begin(&tree)`.
#
#==============================================================================================

# The tree node holding a base node (`static_cast<Node*>`): the base node is its first field.
func rbt_value_node[K, V](node: BaseRedBlackTreeNode[K]*?) -> RedBlackTreeNode[K, V]*?:
    let n = node else return none
    return (RedBlackTreeNode[K, V]*)n

# mark: RedBlackTreeIterator ====================================================================

## Ported from AK/RedBlackTree.h:407 AK::RedBlackTreeIterator::operator!=.
pub func red_black_tree_iterator_ne[K, V](this: const RedBlackTreeIterator[K, V]*, other: RedBlackTreeIterator[K, V]) -> bool:
    return this.m_node != other.m_node

## Ported from AK/RedBlackTree.h:408 AK::RedBlackTreeIterator::operator++.
pub func red_black_tree_iterator_inc[K, V](this: RedBlackTreeIterator[K, V]*) -> RedBlackTreeIterator[K, V]*:
    let node = this.m_node else return this
    this.m_prev = node
    # the complexity is O(logn) for each successor call, but the total complexity for all elements comes out to O(n), meaning the amortized cost for a single call is O(1)
    this.m_node = rbt_value_node[K, V](base_red_black_tree_successor(&node.base))
    return this

## Ported from AK/RedBlackTree.h:417 AK::RedBlackTreeIterator::operator--.
pub func red_black_tree_iterator_dec[K, V](this: RedBlackTreeIterator[K, V]*) -> RedBlackTreeIterator[K, V]*:
    let prev = this.m_prev else return this
    this.m_node = prev
    this.m_prev = rbt_value_node[K, V](base_red_black_tree_predecessor(&prev.base))
    return this

## Ported from AK/RedBlackTree.h:425 AK::RedBlackTreeIterator::operator*.
pub func red_black_tree_iterator_deref[K, V](this: RedBlackTreeIterator[K, V]*) -> V*:
    let node = this.m_node else trap("VERIFY: dereferencing the end of a RedBlackTree")
    return &node.value

## Ported from AK/RedBlackTree.h:426 AK::RedBlackTreeIterator::operator->.
pub func red_black_tree_iterator_arrow[K, V](this: RedBlackTreeIterator[K, V]*) -> V*:
    return red_black_tree_iterator_deref(this)

## Ported from AK/RedBlackTree.h:427 AK::RedBlackTreeIterator::is_end.
pub func red_black_tree_iterator_is_end[K, V](this: const RedBlackTreeIterator[K, V]*) -> bool:
    return this.m_node == none

## Ported from AK/RedBlackTree.h:428 AK::RedBlackTreeIterator::is_begin.
pub func red_black_tree_iterator_is_begin[K, V](this: const RedBlackTreeIterator[K, V]*) -> bool:
    return this.m_prev == none

## Ported from AK/RedBlackTree.h:430 AK::RedBlackTreeIterator::key.
pub func red_black_tree_iterator_key[K, V](this: const RedBlackTreeIterator[K, V]*) -> K:
    let node = this.m_node else trap("VERIFY: key() of the end of a RedBlackTree")
    return node.base.key

## Ported from AK/RedBlackTree.h:434 AK::RedBlackTreeIterator::RedBlackTreeIterator.
pub func red_black_tree_iterator_construct[K, V](this: RedBlackTreeIterator[K, V]*, node: RedBlackTreeNode[K, V]*?, prev: RedBlackTreeNode[K, V]*? = none):
    this.m_node = node
    this.m_prev = prev

## The value the iterator is at, and the iterator moved past it; none at the end (the `for`
## protocol over `*it` and `++it`).
pub func red_black_tree_iterator_next[K, V](this: RedBlackTreeIterator[K, V]*) -> V*?:
    let node = this.m_node else return none
    _ = red_black_tree_iterator_inc(this)
    return &node.value

# mark: RedBlackTree ============================================================================

## Ported from AK/RedBlackTree.h:454 AK::RedBlackTree::find.
pub func red_black_tree_find[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> V*?:
    let node = rbt_value_node[K, V](base_red_black_tree_find(this.base.m_root, key)) else return none
    return &node.value

## Ported from AK/RedBlackTree.h:462 AK::RedBlackTree::find_largest_not_above.
pub func red_black_tree_find_largest_not_above[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> V*?:
    let node = rbt_value_node[K, V](base_red_black_tree_find_largest_not_above(this.base.m_root, key)) else return none
    return &node.value

## Ported from AK/RedBlackTree.h:470 AK::RedBlackTree::find_smallest_not_below.
pub func red_black_tree_find_smallest_not_below[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> V*?:
    let node = rbt_value_node[K, V](base_red_black_tree_find_smallest_not_below(this.base.m_root, key)) else return none
    return &node.value

## Ported from AK/RedBlackTree.h:478 AK::RedBlackTree::try_insert(K, V const&).
pub func red_black_tree_try_insert[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K, value: V) -> !:
    return try red_black_tree_try_insert_2(this, key, value)

## Ported from AK/RedBlackTree.h:483 AK::RedBlackTree::insert(K, V const&).
pub func red_black_tree_insert[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K, value: V):
    red_black_tree_try_insert(this, key, value) else trap("MUST: RedBlackTree::insert")

## Ported from AK/RedBlackTree.h:488 AK::RedBlackTree::try_insert(K, V&&).
pub func red_black_tree_try_insert_2[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K, value: V) -> !:
    var fresh: BaseRedBlackTreeNode[K] = ---
    base_red_black_tree_node_construct_opaque(&fresh, key)
    let node = new RedBlackTreeNode[K, V](base = fresh, value = value) catch:
        return try ak_error_throw(ak_error_from_errno(enomem))
    base_red_black_tree_insert(&this.base, &node.base)

## Ported from AK/RedBlackTree.h:497 AK::RedBlackTree::insert(K, V&&).
pub func red_black_tree_insert_2[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K, value: V):
    red_black_tree_try_insert_2(this, key, value) else trap("MUST: RedBlackTree::insert")

## Ported from AK/RedBlackTree.h:504 AK::RedBlackTree::begin.
pub func red_black_tree_begin[K, V](this: RedBlackTree[K, V]*) -> RedBlackTreeIterator[K, V]:
    return RedBlackTreeIterator[K, V](m_node = rbt_value_node[K, V](this.base.m_minimum), m_prev = none)

## Ported from AK/RedBlackTree.h:505 AK::RedBlackTree::end.
pub func red_black_tree_end[K, V](this: RedBlackTree[K, V]*) -> RedBlackTreeIterator[K, V]:
    _ = this
    return RedBlackTreeIterator[K, V](m_node = none, m_prev = none)

## Ported from AK/RedBlackTree.h:506 AK::RedBlackTree::begin_from.
pub func red_black_tree_begin_from[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> RedBlackTreeIterator[K, V]:
    return RedBlackTreeIterator[K, V](m_node = rbt_value_node[K, V](base_red_black_tree_find(this.base.m_root, key)), m_prev = none)

## Ported from AK/RedBlackTree.h:508 AK::RedBlackTree::find_largest_not_above_iterator.
pub func red_black_tree_find_largest_not_above_iterator[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> RedBlackTreeIterator[K, V]:
    let node = rbt_value_node[K, V](base_red_black_tree_find_largest_not_above(this.base.m_root, key)) else return red_black_tree_end(this)
    return RedBlackTreeIterator[K, V](m_node = node, m_prev = rbt_value_node[K, V](base_red_black_tree_predecessor(&node.base)))

## Ported from AK/RedBlackTree.h:516 AK::RedBlackTree::find_smallest_not_below_iterator.
pub func red_black_tree_find_smallest_not_below_iterator[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> RedBlackTreeIterator[K, V]:
    let node = rbt_value_node[K, V](base_red_black_tree_find_smallest_not_below(this.base.m_root, key)) else return red_black_tree_end(this)
    return RedBlackTreeIterator[K, V](m_node = node, m_prev = rbt_value_node[K, V](base_red_black_tree_predecessor(&node.base)))

## Ported from AK/RedBlackTree.h:526 AK::RedBlackTree::begin const.
pub func red_black_tree_begin_const[K, V](this: const RedBlackTree[K, V]*) -> RedBlackTreeIterator[K, V]:
    return red_black_tree_begin((RedBlackTree[K, V]*)this)

## Ported from AK/RedBlackTree.h:527 AK::RedBlackTree::end const.
pub func red_black_tree_end_const[K, V](this: const RedBlackTree[K, V]*) -> RedBlackTreeIterator[K, V]:
    return red_black_tree_end((RedBlackTree[K, V]*)this)

## Ported from AK/RedBlackTree.h:528 AK::RedBlackTree::begin_from const.
pub func red_black_tree_begin_from_const[K: luce.Comparable, V](this: const RedBlackTree[K, V]*, key: K) -> RedBlackTreeIterator[K, V]:
    return red_black_tree_begin_from((RedBlackTree[K, V]*)this, key)

## Ported from AK/RedBlackTree.h:530 AK::RedBlackTree::find_largest_not_above_iterator const.
pub func red_black_tree_find_largest_not_above_iterator_const[K: luce.Comparable, V](this: const RedBlackTree[K, V]*, key: K) -> RedBlackTreeIterator[K, V]:
    return red_black_tree_find_largest_not_above_iterator((RedBlackTree[K, V]*)this, key)

## Ported from AK/RedBlackTree.h:538 AK::RedBlackTree::find_smallest_not_below_iterator const.
pub func red_black_tree_find_smallest_not_below_iterator_const[K: luce.Comparable, V](this: const RedBlackTree[K, V]*, key: K) -> RedBlackTreeIterator[K, V]:
    return red_black_tree_find_smallest_not_below_iterator((RedBlackTree[K, V]*)this, key)

## Ported from AK/RedBlackTree.h:546 AK::RedBlackTree::unsafe_remove.
pub func red_black_tree_unsafe_remove[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> V:
    let node = base_red_black_tree_find(this.base.m_root, key) else trap("VERIFY: unsafe_remove of a missing key")

    base_red_black_tree_remove(&this.base, node)

    let value_node = (RedBlackTreeNode[K, V]*)node
    let temp = value_node.value

    node.right_child = none
    node.left_child = none
    red_black_tree_delete_node(value_node)

    return temp

## Ported from AK/RedBlackTree.h:562 AK::RedBlackTree::remove.
pub func red_black_tree_remove[K: luce.Comparable, V](this: RedBlackTree[K, V]*, key: K) -> bool:
    let node = base_red_black_tree_find(this.base.m_root, key) else return false

    base_red_black_tree_remove(&this.base, node)

    node.right_child = none
    node.left_child = none
    red_black_tree_delete_node((RedBlackTreeNode[K, V]*)node)

    return true

## Ported from AK/RedBlackTree.h:577 AK::RedBlackTree::clear.
pub func red_black_tree_clear[K, V](this: RedBlackTree[K, V]*):
    if let root = rbt_value_node[K, V](this.base.m_root):
        red_black_tree_delete_node(root)
    this.base.m_root = none
    this.base.m_minimum = none
    this.base.m_size = 0

# RedBlackTree::Node::~Node through `delete`: its children first, then the node.
func red_black_tree_delete_node[K, V](node: RedBlackTreeNode[K, V]*):
    if let left = rbt_value_node[K, V](node.base.left_child):
        red_black_tree_delete_node(left)
    if let right = rbt_value_node[K, V](node.base.right_child):
        red_black_tree_delete_node(right)
    free(node)