1// Package trie is a prefix tree (trie) for autocomplete, as a pure, reusable2// package: insert words, then ask for every word sharing a prefix.3//4// Everything is deterministic and allocation-friendly so it runs reproducibly5// on-chain: no maps in the hot path (map iteration order is unspecified, which6// would make Render output vary), no clocks, no chain imports. Children are7// kept in a slice sorted by rune, so completions always come out in8// lexicographic order — the same input always yields the same output.9//10// A live demo of this package (a gnoweb autocomplete box) is at11// [r/moul/x/daily/triedemo](/r/moul/x/daily/triedemo/v0).12package trie1314import "sort"1516// MaxWordLen bounds a single word so insertion gas stays predictable.17const MaxWordLen = 641819// node is one position in the tree. Children are ordered by Key so walks are20// deterministic; `terminal` marks the end of an inserted word (so "car" can be21// a word even when "carpet" is also stored).22type node struct {23 key rune24 terminal bool25 children []*node26}2728// Trie is a prefix tree. The zero value is an empty, ready-to-use Trie.29type Trie struct {30 root node31 count int32}3334// New returns an empty Trie.35func New() *Trie { return &Trie{} }3637// Len returns how many distinct words the Trie holds.38func (t *Trie) Len() int { return t.count }3940// child finds n's child for rune r, or nil. The slice is sorted, so this is a41// binary search.42func (n *node) child(r rune) *node {43 i := sort.Search(len(n.children), func(i int) bool { return n.children[i].key >= r })44 if i < len(n.children) && n.children[i].key == r {45 return n.children[i]46 }47 return nil48}4950// addChild inserts a child for rune r, keeping children sorted by key.51func (n *node) addChild(r rune) *node {52 i := sort.Search(len(n.children), func(i int) bool { return n.children[i].key >= r })53 if i < len(n.children) && n.children[i].key == r {54 return n.children[i]55 }56 c := &node{key: r}57 n.children = append(n.children, nil)58 copy(n.children[i+1:], n.children[i:])59 n.children[i] = c60 return c61}6263// Insert adds word to the Trie and reports whether it was newly added.64// The empty string and words longer than MaxWordLen are rejected (false).65// Inserting the same word twice is a no-op.66func (t *Trie) Insert(word string) bool {67 rs := []rune(word)68 if len(rs) == 0 || len(rs) > MaxWordLen {69 return false70 }71 n := &t.root72 for _, r := range rs {73 n = n.addChild(r)74 }75 if n.terminal {76 return false77 }78 n.terminal = true79 t.count++80 return true81}8283// Contains reports whether word was inserted as a complete word. A stored84// "carpet" does not make "car" Contains-true — only Insert does.85func (t *Trie) Contains(word string) bool {86 n := t.find(word)87 return n != nil && n.terminal88}8990// HasPrefix reports whether any stored word starts with prefix. The empty91// prefix matches whenever the Trie is non-empty.92func (t *Trie) HasPrefix(prefix string) bool {93 if prefix == "" {94 return t.count > 095 }96 return t.find(prefix) != nil97}9899// find walks to the node for s, or returns nil when the path is absent.100func (t *Trie) find(s string) *node {101 n := &t.root102 for _, r := range s {103 n = n.child(r)104 if n == nil {105 return nil106 }107 }108 return n109}110111// Complete returns up to limit words starting with prefix, in lexicographic112// order. A limit <= 0 means "no cap". An absent prefix yields an empty slice113// (never nil), so callers can range over the result unconditionally.114//115// The empty prefix lists the whole Trie, which is what makes this usable as a116// plain sorted listing too.117func (t *Trie) Complete(prefix string, limit int) []string {118 out := []string{}119 start := t.find(prefix)120 if start == nil {121 return out122 }123 collect(start, []rune(prefix), &out, limit)124 return out125}126127// collect appends every word under n (depth-first, children already sorted)128// to *out, stopping once limit is reached.129func collect(n *node, path []rune, out *[]string, limit int) {130 if limit > 0 && len(*out) >= limit {131 return132 }133 if n.terminal {134 *out = append(*out, string(path))135 }136 for _, c := range n.children {137 if limit > 0 && len(*out) >= limit {138 return139 }140 collect(c, append(path, c.key), out, limit)141 }142}143144// Words returns every stored word in lexicographic order.145func (t *Trie) Words() []string { return t.Complete("", 0) }146147// FromWords builds a Trie from words, skipping any the Trie rejects.148func FromWords(words []string) *Trie {149 t := New()150 for _, w := range words {151 t.Insert(w)152 }153 return t154}155Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.