Class: PrefixTreee

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

Overview

Prefix tree (Trie class)

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PrefixTreee

Returns a new instance of PrefixTreee.



19
20
21
22
 
# File 'lib/prefixtreee.rb', line 19

def initialize
  @root = Node.new('root')
  @csv_container = CSVWrite.new
end

Instance Method Details

#add_character(character, trie) ⇒ Object 



46
47
48
 
# File 'lib/prefixtreee.rb', line 46

def add_character(character, trie)
  trie.find { |n| n.value == character } || add_node(character, trie)
end

#add_node(character, trie) ⇒ Object 



42
43
44
 
# File 'lib/prefixtreee.rb', line 42

def add_node(character, trie)
  Node.new(character).tap { |new_node| trie << new_node }
end

#add_word(word) ⇒ Object 



54
55
56
57
58
59
60
 
# File 'lib/prefixtreee.rb', line 54

def add_word(word)
  csv_write(word)
  letters = word.chars
  base = @root
  letters.each { |letter| base = add_character(letter, base.next) }
  base.word = true
end

#call ⇒ Object 



24
25
26
27
28
29
30
31
32
 
# File 'lib/prefixtreee.rb', line 24

def call
  csv_write(word)
  csv_read
  add_word(word)
  find?(word)
  include?(word)
  delete(word)
  list(prefix)
end

#csv_read ⇒ Object 



38
39
40
 
# File 'lib/prefixtreee.rb', line 38

def csv_read
  @csv_container.read
end

#csv_write(word) ⇒ Object 



34
35
36
 
# File 'lib/prefixtreee.rb', line 34

def csv_write(word)
  @csv_container.write(word)
end

#delete(word) ⇒ Object 



78
79
80
81
82
 
# File 'lib/prefixtreee.rb', line 78

def delete(word)
  find_word(word) do |found, base|
    base.word = false if found == true
  end
end

#empty_stack ⇒ Object 



98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/prefixtreee.rb', line 98

def empty_stack
  until @stack.empty?
    node = @stack.pop
    @prefix_stack.pop and next if node == :guard_node

    @prefix_stack << node.value
    @stack        << :guard_node
    @dictionary << @prefix_stack.join if node.word
    node.next.each { |n| @stack << n }
  end
end

#find?(word) ⇒ Boolean

Returns:

  • (Boolean) 


70
71
72
 
# File 'lib/prefixtreee.rb', line 70

def find?(word)
  find_word(word) { |found, base| return found && base.word }
end

#find_character(character, trie) ⇒ Object 



50
51
52
 
# File 'lib/prefixtreee.rb', line 50

def find_character(character, trie)
  trie.find { |n| n.value == character }
end

#find_word(word) {|word_found, base| ... } ⇒ Object

Yields:

  • (word_found, base) 


62
63
64
65
66
67
68
 
# File 'lib/prefixtreee.rb', line 62

def find_word(word)
  letters = word.chars
  base = @root
  word_found = letters.all? { |letter| base = find_character(letter, base.next) }
  yield word_found, base if block_given?
  base
end

#include?(word) ⇒ Boolean

Returns:

  • (Boolean) 


74
75
76
 
# File 'lib/prefixtreee.rb', line 74

def include?(word)
  find_word(word) { |found| return found }
end

#list(prefix = nil) ⇒ Object 



84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/prefixtreee.rb', line 84

def list(prefix = nil)
  return @dictionary if prefix.nil?

  @stack = []
  @dictionary = []
  @prefix_stack = []
  @stack << find_word(prefix)
  @prefix_stack << prefix.chars.take(prefix.size - 1)
  return [] unless @stack.first

  empty_stack
  @dictionary
end