-
Notifications
You must be signed in to change notification settings - Fork 1
/
trie.go
130 lines (117 loc) · 3.03 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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package utils
// TSTNode represents the ternary search trie node
type TSTNode struct {
Value interface{}
Cb byte
Left, Middle, Right *TSTNode
}
type TernarySearchTrie struct {
Root *TSTNode
}
func NewTST() *TernarySearchTrie {
return &TernarySearchTrie{
// Root: &TSTNode{}, not a R-way trie, root is not empty
}
}
func (t *TernarySearchTrie) Put(key string, val interface{}) {
t.Root = put(t.Root, key, val, 0)
}
func put(node *TSTNode, key string, val interface{}, d int) *TSTNode {
c := key[d]
if node == nil {
node = &TSTNode{
Cb: c,
}
}
if c < node.Cb {
//fmt.Printf("node.Cb: %c, and c: %c,go to left\n", node.Cb, c)
node.Left = put(node.Left, key, val, d)
} else if c > node.Cb {
//fmt.Printf("node.Cb: %c, and c: %c,go to right\n", node.Cb, c)
node.Right = put(node.Right, key, val, d)
} else if d < len(key)-1 {
//fmt.Printf("node.Cb: %c, and c: %c,go to Middle\n", node.Cb, c)
node.Middle = put(node.Middle, key, val, d+1)
} else {
//fmt.Printf("node.c: %c, d=%d, len(key):%d\n", node.Cb, d, len(key))
node.Value = val
}
return node
}
func (t *TernarySearchTrie) WithPrefix(query string) []interface{} {
node := get(t.Root, query, 0)
// fmt.Printf("node: %#v\n", node)
if node == nil {
return nil
}
var res []interface{}
if node.Value != nil {
res = append(res, node.Value)
}
prefixWithNode(node.Middle, &res)
return res
}
func prefixWithNode(node *TSTNode, res *[]interface{}) {
if node == nil {
return
}
// fmt.Printf("node with prefix : %#v\n", node)
if node.Value != nil {
*res = append(*res, node.Value)
}
prefixWithNode(node.Middle, res)
prefixWithNode(node.Left, res)
prefixWithNode(node.Right, res)
}
func (t *TernarySearchTrie) LongestPrefixOf(query string) string {
length := search(t.Root, query, 0, 0)
return query[:length]
}
func search(node *TSTNode, query string, d, length int) int {
if node == nil {
return length
}
if node.Value != nil {
length = d + 1 // d+1 means the actually length
}
if d == len(query) {
return length
}
c := query[d]
if c < node.Cb {
// fmt.Printf("node.Cb: %c, and c: %c,go to Left\n", node.Cb, c)
return search(node.Left, query, d, length)
} else if c > node.Cb {
// fmt.Printf("node.Cb: %c, and c: %c,go to Right\n", node.Cb, c)
return search(node.Right, query, d, length)
} else if d < len(query) {
// fmt.Printf("node.Cb: %c, and c: %c,go to Middle with d:%d, and query:%d\n", node.Cb, c, d, len(query))
return search(node.Middle, query, d+1, length)
}
return length
}
func (t *TernarySearchTrie) Contains(key string) bool {
return t.Get(key) != nil
}
func (t *TernarySearchTrie) Get(key string) interface{} {
x := get(t.Root, key, 0)
if x == nil {
return nil
}
return x.Value
}
func get(node *TSTNode, key string, d int) *TSTNode {
if node == nil || key == "" {
return nil
}
c := key[d]
if c < node.Cb {
return get(node.Left, key, d)
} else if c > node.Cb {
return get(node.Right, key, d)
} else if d < len(key)-1 {
return get(node.Middle, key, d+1)
} else {
return node
}
}