trie_test.gno

 1package trie
 2
 3import (
 4	"strings"
 5	"testing"
 6
 7	"gno.land/p/nt/uassert/v0"
 8)
 9
10func TestInsertAndContains(t *testing.T) {
11	cases := []struct {
12		name     string
13		word     string
14		wantOK   bool
15		contains bool
16	}{
17		{"plain word", "car", true, true},
18		{"empty rejected", "", false, false},
19		{"too long rejected", strings.Repeat("a", MaxWordLen+1), false, false},
20		{"exactly max accepted", strings.Repeat("b", MaxWordLen), true, true},
21	}
22	for _, c := range cases {
23		t.Run(c.name, func(t *testing.T) {
24			tr := New()
25			uassert.Equal(t, c.wantOK, tr.Insert(c.word))
26			uassert.Equal(t, c.contains, tr.Contains(c.word))
27		})
28	}
29}
30
31func TestInsertIsIdempotent(t *testing.T) {
32	tr := New()
33	uassert.True(t, tr.Insert("gno"))
34	uassert.False(t, tr.Insert("gno"))
35	uassert.Equal(t, 1, tr.Len())
36}
37
38// A prefix of a stored word is not itself a word until inserted.
39func TestPrefixIsNotAWord(t *testing.T) {
40	tr := FromWords([]string{"carpet"})
41	uassert.False(t, tr.Contains("car"))
42	uassert.True(t, tr.HasPrefix("car"))
43	uassert.True(t, tr.Contains("carpet"))
44}
45
46func TestCompleteIsLexicographic(t *testing.T) {
47	// deliberately inserted out of order
48	tr := FromWords([]string{"carpet", "car", "cat", "dog", "cart"})
49	got := tr.Complete("car", 0)
50	want := []string{"car", "carpet", "cart"}
51	uassert.Equal(t, strings.Join(want, ","), strings.Join(got, ","))
52}
53
54func TestCompleteLimit(t *testing.T) {
55	tr := FromWords([]string{"a", "ab", "abc", "abcd"})
56	uassert.Equal(t, 2, len(tr.Complete("a", 2)))
57	uassert.Equal(t, 4, len(tr.Complete("a", 0)))
58	uassert.Equal(t, 4, len(tr.Complete("a", -1)))
59}
60
61func TestCompleteUnknownPrefixIsEmptyNotNil(t *testing.T) {
62	tr := FromWords([]string{"gno"})
63	got := tr.Complete("zzz", 0)
64	uassert.Equal(t, 0, len(got))
65	// must be safe to range over / join without a nil check
66	uassert.Equal(t, "", strings.Join(got, ","))
67}
68
69func TestEmptyPrefixListsEverything(t *testing.T) {
70	tr := FromWords([]string{"beta", "alpha", "gamma"})
71	uassert.Equal(t, "alpha,beta,gamma", strings.Join(tr.Words(), ","))
72	uassert.True(t, tr.HasPrefix(""))
73	uassert.False(t, New().HasPrefix(""))
74}
75
76func TestUnicode(t *testing.T) {
77	tr := FromWords([]string{"éclair", "école", "zèbre"})
78	uassert.Equal(t, "éclair,école", strings.Join(tr.Complete("é", 0), ","))
79	uassert.True(t, tr.Contains("zèbre"))
80}
81
82// Children are kept sorted on insert, so output order never depends on
83// insertion order — the property that keeps Render deterministic on-chain.
84func TestOrderIndependentOfInsertionOrder(t *testing.T) {
85	a := FromWords([]string{"delta", "alpha", "charlie", "bravo"})
86	b := FromWords([]string{"bravo", "charlie", "alpha", "delta"})
87	uassert.Equal(t, strings.Join(a.Words(), ","), strings.Join(b.Words(), ","))
88}