package core:container/avl

⌘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 ¶

    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 ¶

    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 ¶

    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 ¶

    Ordering :: slice.Ordering
     

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

    Tree ¶

    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 ¶

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

    destroy de-initializes a tree.

    find ¶

    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 ¶

    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 ¶

    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 ¶

    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 ¶

    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 ¶

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

    iterator returns a tree iterator in the specified direction.

    iterator_from_pos ¶

    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 ¶

    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 ¶

    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 ¶

    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 ¶

    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 ¶

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

    len returns the number of elements in the tree.

    remove_node ¶

    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 ¶

    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 ¶

    init :: proc{
    	init_ordered,
    	init_cmp,
    }
    
     

    init initializes a tree.

    remove ¶

    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-04 (vendor "odin") Windows_amd64 @ 2024-04-23 21:09:30.012537700 +0000 UTC