Contents

module Rambling
  module Trie
    # Provides the compressing behavior for the Trie data structure.
    module Compressor
      # Flag for compressed tries.
      # @return [Boolean] `true` for compressed tries, `false` otherwise.
      def compressed?
        parent && parent.compressed?
      end

      # Compress the current node using redundant node elimination.
      # @return [Root, Node] the compressed node.
      def compress_tree!
        if compressable?
          merge_with! children.first
          compress_tree!
        end

        children.each &:compress_tree!

        self
      end

      private

      def compressable?
        !(root? || terminal?) && children_tree.size == 1
      end

      def merge_with!(child)
        delete_old_key_on_parent!
        redefine_self! child

        children.each { |node| node.parent = self }
      end

      def delete_old_key_on_parent!
        return if parent.nil?

        parent.delete letter
      end

      def redefine_self!(merged_node)
        self.letter = letter.to_s << merged_node.letter.to_s
        self.children_tree = merged_node.children_tree
        self.terminal = merged_node.terminal?
      end
    end
  end
end

Version data entries

2 entries across 2 versions & 1 rubygems

Version	Path
rambling-trie-0.6.1	lib/rambling/trie/compressor.rb
rambling-trie-0.6.0	lib/rambling/trie/compressor.rb