Class: Rambling::Trie::Compressor

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

Overview

Responsible for the compression process of a trie data structure.

Instance Method Summary collapse

Instance Method Details

#compress(node) ⇒ Nodes::Compressed?

Compresses a Node from a trie data structure.

Parameters:

Returns:



10
11
12
13
14
15
16
17
18
 
# File 'lib/rambling/trie/compressor.rb', line 10

def compress node
  return unless node

  if node.compressible?
    compress_only_child_and_merge node
  else
    compress_children_and_copy node
  end
end

#compress_children(tree) ⇒ Hash[Symbol, Nodes::Node[TValue]]

Parameters:

Returns:



56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/rambling/trie/compressor.rb', line 56

def compress_children tree
  # @type var new_tree: Hash[Symbol, Nodes::Node]
  new_tree = {}

  tree.each do |letter, child|
    compressed_child = compress(child) || raise(InvalidOperation, "got nil while compressing #{letter}")
    new_tree[letter] = compressed_child
  end

  new_tree
end

#compress_children_and_copy(node) ⇒ Nodes::Compressed[TValue]

Parameters:

Returns:



45
46
47
48
49
50
51
52
53
54
 
# File 'lib/rambling/trie/compressor.rb', line 45

def compress_children_and_copy node
  children_tree = compress_children(node.children_tree)
  compressed = Rambling::Trie::Nodes::Compressed.new node.letter, node.parent, children_tree
  if node.terminal?
    compressed.terminal!
    value = node.value
    compressed.value = value unless value.nil?
  end
  compressed
end

#compress_only_child_and_merge(node) ⇒ Nodes::Compressed

Compresses a Node with an only child from a trie data structure. By this point we already know the node is not nil and that it has an only child, so we use the type annotation because compressed_child will always have a value.

Parameters:

Returns:

See Also:



28
29
30
31
 
# File 'lib/rambling/trie/compressor.rb', line 28

def compress_only_child_and_merge node
  compressed_child = compress(node.first_child) || raise(InvalidOperation, 'got nil while compressing only child')
  merge node, compressed_child
end

#merge(node, other) ⇒ Nodes::Compressed[TValue]

Parameters:

Returns:



33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/rambling/trie/compressor.rb', line 33

def merge node, other
  letter = node.letter.to_s << other.letter.to_s

  compressed = Rambling::Trie::Nodes::Compressed.new letter.to_sym, node.parent, other.children_tree
  if other.terminal?
    compressed.terminal!
    value = other.value
    compressed.value = value unless value.nil?
  end
  compressed
end