-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.go
116 lines (103 loc) · 2.62 KB
/
trie.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
package compiler
// Author: Ersi Ni
import "errors"
//FlagVar is enum type for flags
type FlagVar int
const (
//Static Trie: No new nodes
Static FlagVar = iota
//Dynamic Trie: New node are added
Dynamic
)
//NewTrieNode constructs a TrieNode and return the pointer to it.
//It creates 128 nil pointers and of children nodes and they will occupy 1KB
//(8 bytes * 128)
func NewTrieNode() *TrieNode {
return &TrieNode{
Children: make([]*TrieNode, 128, 128),
HasWord: false,
Index: 0,
}
}
//TrieNode states whether it is a finishing state (HasWord) and the index of
//the word from root to current node inside the symbol table. Each node has a
//fixed branch bound of 128 children nodes (range of ascii characters)
type TrieNode struct {
Children []*TrieNode
HasWord bool
Index int
}
//Process scan the input string character by character, depending on the flag
//it updates the Trie based SymbolTable data structure and return the index of
//the input symbol in the SymbolTable when appropiate.
func (s *SymbolTable) Process(text string, flag FlagVar) (int, error) {
current := s.TrieHead
for _, r := range text {
haz, err := current.has(r)
if err != nil {
return -1, err // crash here? or recover?
}
if !haz {
switch flag {
case Dynamic:
node := NewTrieNode()
current.set(r, node)
current = node
case Static:
return -1, nil
default:
return -1, errors.New("undefined flag")
}
} else {
current = current.get(r)
}
}
// reached eof; if dynamic then assign word
if !current.HasWord && flag == Dynamic {
current.HasWord = true
current.Index = len(s.Table)
s.Table = append(s.Table, text)
return current.Index, nil
}
if current.HasWord {
return current.Index, nil
}
// reached eof, no word && flag = static
return -1, nil
}
func validASCII(t int) bool {
if t >= 0 && t < 128 {
return true
}
return false
}
//SymbolTable contains a pointer to a Trie and maintains a slice of symbols
type SymbolTable struct {
TrieHead *TrieNode
Table []string
}
//NewSymbolTable constructs a SymbolTable with a new Trie Head and an empty
//string slice with 0 length
func NewSymbolTable() *SymbolTable {
return &SymbolTable{
TrieHead: NewTrieNode(),
Table: make([]string, 0),
}
}
func (t *TrieNode) set(r rune, n *TrieNode) {
idx := int(r)
t.Children[idx] = n
}
func (t *TrieNode) has(r rune) (bool, error) {
idx := int(r)
if !validASCII(idx) {
return false, errors.New("while checking nodes, " +
"character is not in valid range of ascii")
}
ret := t.Children[idx] != nil
return ret, nil
}
func (t *TrieNode) get(r rune) *TrieNode {
idx := int(r)
return t.Children[idx]
}