core/container/avl

container_avl

Types

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

Source

Originally based on the CC0 implementation by Eric Biggers See: https://github.com/ebiggers/avl_tree/ Direction specifies the traversal direction for a tree iterator.

Iterator :: struct {}Source

Iterator is a tree iterator.

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

Node :: struct {}Source

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.

Ordering :: OrderingSource

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

Tree :: struct {}Source

Tree is an AVL tree.

Procedures

destroy :: proc(t: ^T, call_on_remove: bool)Source

destroy de-initializes a tree.

find :: proc(t: ^T, value: Value) -> (^Node(Value))Source

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 :: proc(t: ^T, value: Value) -> (n: ^Node(Value), inserted: bool, err: runtime.Allocator_Error)Source

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 :: proc(t: ^T) -> (^Node(Value))Source

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

init_cmp :: proc(t: ^T, cmp_fn: proc(a: Value, b: Value) -> (Ordering), node_allocator: mem.Allocator = context.allocator)

Source

init_cmp initializes a tree.

init_ordered :: proc(t: ^T, node_allocator: mem.Allocator = context.allocator)Source

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

iterator :: proc(t: ^T, direction: Direction) -> (Iterator(Value))Source

iterator returns a tree iterator in the specified direction.

iterator_from_pos :: proc(t: ^T, pos: ^Node(Value), direction: Direction) -> (Iterator(Value))Source

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

iterator_get :: proc(it: ^I) -> (^Node(Value))Source

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 :: proc(it: ^I) -> (^Node(Value), bool)Source

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 :: proc(it: ^I, call_on_remove: bool) -> (bool)Source

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 :: proc(t: ^T) -> (^Node(Value))Source

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

len :: proc(t: ^T) -> (int)Source

len returns the number of elements in the tree.

remove_node :: proc(t: ^T, node: ^Node(Value), call_on_remove: bool) -> (bool)Source

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 :: proc(t: ^T, value: Value, call_on_remove: bool) -> (bool)Source

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

init :: proc{init_ordered, init_cmp}Source

init initializes a tree.

remove :: proc{remove_value, remove_node}Source

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.

container_avl

Types

Procedures

Procedure Groups

Find anything

Settings