package core:container/avl
Source

⌘K
Ctrl+K
or
/

    Overview

    package avl implements an AVL tree.

    The implementation is non-intrusive, and non-recursive.

    Index

    Constants (0)

    This section is empty.

    Variables (0)

    This section is empty.

    Procedure Groups (2)

    Types

    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($Value: typeid) {}
     

    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($Value: typeid) {}
     

    Node is an AVL 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
     

    Ordering specifies order when inserting/finding values into the tree.

    Tree ¶
    Source

    Tree :: struct($Value: typeid) {}
     

    Tree is an AVL tree.

    Related Procedures With Parameters

    Constants

    This section is empty.

    Variables

    This section is empty.

    Procedures

    destroy ¶
    Source

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

    destroy de-initializes a tree.

    find ¶
    Source

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

    find finds the value 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($Value), value: $T) -> (n: ^Node($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 returned un-altered.

    first ¶
    Source

    first :: proc "contextless" (t: ^$T/Tree($Value)) -> ^Node($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($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($Value), node_allocator := context.allocator) {…}
     

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

    iterator ¶
    Source

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

    iterator returns a tree iterator in the specified direction.

    iterator_from_pos ¶
    Source

    iterator_from_pos :: proc "contextless" (t: ^$T/Tree($Value), pos: ^Node($Value), direction: Direction) -> Iterator($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($Value)) -> ^Node($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($Value)) -> (^Node($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($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($Value)) -> ^Node($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($Value)) -> int {…}
     

    len returns the number of elements in the tree.

    remove_node ¶
    Source

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

    remove_node removes a node 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.

    remove_value ¶
    Source

    remove_value :: proc(t: ^$T/Tree($Value), value: $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 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_value,
	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-16 21:10:09.799411800 +0000 UTC