class Zenlish::Trie::Trie
A trie (aka prefix tree or digital tree) is a kind of search tree.
Attributes
root[R]
@return [TrieRoot] The root node of the trie data structure
Public Class Methods
new()
click to toggle source
# File lib/zenlish/trie/trie.rb, line 16 def initialize @root = TrieRoot.new end
Public Instance Methods
add(aWord, aValue)
click to toggle source
# File lib/zenlish/trie/trie.rb, line 20 def add(aWord, aValue) append_node(root, aWord, 0, aValue) end
search(aWord)
click to toggle source
# File lib/zenlish/trie/trie.rb, line 24 def search(aWord) search_node(root, aWord, 0) end
Private Instance Methods
append_node(aNode, aText, anIndex, aValue)
click to toggle source
# File lib/zenlish/trie/trie.rb, line 30 def append_node(aNode, aText, anIndex, aValue) key = aText[anIndex] unless aNode.include?(key) aNode.add_succ(key, TrieNode.new(key)) end successor = aNode.succ[key] if anIndex == aText.size - 1 current_value = successor.value if current_value if current_value.kind_of?(Array) current_value << aValue else successor.value = [current_value, aValue] end else successor.value = aValue end else append_node(successor, aText, anIndex + 1, aValue) end end
search_node(aNode, aText, anIndex)
click to toggle source
# File lib/zenlish/trie/trie.rb, line 53 def search_node(aNode, aText, anIndex) key = aText[anIndex] return nil unless aNode.include?(key) successor = aNode.succ[key] return successor if anIndex == aText.size - 1 search_node(successor, aText, anIndex + 1) end