Class: Storage::Node

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

Overview

Class Node of trie

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Node

Returns a new instance of Node.



77
78
79
80
 
# File 'lib/trie-storage.rb', line 77

def initialize
  @final = false
  @subtrie = {}
end

Instance Attribute Details

#subtrie ⇒ Object

subtrie and property of ending word on this node



67
68
69
 
# File 'lib/trie-storage.rb', line 67

def subtrie
  @subtrie
end

Instance Method Details

#add_word(word) ⇒ Object

add word in trie



94
95
96
97
98
99
100
101
102
103
104
 
# 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) ⇒ Boolean

check contains str starting from current node

Returns:

  • (Boolean) 


83
84
85
86
87
88
89
90
91
 
# 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! ⇒ Object 



69
70
71
 
# File 'lib/trie-storage.rb', line 69

def final!
  @final = true
end

#final? ⇒ Boolean

Returns:

  • (Boolean) 


73
74
75
 
# File 'lib/trie-storage.rb', line 73

def final?
  @final
end

#find(res, str, st) ⇒ Object

find all words starting from current node and str



116
117
118
119
120
121
122
123
124
125
126
127
128
 
# 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) ⇒ Object

get all words starting from current node



107
108
109
110
111
112
113
 
# 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