A non-intrusive and non-recursive implementation of `AVL` trees.

Collection Info

View Source
Collection
core
Path
container/avl
Entries
22
Constants 0
Types 5
Jump to Types
Direction Iterator Node Ordering Tree
Procedures 15
Jump to Procedures
destroy find find_or_insert first init_cmp init_ordered iterator iterator_from_pos iterator_get iterator_next iterator_remove last len remove_node remove_value
Procedure Groups 2
Jump to Procedure Groups
init remove
Variables 0

Source Files

Types

5

Iterator #

Source 
Iterator :: Iterator

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

Node #

Source 
Node :: Node

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.

Procedures

15

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: $Value) -> $$deferred_return {…}

find finds the value in the tree, and returns the corresponding node or nil if and only if (⟺) the value is not present.

find_or_insert #

Source 
find_or_insert :: proc(t: ^$T/Tree($Value), value: $Value) -> (n: $$deferred_return, inserted: bool, err: 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)) -> $$deferred_return {…}

first returns the first node in the tree (in-order) or nil if and only if (⟺) the tree is empty.

init_cmp #

Source 
init_cmp :: proc(t: ^$T/Tree($Value), cmp_fn: proc(a, b: $Value) -> 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) -> $$deferred_return {…}

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) -> $$deferred_return {…}

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)) -> $$deferred_return {…}

iterator_get returns the node currently pointed to by the iterator, or nil if and only if (⟺) 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)) -> ($$deferred_return, bool) {…}

iterator_next advances the iterator and returns the (node, true) or or (nil, false) if and only if (⟺) 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 if and only if (⟺) the removal was successful. Semantics are the same as the Tree remove.

last #

Source 
last :: proc "contextless" (t: ^$T/Tree($Value)) -> $$deferred_return {…}

last returns the last element in the tree (in-order) or nil if and only if (⟺) 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 if and only if (⟺) 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: $Value, call_on_remove: bool = true) -> bool {…}

remove_value removes a value from the tree, and returns true if and only if (⟺) 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

2

remove #

Source 
remove :: proc{
	remove_value,
	remove_node,
}

remove removes a node or value from the tree, and returns true if and only if (⟺) 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.