Class: Rambling::Trie::Nodes::Compressed

Inherits:
Node
  • Object
show all
Defined in:
lib/rambling/trie/nodes/compressed.rb,
sig/lib/rambling/trie/nodes/compressed.rbs

Overview

A representation of a node in a compressed trie data structure. :reek:RepeatedConditional { max_ifs: 4 }

Instance Attribute Summary

Attributes inherited from Node

#children_tree, #letter, #parent, #terminal, #value

Instance Method Summary collapse

Methods inherited from Node

#[], #[]=, #children, #delete, #first_child, #key?, #match_prefix, #missing, #partial_word?, #root?, #scan, #terminal!, #terminal?, #word?

Methods included from Inspectable

#attributes, #children_inspect, #children_tree, #class_name, #inspect, #letter, #letter_inspect, #terminal, #terminal_inspect, #value, #value_inspect

Methods included from Stringifyable

#as_word, #children_tree, #letter, #parent, #terminal?, #to_s

Methods included from Comparable

#==, #children_tree, #letter, #terminal?, #value

Methods included from Enumerable

#as_word, #children_tree, #each, #empty_enum, #terminal?

Methods included from Compressible

#children_tree, #compressible?, #root?, #terminal?

Constructor Details

#initialize(letter = nil, parent = nil, children_tree = {}) ⇒ Compressed

Creates a new compressed 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>) (defaults to: {}) —

    the children tree of the current node.

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


13
14
15
16
17
18
 
# File 'lib/rambling/trie/nodes/compressed.rb', line 13

def initialize letter = nil, parent = nil, children_tree = {}
  super

  # Ensure all children have the current compressed node as the parent
  children_tree.each_value { |child| child.parent = self }
end

Instance Method Details

#add(_word, _value = nil) ⇒ Node[TValue]

Always raises InvalidOperation when trying to add a word to the current compressed trie node

Parameters:

  • _word (Array<Symbol>) —

    the word chars to add to the trie.

  • _value (Object, nil) (defaults to: nil) —

    the value to associate with the word.

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

Returns:

Raises:



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

def add _word, _value = nil
  raise Rambling::Trie::InvalidOperation, 'Cannot add word to compressed trie'
end

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

Parameters:

  • (Array[String])

Yields:

Yield Parameters:

  • arg0 (String)

Yield Returns:

  • (void)

Returns:

  • (Enumerator[String, void]) 


88
89
90
91
92
93
94
95
96
97
 
# File 'lib/rambling/trie/nodes/compressed.rb', line 88

def children_match_prefix chars
  return enum_for :children_match_prefix, chars unless block_given?

  return empty_enum if chars.empty?

  child = children_tree[(chars.first || raise).to_sym]
  return empty_enum unless child

  match_child_prefix(child, chars) { |word| yield word }
end

#closest_node(chars) ⇒ Node[TValue]

Parameters:

  • (Array[String])

Returns:



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/rambling/trie/nodes/compressed.rb', line 72

def closest_node chars
  child = children_tree[(chars.first || raise).to_sym]
  return missing unless child

  child_letter = child.letter.to_s

  if chars.size < child_letter.size
    return child_letter.start_with?(chars.join) ? child : missing
  end

  letter = (chars.shift(child_letter.size) || raise).join
  return missing unless child_letter == letter

  child.scan chars
end

#compressed? ⇒ Boolean

Always return true for a compressed node.

Returns:

  • (Boolean) —

    always true for a compressed node.



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

def compressed?
  true
end

#match_child_prefix(child, chars) {|arg0| ... } ⇒ Enumerator[String, void]

Parameters:

  • (Node[TValue])
  • (Array[String])

Yields:

Yield Parameters:

  • arg0 (String)

Yield Returns:

  • (void)

Returns:

  • (Enumerator[String, void]) 


99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/rambling/trie/nodes/compressed.rb', line 99

def match_child_prefix child, chars
  child_letter = child.letter.to_s

  # stop early if we already know that the remaining characters in the
  # given phrase do not even cover the current node's compressed key
  return empty_enum if chars.size < child_letter.size

  letter = (chars.shift(child_letter.size) || raise).join

  return empty_enum unless child_letter == letter

  child.match_prefix(chars) { |word| yield word }
end

#partial_word_chars?(chars) ⇒ Boolean

Parameters:

  • (Array[String])

Returns:

  • (Boolean) 


37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/rambling/trie/nodes/compressed.rb', line 37

def partial_word_chars? chars
  child = children_tree[(chars.first || raise).to_sym]
  return false unless child

  child_letter = child.letter.to_s

  if chars.size >= child_letter.size
    letter = (chars.shift(child_letter.size) || raise).join
    return false unless child_letter == letter

    child.partial_word? chars
  else
    child_letter.start_with? chars.join
  end
end

#word_chars?(chars) ⇒ Boolean

Parameters:

  • (Array[String])

Returns:

  • (Boolean) 


53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/rambling/trie/nodes/compressed.rb', line 53

def word_chars? chars
  letter = chars.shift || raise
  letter_sym = letter.to_sym

  child = children_tree[letter_sym]
  return false unless child

  loop do
    return child.word? chars if letter_sym == child.letter

    break if chars.empty?

    letter << (chars.shift || raise)
    letter_sym = letter.to_sym
  end

  false
end