package core:container/rbtree
Source

⌘K
Ctrl+K
or
/

    Overview

    This package implements a red-black tree

    Index

    Constants (0)

    This section is empty.

    Variables (0)

    This section is empty.

    Procedure Groups (2)

    Types

    Color ¶
    Source

    Color :: enum uintptr {
	Black = 0, 
	Red   = 1, 
}
     

    Might store this in the node pointer in the future, but that'll require a decent amount of rework to pass ^^N instead of ^N

    Related Procedures With Returns

    Direction ¶
    Source

    Direction :: enum i8 {
	// Backward is the in-order backwards direction.
	Backward = -1, 
	// Forward is the in-order forwards direction.
	Forward  = 1, 
}
     

    Direction specifies the traversal direction for a tree iterator.

    Related Procedures With Parameters

    Iterator ¶
    Source

    Iterator :: struct($Key: typeid, $Value: typeid) where intrinsics.type_is_valid_map_key(Key) {}
     

    Iterator is a tree iterator.

    WARNING: It is unsafe to modify the tree while iterating, except via the iterator_remove method.

    Related Procedures With Parameters
    Related Procedures With Returns

    Node ¶
    Source

    Node :: struct($Key: typeid, $Value: typeid) where intrinsics.type_is_valid_map_key(Key) {}
     

    Node is a red-black tree node.

    WARNING: It is unsafe to mutate value if the node is part of a tree if doing so will alter the Node's sort position relative to other elements in the tree.

    Related Procedures With Parameters
    Related Procedures With Returns

    Ordering ¶
    Source

    Ordering :: slice.Ordering

    Tree ¶
    Source

    Tree :: struct($Key: typeid, $Value: typeid) where intrinsics.type_is_valid_map_key(Key) {}
     

    Tree is a red-black tree

    Related Procedures With Parameters

    Constants

    This section is empty.

    Variables

    This section is empty.

    Procedures

    destroy ¶
    Source

    destroy :: proc(t: ^$T/Tree($Key, $Value), call_on_remove: bool = true) {…}
     

    destroy de-initializes a tree.

    find ¶
    Source

    find :: proc(t: ^$T/Tree($Key, $Value), key: $T) -> (node: ^Node($Key, $Value)) {…}
     

    find finds the key in the tree, and returns the corresponding node, or nil iff the value is not present.

    find_or_insert ¶
    Source

    find_or_insert :: proc(t: ^$T/Tree($Key, $Value), key: $T, value: $T) -> (n: ^Node($Key, $Value), inserted: bool, err: runtime.Allocator_Error) {…}
     

    find_or_insert attempts to insert the value into the tree, and returns the node, a boolean indicating if the value was inserted, and the node allocator error if relevant. If the value is already present, the existing node is updated.

    find_value ¶
    Source

    find_value :: proc(t: ^$T/Tree($Key, $Value), key: $T) -> (value: $T, ok: bool) #optional_ok {…}
     

    find_value finds the key in the tree, and returns the corresponding value, or nil iff the value is not present.

    first ¶
    Source

    first :: proc "contextless" (t: ^$T/Tree($Key, $Value)) -> ^Node($Key, $Value) {…}
     

    first returns the first node in the tree (in-order) or nil iff the tree is empty.

    init_cmp ¶
    Source

    init_cmp :: proc(t: ^$T/Tree($Key, $Value), cmp_fn: proc(a, b: $T) -> slice.Ordering, node_allocator := context.allocator) {…}
     

    init_cmp initializes a tree.

    init_ordered ¶
    Source

    init_ordered :: proc(t: ^$T/Tree($Key, $Value), node_allocator := context.allocator) {…}
     

    init_ordered initializes a tree containing ordered keys, with a comparison function that results in an ascending order sort.

    iterator ¶
    Source

    iterator :: proc "contextless" (t: ^$T/Tree($Key, $Value), direction: Direction) -> Iterator($Key, $Value) {…}
     

    iterator returns a tree iterator in the specified direction.

    iterator_from_pos ¶
    Source

    iterator_from_pos :: proc "contextless" (t: ^$T/Tree($Key, $Value), pos: ^Node($Key, $Value), direction: Direction) -> Iterator($Key, $Value) {…}
     

    iterator_from_pos returns a tree iterator in the specified direction, spanning the range [pos, last] (inclusive).

    iterator_get ¶
    Source

    iterator_get :: proc "contextless" (it: ^$I/Iterator($Key, $Value)) -> ^Node($Key, $Value) {…}
     

    iterator_get returns the node currently pointed to by the iterator, or nil iff the node has been removed, the tree is empty, or the end of the tree has been reached.

    iterator_next ¶
    Source

    iterator_next :: proc "contextless" (it: ^$I/Iterator($Key, $Value)) -> (^Node($Key, $Value), bool) {…}
     

    iterator_next advances the iterator and returns the (node, true) or or (nil, false) iff the end of the tree has been reached.

    Note: The first call to iterator_next will return the first node instead of advancing the iterator.

    iterator_remove ¶
    Source

    iterator_remove :: proc(it: ^$I/Iterator($Key, $Value), call_on_remove: bool = true) -> bool {…}
     

    iterator_remove removes the node currently pointed to by the iterator, and returns true iff the removal was successful. Semantics are the same as the Tree remove.

    last ¶
    Source

    last :: proc "contextless" (t: ^$T/Tree($Key, $Value)) -> ^Node($Key, $Value) {…}
     

    last returns the last element in the tree (in-order) or nil iff the tree is empty.

    len ¶
    Source

    len :: proc "contextless" (t: ^$T/Tree($Key, $Value)) -> (node_count: int) {…}

    node_color ¶
    Source

    node_color :: proc(n: ^$N/Node($Key, $Value)) -> (c: Color) {…}

    remove_key ¶
    Source

    remove_key :: proc(t: ^$T/Tree($Key, $Value), key: $T, call_on_remove: bool = true) -> bool {…}
     

    remove_value removes a value from the tree, and returns true iff the removal was successful. While the node's key + value will be left intact, the node itself will be freed via the tree's node allocator.

    remove_node ¶
    Source

    remove_node :: proc(t: ^$T/Tree($Key, $Value), node: ^$N/Node($Key, $Value), call_on_remove: bool = true) -> (found: bool) {…}
     

    remove_node removes a node from the tree, and returns true iff the removal was successful. While the node's key + value will be left intact, the node itself will be freed via the tree's node allocator.

    Procedure Groups

    init ¶
    Source

    init :: proc{
	init_ordered,
	init_cmp,
}
     

    init initializes a tree.

    remove ¶
    Source

    remove :: proc{
	remove_key,
	remove_node,
}
     

    remove removes a node or value from the tree, and returns true iff the removal was successful. While the node's value will be left intact, the node itself will be freed via the tree's node allocator.

    Source Files

    Generation Information

    Generated with odin version dev-2024-11 (vendor "odin") Windows_amd64 @ 2024-11-20 21:11:50.519713800 +0000 UTC