package core:container/rbtree
Overview
This package implements a red-black tree
Index
Constants (0)
This section is empty.
Variables (0)
This section is empty.
Types
Color ¶
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 ¶
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($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 ¶
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
- iterator_from_pos
- node_color
- remove_node
- remove (procedure groups)
Related Procedures With Returns
Ordering ¶
Ordering :: slice.Ordering
Tree ¶
Tree :: struct($Key: typeid, $Value: typeid) where intrinsics.type_is_valid_map_key(Key) {}
Tree is a red-black tree
Related Procedures With Parameters
- destroy
- find
- find_or_insert
- find_value
- first
- init_cmp
- init_ordered
- iterator
- iterator_from_pos
- last
- len
- remove_key
- remove_node
- init (procedure groups)
- remove (procedure groups)
Constants
This section is empty.
Variables
This section is empty.
Procedures
destroy ¶
destroy de-initializes a tree.
find ¶
find finds the key 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($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 ¶
find_value finds the key in the tree, and returns the corresponding value, or nil iff the value is not present.
first ¶
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($Key, $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($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 ¶
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 ¶
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 ¶
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($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 ¶
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 returns the last element in the tree (in-order) or nil iff the tree is empty.
remove_key ¶
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 ¶
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
remove ¶
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-09 (vendor "odin") Windows_amd64 @ 2024-09-07 21:12:27.267759600 +0000 UTC