func NewNode
NewNode creates a new node with the given key and value.
avl source pure
v0 - Unaudited: This is an initial version that has not yet been formally audited. A fully audited version will be pu...
v0 - Unaudited: This is an initial version that has not yet been formally audited. A fully audited version will be published as a subsequent release. Use in production at your own risk.
Package avl provides a gas-efficient AVL tree implementation for storing key-value data in Gno realms.
2
4
type ITree
interface 1type ITree interface {
2 Size() int
3 Has(key string) bool
4 Get(key string) (value any, exists bool)
5 GetByIndex(index int) (key string, value any)
6 Iterate(start, end string, cb IterCbFn) bool
7 ReverseIterate(start, end string, cb IterCbFn) bool
8 IterateByOffset(offset int, count int, cb IterCbFn) bool
9 ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool
10
11 Set(key string, value any) (updated bool)
12 Remove(key string) (value any, removed bool)
13}type IterCbFn
functype Node
struct1type Node struct {
2 key string // key is the unique identifier for the node.
3 value any // value is the data stored in the node.
4 height int8 // height is the height of the node in the tree.
5 size int // size is the number of leaf nodes (key-value pairs) in the subtree rooted at this node.
6 leftNode *Node // leftNode is the left child of the node.
7 rightNode *Node // rightNode is the right child of the node.
8}Node represents a node in an AVL tree.
Methods on Node
func Get
method on NodeGet searches for a node with the given key in the subtree rooted at the node and returns its index, value, and whether it exists.
func GetByIndex
method on NodeGetByIndex retrieves the key-value pair of the node at the given index in the subtree rooted at the node.
func Has
method on NodeHas checks if a node with the given key exists in the subtree rooted at the node.
func IsLeaf
method on NodeIsLeaf checks if the node is a leaf node (has no children).
func Iterate
method on NodeShortcut for TraverseInRange.
func Key
method on NodeKey returns the key of the node.
func Remove
method on NodeRemove deletes the node with the given key from the subtree rooted at the node. returns the new root of the subtree, the new leftmost leaf key (if changed), the removed value and the removal was successful.
func ReverseIterate
method on NodeShortcut for TraverseInRange.
func Set
method on NodeSet inserts a new node with the given key-value pair into the subtree rooted at the node, and returns the new root of the subtree and whether an existing node was updated.
XXX consider a better way to do this... perhaps split Node from Node.
func Size
method on NodeSize returns the size of the subtree rooted at the node.
func TraverseByOffset
method on Node1func (node *Node) TraverseByOffset(offset, limit int, ascending bool, leavesOnly bool, cb func(*Node) bool) boolTraverseByOffset traverses all nodes, including inner nodes. A limit of math.MaxInt means no limit.
func TraverseInRange
method on Node1func (node *Node) TraverseInRange(start, end string, ascending bool, leavesOnly bool, cb func(*Node) bool) boolTraverseInRange traverses all nodes, including inner nodes. Start is inclusive and end is exclusive when ascending, Start and end are inclusive when descending. Empty start and empty end denote no start and no end. If leavesOnly is true, only visit leaf nodes. NOTE: To simulate an exclusive reverse traversal, just append 0x00 to start.
func Value
method on NodeValue returns the value of the node.
type Tree
structThe zero struct can be used as an empty tree.
Methods on Tree
func Get
method on TreeGet retrieves the value associated with the given key. It returns the value and a boolean indicating whether the key exists.
func GetByIndex
method on TreeGetByIndex retrieves the key-value pair at the specified index in the tree. It returns the key and value at the given index.
func Has
method on TreeHas checks whether a key exists in the tree. It returns true if the key exists, otherwise false.
func Iterate
method on TreeIterate performs an in-order traversal of the tree within the specified key range. It calls the provided callback function for each key-value pair encountered. If the callback returns true, the iteration is stopped.
func IterateByOffset
method on TreeIterateByOffset performs an in-order traversal of the tree starting from the specified offset. It calls the provided callback function for each key-value pair encountered, up to the specified count. If the callback returns true, the iteration is stopped.
func Remove
method on TreeRemove removes a key-value pair from the tree. It returns the removed value and a boolean indicating whether the key was found and removed.
func ReverseIterate
method on TreeReverseIterate performs a reverse in-order traversal of the tree within the specified key range. It calls the provided callback function for each key-value pair encountered. If the callback returns true, the iteration is stopped.
func ReverseIterateByOffset
method on TreeReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset. It calls the provided callback function for each key-value pair encountered, up to the specified count. If the callback returns true, the iteration is stopped.
func Set
method on TreeSet inserts a key-value pair into the tree. If the key already exists, the value will be updated. It returns a boolean indicating whether the key was newly inserted or updated.
func Size
method on TreeSize returns the number of key-value pair in the tree.
