Contents

module Rambling
  module Trie
    # Responsible for the compression process of a Trie data structure.
    class Compressor
      # Compresses a node from a Trie data structure.
      # @param [RawNode] node the node to compress
      # @return [CompressedNode] node the compressed version of the node
      def compress node
        if node.compressable?
          merge_with_child_and_compress node
        else
          copy_node_and_compress_children node
        end
      end

      private

      def merge_with_child_and_compress node
        child = node.children.first

        new_node = Rambling::Trie::CompressedNode.new node.parent
        new_node.letter = node.letter.to_s << child.letter.to_s
        new_node.terminal! if child.terminal?
        new_node.children_tree = child.children_tree

        compress new_node
      end

      def copy_node_and_compress_children node
        new_node = Rambling::Trie::CompressedNode.new node.parent
        new_node.letter = node.letter
        new_node.terminal! if node.terminal?

        node.children.each do |child|
          compressed_child = compress child

          compressed_child.parent = new_node
          new_node[compressed_child.letter] = compressed_child
        end

        new_node
      end
    end
  end
end

Version data entries

3 entries across 3 versions & 1 rubygems

Version	Path
rambling-trie-0.9.3	lib/rambling/trie/compressor.rb
rambling-trie-0.9.2	lib/rambling/trie/compressor.rb
rambling-trie-0.9.1	lib/rambling/trie/compressor.rb