Contents

# frozen_string_literal: true

module Rambling
  module Trie
    # Responsible for the compression process of a trie data structure.
    class Compressor
      # 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.
      def compress node
        if node.compressible?
          compress_child_and_merge node
        else
          compress_children_and_copy node
        end
      end

      private

      def compress_child_and_merge node
        merge node, compress(node.first_child)
      end

      def merge node, other
        return new_compressed_node node.letter, node.parent, node.children_tree, node.terminal? if other.nil?

        letter = node.letter.to_s << other.letter.to_s

        new_compressed_node letter.to_sym, node.parent, other.children_tree, other.terminal?
      end

      def compress_children_and_copy node
        new_compressed_node node.letter, node.parent, compress_children(node.children_tree), node.terminal?
      end

      def compress_children tree
        new_tree = {}

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

        new_tree
      end

      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
    end
  end
end

Version data entries

1 entries across 1 versions & 1 rubygems

Version	Path
rambling-trie-2.5.0	lib/rambling/trie/compressor.rb