8C7519559AFDB0…CE6F8C7FA20D

Arguments · 13

1. #1trie
2. #2README.md
3. #3# 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`](https://gno.land/p/nt/avl/v0$source&file=tree.gno) 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](https://github.com/jeronimoalbi/gnome), as part of `jeronimoalbi`'s Gno smart contracts monorepo. ## Usage [embedmd]:# (filetests/readme_filetest.gno go) ```go package main import "gno.land/p/jeronimoalbi/trie" func main() { tree := trie.NewTree() tree.Set("apple", 1) tree.Set("app", 2) tree.Set("banana", 3) // Get value for app v := tree.Get("app") println(v) // Iterate keys in lexicographic order: app, apple, banana. tree.Iterate("", "", func(key string, value any) bool { println(key, value) return false }) } // Output: // 2 // app 2 // apple 1 // banana 3 ```
4. #4doc.gno
5. #5// 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. package trie
6. #6gnomod.toml
7. #7module = "gno.land/p/jeronimoalbi/trie" gno = "0.9"
8. #8node.gno
9. #9package trie // node is a single position in the trie tree type node struct { char byte // node's char, unused in the root node value any // node's value, stored when isKey is true isKey bool // whether a key terminates at this node children []*node // child nodes, kept sorted ascending by char } // childIndex returns the index of the child reached by byte c and whether such // a child exists. When it does not exist, the returned index is the position at // which a child with byte c must be inserted to keep children sorted. func (n *node) childIndex(c byte) (int, bool) { lo := 0 hi := len(n.children) for lo < hi { mid := (lo + hi) / 2 switch { case n.children[mid].char < c: lo = mid + 1 case n.children[mid].char > c: hi = mid default: return mid, true } } return lo, false } // get retrieves the value stored under key in the subtree rooted at n. func (n *node) get(key string) (value any, exists bool) { cur := n for i := 0; i < len(key); i++ { idx, ok := cur.childIndex(key[i]) if !ok { return nil, false } cur = cur.children[idx] } if !cur.isKey { return nil, false } return cur.value, true } // set inserts or updates key with value. It returns true when the key already // existed and its value updated, and false when it was newly inserted. func (n *node) set(key string, value any) (updated bool) { cur := n for i := 0; i < len(key); i++ { c := key[i] idx, ok := cur.childIndex(c) if ok { cur = cur.children[idx] continue } child := &node{char: c} cur.children = append(cur.children, nil) copy(cur.children[idx+1:], cur.children[idx:]) cur.children[idx] = child cur = child } if cur.isKey { cur.value = value return true } cur.isKey = true cur.value = value return false } // remove deletes key from the subtree rooted at n, pruning any nodes that no // longer terminate a key and have no children. It returns the removed value and // whether the key was found. func (n *node) remove(key string) (value any, removed bool) { if key == "" { if !n.isKey { return nil, false } value = n.value n.isKey = false n.value = nil return value, true } idx, ok := n.childIndex(key[0]) if !ok { return nil, false } child := n.children[idx] value, removed = child.remove(key[1:]) if removed && !child.isKey && len(child.children) == 0 { n.children = append(n.children[:idx], n.children[idx+1:]...) } return value, removed } // inorder visits this node (when it terminates a key) and its whole subtree. // key is the full key spelled from the root to this node. When ascending is // true keys are produced in lexicographic order, otherwise in reverse. Because // a key always sorts before any key that extends it, the terminal value is // emitted before the children when ascending and after them when descending. // It returns true as soon as cb requests the walk to stop. func (n *node) inorder(key string, ascending bool, cb func(key string, value any) bool) (stop bool) { if ascending { if n.isKey && cb(key, n.value) { return true } for _, c := range n.children { if c.inorder(key+string([]byte{c.char}), ascending, cb) { return true } } return false } for i := len(n.children) - 1; i >= 0; i-- { c := n.children[i] if c.inorder(key+string([]byte{c.char}), ascending, cb) { return true } } if n.isKey && cb(key, n.value) { return true } return false }
10. #10tree.gno
11. #11package trie import "gno.land/p/nt/avl/v0" // Verify that Tree implements the ITree interface. var _ avl.ITree = (*Tree)(nil) // Tree 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. type Tree struct { root *node size int } // NewTree creates a new empty trie tree. func NewTree() *Tree { return &Tree{root: &node{}} } // Size returns the number of key-value pairs stored in the tree. func (t *Tree) Size() int { return t.size } // Has reports whether key exists in the tree. func (t *Tree) Has(key string) bool { if t.root == nil { return false } _, exists := t.root.get(key) return exists } // Get retrieves the value associated with key. func (t *Tree) Get(key string) any { if t.root == nil { return nil } v, _ := t.root.get(key) return v } // GetByIndex retrieves the key-value pair at the given index // in lexicographic order. It panics if index is out of range. func (t *Tree) GetByIndex(index int) (key string, value any) { if index < 0 || index >= t.size { panic("trie: index out of range") } i := 0 t.root.inorder("", true, func(k string, v any) bool { if i == index { key, value = k, v return true } i++ return false }) return key, value } // Set 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 (t *Tree) Set(key string, value any) (updated bool) { if t.root == nil { t.root = &node{} } updated = t.root.set(key, value) if !updated { t.size++ } return updated } // Remove deletes the pair stored under key. // It returns the removed value and whether the key was found and removed. func (t *Tree) Remove(key string) (value any, removed bool) { if t.root == nil { return nil, false } value, removed = t.root.remove(key) if removed { t.size-- } return value, removed } // Iterate 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 (t *Tree) Iterate(start, end string, cb avl.IterCbFn) bool { if t.root == nil { return false } return t.root.inorder("", true, func(key string, value any) bool { if start != "" && key < start { return false } if end != "" && key >= end { return false } return cb(key, value) }) } // ReverseIterate 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 (t *Tree) ReverseIterate(start, end string, cb avl.IterCbFn) bool { if t.root == nil { return false } return t.root.inorder("", false, func(key string, value any) bool { if start != "" && key < start { return false } if end != "" && key > end { return false } return cb(key, value) }) } // IterateByOffset 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 (t *Tree) IterateByOffset(offset int, count int, cb avl.IterCbFn) bool { return t.iterateByOffset(offset, count, true, cb) } // ReverseIterateByOffset 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 (t *Tree) ReverseIterateByOffset(offset int, count int, cb avl.IterCbFn) bool { return t.iterateByOffset(offset, count, false, cb) } func (t *Tree) iterateByOffset(offset, count int, ascending bool, cb avl.IterCbFn) bool { if t.root == nil || count <= 0 { return false } skipped, emitted := 0, 0 stopped := false t.root.inorder("", ascending, func(key string, value any) bool { if skipped < offset { skipped++ return false } stopped = cb(key, value) emitted++ return stopped || emitted >= count }) return stopped }
12. #12/gno.MemPackageType
13. #13 MPUserAll