-
Notifications
You must be signed in to change notification settings - Fork 2
/
js_suffix_trie.coffee
119 lines (88 loc) · 2.33 KB
/
js_suffix_trie.coffee
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
class JsSuffixTrie
constructor: () ->
@count = 0
@structure = {}
@prefix = ""
add: (string) ->
node = @structure
length = string.length
index = 0
while index < length
chr = string[index++]
next = node[chr]
if next
node = next
else
node[chr] = {}
node = node[chr]
if node.terminator
false
else
node.terminator = true
@count++
true
remove: (string) ->
node = @structure
length = string.length
index = 0
while index < length
chr = string[index++]
node = node[chr]
return false unless node
if node.terminator
delete node.terminator
@count--
true
else
false
contains: (string) ->
node = @findNode(string)
node isnt null && node.terminator
subTrie: (prefix) ->
node = @findNode(prefix)
subTrie = new JsSuffixTrie
subTrie.structure = node
subTrie.prefix = prefix
subTrie
find: (prefix) -> JsSuffixTrie.nodeToArray @findNode(prefix), prefix
findNode: (string) ->
node = @structure
length = string.length
index = 0
while index < length
currentChar = string[index++]
node = node[currentChar]
return null unless node
return node
each: (callback) -> JsSuffixTrie.each(callback, @structure, 0, @prefix)
@each: (callback, node, index, string) ->
callback(index++, string) if node && node.terminator
for property of node
index = @each(callback, node[property], index, string + property)
index
size: -> @count
calculateSize: (node = @structure) ->
size = if node.terminator then 1 else 0
for property of node
size += @calculateSize node[property]
size
@fromArray: (array) ->
trie = new JsSuffixTrie
length = array.length
i = 0
trie.add array[i++] while i < length
trie.count = i
trie
toArray: -> JsSuffixTrie.nodeToArray(@structure, @prefix)
@nodeToArray: (node, prefix) ->
array = []
@each (index, value) ->
array[index] = value
, node, 0, prefix
array
@fromJSON: (json) ->
trie = new JsSuffixTrie
trie.structure = JSON.parse json
trie.calculateSize()
trie
toJSON: -> JSON.stringify @structure