-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie_test.go
138 lines (135 loc) · 3.61 KB
/
trie_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package sqlike
import (
"github.com/stretchr/testify/assert"
"testing"
)
func TestLikeTrie(t *testing.T) {
tables := []struct {
expressions []string
matches map[string]string
nomatches []string
}{
// Case of direct match
// Note: "" doesnt match any expression, not even ""
{
[]string{"test", "a", ""},
map[string]string{
"test": "test",
"a": "a",
},
[]string{"", "notest", "b", "tesb"},
},
// Case of similar direct matches
{
[]string{"test-a-post", "test-b-post", "test-c-post"},
map[string]string{
"test-b-post": "test-b-post",
},
[]string{"test-d-post"},
},
// Case of empty wild card matches
{
[]string{"a%b", "a%bb"},
map[string]string{
"ab": "a%b",
"abb": "a%bb",
},
[]string{},
},
// Case of similar direct wild card matches
{
[]string{"testa-%-posta", "testa-%-postb", "testb-%-postb"},
map[string]string{
"testa-abc-posta": "testa-%-posta",
"testa-abc-postb": "testa-%-postb",
"testb-abc-postb": "testb-%-postb",
},
[]string{"testb-abc-posta", "testa-abc-postc"},
},
// Case of partial matches
{
[]string{"test-%-post-a", "test-%-post"},
map[string]string{
"test-abc-post-a": "test-%-post-a",
"test-abc-post": "test-%-post",
},
[]string{"test-abc-post-", "test-abc-pos"},
},
// Case of prefixes
{
[]string{"test-%", "test-%-post", "test-a-%"},
map[string]string{
"test-b-post": "test-%-post",
"test-a-test": "test-a-%",
"test-b-test": "test-%",
},
[]string{"testpost"},
},
// Case of suffixes
{
[]string{"%-post", "%-a-post", "test-%-post"},
map[string]string{
"test-a-post": "test-%-post",
"pre-a-post": "%-a-post",
"pre-b-post": "%-post",
},
[]string{"testpost"},
},
// Case of protected sections
{
[]string{"test-[%]-post", "test-[%-noclose"},
map[string]string{
"test-%-post": "test-[%]-post",
"test-[]-noclose": "test-[%-noclose",
},
[]string{"test-a-post", "test-[]-post"},
},
// Case of similar expressions with protected sections
{
[]string{"test-%-post", "test-[%]-post"},
map[string]string{
"test-a-post": "test-%-post",
"test-%-post": "test-[%]-post",
},
[]string{"testpost"},
},
// Case of protected sections with brackets
{
[]string{"test-[[]%[]]-post", "test-[[][]]-test", "pre-[%]%[%]-post"},
map[string]string{
"test-[]-post": "test-[[]%[]]-post",
"test-[abc]-post": "test-[[]%[]]-post",
"test-[%[]]-post": "test-[[]%[]]-post",
"test-[]%[]-post": "test-[[]%[]]-post",
"test-[[]a[]]-post": "test-[[]%[]]-post",
"test-[]-test": "test-[[][]]-test",
"pre-%%-post": "pre-[%]%[%]-post",
"pre-%test%-post": "pre-[%]%[%]-post",
},
[]string{"test-[][]-test", "test-[[][]]-test", "pre-abc-post"},
},
}
for _, table := range tables {
trie := NewLikeTrie(0)
expected_meta := map[string]int{}
for idx, expr := range table.expressions {
trie.SaveExpression(expr, idx)
expected_meta[expr] = idx
}
for text, match := range table.matches {
expr, meta, err := trie.FindExpression(text)
if assert.NoError(t, err, "Error looking for expression") {
assert.Equal(t, match, expr, "text matched incorrect expression")
assert.Equal(t, expected_meta[expr], meta, "Incorrect meta stored or fetched")
}
}
for _, text := range table.nomatches {
expr, meta, err := trie.FindExpression(text)
assert.Nil(t, meta, "A meta was found for an unmatched text")
if assert.Error(t, err) {
assert.Equal(t, ExpressionNotFound, err)
}
assert.Equal(t, "", expr, "A matching expression was found")
}
}
}