const MaxWordLen
MaxWordLen bounds a single word so insertion gas stays predictable.
v0 source pure
Package trie is a prefix tree (trie) for autocomplete, as a pure, reusable package: insert words, then ask for every ...
View source
gno.land/p/moul/x/daily/trie/v0
Prefix tree (trie) for autocomplete — Insert, Contains, HasPrefix, Complete, Words, FromWords, MaxWordLen.
Insert words, then ask for everything sharing a prefix. Children are stored in a
slice kept sorted by rune (binary search on lookup, insertion sort on add), so
completions always come back in lexicographic order and the output never depends
on insertion order — no maps anywhere, because Go/gno map iteration order is
unspecified and would make a realm's Render vary between calls. No clocks and
no chain imports either: same input, same output, always.
MaxWordLen (64) bounds a single word so insertion gas stays predictable.
1import "gno.land/p/moul/x/daily/trie/v0"
2
3t := trie.FromWords([]string{"carpet", "car", "cat"})
4t.Complete("car", 0) // ["car" "carpet"] — lexicographic, 0 = no cap
5t.Complete("car", 1) // ["car"]
6t.Contains("car") // true
7t.Contains("ca") // false — a prefix is not a word until inserted
8t.HasPrefix("ca") // true
9t.Words() // ["car" "carpet" "cat"]
Complete returns an empty (never nil) slice for an unknown prefix, so callers
can range over the result without a nil check. The empty prefix lists the whole
trie, which makes it usable as a plain sorted listing too.
Live demo: r/moul/x/daily/triedemo
· render it at /r/moul/x/daily/triedemo/v0.
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.
Package trie is a prefix tree (trie) for autocomplete, as a pure, reusable package: insert words, then ask for every word sharing a prefix.
Everything is deterministic and allocation-friendly so it runs reproducibly on-chain: no maps in the hot path (map iteration order is unspecified, which would make Render output vary), no clocks, no chain imports. Children are kept in a slice sorted by rune, so completions always come out in lexicographic order — the same input always yields the same output.
A live demo of this package (a gnoweb autocomplete box) is at r/moul/x/daily/triedemo(/r/moul/x/daily/triedemo/v0).
1
2
1
type Trie
structTrie is a prefix tree. The zero value is an empty, ready-to-use Trie.
Methods on Trie
func Complete
method on TrieComplete returns up to limit words starting with prefix, in lexicographic order. A limit <= 0 means "no cap". An absent prefix yields an empty slice (never nil), so callers can range over the result unconditionally.
The empty prefix lists the whole Trie, which is what makes this usable as a plain sorted listing too.
func Contains
method on TrieContains reports whether word was inserted as a complete word. A stored "carpet" does not make "car" Contains-true — only Insert does.
func HasPrefix
method on TrieHasPrefix reports whether any stored word starts with prefix. The empty prefix matches whenever the Trie is non-empty.
func Insert
method on TrieInsert adds word to the Trie and reports whether it was newly added. The empty string and words longer than MaxWordLen are rejected (false). Inserting the same word twice is a no-op.
func Len
method on TrieLen returns how many distinct words the Trie holds.
func Words
method on TrieWords returns every stored word in lexicographic order.
1
- sort stdlib
