Class: Algorithms::Containers::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/containers/trie.rb

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Create a new, empty Trie.

t =

Trie.new

t["hello"] = "world"
t["hello] #=> "world"



20
21
22
 
# File 'lib/containers/trie.rb', line 20

def initialize
  @root = nil
end

Instance Method Details

#get(key) ⇒ Object Also known as: []

Returns the value of the desired key, or nil if the key doesn’t exist.

Complexity: O(m) worst case

t = Algorithms::Containers::Trie.new
t.get("hello") = "world"
t.get("non-existant") #=> nil



61
62
63
64
65
66
 
# File 'lib/containers/trie.rb', line 61

def get(key)
  key = key.to_s
  return nil if key.empty?
  node = get_recursive(@root, key, 0)
  node ? node.last : nil
end

#get_recursive(node, string, index) ⇒ Object

Returns [char, value] if found



173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/containers/trie.rb', line 173

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

#has_key?(key) ⇒ Boolean Also known as: include?

Returns true if the key is contained in the Trie.

Complexity: O(m) worst case

Returns:

  • (Boolean) 


47
48
49
50
51
 
# File 'lib/containers/trie.rb', line 47

def has_key?(key)
  key = key.to_s
  return false if key.empty?
  !(get_recursive(@root, key, 0).nil?)
end

#longest_prefix(string) ⇒ Object

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 = Algorithms::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"



81
82
83
84
85
86
 
# File 'lib/containers/trie.rb', line 81

def longest_prefix(string)
  string = string.to_s
  return nil if string.empty?
  len = prefix_recursive(@root, string, 0)
  string[0...len]
end

#prefix_recursive(node, string, index) ⇒ Object 



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/containers/trie.rb', line 140

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

#push(key, value) ⇒ Object Also known as: []=

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 = Algorithms::Containers::Trie.new
t["hello"] = "world"
t.push("hello", "world") # does the same thing
t["hello"] #=> "world"
t[1] = 1
t[1] #=> 1



35
36
37
38
39
40
 
# File 'lib/containers/trie.rb', line 35

def push(key, value)
  key = key.to_s
  return nil if key.empty?
  @root = push_recursive(@root, key, 0, value)
  value
end

#push_recursive(node, string, index, value) ⇒ Object 



156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
 
# File 'lib/containers/trie.rb', line 156

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

#wildcard(string) ⇒ Object

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 = Algorithms::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") #=> []



100
101
102
103
104
105
106
 
# File 'lib/containers/trie.rb', line 100

def wildcard(string)
  string = string.to_s
  return nil if string.empty?
  ary = [] 
  ary << wildcard_recursive(@root, string, 0, "")
  ary.flatten.compact.sort
end

#wildcard_recursive(node, string, index, prefix) ⇒ Object 



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/containers/trie.rb', line 123

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