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

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