Class: Kotoshu::Core::Trie::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/kotoshu/core/trie/trie.rb

Overview

Trie (prefix tree) data structure for efficient word storage and lookup. Supports prefix matching, word validation, and traversal.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Returns a new instance of Trie.



11
12
13
14
 
# File 'lib/kotoshu/core/trie/trie.rb', line 11

def initialize
  @root = Node.new
  @size = 0
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



9
10
11
 
# File 'lib/kotoshu/core/trie/trie.rb', line 9

def root
  @root
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



9
10
11
 
# File 'lib/kotoshu/core/trie/trie.rb', line 9

def size
  @size
end

Instance Method Details

#&(other) ⇒ Trie

Create a new trie with common words from two tries.

Parameters:

  • other (Trie) —

    The other trie

Returns:

  • (Trie) —

    New trie with common words



180
181
182
183
184
185
186
 
# File 'lib/kotoshu/core/trie/trie.rb', line 180

def &(other)
  result = Trie.new
  each_word do |word, _payload|
    result.insert(word) if other.lookup(word)
  end
  result
end

#all_words ⇒ Array<String>

Get all words in the trie.

Returns:

  • (Array<String>) —

    Array of all words



83
84
85
86
87
 
# File 'lib/kotoshu/core/trie/trie.rb', line 83

def all_words
  words = []
  collect_words(@root, "", words)
  words
end

#clear ⇒ Trie

Clear all words from the trie.

Returns:

  • (Trie) —

    Self for chaining



159
160
161
162
163
 
# File 'lib/kotoshu/core/trie/trie.rb', line 159

def clear
  @root = Node.new
  @size = 0
  self
end

#count_prefix(prefix) ⇒ Integer

Count words with the given prefix.

Parameters:

  • prefix (String) —

    The prefix to count

Returns:

  • (Integer) —

    Number of words with the prefix



93
94
95
 
# File 'lib/kotoshu/core/trie/trie.rb', line 93

def count_prefix(prefix)
  words_with_prefix(prefix).size
end

#each_word {|word, payload| ... } ⇒ Enumerator

Iterate over all words in the trie.

Yields:

  • (word, payload) —

    Each word and its optional payload

Returns:

  • (Enumerator) —

    Enumerator if no block given



123
124
125
126
127
128
129
130
131
 
# File 'lib/kotoshu/core/trie/trie.rb', line 123

def each_word
  return enum_for(:each_word) unless block_given?

  traverse(@root, "") do |word, node|
    yield word, node.payload if node.terminal?
  end

  self
end

#empty? ⇒ Boolean

Check if the trie is empty.

Returns:

  • (Boolean) —

    True if trie has no words



152
153
154
 
# File 'lib/kotoshu/core/trie/trie.rb', line 152

def empty?
  @size.zero?
end

#find_node(word) ⇒ Node?

Get the node for a given word/prefix.

Parameters:

  • word (String) —

    The word or prefix to find

Returns:

  • (Node, nil) —

    The node or nil if not found



57
58
59
60
61
62
63
64
65
 
# File 'lib/kotoshu/core/trie/trie.rb', line 57

def find_node(word)
  node = @root
  word.each_char do |char|
    return nil unless node.has_child?(char)

    node = node.child(char)
  end
  node
end

#has_prefix?(prefix) ⇒ Boolean

Check if any words in the trie start with the given prefix.

Parameters:

  • prefix (String) —

    The prefix to check

Returns:

  • (Boolean) —

    True if any words have this prefix



49
50
51
 
# File 'lib/kotoshu/core/trie/trie.rb', line 49

def has_prefix?(prefix)
  !find_node(prefix).nil?
end

#insert(word, payload = nil) ⇒ Trie

Insert a word into the trie.

Parameters:

  • word (String) —

    The word to insert

  • payload (Object) (defaults to: nil) —

    Optional payload to store with the word

Returns:

  • (Trie) —

    Self for chaining



21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/kotoshu/core/trie/trie.rb', line 21

def insert(word, payload = nil)
  node = @root
  word.each_char do |char|
    node = node.add_child(char)
  end

  # Only increment size if this is a new word
  @size += 1 unless node.terminal?
  node.mark_terminal(payload)

  self
end

#inspect ⇒ String

Inspect the trie.

Returns:

  • (String) —

    Inspection string



209
210
211
 
# File 'lib/kotoshu/core/trie/trie.rb', line 209

def inspect
  to_s
end

#lookup(word) ⇒ Boolean Also known as: has_word?, contains?

Check if a word exists in the trie.

Parameters:

  • word (String) —

    The word to look up

Returns:

  • (Boolean) —

    True if the word exists



38
39
40
41
 
# File 'lib/kotoshu/core/trie/trie.rb', line 38

def lookup(word)
  node = find_node(word)
  !node.nil? && node.terminal?
end

#merge!(other) ⇒ Trie

Merge another trie into this one.

Parameters:

  • other (Trie) —

    The trie to merge

Returns:

  • (Trie) —

    Self for chaining



169
170
171
172
173
174
 
# File 'lib/kotoshu/core/trie/trie.rb', line 169

def merge!(other)
  other.each_word do |word, payload|
    insert(word, payload)
  end
  self
end

#suggestions(word, max_results: 10) ⇒ Array<String>

Get suggestions for a word based on prefix matching. Returns words that share the longest common prefix.

Parameters:

  • word (String) —

    The word to get suggestions for

  • max_results (Integer) (defaults to: 10) —

    Maximum number of results

Returns:

  • (Array<String>) —

    Array of suggested words



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/kotoshu/core/trie/trie.rb', line 103

def suggestions(word, max_results: 10)
  # Find the longest matching prefix
  node = @root
  i = 0

  while i < word.length && node.has_child?(word[i])
    node = node.child(word[i])
    i += 1
  end

  # Collect all completions from this point
  words = []
  collect_words_limited(node, word[0...i], words, max_results)
  words
end

#to_s ⇒ String

Convert trie to string representation.

Returns:

  • (String) —

    String representation



202
203
204
 
# File 'lib/kotoshu/core/trie/trie.rb', line 202

def to_s
  "Trie(size: #{@size})"
end

#traverse(node = @root, prefix = "") {|prefix, node| ... } ⇒ Trie

Traverse the trie with a visitor.

Yields:

  • (prefix, node) —

    Each prefix and node visited

Returns:

  • (Trie) —

    Self for chaining



137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/kotoshu/core/trie/trie.rb', line 137

def traverse(node = @root, prefix = "", &block)
  return enum_for(:traverse, node, prefix) unless block_given?

  yield prefix, node

  node.all_children.each_value do |child|
    traverse(child, prefix + child.character, &block)
  end

  self
end

#words_with_prefix(prefix) ⇒ Array<String>

Get all words with the given prefix.

Parameters:

  • prefix (String) —

    The prefix to match

Returns:

  • (Array<String>) —

    Array of words with the prefix



71
72
73
74
75
76
77
78
 
# File 'lib/kotoshu/core/trie/trie.rb', line 71

def words_with_prefix(prefix)
  start_node = find_node(prefix)
  return [] if start_node.nil?

  words = []
  collect_words(start_node, prefix, words)
  words
end

#|(other) ⇒ Trie

Create a new trie with words from either trie.

Parameters:

  • other (Trie) —

    The other trie

Returns:

  • (Trie) —

    New trie with all words



192
193
194
195
196
197
 
# File 'lib/kotoshu/core/trie/trie.rb', line 192

def |(other)
  result = Trie.new
  each_word { |word, payload| result.insert(word, payload) }
  other.each_word { |word, payload| result.insert(word, payload) }
  result
end