class Storage::Node

Class Node of trie

Attributes

subtrie[RW]

subtrie and property of ending word on this node

Public Class Methods

new() click to toggle source
# File lib/trie-storage.rb, line 77
def initialize
  @final = false
  @subtrie = {}
end

Public Instance Methods

add_word(word) click to toggle source

add word in trie

# File lib/trie-storage.rb, line 94
def add_word(word)
  let = word[0]
  if !word.empty?
    if !@subtrie[let]
      @subtrie[let] = Node.new
    end
    @subtrie[let].add_word(word[1..-1])
  else
    final!
  end
end
contains?(str) click to toggle source

check contains str starting from current node

# File lib/trie-storage.rb, line 83
def contains?(str)
  let = str[0]
  if str.empty?
    final?
  elsif @subtrie[let]
    @subtrie[let].contains?(str[1..-1])
  else false
  end
end
final!() click to toggle source
# File lib/trie-storage.rb, line 69
def final!
  @final = true
end
final?() click to toggle source
# File lib/trie-storage.rb, line 73
def final?
  @final
end
find(res,str,st) click to toggle source

find all words starting from current node and str

# File lib/trie-storage.rb, line 116
def find(res,str,st)
  let = str[0]
  if @subtrie[let]
    if str.length == 1
      res.push(st) if @subtrie[let].final?
      @subtrie[let].get_subtrie_words(res,st)
    else
      @subtrie[let].find(res,str[1..-1],st)
    end
  else
    res
  end
end
get_subtrie_words(res,str) click to toggle source

get all words starting from current node

# File lib/trie-storage.rb, line 107
def get_subtrie_words(res,str)
  @subtrie.each do |k,node|
    res.push(str+k) if node.final?
    node.get_subtrie_words(res,str+k) if !node.subtrie.empty?
  end
  res
end