/
node.rb
172 lines (141 loc) · 5.94 KB
/
node.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
# frozen_string_literal: true
module Rambling
module Trie
module Nodes
# A representation of a node in the trie data structure.
class Node
include Rambling::Trie::Compressible
include Rambling::Trie::Enumerable
include Rambling::Trie::Comparable
include Rambling::Trie::Stringifyable
include Rambling::Trie::Inspectable
# @overload letter
# Letter(s) corresponding to the current node.
# @overload letter=(letter)
# Sets the letter(s) corresponding to the current node. Ensures the
# {Node#letter #letter} in the {Node#parent #parent}'s
# {Node#children_tree #children_tree} is updated.
# @param [String, Symbol, nil] letter the letter value.
# @return [Symbol, nil] the corresponding letter(s).
attr_reader :letter
# Child nodes tree.
# @return [Hash<Symbol, Node>] the children tree hash, consisting of +:letter => node+.
attr_accessor :children_tree
# Parent node.
# @return [Node, nil] the parent of the current node.
attr_accessor :parent
# Creates a new node.
# @param [Symbol, nil] letter the Node's letter value.
# @param [Node, nil] parent the parent of the current node.
def initialize letter = nil, parent = nil, children_tree = {}
@letter = letter
@parent = parent
@children_tree = children_tree
end
# Child nodes.
# @return [Array<Node>] the array of child nodes contained in the current node.
def children
children_tree.values
end
# First child node.
# @return [Node, nil] the first child contained in the current node.
def first_child
return if children_tree.empty?
# rubocop:disable Lint/UnreachableLoop
children_tree.each_value { |child| return child }
# rubocop:enable Lint/UnreachableLoop
nil
end
# Indicates if the current node is the root node.
# @return [Boolean] +true+ if the node does not have a parent, +false+ otherwise.
def root?
!parent
end
# Indicates if a {Node Node} is terminal or not.
# @return [Boolean] +true+ for terminal nodes, +false+ otherwise.
def terminal?
!!terminal
end
# Mark {Node Node} as terminal.
# @return [self] the modified node.
def terminal!
self.terminal = true
self
end
def letter= letter
@letter = letter.to_sym if letter
end
# Checks if a path for a set of characters exists in the trie.
# @param [Array<String>] chars the characters to look for in the trie.
# @return [Boolean] +true+ if the characters are found, +false+ otherwise.
def partial_word? chars
return true if chars.empty?
partial_word_chars? chars
end
# Checks if a path for set of characters represents a word in the trie.
# @param [Array<String>] chars the characters to look for in the trie.
# @return [Boolean] +true+ if the characters are found and form a word, +false+ otherwise.
def word? chars = []
return terminal? if chars.empty?
word_chars? chars
end
# Returns the node that starts with the specified characters.
# @param [Array<String>] chars the characters to look for in the trie.
# @return [Node] the node that matches the specified characters.
# {Missing Missing} when not found.
def scan chars
return self if chars.empty?
closest_node chars
end
# Returns all words that match a prefix of any length within chars.
# @param [Array[String]] chars the chars to base the prefix on.
# @return [Enumerator<String>] all the words that match a prefix by chars.
# @yield [String] each word found.
def match_prefix chars
return enum_for :match_prefix, chars unless block_given?
yield as_word if terminal?
children_match_prefix chars do |word|
yield word
end
end
# Get {Node Node} corresponding to a given letter.
# @param [Symbol] letter the letter to search for in the node.
# @return [Node] the node corresponding to that letter.
# @see https://ruby-doc.org/core-2.7.0/Hash.html#method-i-5B-5D Hash#[]
def [] letter
children_tree[letter]
end
# Set the {Node Node} that corresponds to a given letter.
# @param [Symbol] letter the letter to insert or update in the node's
# @param [Node] node the {Node Node} to assign to that letter.
# @return [Node] the node corresponding to the inserted or updated letter.
# @see https://ruby-doc.org/core-2.7.0/Hash.html#method-i-5B-5D Hash#[]
def []= letter, node
children_tree[letter] = node
end
# Check if a {Node Node}'s children tree contains a given letter.
# @param [Symbol] letter the letter to search for in the node.
# @return [Boolean] +true+ if the letter is present, +false+ otherwise.
# @see https://ruby-doc.org/core-2.7.0/Hash.html#method-i-has_key-3F Hash#key?
def key? letter
children_tree.key? letter
end
# Delete a given letter and its corresponding {Node Node} from
# this {Node Node}'s children tree.
# @param [Symbol] letter the letter to delete from the node's children tree.
# @return [Node, nil] the node corresponding to the deleted letter.
# @see https://ruby-doc.org/core-2.7.0/Hash.html#method-i-delete Hash#delete
def delete letter
children_tree.delete letter
end
alias_method :has_key?, :key?
protected
def missing
Rambling::Trie::Nodes::Missing.new
end
private
attr_accessor :terminal
end
end
end
end