func NewTree
NewTree creates a new empty trie tree.
trie source pure
Package trie provides a simple prefix-tree (trie) for storing key-value data in Gno realms.
View source
Trie Package
Package implements a simple prefix-tree (trie) for Gno realms, keyed by
string with values of any type.
Tree implements the avl.ITree
interface from gno.land/p/nt/avl, so it can be used as a drop-in alternative
to an AVL tree.
Repository can be found at jeronimoalbi/gnome,
as part of jeronimoalbi's Gno smart contracts monorepo.
Usage
1package main
2
3import "gno.land/p/jeronimoalbi/trie"
4
5func main() {
6 tree := trie.NewTree()
7 tree.Set("apple", 1)
8 tree.Set("app", 2)
9 tree.Set("banana", 3)
10
11 // Get value for app
12 v := tree.Get("app")
13 println(v)
14
15 // Iterate keys in lexicographic order: app, apple, banana.
16 tree.Iterate("", "", func(key string, value any) bool {
17 println(key, value)
18 return false
19 })
20}
21
22// Output:
23// 2
24// app 2
25// apple 1
26// banana 3
Package trie provides a simple prefix-tree (trie) for storing key-value data in Gno realms.
Keys are strings ordered lexicographically by their raw bytes and values can be of any type. Tree implements the avl.ITree interface from `gno.land/p/nt/avl`, so it can be used as an alternative to an AVL tree.
1
1
type Tree
structTree is a prefix tree (trie) keyed by string with values of any type. It implements the avl.ITree interface, so it can be used as a drop-in alternative to an AVL tree. Keys are ordered lexicographically by theiri raw bytes.
The zero Tree is an empty, ready-to-use tree.
Methods on Tree
func Get
method on TreeGet retrieves the value associated with key.
func GetByIndex
method on TreeGetByIndex retrieves the key-value pair at the given index in lexicographic order. It panics if index is out of range.
func Has
method on TreeHas reports whether key exists in the tree.
func Iterate
method on TreeIterate performs an in-order (ascending) traversal over the keys in the range [start, end), start is inclusive and end is exclusive. An empty start or end means unbounded on that side. Iteration stops when the callback returns true, the method returns whether it was stopped that way.
func IterateByOffset
method on TreeIterateByOffset performs an in-order (ascending) traversal that skips the first offset keys and then visits up to count keys. Iteration stops early when the callback returns true, the method returns whether it was stopped that way.
func Remove
method on TreeRemove deletes the pair stored under key. It returns the removed value and whether the key was found and removed.
func ReverseIterate
method on TreeReverseIterate performs a reverse in-order (descending) traversal over the keys in the range [start, end], where both start and end are inclusive. An empty start or end means unbounded on that side. Iteration stops when the callback returns true; the method returns whether it was stopped that way.
func ReverseIterateByOffset
method on TreeReverseIterateByOffset performs a reverse in-order (descending) traversal that skips the first offset keys and then visits up to count keys. Iteration stops early when the callback returns true; the method returns whether it was stopped that way.
func Set
method on TreeSet inserts or updates a key-value pair. It returns true when the key already existed and its value was updated, and false when the key was newly inserted.
func Size
method on TreeSize returns the number of key-value pairs stored in the tree.
