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
|
package keyseq
type Matcher struct {
*TernaryTrie
}
type Match struct {
Index int
Pattern KeyList
Value interface{}
}
type nodeData struct {
pattern *KeyList
value interface{}
failure *TernaryNode
}
func (n *nodeData) Value() interface{} {
return n.value
}
func NewMatcher() *Matcher {
return &Matcher{
NewTernaryTrie(),
}
}
func (m *Matcher) Clear() {
m.Root().RemoveAll()
}
func (m *Matcher) Add(pattern KeyList, v interface{}) {
m.Put(pattern, &nodeData{
pattern: &pattern,
value: v,
})
}
func (m *Matcher) Compile() error {
m.Balance()
root := m.Root().(*TernaryNode)
root.SetValue(&nodeData{failure: root})
// fill data.failure of each node.
EachWidth(m, func(n Node) bool {
parent := n.(*TernaryNode)
parent.Each(func(m Node) bool {
fillFailure(m.(*TernaryNode), root, parent)
return true
})
return true
})
return nil
}
func fillFailure(curr, root, parent *TernaryNode) {
data := getNodeData(curr)
if data == nil {
data = &nodeData{}
curr.SetValue(data)
}
if parent == root {
data.failure = root
return
}
// Determine failure node.
fnode := getNextNode(getNodeFailure(parent, root), root, curr.Label())
data.failure = fnode
}
func (m *Matcher) Match(text KeyList) <-chan Match {
ch := make(chan Match, 1)
go m.startMatch(text, ch)
return ch
}
func (m *Matcher) startMatch(text KeyList, ch chan<- Match) {
defer close(ch)
root := m.Root().(*TernaryNode)
curr := root
for i, r := range text {
curr = getNextNode(curr, root, r)
if curr == root {
continue
}
fireAll(curr, root, ch, i)
}
}
func getNextNode(node, root *TernaryNode, r Key) *TernaryNode {
for {
next, _ := node.Get(r).(*TernaryNode)
if next != nil {
return next
} else if node == root {
return root
}
node = getNodeFailure(node, root)
}
}
func fireAll(curr, root *TernaryNode, ch chan<- Match, idx int) {
for curr != root {
data := getNodeData(curr)
if data.pattern != nil {
ch <- Match{
Index: idx - len(*data.pattern) + 1,
Pattern: *data.pattern,
Value: data.value,
}
}
curr = data.failure
}
}
func getNodeData(node *TernaryNode) *nodeData {
d, _ := node.Value().(*nodeData)
return d
}
func getNodeFailure(node, root *TernaryNode) *TernaryNode {
next := getNodeData(node).failure
if next == nil {
return root
}
return next
}
|
