/
trie.rb
182 lines (168 loc) · 5.37 KB
/
trie.rb
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
=begin rdoc
A Trie is a data structure that stores key value pairs in a tree-like fashion. It allows
O(m) lookup speed, where m is the length of the key searched, and has no chance of collisions,
unlike hash tables. Because of its nature, search misses are quickly detected.
Tries are often used for longest prefix algorithms, wildcard matching, and can be used to
implement a radix sort.
This implemention is based on a Ternary Search Tree.
=end
class Containers::Trie
# Create a new, empty Trie.
#
# t = Containers::Trie.new
# t["hello"] = "world"
# t["hello"] #=> "world"
def initialize
@root = nil
end
# Adds a key, value pair to the Trie, and returns the value if successful. The to_s method is
# called on the parameter to turn it into a string.
#
# Complexity: O(m)
#
# t = Containers::Trie.new
# t["hello"] = "world"
# t.push("hello", "world") # does the same thing
# t["hello"] #=> "world"
# t[1] = 1
# t[1] #=> 1
def push(key, value)
key = key.to_s
return nil if key.empty?
@root = push_recursive(@root, key, 0, value)
value
end
alias_method :[]=, :push
# Returns true if the key is contained in the Trie.
#
# Complexity: O(m) worst case
#
def has_key?(key)
key = key.to_s
return false if key.empty?
!(get_recursive(@root, key, 0).nil?)
end
# Returns the value of the desired key, or nil if the key doesn't exist.
#
# Complexity: O(m) worst case
#
# t = Containers::Trie.new
# t.get("hello") = "world"
# t.get("non-existant") #=> nil
def get(key)
key = key.to_s
return nil if key.empty?
node = get_recursive(@root, key, 0)
node ? node.last : nil
end
alias_method :[], :get
# Returns the longest key that has a prefix in common with the parameter string. If
# no match is found, the blank string "" is returned.
#
# Complexity: O(m) worst case
#
# t = Containers::Trie.new
# t.push("Hello", "World")
# t.push("Hello, brother", "World")
# t.push("Hello, bob", "World")
# t.longest_prefix("Hello, brandon") #=> "Hello"
# t.longest_prefix("Hel") #=> ""
# t.longest_prefix("Hello") #=> "Hello"
def longest_prefix(string)
string = string.to_s
return nil if string.empty?
len = prefix_recursive(@root, string, 0)
string[0...len]
end
# Returns a sorted array containing strings that match the parameter string. The wildcard
# characters that match any character are '*' and '.' If no match is found, an empty
# array is returned.
#
# Complexity: O(n) worst case
#
# t = Containers::Trie.new
# t.push("Hello", "World")
# t.push("Hilly", "World")
# t.push("Hello, bob", "World")
# t.wildcard("H*ll.") #=> ["Hello", "Hilly"]
# t.wildcard("Hel") #=> []
def wildcard(string)
string = string.to_s
return nil if string.empty?
ary = []
ary << wildcard_recursive(@root, string, 0, "")
ary.flatten.compact.sort
end
class Node # :nodoc: all
attr_accessor :left, :mid, :right, :char, :value, :end
def initialize(char, value)
@char = char
@value = value
@left = @mid = @right = nil
@end = false
end
def last?
@end == true
end
end
def wildcard_recursive(node, string, index, prefix)
return nil if node.nil? || index == string.length
arr = []
char = string[index]
if (char.chr == "*" || char.chr == "." || char < node.char)
arr << wildcard_recursive(node.left, string, index, prefix)
end
if (char.chr == "*" || char.chr == "." || char > node.char)
arr << wildcard_recursive(node.right, string, index, prefix)
end
if (char.chr == "*" || char.chr == "." || char == node.char)
arr << "#{prefix}#{node.char.chr}" if node.last?
arr << wildcard_recursive(node.mid, string, index+1, prefix + node.char.chr)
end
arr
end
def prefix_recursive(node, string, index)
return 0 if node.nil? || index == string.length
len = 0
rec_len = 0
char = string[index]
if (char < node.char)
rec_len = prefix_recursive(node.left, string, index)
elsif (char > node.char)
rec_len = prefix_recursive(node.right, string, index)
else
len = index+1 if node.last?
rec_len = prefix_recursive(node.mid, string, index+1)
end
len > rec_len ? len : rec_len
end
def push_recursive(node, string, index, value)
char = string[index]
node = Node.new(char, value) if node.nil?
if (char < node.char)
node.left = push_recursive(node.left, string, index, value)
elsif (char > node.char)
node.right = push_recursive(node.right, string, index, value)
elsif (index < string.length-1) # We're not at the end of the input string; add next char
node.mid = push_recursive(node.mid, string, index+1, value)
else
node.end = true
node.value = value
end
node
end
# Returns [char, value] if found
def get_recursive(node, string, index)
return nil if node.nil?
char = string[index]
if (char < node.char)
return get_recursive(node.left, string, index)
elsif (char > node.char)
return get_recursive(node.right, string, index)
elsif (index < string.length-1) # We're not at the end of the input string; add next char
return get_recursive(node.mid, string, index+1)
else
return node.last? ? [node.char, node.value] : nil
end
end
end