-
Notifications
You must be signed in to change notification settings - Fork 0
/
bitwise_trie.go
106 lines (91 loc) · 2.11 KB
/
bitwise_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
package typeahead
import (
"strings"
)
// http://www.cs.yale.edu/homes/aspnes/pinewiki/RadixSearch.html?highlight=%28CategoryAlgorithmNotes%29
// PerByte = 8
var BitsPerByte = 8
const TrieBase = 2
// func main() {
// var t *Trie
// t = trieInsert(t, "hello")
// t = trieInsert(t, "car")
// fmt.Println("has hello", trieContains(t, "hello"))
// fmt.Println("has cac", trieContains(t, "cac"))
// fmt.Println("has cac", trieContains(t, "car"))
// }
func GetBit(key string, n int) int {
if len(key) == n/BitsPerByte {
return 0
}
if key[n/BitsPerByte]&(0x1<<uint(BitsPerByte-1-n%BitsPerByte)) != 0 {
return 1
}
return 0
}
type Trie struct {
key string
children [TrieBase]*Trie
}
func NewTrie(key string) *Trie {
return &Trie{
key: key,
// children: make([TrieBase]*Trie, TrieBase),
}
}
func isLeaf(trie *Trie) bool {
if trie == nil {
return true
}
return (trie.children[0] == nil) && (trie.children[1] == nil)
}
func TrieInsert(trie *Trie, key string) *Trie {
var bit, bitvalue int
var t, kid *Trie
var oldKey string
if trie == nil {
return NewTrie(key)
}
// Search for the key.
for t = trie; !isLeaf(t); bit, t = bit+1, kid {
bitvalue = GetBit(key, bit)
kid = t.children[bitvalue]
if kid == nil {
t.children[bitvalue] = NewTrie(key)
return trie
}
}
// Nothing to do here.
// if strings.EqualFold(t.key, key) {
if strings.Compare(t.key, key) == 0 {
// if t.key == key {
return trie
}
// Extend the trie.
oldKey = t.key
t.key = ""
// Walk the common prefix.
// bitvalue = GetBit(key, bit)
bitvalue = GetBit(key, bit)
for GetBit(oldKey, bit) == bitvalue {
kid = NewTrie("")
t.children[bitvalue] = kid
bit++
t = kid
bitvalue = GetBit(key, bit)
}
// Then split.
t.children[bitvalue] = NewTrie(key)
// There is no NOT operator in golang.
t.children[1^bitvalue] = NewTrie(oldKey)
return trie
}
func TrieContains(trie *Trie, target string) bool {
for bit := 0; trie != nil && !isLeaf(trie); bit++ {
trie = trie.children[GetBit(target, bit)]
}
if trie == nil {
return false
}
return strings.EqualFold(trie.key, target)
}