Class: Rambling::Trie::Nodes::Node

Inherits:
Object
  • Object
show all
Includes:
Comparable[TValue], Compressible[TValue], Enumerable[TValue], Inspectable[TValue], Comparable, Compressible, Enumerable, Inspectable, Stringifyable, Stringifyable[TValue]
Defined in:
lib/rambling/trie/nodes/node.rb,
sig/lib/rambling/trie/nodes/node.rbs

Overview

A representation of a node in the trie data structure. :reek:MissingSafeMethod { exclude: [ terminal! ] } :reek:RepeatedConditional { max_ifs: 3 }

Direct Known Subclasses

Compressed, Missing, Raw

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Inspectable

#attributes, #children_inspect, #class_name, #inspect, #letter_inspect, #terminal_inspect, #value_inspect

Methods included from Stringifyable

#as_word, #to_s

Methods included from Comparable

#==

Methods included from Enumerable

#as_word, #each, #empty_enum

Methods included from Compressible

#compressible?

Constructor Details

#initialize(letter = nil, parent = nil, children_tree = nil) ⇒ Node

Creates a new node.

Parameters:

  • letter (Symbol, nil) (defaults to: nil) —

    the Node's letter value.

  • parent (Node, nil) (defaults to: nil) —

    the parent of the current node.

  • children_tree (Hash<Symbol, Node>, nil) (defaults to: nil) —

    the children tree of the current node, or nil to start with an empty tree. When a hash is provided, ownership transfers to the node; callers must not retain references to or mutate the hash after passing it.

  • (Symbol, nil)
  • (Node[TValue], nil)
  • (Hash[Symbol, Node[TValue]], nil) 


45
46
47
48
49
 
# File 'lib/rambling/trie/nodes/node.rb', line 45

def initialize letter = nil, parent = nil, children_tree = nil
  @letter = letter
  @parent = parent
  @children_tree = children_tree || {}
end

Instance Attribute Details

#children_tree ⇒ Hash<Symbol, Node>

Child nodes tree.

Returns:

  • (Hash<Symbol, Node>) —

    the children tree hash, consisting of :letter => node.



29
30
31
 
# File 'lib/rambling/trie/nodes/node.rb', line 29

def children_tree
  @children_tree
end

#letter ⇒ Symbol? #letter=(letter) ⇒ Symbol?

Returns the corresponding letter(s).

Overloads:

  • #letter ⇒ Symbol?

    Letter(s) corresponding to the current node.

  • #letter=(letter) ⇒ Symbol?

    Sets the letter(s) corresponding to the current node. Ensures the #letter in the #parent's #children_tree is updated.

    Parameters:

    • letter (String, Symbol, nil) —

      the letter value.

Returns:

  • (Symbol, nil) —

    the corresponding letter(s).



25
26
27
 
# File 'lib/rambling/trie/nodes/node.rb', line 25

def letter
  @letter
end

#parent ⇒ Node?

Parent node.

Returns:

  • (Node, nil) —

    the parent of the current node.



33
34
35
 
# File 'lib/rambling/trie/nodes/node.rb', line 33

def parent
  @parent
end

#terminal ⇒ Boolean?

Returns the value of attribute terminal.

Returns:

  • (Boolean, nil) 


172
173
174
 
# File 'lib/rambling/trie/nodes/node.rb', line 172

def terminal
  @terminal
end

#value ⇒ TValue?

Arbitrary value stored in this node

Returns:

  • (TValue, nil) —

    the value stored in this node.



37
38
39
 
# File 'lib/rambling/trie/nodes/node.rb', line 37

def value
  @value
end

Instance Method Details

#[](letter) ⇒ Node

Get Node corresponding to a given letter.

Parameters:

  • letter (Symbol) —

    the letter to search for in the node.

  • (Symbol)

Returns:

  • (Node) —

    the node corresponding to that letter.

See Also:



132
133
134
 
# File 'lib/rambling/trie/nodes/node.rb', line 132

def [] letter
  children_tree[letter]
end

#[]=(letter, node) ⇒ Node

Set the Node that corresponds to a given letter.

Parameters:

  • letter (Symbol) —

    the letter to insert or update in the node's children tree.

  • node (Node) —

    the Node to assign to that letter.

  • (Symbol)
  • (Node[TValue])

Returns:

  • (Node) —

    the node corresponding to the inserted or updated letter.

See Also:



141
142
143
 
# File 'lib/rambling/trie/nodes/node.rb', line 141

def []= letter, node
  children_tree[letter] = node
end

#add ⇒ Node[TValue]

Parameters:

  • (Array[Symbol])
  • (TValue, nil)

Returns:



19
 
# File 'sig/lib/rambling/trie/nodes/node.rbs', line 19

def add: (Array[Symbol], ?TValue?) -> Node[TValue]

#children ⇒ Array<Node>

Child nodes.

Returns:

  • (Array<Node>) —

    the array of child nodes contained in the current node.



53
54
55
 
# File 'lib/rambling/trie/nodes/node.rb', line 53

def children
  children_tree.values
end

#children_match_prefix(_chars) {|arg0| ... } ⇒ Enumerator[String, void]

This method is abstract.

Subclass and override #children_match_prefix to match a prefix against child nodes.

Parameters:

  • (Array[String])

Yields:

Yield Parameters:

  • arg0 (String)

Yield Returns:

  • (void)

Returns:

  • (Enumerator[String, void])

Raises:

  • (NotImplementedError) —

    when not overridden by a subclass



176
177
178
 
# File 'lib/rambling/trie/nodes/node.rb', line 176

