class Rambling::Trie::Compressor

Responsible for the compression process of a trie data structure.

Public Instance Methods

compress(node) click to toggle source

Compresses a {Nodes::Node Node} from a trie data structure. @param [Nodes::Raw] node the node to compress. @return [Nodes::Compressed] node the compressed version of the node.

# File lib/rambling/trie/compressor.rb, line 10
def compress node
  if node.compressible?
    compress_child_and_merge node
  else
    compress_children_and_copy node
  end
end

Private Instance Methods

compress_child_and_merge(node) click to toggle source
# File lib/rambling/trie/compressor.rb, line 20
def compress_child_and_merge node
  merge node, compress(node.first_child)
end
compress_children(tree) click to toggle source
# File lib/rambling/trie/compressor.rb, line 44
def compress_children tree
  new_tree = {}

  tree.each do |letter, child|
    compressed_child = compress child
    new_tree[letter] = compressed_child
  end

  new_tree
end
compress_children_and_copy(node) click to toggle source
# File lib/rambling/trie/compressor.rb, line 35
def compress_children_and_copy node
  new_compressed_node(
    node.letter,
    node.parent,
    compress_children(node.children_tree),
    node.terminal?,
  )
end
merge(node, other) click to toggle source
# File lib/rambling/trie/compressor.rb, line 24
def merge node, other
  letter = node.letter.to_s << other.letter.to_s

  new_compressed_node(
    letter.to_sym,
    node.parent,
    other.children_tree,
    other.terminal?,
  )
end
new_compressed_node(letter, parent, tree, terminal) click to toggle source
# File lib/rambling/trie/compressor.rb, line 55
def new_compressed_node letter, parent, tree, terminal
  node = Rambling::Trie::Nodes::Compressed.new letter, parent, tree
  node.terminal! if terminal

  tree.each_value { |child| child.parent = node }
  node
end