Class: PreTree

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

Overview

Prefix tree (Trie class)

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PreTree

Returns a new instance of PreTree.



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

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

Instance Method Details

#add_character(character, trie) ⇒ Object 



36
37
38
 
# File 'lib/pretree.rb', line 36

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

#add_node(character, trie) ⇒ Object 



32
33
34
 
# File 'lib/pretree.rb', line 32

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

#add_word(word) ⇒ Object 



44
45
46
47
48
49
50
 
# File 'lib/pretree.rb', line 44

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

#csv_read ⇒ Object 



28
29
30
 
# File 'lib/pretree.rb', line 28

def csv_read
  @csv_box.read
end

#csv_write(word) ⇒ Object 



24
25
26
 
# File 'lib/pretree.rb', line 24

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

#delete(word) ⇒ Object 



68
69
70
71
72
 
# File 'lib/pretree.rb', line 68

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

#empty_stack ⇒ Object 



88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/pretree.rb', line 88

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) 


60
61
62
 
# File 'lib/pretree.rb', line 60

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

#find_character(character, trie) ⇒ Object 



40
41
42
 
# File 'lib/pretree.rb', line 40

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

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

Yields:

  • (word_found, base) 


52
53
54
55
56
57
58
 
# File 'lib/pretree.rb', line 52

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) 


64
65
66
 
# File 'lib/pretree.rb', line 64

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

#list(prefix = nil) ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/pretree.rb', line 74

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