class RhEntitlement::HuffmanNodeQueue

Attributes

nodes[RW]
root[RW]

Public Class Methods

new(list) click to toggle source
# File lib/rh_entitlement/huffman_encoding.rb, line 94
def initialize(list)
  frequencies = {}
  list.each do |c|
    frequencies[c] ||= 0
    frequencies[c] += 1
  end
  @nodes = []
  frequencies.each do |c, w|
    @nodes << HuffmanNode.new(:symbol => c, :weight => w)
  end
  generate_tree
end

Public Instance Methods

find_smallest(not_this) click to toggle source
# File lib/rh_entitlement/huffman_encoding.rb, line 107
def find_smallest(not_this)
  smallest = nil
  for i in 0..@nodes.size - 1
    if i == not_this
      next
    end
    if smallest.nil? or @nodes[i].weight < @nodes[smallest].weight
      smallest = i
    end
  end
  smallest
end
generate_tree() click to toggle source
# File lib/rh_entitlement/huffman_encoding.rb, line 120
def generate_tree
  while @nodes.size > 1
    node1 = self.find_smallest(-1)
    node2 = self.find_smallest(node1)
    hn1 = @nodes[node1]
    hn2 = @nodes[node2]
    new = merge_nodes(hn1, hn2)
    @nodes.delete(hn1)
    @nodes.delete(hn2)
    @nodes.concat(Array.new(1,new))
  end
  @root = @nodes.first
end
merge_nodes(node1, node2) click to toggle source
# File lib/rh_entitlement/huffman_encoding.rb, line 134
def merge_nodes(node1, node2)
  left = node1
  right = node2
  node = HuffmanNode.new(:weight => left.weight + right.weight, :left => left, :right => right)
  left.parent = right.parent = node
  node
end