1package trie23import "gno.land/p/nt/avl/v0"45// Verify that Tree implements the ITree interface.6var _ avl.ITree = (*Tree)(nil)78// Tree is a prefix tree (trie) keyed by string with values of any type.9// It implements the avl.ITree interface, so it can be used as a drop-in10// alternative to an AVL tree. Keys are ordered lexicographically by theiri11// raw bytes.12//13// The zero Tree is an empty, ready-to-use tree.14type Tree struct {15 root *node16 size int17}1819// NewTree creates a new empty trie tree.20func NewTree() *Tree {21 return &Tree{root: &node{}}22}2324// Size returns the number of key-value pairs stored in the tree.25func (t *Tree) Size() int {26 return t.size27}2829// Has reports whether key exists in the tree.30func (t *Tree) Has(key string) bool {31 if t.root == nil {32 return false33 }3435 _, exists := t.root.get(key)36 return exists37}3839// Get retrieves the value associated with key.40func (t *Tree) Get(key string) any {41 if t.root == nil {42 return nil43 }4445 v, _ := t.root.get(key)46 return v47}4849// GetByIndex retrieves the key-value pair at the given index50// in lexicographic order. It panics if index is out of range.51func (t *Tree) GetByIndex(index int) (key string, value any) {52 if index < 0 || index >= t.size {53 panic("trie: index out of range")54 }5556 i := 057 t.root.inorder("", true, func(k string, v any) bool {58 if i == index {59 key, value = k, v60 return true61 }6263 i++64 return false65 })66 return key, value67}6869// Set inserts or updates a key-value pair.70// It returns true when the key already existed and its value71// was updated, and false when the key was newly inserted.72func (t *Tree) Set(key string, value any) (updated bool) {73 if t.root == nil {74 t.root = &node{}75 }7677 updated = t.root.set(key, value)78 if !updated {79 t.size++80 }81 return updated82}8384// Remove deletes the pair stored under key.85// It returns the removed value and whether the key was found and removed.86func (t *Tree) Remove(key string) (value any, removed bool) {87 if t.root == nil {88 return nil, false89 }9091 value, removed = t.root.remove(key)92 if removed {93 t.size--94 }95 return value, removed96}9798// Iterate performs an in-order (ascending) traversal over the keys in the99// range [start, end), start is inclusive and end is exclusive.100// An empty start or end means unbounded on that side.101// Iteration stops when the callback returns true, the method returns whether102// it was stopped that way.103func (t *Tree) Iterate(start, end string, cb avl.IterCbFn) bool {104 if t.root == nil {105 return false106 }107108 return t.root.inorder("", true, func(key string, value any) bool {109 if start != "" && key < start {110 return false111 }112113 if end != "" && key >= end {114 return false115 }116 return cb(key, value)117 })118}119120// ReverseIterate performs a reverse in-order (descending) traversal over the121// keys in the range [start, end], where both start and end are inclusive.122// An empty start or end means unbounded on that side.123// Iteration stops when the callback returns true; the method returns whether124// it was stopped that way.125func (t *Tree) ReverseIterate(start, end string, cb avl.IterCbFn) bool {126 if t.root == nil {127 return false128 }129130 return t.root.inorder("", false, func(key string, value any) bool {131 if start != "" && key < start {132 return false133 }134135 if end != "" && key > end {136 return false137 }138 return cb(key, value)139 })140}141142// IterateByOffset performs an in-order (ascending) traversal that skips the143// first offset keys and then visits up to count keys.144// Iteration stops early when the callback returns true, the method returns145// whether it was stopped that way.146func (t *Tree) IterateByOffset(offset int, count int, cb avl.IterCbFn) bool {147 return t.iterateByOffset(offset, count, true, cb)148}149150// ReverseIterateByOffset performs a reverse in-order (descending) traversal151// that skips the first offset keys and then visits up to count keys.152// Iteration stops early when the callback returns true; the method returns whether153// it was stopped that way.154func (t *Tree) ReverseIterateByOffset(offset int, count int, cb avl.IterCbFn) bool {155 return t.iterateByOffset(offset, count, false, cb)156}157158func (t *Tree) iterateByOffset(offset, count int, ascending bool, cb avl.IterCbFn) bool {159 if t.root == nil || count <= 0 {160 return false161 }162163 skipped, emitted := 0, 0164 stopped := false165 t.root.inorder("", ascending, func(key string, value any) bool {166 if skipped < offset {167 skipped++168 return false169 }170171 stopped = cb(key, value)172 emitted++173 return stopped || emitted >= count174 })175 return stopped176}177Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.