def children_match_prefix _chars
  not_implemented
end

#closest_node(_chars) ⇒ Node[TValue]

This method is abstract.

Subclass and override #closest_node to return the deepest matching node.

Parameters:

  • (Array[String])

Returns:

Raises:

  • (NotImplementedError) —

    when not overridden by a subclass



194
195
196
 
# File 'lib/rambling/trie/nodes/node.rb', line 194

def closest_node _chars
  not_implemented
end

#compressed? ⇒ Boolean

Returns:

  • (Boolean) 


37
 
# File 'sig/lib/rambling/trie/nodes/node.rbs', line 37

def compressed?: -> bool

#delete(letter) ⇒ Node?

Delete a given letter and its corresponding Node from this Node's children tree.

Parameters:

  • letter (Symbol) —

    the letter to delete from the node's children tree.

  • (Symbol)

Returns:

  • (Node, nil) —

    the node corresponding to the deleted letter.

See Also:



158
159
160
 
# File 'lib/rambling/trie/nodes/node.rb', line 158

def delete letter
  children_tree.delete letter
end

#first_child ⇒ Node?

First child node.

Returns:

  • (Node, nil) —

    the first child contained in the current node.



59
60
61
 
# File 'lib/rambling/trie/nodes/node.rb', line 59

def first_child
  children_tree.each_value.first
end

#key?(letter) ⇒ Boolean Also known as: has_key?

Check if a Node's children tree contains a given letter.

Parameters:

  • letter (Symbol) —

    the letter to search for in the node.

  • (Symbol)

Returns:

  • (Boolean) —

    true if the letter is present, false otherwise.

See Also:



149
150
151
 
# File 'lib/rambling/trie/nodes/node.rb', line 149

def key? letter
  children_tree.key? letter
end

#match_prefix(chars) {|String| ... } ⇒ Enumerator<String>

Returns all words that match a prefix of any length within chars.

Parameters:

  • chars (Array[String]) —

    the chars to base the prefix on.

  • (Array[String])

Yields:

  • (String) —

    each word found.

Yield Parameters:

  • arg0 (String)

Yield Returns:

  • (void)

Returns:

  • (Enumerator<String>) —

    all the words that match a prefix by chars.



118
119
120
121
122
123
124
125
126
 
# File 'lib/rambling/trie/nodes/node.rb', line 118

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

#missing ⇒ Node[TValue]

Returns:



166
167
168
 
# File 'lib/rambling/trie/nodes/node.rb', line 166

def missing
  Rambling::Trie::Nodes::Missing.new
end

#partial_word?(chars) ⇒ Boolean

Checks if a path for a set of characters exists in the trie.

Parameters:

  • chars (Array<String>) —

    the characters to look for in the trie.

  • (Array[String])

Returns:

  • (Boolean) —

    true if the characters are found, false otherwise.



89
90
91
92
93
 
# File 'lib/rambling/trie/nodes/node.rb', line 89

def partial_word? chars
  return true if chars.empty?

  partial_word_chars? chars
end

#partial_word_chars?(_chars) ⇒ Boolean

This method is abstract.

Subclass and override #partial_word_chars? to check for a partial-word path.

Parameters:

  • (Array[String])

Returns:

  • (Boolean)

Raises:

  • (NotImplementedError) —

    when not overridden by a subclass



182
183
184
 
# File 'lib/rambling/trie/nodes/node.rb', line 182

def partial_word_chars? _chars
  not_implemented
end

#root? ⇒ Boolean

Indicates if the current node is the root node.

Returns:

  • (Boolean) —

    true if the node does not have a parent, false otherwise.



65
66
67
 
# File 'lib/rambling/trie/nodes/node.rb', line 65

def root?
  !parent
end

#scan(chars) ⇒ Node

Returns the node that starts with the specified characters.

Parameters:

  • chars (Array<String>) —

    the characters to look for in the trie.

  • (Array[String])

Returns:

  • (Node) —

    the node that matches the specified characters. Missing when not found.



108
109
110
111
112
 
# File 'lib/rambling/trie/nodes/node.rb', line 108

def scan chars
  return self if chars.empty?

  closest_node chars
end

#terminal! ⇒ self

Mark Node as terminal.

Returns:

  • (self) —

    the modified node.



77
78
79
80
 
# File 'lib/rambling/trie/nodes/node.rb', line 77

def terminal!
  self.terminal = true
  self
end

#terminal? ⇒ Boolean

Indicates if a Node is terminal or not.

Returns:

  • (Boolean) —

    true for terminal nodes, false otherwise.



71
72
73
 
# File 'lib/rambling/trie/nodes/node.rb', line 71

def terminal?
  !!terminal
end

#word?(chars = []) ⇒ Boolean

Checks if a path for set of characters represents a word in the trie.

Parameters:

  • chars (Array<String>) (defaults to: []) —

    the characters to look for in the trie.

  • (Array[String])

Returns:

  • (Boolean) —

    true if the characters are found and form a word, false otherwise.



98
99
100
101
102
 
# File 'lib/rambling/trie/nodes/node.rb', line 98

def word? chars = []
  return terminal? if chars.empty?

  word_chars? chars
end

#word_chars?(_chars) ⇒ Boolean

This method is abstract.

Subclass and override #word_chars? to check for a full-word path.

Parameters:

  • (Array[String])

Returns:

  • (Boolean)

Raises:

  • (NotImplementedError) —

    when not overridden by a subclass



188
189
190
 
# File 'lib/rambling/trie/nodes/node.rb', line 188

def word_chars? _chars
  not_implemented
end