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

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

Overview

A representation of a node in the trie data structure.

Direct Known Subclasses

Compressed, Missing, Raw

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Inspectable

#inspect

Methods included from Stringifyable

#as_word, #to_s

Methods included from Comparable

#==

Methods included from Enumerable

#each

Methods included from Compressible

#compressible?

Constructor Details

#initialize(letter = nil, parent = nil, children_tree = {}) ⇒ 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.



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

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

Instance Attribute Details

#children_treeHash

Child nodes tree.

Returns:

  • (Hash)

    the children_tree hash, consisting of ‘:letter => node`.



27
28
29
# File 'lib/rambling/trie/nodes/node.rb', line 27

def children_tree
  @children_tree
end

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

Returns the corresponding letter(s).

Overloads:

  • #letterSymbol?

    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).



22
23
24
# File 'lib/rambling/trie/nodes/node.rb', line 22

def letter
  @letter
end

#parentNode?

Parent node.

Returns:

  • (Node, nil)

    the parent of the current node.



31
32
33
# File 'lib/rambling/trie/nodes/node.rb', line 31

def parent
  @parent
end

Instance Method Details

#[](letter) ⇒ Node

Get Node corresponding to a given letter.

Parameters:

  • letter (Symbol)

    the letter to search for in the node.

Returns:

  • (Node)

    the node corresponding to that letter.

See Also:



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

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

  • node (Node)

    the Node to assign to that letter.

Returns:

  • (Node)

    the node corresponding to the inserted or updated letter.

See Also:



144
145
146
# File 'lib/rambling/trie/nodes/node.rb', line 144

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

#childrenArray<Node>

Child nodes.

Returns:

  • (Array<Node>)

    the array of children nodes contained in the current node.



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

def children
  children_tree.values
end

#delete(letter) ⇒ Node

Delete a given letter and its corresponding Node from

this {Node Node}'s children tree.

Parameters:

  • letter (Symbol)

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

Returns:

  • (Node)

    the node corresponding to the deleted letter.

See Also:



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

def delete letter
  children_tree.delete letter
end

#first_childNode?

First child node.

Returns:

  • (Node, nil)

    the first child contained in the current node.



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

def first_child
  return if children_tree.empty?

  children_tree.each_value do |child|
    return child
  end
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.

Returns:

  • (Boolean)

    ‘true` if the letter is present, `false` otherwise

See Also:



154
155
156
# File 'lib/rambling/trie/nodes/node.rb', line 154

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 (String)

    the chars to base the prefix on.

Yields:

  • (String)

    each word found.

Returns:

  • (Enumerator<String>)

    all the words that match a prefix given 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

#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.

Returns:

  • (Boolean)

    ‘true` if the characters are found, `false` otherwise.



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

def partial_word? chars
  return true if chars.empty?

  partial_word_chars? chars
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.



62
63
64
# File 'lib/rambling/trie/nodes/node.rb', line 62

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.

Returns:

  • (Node)

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



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

def scan chars
  return self if chars.empty?

  closest_node chars
end

#terminal!Node

Mark Node as terminal.

Returns:

  • (Node)

    the modified node.



74
75
76
77
# File 'lib/rambling/trie/nodes/node.rb', line 74

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.



68
69
70
# File 'lib/rambling/trie/nodes/node.rb', line 68

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.

Returns:

  • (Boolean)

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



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

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

  word_chars? chars
end