-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.lua
103 lines (86 loc) · 1.86 KB
/
trie.lua
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
local mt = {}
local function new_node(k)
local node = {
key = k,
ref = 0,
child = false,
value = false,
}
return node
end
local function new()
local raw = {
root = new_node('.Root'),
}
return setmetatable(raw, {__index = mt})
end
local function get_node(parent, key)
local child = parent.child
if not child then
child = {}
parent.child = child
end
local v = child[key]
if not v then
v = new_node(key)
child[key] = v
end
return v
end
function mt:insert(str)
local parent = self.root
for _, c in utf8.codes(str) do
local v = get_node(parent, c)
v.ref = v.ref + 1
parent = v
end
assert(parent.value == false)
parent.value = str
end
local function is_empty(t)
return not not next(t)
end
function mt:delete(str)
local parent = self.root
for _, c in utf8.codes(str) do
local child = parent.child
local node = child and child[c]
if not node then
return
end
local ref = node.ref - 1
node.ref = ref
assert(ref >= 0)
if ref <= 0 then
child[c] = nil
end
parent = node
end
end
function mt:search(prefix)
local parent = self.root
for _, c in utf8.codes(prefix) do
local child = parent.child
local node = child and child[c]
if not node then
return
end
parent = node
end
local function dump_token(node, out)
local value = node.value
if value then
out[#out+1] = value
end
local child = node.child
if child then
for k,v in pairs(child) do
dump_token(v, out)
end
end
end
local out = {}
dump_token(parent, out)
return out
end
return new