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